文献

J-GLOBAL ID：200902210396143565   整理番号：09A0916440

グラフ索引構造を用いた高速類似探索

著者 (4件)： 青山一生 (NTT コミュニケーション科学基礎研) ,  斉藤和巳 (静岡県大 経営情報) ,  山田武士 (NTT コミュニケーション科学基礎研) ,  上田修功 (NTT コミュニケーション科学基礎研)
資料名： 電子情報通信学会論文誌 D  (IEICE Transactions on Information and Systems (Japanese Edition))
巻： J92-D  号： 9  ページ： 1543-1554  発行年： 2009年09月01日 
JST資料番号： S0757C  ISSN： 1880-4535  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 大規模な高次元のデータに対して高速な類似探索を可能とする新たなアプローチを提案する。このアプローチは,オブジェクト集合から構築されたスモールワールド性を有するグラフを索引構造として用い,類似オブジェクト探索問題を,グラフの辺をたどりながらクエリオブジェクトに類似する頂点を見つけるグラフ探索問題としてとらえる。我々は,探索の効率性に優れた索引構造として,単純な近傍グラフの拡張である次数低減近傍グラフを提案し,このグラフを構成する効率的アルゴリズムと,これに最良優先近傍探索アルゴリズムを組み合わせた高速類似探索法を提案する。提案法の探索性能を,探索対象として文書データを用いた実験により評価し,探索性能と次元数との関係を,人工データを用いて解析した。結果,高次元データを対象とした場合,提案法が非常に小さい探索コストで類似探索することを確認した。(著者抄録)

シソーラス用語： 高次元 ,  *探索問題 ,  類似性 ,  ネットワーク構造 ,  グラフ ,  *情報検索 ,  データ構造 ,  *データ検索
準シソーラス用語： スモールワールド ,  索引構造 ,  *類似検索 ,  *探索アルゴリズム

分類 (2件)： 検索技術  (AC06020S) ,  人工知能  (JE08000Z)

引用文献 (15件)：

• S. Milgram,“The small world problem,” Psychology Today, vol.2, pp. 60-67, 1967.
• D. J. Watts and S. H. Strogatz,“Collective dynamics of ‘small-world’ networks,” Nature, vol.393, pp. 440-442, 1998.
• D. J. Watts, P. S. Dodds, and M. E. J. Newman,“Identity and search in social networks,” Science, vol.296, pp. 1302-1305, 2002.
• J. Kleinberg,“The small-world phenomenon: An algorithmic perspective,” Proc. ACM Symp. Theory of Computing, pp. 163-170, 2000.
• G. R. Hjaltason and H. Samet,“Index-driven similarity search in metric spaces,” ACM Trans. Database Syst., vol.28, no.4, pp. 517 580, 2003.

タイトルに関連する用語 (4件)： グラフ ,  索引構造 ,  類似 ,  探索