Query filtering with low-dimensional local embeddings

Edgar Chávez, Richard Connor*, Lucia Vadicamo

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

The concept of local pivoting is to partition a metric space so that each element in the space is associated with precisely one of a fixed set of reference objects or pivots. The idea is that each object of the data set is associated with the reference object that is best suited to filter that particular object if it is not relevant to a query, maximising the probability of excluding it from a search. The notion does not in itself lead to a scalable search mechanism, but instead gives a good chance of exclusion based on a tiny memory footprint and a fast calculation. It is therefore most useful in contexts where main memory is at a premium, or in conjunction with another, scalable, mechanism.

In this paper we apply similar reasoning to metric spaces which possess the four-point property, which notably include Euclidean, Cosine, Triangular, Jensen-Shannon, and Quadratic Form. In this case, each element of the space can be associated with two reference objects, and a four-point lower-bound property is used instead of the simple triangle inequality. The probability of exclusion is strictly greater than with simple local pivoting; the space required per object and the calculation are again tiny in relative terms.

We show that the resulting mechanism can be very effective. A consequence of using the four-point property is that, for m reference points, there are (m/2) pivot pairs to choose from, giving a very good chance of a good selection being available from a small number of distance calculations. Finding the best pair has a quadratic cost with the number of references; however, we provide experimental evidence that good heuristics exist. Finally, we show how the resulting mechanism can be integrated with a more scalable technique to provide a very significant performance improvement, for a very small overhead in build-time and memory cost.

Original languageEnglish
Title of host publicationSimilarity Search and Applications
Subtitle of host publication12th International Conference, SISAP 2019, Newark, NJ, USA, October 2–4, 2019, Proceedings
EditorsGiuseppe Amato, Claudio Gennaro, Vincent Oria, Miloš Radovanovic
Place of PublicationCham
PublisherSpringer
Pages233-246
Number of pages14
ISBN (Electronic)9783030320478
ISBN (Print)9783030320461
DOIs
Publication statusPublished - 2019
Event12th International Conference on Similarity Search and Applications, SISAP 2019 - Newark, United States
Duration: 2 Oct 20194 Oct 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11807 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on Similarity Search and Applications, SISAP 2019
Country/TerritoryUnited States
CityNewark
Period2/10/194/10/19

Keywords

  • Extreme pivoting
  • Four-point property
  • Metric search
  • Pivot based index
  • Supermetric space

Fingerprint

Dive into the research topics of 'Query filtering with low-dimensional local embeddings'. Together they form a unique fingerprint.

Cite this