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.
|Title of host publication
|Similarity Search and Applications
|Subtitle of host publication
|12th International Conference, SISAP 2019, Newark, NJ, USA, October 2–4, 2019, Proceedings
|Giuseppe Amato, Claudio Gennaro, Vincent Oria, Miloš Radovanovic
|Place of Publication
|Number of pages
|Published - 2019
|12th International Conference on Similarity Search and Applications, SISAP 2019 - Newark, United States
Duration: 2 Oct 2019 → 4 Oct 2019
|Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|12th International Conference on Similarity Search and Applications, SISAP 2019
|2/10/19 → 4/10/19
- Extreme pivoting
- Four-point property
- Metric search
- Pivot based index
- Supermetric space