Name
Abstract | ||
|---|---|---|
This paper discusses a new family of bounds for use in similarity search,
related to those used in metric indexing, but based on Ptolemy's inequality,
rather than the metric axioms. Ptolemy's inequality holds for the well-known
Euclidean distance, but is also shown here to hold for quadratic form metrics
in general. In addition, the square root of any metric is Ptolemaic, which
means that the principles introduced in this paper have a very wide
applicability. The inequality is examined empirically on both synthetic and
real-world data sets and is also found to hold approximately, with a very low
degree of error, for important distances such as the angular pseudometric and
several Lp norms. Indexing experiments are performed on several data sets,
demonstrating a highly increased filtering power when using certain forms of
Ptolemaic filtering, compared to existing, triangular methods. It is also shown
that combining the Ptolemaic and triangular filtering can lead to better
results than using either approach on its own. |
Year | Venue | Keywords |
|---|---|---|
2015 | JoCG | ptolemy's inequality,similarity retrieval,metric indexing,information retrieval,algorithms,data structures |
DocType | Volume | Issue |
Journal | abs/0911.4 | 1 |
ISSN | Citations | PageRank |
Journ. of Comp. Geom., JoCG, vol 6, no 1 (2015) 165-184 | 0 | 0.34 |
References | Authors | |
10 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Magnus Lie Hetland | 1 | 73 | 8.04 |