WEKO3
-
RootNode
アイテム
LOUDSトライのオンライン構築のためのブルームフィルタ構築法
https://ipsj.ixsq.nii.ac.jp/records/81509
https://ipsj.ixsq.nii.ac.jp/records/8150971a95f5b-684b-46de-8277-b5434dfa3c0f
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2012 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | Trans(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2012-03-22 | |||||||
タイトル | ||||||||
タイトル | LOUDSトライのオンライン構築のためのブルームフィルタ構築法 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Method to Build Bloom Filters for Online Building of LOUDS TRIE | |||||||
言語 | ||||||||
言語 | jpn | |||||||
キーワード | ||||||||
主題Scheme | Other | |||||||
主題 | アルゴリズム | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
資源タイプ | journal article | |||||||
著者所属 | ||||||||
筑波大学システム情報工学研究科コンピュータサイエンス専攻/日本アイ・ビー・エム大和ソフトウェア研究所 | ||||||||
著者所属 | ||||||||
日本アイ・ビー・エム東京基礎研究所 | ||||||||
著者所属 | ||||||||
株式会社Preferred Infrastructure | ||||||||
著者所属 | ||||||||
筑波大学システム情報工学研究科コンピュータサイエンス専攻 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Computer Science, University of Tsukuba / Yamato Software Laboratory, IBM Japan | ||||||||
著者所属(英) | ||||||||
en | ||||||||
IBM Research - Tokyo, IBM Japan | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Preferred Infrastructure, inc. | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Computer Science, University of Tsukuba | ||||||||
著者名 |
小柳, 光生
× 小柳, 光生
|
|||||||
著者名(英) |
Teruo, Koyanagi
× Teruo, Koyanagi
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 簡潔データ構造は空間効率のきわめて高いデータ構造であり,その一種であるLOUDS(Level-Order Unary Degree Sequence)を用いてトライ木を作れば,大量のキー文字列を少ない容量で格納できる.インクリメンタルにデータを追加しながらLOUDSを構築するには,差分を保持するLOUDSを複数作成して,それらを定期的にマージする方法がある.このとき,各LOUDSにブルームフィルタを添付すると,不要な検索をスキップすることで,検索性能を改善できる.しかし,ブルームフィルタを作成するには,素朴な方法ではマージ処理とは別にLOUDSトライを探索する必要があり,性能が悪い.本論文では,LOUDSの構築・マージと同時にブルームフィルタを作成することで,ブルームフィルタの構築時間を削減する方法を提案する.実データから抽出した650万件の語彙を含む約2.4億件の単語データから辞書を作成する実験を行い,提案方式の有効性を確認した. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 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. LOUDS TRIE can be incrementally built by creating multiple LOUDS to keep deltas and merging them periodically. Setting Bloom filters with respective LOUDS improves the search performance by excluding unnecessary searches. However, it costs a substantial time to create Bloom filters by reading all key strings stored in LOUDS. In this paper, we propose a method to create Bloom filters concurrently with building and merging LOUDS. It conserves the time to build Bloom filters. The efficiency of our method is confirmed by the experiment using about 240 million word stream that consists of 6.5 million unique keywords, which are extracted from the real data. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AA11833852 | |||||||
書誌情報 |
情報処理学会論文誌コンピューティングシステム(ACS) 巻 5, 号 2, p. 1-9, 発行日 2012-03-22 |
|||||||
ISSN | ||||||||
収録物識別子タイプ | ISSN | |||||||
収録物識別子 | 1882-7829 | |||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |