Indexing for similarity search operators

P. Deepak*, Prasad M. Deshpande

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter


This chapter deviates from the semantics-oriented discussion in this book and considers the motivation for indexes and efficient algorithms for evaluating similarity queries. We start with the computationally simplest case of processing similarity queries over data objects in a Euclidean space where we illustrate the utility of the k-d Tree to enable efficient search. We then relax the constraints and move to general metric spaces, where the triangle inequality becomes the most important property. We describe a commonly used index called the VP Tree for such a case. Finally, we consider the most general scenario where the distance measure can be arbitrary. The only property assumed is the monotonicity of the distance function. Here we consider two approaches—the family of Threshold algorithms and the AL Tree based indexing method and show how they can be used for Top-k search in such situations.

Original languageEnglish
Title of host publicationSpringerBriefs in Computer Science
Number of pages13
Publication statusPublished - 01 Jan 2015
Externally publishedYes

Publication series

NameSpringerBriefs in Computer Science
ISSN (Print)2191-5768
ISSN (Electronic)2191-5776

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Indexing for similarity search operators'. Together they form a unique fingerprint.

Cite this