{"updated":"2025-01-21T20:09:45.635029+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00079661","sets":["934:1022:6385:6638"]},"path":["6638"],"owner":"11","recid":"79661","title":["簡潔データ構造のオンライン構築とブルームフィルタによる検索性能の向上"],"pubdate":{"attribute_name":"公開日","attribute_value":"2011-12-28"},"_buckets":{"deposit":"7409c0f4-8d32-4700-9500-881e74b64fbb"},"_deposit":{"id":"79661","pid":{"type":"depid","value":"79661","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"簡潔データ構造のオンライン構築とブルームフィルタによる検索性能の向上","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"簡潔データ構造のオンライン構築とブルームフィルタによる検索性能の向上"},{"subitem_title":"Online Building of Succinct Data Structures and Search Performance Improvement by Bloom Filters","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"研究論文","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2011-12-28","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻／日本アイ・ビー・エム大和ソフトウェア研究所"},{"subitem_text_value":"日本アイ・ビー・エム東京基礎研究所"},{"subitem_text_value":"株式会社Preferred Infrastructure"},{"subitem_text_value":"筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Computer Science, University of Tsukuba / IBM Yamato Software Laboratory","subitem_text_language":"en"},{"subitem_text_value":"IBM Research - Tokyo","subitem_text_language":"en"},{"subitem_text_value":"Preferred Infrastructure, Inc.","subitem_text_language":"en"},{"subitem_text_value":"Department of Computer Science, University of Tsukuba","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/79661/files/IPSJ-TOD0404002.pdf"},"date":[{"dateType":"Available","dateValue":"2013-12-28"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TOD0404002.pdf","filesize":[{"value":"582.7 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"13"},{"tax":["include_tax"],"price":"0","billingrole":"39"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"a4b0c1b4-989a-49ca-8929-ed8f193c0393","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2011 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"小柳, 光生"},{"creatorName":"吉田, 一星"},{"creatorName":"海野, 裕也"},{"creatorName":"新城, 靖"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Teruo, Koyanagi","creatorNameLang":"en"},{"creatorName":"Issei, Yoshida","creatorNameLang":"en"},{"creatorName":"Yuya, Unno","creatorNameLang":"en"},{"creatorName":"Yasushi, Shinjo","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_3_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11464847","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_3_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7799","subitem_source_identifier_type":"ISSN"}]},"item_3_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"簡潔データ構造は空間効率のきわめて高いデータ構造であり，その一種であるLOUDS（Level-Order Unary Degree Sequence）を用いてトライ木を作れば，大量の文字列を少ない容量で格納できる．インクリメンタルにデータを追加しながらLOUDSを構築するには，差分を保持するLOUDSを複数作成して，それらを定期的にマージする方法がある．しかし，この方法では，検索すべきLOUDSの数が増え，検索速度が低下するという問題がある．本論文では，この問題を解決するために，各LOUDSにブルームフィルタを設置する手法を提案する．提案手法では，ブルームフィルタによって検索の不要なLOUDSをスキップし，検索コストを削減する．実験により，ブルームフィルタの精度が全体の性能に与える影響を明らかにする．650万件の語彙を含む約2.4億件の単語データから辞書を作成する実験を行い，提案方式の有効性を確認した．","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Succinct data structures are extremely space efficient data representations. LOUDS (Level-Order Unary Degree Sequence) is a succinct data structure for trees which can be used as a TRIE to store a large number of strings. To add data incrementally into LOUDS, we can use a method to create multiple LOUDS as deltas and to merge them periodically. In this approach, there is a problem that the search performance degrades proportional to the number of LOUDS. To solve this problem, we propose a method to set bloom filters with created LOUDS, respectively. The bloom filters avoid unnecessary searches in many cases that the search key is not included in the key set of LOUDS. The efficiency of our method is confirmed by the experiment using 240 million word stream that consists of 6.5 million unique keywords.","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"10","bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌データベース（TOD）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2011-12-28","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"4","bibliographicVolumeNumber":"4"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"created":"2025-01-18T23:34:18.792847+00:00","id":79661,"links":{}}