### 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 language | English |
---|---|

Title of host publication | SpringerBriefs in Computer Science |

Publisher | Springer |

Pages | 91-103 |

Number of pages | 13 |

Edition | 9783319212562 |

DOIs | |

Publication status | Published - 01 Jan 2015 |

Externally published | Yes |

### Publication series

Name | SpringerBriefs in Computer Science |
---|---|

Number | 9783319212562 |

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

*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