The purpose of my research is to reduce the query execution cost of a similarity search in Metric spaces. Although a large number of studies have been made on indexing techniques for similarity searches, only a few exploit the data distribution in a Metric space to indexing. My goal is to develop a new partitioning scheme based on the data distribution that can prune objects while the search more effectively.

Finding similar objects in a large dataset is a fundamental process in various applications, such as record linkage, and GIS. The reduction of the query execution cost of a similarity search can speed up these applications. Similarity searches based on a Metric space can be applied to all types of data whose distance obey Metric space postulates such as the triangle inequality. Therefore, Metric space indexes are very useful for applications that deal with huge amounts of vectors, strings, graphs, sets, and so on.

Similarity search indexes are used for pruning objects dissimilar to a query and reduce the search cost, such as the distance computations and the disk accesses. Most indexing schemes use pivots, which are reference objects. They recursively divide a region into subregions by using pivots and construct a tree structure index. They prune some of the subregions by using the triangle inequality while searching. That is, the methods of selecting pivots and dividing up the space by using these pivots determine the index structure and pruning performance.

Pivot selection methods proposed in early researches were based on heuristics. They asserted that good pivots should be outliners of the space, because the distances from a pivot to each object vary and the pivot easily classifies the objects. They used simple statistical features such as the mean and the variance for selecting pivots. However, their choices of pivots are only a little better than random selection. Several proposed selection mechanisms exploit data distribution by clustering techniques. These methods set cluster center as the pivots and divide the space on the basis of the distances from the pivots. Although they can effectively classify dense regions, they only work well on particular distribution patterns. A cluster may be separated into multiple regions by a pivot, because their partitioning boundaries are based on cluster centers rather than cluster shapes. I focus on the problem in the existing indexes that they don't consider the partitioning boundary of the pivot and cannot select a good pivot for pruning.

I developed two novel methods for pivot partitioning called Maximal Metric Margin Partitioning (MMMP) and Pivot Capacity Tree (PCTree). The MMMP firstly extracts the data distribution pattern, especially for the boundaries of clusters. Then, it selects a pivot and its partitioning distance based on the shapes of data clusters. The partitioning boundary of the MMMP is at maximum distances from the neighbor cluster edges. The MMMP is good for dealing with clustered data. On the other hand, the PCTree considers the index tree balancing as well as the data distribution. The PCTree chooses a pivot based on both the balance of the subregions partitioned by a pivot and the estimated effectiveness of the search pruning by the pivot. As a result, PCTree automatically optimizes the index structure according to the data distribution. The PCTree improves the tree imbalance of the MMMP. These indexing methods successfully reduce the similarity search cost.

The main contribution is that I have developed a new pivot selection approach called ``the data distribution-based approach", which is based on the data distribution. To my best knowledge, this is the first study to exploit the cluster shapes and the tree balancing for the pivot selection.

I show the efficiency of these methods empirically through the results from several experiments where I compared the methods with several Metric space indexes. In this thesis, I firstly introduce the basic techniques of similarity search, and then show my methods and experimental results.

本論文は、「A Study of Fast Similarity Search Techniques in Metric Spaces (メトリック空間における類似検索の高速化に関する研究)」と題し、英文5章から構成されている。情報検索の基礎的な研究分野として、距離空間での類似検索において検索コストを削減するための手法について論じたものである。検索対象となるオブジェクトの空間における分布の特徴を活用して効率的な索引を構成する手法として二つの新しい方式を提案し、従来手法よりもすぐれた特性を持つことを検証している。

第1章は「Introduction(序章)」であり、距離空間にあるオブジェクト群に対する類似検索の問い合わせコスト削減の問題を提示し概観している。従来から多数の類似検索のための索引付け手法が提案されてきたが、いずれの手法も検索対象のオブジェクトの特徴を索引構築に活かせていなかった。ここで新たに、オブジェクトの分布の特徴にもとづいたdata distribution-based approachと呼ぶ索引付けの方策を提案している。そしてこの方策に基づく2つの新しいPivot分割手法としてMaximal Metric Margin Partitioning (MMMP)とPivot Capacity Tree (PCTree)の開発の経緯を述べている。

第2章は「Related Work(関連研究)」であり、前半では、距離空間の定義や距離関数の具体例、さらに検索タスクについて説明している。後半では、従来提案されている類似検索索引における枝刈り手法と索引付け手法を紹介してそれらに見られる課題について論じている。ほぼすべての枝刈り手法にはPivotと呼ばれる参照オブジェクトが使われているが、このPivotの選び方によって性能が大きく左右される。本論文では、従来研究においてはPivotによって形成される分割面について考慮が十分でないために枝刈りに効果的なPivotを選べていないという、既存手法の問題に注目している。

第3章は「MMMP: Margin-based Pivot Selection Scheme」と題し、第一の提案手法MMMPを説明するものである。MMMPは、クラスタ間のマージンを利用した類似検索索引である。MMMPではまず、データの分布傾向のうち特にクラスタの境界を抽出する。そして、クラスタ形状にもとづいてPivotとその分割距離を決める。MMMPの分割面は、隣り合うクラスタの端からの距離を最大にするように置かれる。MMMPは偏った分布のデータに対して効果的な手法である。MMMPにおける索引作成手法を提示した後、従来手法との間で性能評価を行っている。人工の2から30次元のベクトルデータと三つの実データに対して、iDistance、D-Index、List of Clustersという三つの先行手法との間で、検索応答時間、距離計算回数、ページアクセス回数の比較を行い、いずれにおいても提案するMMMPが良好な特性を持つことを示した。しかし課題としてPivot選択コストの大きさが上げられ、クラスタ化していないオブジェクト空間において弱いことも判明した。

第4章は「PCTree: Pivot Selection Scheme for Optimizing both Pruning and Balancing」と題して、第二の提案手法PCTreeについてのべている。提案手法PCTreeは、データの分布だけでなく、索引木のバランスも考慮した手法である。PCTreeでは、Pivotによって分割される部分空間のバランスと、Pivotによる検索時の枝刈りの効果の、2つを考慮してPivotを選択する。その結果、PCTreeはデータの分布に合わせて索引構造を効果的に変化させている。PCTreeは、MMMPの索引木が不均衡になりうる欠点を改善した手法と言える。先行する研究GHT、MVP、List of ClustersおよびSATの四つの手法との間で人工データ(2から64次元のベクトルデータ、Euclid距離)、実データ(画像データでEuclid距離、英単語で編集距離等、5種)に対して評価実験を行った。近傍検索に必要な距離計算回数、そして索引木の高さなどを比較し、提案するPCTreeは、類似検索索引における枝刈り効果とバランスを考慮した分割手法であることが判明し、先行する手法に対して、様々な分布のデータに対して全般的に有効な索引であることが明らかになった。

第5章は「Conclusion (結論)」であり、本研究の全体をまとめている。本研究の貢献は、Pivot選択の新しい方策data distribution-based approachを確立したことである。従来研究を概観すると、クラスタ形状や索引木のバランスをPivot選択に考慮しているような研究は他に見られず、本研究が初めてのものである。これら2つの提案手法の有効性を、既存研究と比較した評価実験を通して明らかにした。

以上これを要するに、本論文は、極めて基礎的な距離空間にあるオブジェクト群に対する類似検索において、問い合わせコストを削減するための一般的な手法を論じたもので、オブジェクトの分布の特徴にもとづいたdata distribution-based approachと呼ぶ索引付けの一般的概念を提示し、その具体的な実現方法として2つの新しいPivot分割手法、すなわちMaximal Metric Margin Partitioning (MMMP)およびPivot Capacity Tree (PCTree)を提案し、複数のデータセットに対して性能評価を行い、提案手法が先行する手法に比して全般的に優れた性能を持つことを実証することにより、情報検索の基礎分野で有用な知見を明らかにしたものとして、電子情報学上貢献するところが少なくない。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。