Versatile probability-based indexing for approximate similarity search
Takao Murakami, Kenta Takahashi, Susumu Serita, Yasuhiro Fujii · 2011
We aim at reducing the number of distance computations as much as possible in the inexact indexing schemes which sort the objects according to some promise values. To achieve this aim, we propose a new probability-based indexing scheme which can be applied to any inexact indexing scheme that uses the promise values. Our scheme (1) uses the promise values obtained from any inexact scheme to compute the new probability-based promise values. In order to estimate the new promise values, we (2) use the object-specific parameters in logistic regression and learn the parameters using MAP (Maximum a Posteriori) estimation. We also propose a technique which (3) speeds up learning the parameters using the promise values. We applied our scheme to the standard pivot-based scheme and the permutation-based scheme, and evaluated them using various kinds of datasets from the Metric Space Library. The results showed that our scheme improved the conventional schemes, in all cases.