High dimensional search using polyhedral query

Richard Connor*, Stewart MacKenzie-Leigh, Robert Moss

*Corresponding author for this work

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

1 Citation (Scopus)


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 - 7th International Conference, SISAP 2014, Proceedings
EditorsAgma Juci Machado Traina, Caetano Traina, Robson Leonardo Ferreira Cordeiro
Number of pages13
ISBN (Electronic)9783319119878
Publication statusPublished - 1 Jan 2014
Event7th International Conference on Similarity Search and Applications, SISAP 2014 - Los Cabos, Mexico
Duration: 29 Oct 201431 Oct 2014

Publication series

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


Conference7th International Conference on Similarity Search and Applications, SISAP 2014
CityLos Cabos


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

Cite this