Indexing for similarity search operators

P. Deepak*, Prasad M. Deshpande

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

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
PublisherSpringer
Pages91-103
Number of pages13
Edition9783319212562
DOIs
Publication statusPublished - 01 Jan 2015
Externally publishedYes

Publication series

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

ASJC Scopus subject areas

  • Computer Science(all)

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

  • Cite this

    Deepak, P., & Deshpande, P. M. (2015). Indexing for similarity search operators. In SpringerBriefs in Computer Science (9783319212562 ed., pp. 91-103). (SpringerBriefs in Computer Science; No. 9783319212562). Springer. https://doi.org/10.1007/978-3-319-21257-9_6