High dimensional search using polyhedral query

Richard Connor, Stewart MacKenzie-Leigh, Robert Moss

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

1 Citation (Scopus)

Abstract

It is well known that, as the dimensionality of a metric space increases, metric search techniques become less effective and the cost of indexing mechanisms becomes greater than the saving they give. This is due to the so-called curse of dimensionality.
One effect of increasing dimensionality is that the ratio of unit hypersphere to unit hypercube volume decreases rapidly, making the solution to a similarity query (the query ball, or hypersphere) ever more difficult to identify by using metric invariants such as triangle inequality.
In this paper we take a different approach, by identifying points within a query polyhedron rather than a ball. We show how this can be achieved by constructing a surrogate metric space, such that a query ball in the surrogate space corresponds to a polyhedron in the original space. If the polyhedron contains the ball, the overall cost of the query is likely to be increased in high dimensions; however, we show that shrinking the polyhedron can capture a surprisingly high proportion of the points within the ball, whilst at the same time giving a more efficient, and more scalable, search.
We show results which confirm our underlying hypothesis. In some cases we can retrieve significant volumes of query results from spaces which are otherwise intractable.
Original languageEnglish
Title of host publicationSimilarity Search and Applications
Subtitle of host publication7th International Conference, SISAP 2014, Los Cabos, Mexico, October 29-31, 2014. Proceedings
PublisherSpringer-Verlag
Pages176-188
Number of pages13
Volume8821
ISBN (Print)9783319119878
DOIs
Publication statusPublished - 20 Oct 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume8821
ISSN (Print)0302-9743

Keywords

  • high dimensional search
  • similarity search
  • hypersphere
  • hyperpolyhedron
  • high performance search

Fingerprint Dive into the research topics of 'High dimensional search using polyhedral query'. Together they form a unique fingerprint.

  • Cite this

    Connor, R., MacKenzie-Leigh, S., & Moss, R. (2014). High dimensional search using polyhedral query. In Similarity Search and Applications: 7th International Conference, SISAP 2014, Los Cabos, Mexico, October 29-31, 2014. Proceedings (Vol. 8821, pp. 176-188). (Lecture Notes in Computer Science; Vol. 8821). Springer-Verlag. https://doi.org/10.1007/978-3-319-11988-5_16