Nearest Neighbours Search Using the PM-Tree

Abstract. We introduce a method of searching the k nearest neighbours (k-NN) using PM-tree. The PM-tree is a metric access method for sim-ilarity search in large multimedia databases. As an extension of M-tree, the structure of PM-tree exploits local dynamic pivots (like M-tree does it) as well as global static pivots (used by LAESA-like methods). While in M-tree a metric region is represented by a hyper-sphere, in PM-tree the ”volume ” of metric region is further reduced by a set of hyper-rings. As a consequence, the shape of PM-tree’s metric region bounds the in-dexed objects more tightly which, in turn, improves the overall search efficiency. Besides the description of PM-tree, we propose an optimal k-NN search algorithm. Finally, the efficiency of k-NN search is experi-mentally evaluated on large synthetic as well as real-world datasets.