Result: Nearest neighbours search using the PM-tree

Title:
Nearest neighbours search using the PM-tree
Authors:
SKOPAL, Tomas, POKORNY, Jaroslav, SNASEL, Vaclav
Source:
DASFFA 2005 : database systems for advanced applications (Beijing, 17-20 April 2005)Lecture notes in computer science. :803-815
Publisher Information:
Berlin: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 13 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Logiciel, Software, Organisation des mémoires. Traitement des données, Memory organisation. Data processing, Systèmes d'information. Bases de données, Information systems. Data bases, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Algorithme recherche, Search algorithm, Algoritmo búsqueda, Anneau, Ring, Anillo, Arbre recherche, Search tree, Arbol investigación, Base donnée multimédia, Multimedia databases, Méthode arborescente, Tree structured method, Método arborescente, Méthode pivotage, Pivoting method, Método pivotaje, Métrique, Metric, Métrico, Plus proche voisin, Nearest neighbour, Vecino más cercano, Similitude, Similarity, Similitud, Sphère, Sphere, Esfera
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Charles University in Prague, FMP, Department of Software Engineering, Malostranské nám. 25, 118 00 Prague, Czech Republic
VŠB-Technical University of Ostrava, FECS, Dept. of Computer Science, tr. 17. listopadu 15, 708 33 Ostrava, Czech Republic
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=16923579
Rights:
Copyright 2005 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.16923579
Database:
PASCAL Archive

Further Information

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.