2005 | OriginalPaper | Buchkapitel
Nearest Neighbours Search Using the PM-Tree
verfasst von : Tomáš Skopal, Jaroslav Pokorný, Václav Snášel
Erschienen in: Database Systems for Advanced Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We introduce a method of searching the
k
nearest neighbours (
k
-NN) using PM-tree. The PM-tree is a metric access method for similarity 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 indexed 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 experimentally evaluated on large synthetic as well as real-world datasets.