Antipole tree indexing to support range search and k-nearest neighbor search in metric spaces

Domenico Cantone, Alfredo Ferro, Alfredo Pulvirenti, Diego Reforgiato Recupero, Dennis Shasha

Research output: Contribution to journalArticlepeer-review


Range and k-nearest neighbor searching are core problems in pattern recognition. Given a database S of objects in a metric space M and a query object q in M, in a range searching problem the goal is to find the objects of 5 within some threshold distance to q, whereas in a k-nearest neighbor searching problem, the q elements of 5 closest to q must be produced. These problems can obviously be solved with a linear number of distance calculations, by comparing the query object against every object in the database. However, the goal is to solve such problems much faster. We combine and extend ideas from the M-Tree, the Multivantage Point structure, and the FQ-Tree to create a new structure in the "bisector tree" class, called the Antipole Tree. Bisection is based on the proximity to an "Antipole" pair of elements generated by a suitable linear randomized tournament. The final winners a, b of such a tournament are far enough apart to approximate the diameter of the splitting set. If dist(a, b) is larger than the chosen cluster diameter threshold, then the cluster is split. The proposed data structure is an indexing scheme suitable for (exact and approximate) best match searching on generic metric spaces. The Antipole Tree outperforms by a factor of approximately two existing structures such as List of Clusters, M-Trees, and others and, in many cases, it achieves better clustering properties.

Original languageEnglish (US)
Pages (from-to)535-550
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number4
StatePublished - Apr 2005


  • Indexing methods
  • Information search and retrieval
  • Similarity measures

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Antipole tree indexing to support range search and k-nearest neighbor search in metric spaces'. Together they form a unique fingerprint.

Cite this