Ptolemaic Indexing

Details Ptolemaic Indexing Ptolemaic Indexing

2009-11-23

arxiv.org/abs/0911.4384v2

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Ptolemaic Indexing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Ptolemaic Indexing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ptolemaic Indexing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-173185