| 講演抄録／キーワード |
| 講演名 |
2006-07-13 11:45
N.M-gram: ハッシュ値付きN-gram 法による転置インデックスの実現
○平林幹雄（ミクシィ）・江渡浩一郎（産総研） |
| 抄録 |
（和） |
全文検索システムの転置インデックスを実現するにあたり，テキストデータからN-gram法によって切り出したトークンを検索キーにする手法が広く用いられている．この手法には，言語中立性や再現率の完全性という利点がある反面，検索対象の文書群から抽出するトークンの数が膨大になるために，転置インデックスのサイズが肥大化して空間効率が悪化するという欠点がある．検索の際にクエリから切り出した各トークンが対象文書のテキスト内でも連接しているかどうかを判断するためには，転置インデックス内にトークンの文書内での出現位置を記録しておくことが必要となるが，この位置情報が転置インデックスの肥大化の一因となっている．本稿では，N-gram法の欠点である転置インデックスの空間効率を改善する手法として，N.M-gram法を提案する．N.M-gram法では，各トークンの文書内での位置情報のかわりに後続のトークンのハッシュ値を用いることによって，N-gram法の利点である言語中立性や再現率の完全性を保持したまま，空間効率を改善することができる． |
| （英） |
When constructing inverted index for full-text search system, using N-gram is very popular for tokenizing text data of target documents. Although the method has many advantages like language neutrality and perfect recall ratio, it has also shortage that the inverted index becomes large. The tokens extracted from documents tend to be enormous. The system needs to record each offset of tokens into inverted index because the offset is used for checking adjacency of tokens. The inverted index tends to be large because of the offset. In this paper, we describe N.M-gram method, which improves space efficiency of N-gram. The method uses hash values of succeeding tokens instead of offset in each document. The method can improve space efficiency without losing advantages of N-gram. |
| キーワード |
（和） |
N.M-gram / N-gram / 転置インデックス / 全文検索 / ハッシュ / / / |
| （英） |
N.M-gram / N-gram / inverted index / full-text search / hash / / / |
| 文献情報 |
信学技報, vol. 106, no. 149, DE2006-78, pp. 167-172, 2006年7月. |
| 資料番号 |
DE2006-78 |
| 発行日 |
2006-07-06 (DE) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
DE |
| 開催期間 |
2006-07-12 - 2006-07-14 |
| 開催地（和） |
ホテル泉慶 |
| 開催地（英） |
HOTEL SENKEI |
| テーマ（和） |
データ工学, 一般 |
| テーマ（英） |
Data Engineering, etc. |
| 講演論文情報の詳細 |
| 申込み研究会 |
DE |
| 会議コード |
2006-07-DE |
| 本文の言語 |
日本語 |
| タイトル（和） |
N.M-gram: ハッシュ値付きN-gram 法による転置インデックスの実現 |
| サブタイトル（和） |
|
| タイトル（英） |
N.M-gram: Implementation of Inverted Index Using N-gram with Hash Values |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
N.M-gram / N.M-gram |
| キーワード(2)（和/英） |
N-gram / N-gram |
| キーワード(3)（和/英） |
転置インデックス / inverted index |
| キーワード(4)（和/英） |
全文検索 / full-text search |
| キーワード(5)（和/英） |
ハッシュ / hash |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
平林 幹雄 / Mikio Hirabayashi / ヒラバヤシ ミキオ |
| 第1著者 所属（和/英） |
株式会社ミクシィ (略称： ミクシィ)
mixi, Inc. (略称： mixi) |
| 第2著者 氏名（和/英/ヨミ） |
江渡 浩一郎 / Koichiro Eto / |
| 第2著者 所属（和/英） |
独立行政法人産業技術総合研究所 (略称： 産総研)
National Institute of Advanced Industrial Science and Technology (略称： AIST) |
| 第3著者 氏名（和/英/ヨミ） |
/ / |
| 第3著者 所属（和/英） |
(略称： )
(略称： ) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 第21著者 氏名（和/英/ヨミ） |
/ / |
| 第21著者 所属（和/英） |
(略称： )
(略称： ) |
| 第22著者 氏名（和/英/ヨミ） |
/ / |
| 第22著者 所属（和/英） |
(略称： )
(略称： ) |
| 第23著者 氏名（和/英/ヨミ） |
/ / |
| 第23著者 所属（和/英） |
(略称： )
(略称： ) |
| 第24著者 氏名（和/英/ヨミ） |
/ / |
| 第24著者 所属（和/英） |
(略称： )
(略称： ) |
| 第25著者 氏名（和/英/ヨミ） |
/ / |
| 第25著者 所属（和/英） |
(略称： )
(略称： ) |
| 第26著者 氏名（和/英/ヨミ） |
/ / |
| 第26著者 所属（和/英） |
(略称： )
(略称： ) |
| 第27著者 氏名（和/英/ヨミ） |
/ / |
| 第27著者 所属（和/英） |
(略称： )
(略称： ) |
| 第28著者 氏名（和/英/ヨミ） |
/ / |
| 第28著者 所属（和/英） |
(略称： )
(略称： ) |
| 第29著者 氏名（和/英/ヨミ） |
/ / |
| 第29著者 所属（和/英） |
(略称： )
(略称： ) |
| 第30著者 氏名（和/英/ヨミ） |
/ / |
| 第30著者 所属（和/英） |
(略称： )
(略称： ) |
| 第31著者 氏名（和/英/ヨミ） |
/ / |
| 第31著者 所属（和/英） |
(略称： )
(略称： ) |
| 第32著者 氏名（和/英/ヨミ） |
/ / |
| 第32著者 所属（和/英） |
(略称： )
(略称： ) |
| 第33著者 氏名（和/英/ヨミ） |
/ / |
| 第33著者 所属（和/英） |
(略称： )
(略称： ) |
| 第34著者 氏名（和/英/ヨミ） |
/ / |
| 第34著者 所属（和/英） |
(略称： )
(略称： ) |
| 第35著者 氏名（和/英/ヨミ） |
/ / |
| 第35著者 所属（和/英） |
(略称： )
(略称： ) |
| 第36著者 氏名（和/英/ヨミ） |
/ / |
| 第36著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2006-07-13 11:45:00 |
| 発表時間 |
20分 |
| 申込先研究会 |
DE |
| 資料番号 |
DE2006-78 |
| 巻番号（vol） |
vol.106 |
| 号番号（no） |
no.149 |
| ページ範囲 |
pp.167-172 |
| ページ数 |
6 |
| 発行日 |
2006-07-06 (DE) |
|