拡張ハッシュ法による検索技法の拡張 －部分文字列検索と順検索への拡張－

• Item type: SIG Technical Reports(1)
• 公開日: 1994-10-13
• タイトル: 拡張ハッシュ法による検索技法の拡張 －部分文字列検索と順検索への拡張－
• タイトル / 言語: en
• タイトル: Improvements of Extensible Hashing Schemes -Substring and Order Searching-
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 徳島大学工学部
• 著者所属: 徳島大学工学部
• 著者所属: 徳島大学工学部
• 著者所属: 徳島大学工学部
• 著者所属(英): en
• 著者所属(英): The University of Tokushima
• 著者所属(英): en
• 著者所属(英): The University of Tokushima
• 著者所属(英): en
• 著者所属(英): The University of Tokushima
• 著者所属(英): en
• 著者所属(英): The University of Tokushima
• 著者名: 望月, 久稔; 清原, 聡; 森本, 勝士; 青江, 順一
• 著者名(英): Hisatoshi, Mochiduki; Satoshi, Kiyohara; Katsushi, Morimoto; Jun-Ichi, Aoe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 拡張ハッシュ法は動的なキー集合に対して，高速な検索を実現する手法である．拡張ハッシュ法でキーの順検索を可能にするコンパクト2進木法がJongeらにより提案されているが，キーの検索時間が大きい．本稿では，キーの順検索特性を保存して従来の手法を改良することにより，キーの検索時間の改善方法を提案する．本手法を用いることで、検索速度が58倍高速になることが実験結果より確かめられた。また，これまでの提案方法では、与えられた任意の文字列を含むキーの検索（部分文字列検索）を効率的に行うことはできなかった．本稿では、部分文字列検索を効率的に行うため，特徴ベクトルと呼ばれるビット列を用いる方法を提案する，また，通常の拡張ハッシュ法では、複数のパケットを参照する必要が生じる。本稿では更に、その参照数の抑制のためにディスクリプタを利用してキーの処理時間の改善方法も提案する．本手法の有効性を確認するため実験を行った結果、通常の拡張ハッシュ法に比べ，40倍以上高速に検索できることがわかった。また、検索キーの長さが長くなるほど、高速に検索できることが確認できた。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Extensible hashing schemes keep fast key retrieval for dynamic key sets. Although Jonge et al proposed the compact binary tree (CB-Tree) method that enables order preserved searching by extensible hashing schemes, searching and updating a key takes a lot of time for a large set of keys. This article proposes a method for dividing the CB-Tree, in order to improve the time cost. The simulation results shows that the method presented is 58 times faster than the traditional CB-Tree, Extensible hashing schemes can not detect substrings of a given string without accessing all buckets. In order to realize effective substring searching, this article proposes a new idea that uses signature vectors as a hash value and that uses a descriptor for each bucket like a multidimensional extensible hashing method. The results of the simulations show that the method presented is 40 times faster than the traditional extensible hashing scheme.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 1994, 号 86(1994-DBS-100), p. 129-136, 発行日 1994-10-13
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会