分散ネットワークによる大規模検索基盤に関する研究

点击翻译按钮获取中文摘要

本研究は,際限なく増え続ける非構造化データの類似検索基盤の構築を目的とする.本研究は,様々な非構造化データに広く適用できる技術を目指し,距離空間という極めて基礎的な距離に関する空間を扱った.本年度は,類似検索索引と近傍ペア探索アルゴリズムの開発に取り組んだ.類似検索索引は,データセットの中から任意のオブジェクトと類似したものを探すのに使われる.類似検索索引は,クエリから距離の遠いオーブジェクトを枝刈りし,距離計算コストを削減する.ほぼすべての類似検索索引では,Pivotと呼ばれる参照オブジェクトからの距離で空間を部分空間へ再帰的に分割し,木構造の索引を構築する.本年度は,昨年度に提案したMMMPを改良し,PCTreeと呼ぶ新たな検索索引を開発した.PCTreeでは,Pivotによって分割される空間のバランスと,Pivotによる枝刈り効果の,2つを考慮してPivotを選択する.その結果,PCTreeはデータの分布に合わせて索引構造を効果的に変化させ,MMMPの索引木が不均衡になりうる欠点を改善した.人工の2から64次元のベクトルデータと5つの実データに対して,GHT,MVP,LC,およびSATの4つの先行研究との間で,近傍検索に必要な距離計算回数などを比較した.その結果,提案手法は様々な分布のデータに対して全般的に有効な索引であることが明らかになった.一方,近傍ペア探索アルゴリズムは,データセットの中から類似したオブジェクトのペアを探すのに使われる.一般に,近傍ペア探索アルゴリズムでは,k番目の類似ペア間の距離の上限値を更新しながら分割統治法で枝刈りする.本研究では、AMPと呼ぶ適応型空間多分割手法を提案した.AMPは,距離に対するオブジェクトの分布が密な空間のほうが収束した上限値による枝刈りの効果が大きいことを利用して,Pivotからオブジェクトまでの距離が分散している空間から順に分割統治でk最近傍ペアを探索する.3つの実データに対して,QuickjoinおよびAMPの分割順序を逆にした手法との間で,距離計算回数の比較を行い,AMPが良好な特性を持つことを示した.