Bounded Approximation: A New Criterion for Dimensionality Reduction Approximation in Similarity Search

摘要

We examine the problem of efficient distance-based similarity search over high-dimensional data. A promising approach to this problem is to reduce dimensions and allow fast approximation. Conventional reduction approaches, however, entail a significant shortcoming: the approximation volume extends across the dataspace, which causes over-estimation of retrieval sets and impairs performance. This paper focuses on a new criterion for dimensionality reduction methods: bounded approximation. We show that this requirement can be accomplished by a novel non-linear transformation scheme that extracts two important parameters from the data. We devise two approximation formulations, rectangular and spherical range search, each corresponding to a closed volume around the original search sphere. We discuss in detail how to derive tight bounds for the parameters and to prove further results, as well as highlighting insights into the problems and our proposed solutions. To demonstrate the benefits of the new criterion, we study the effects of (un)boundedness on approximation performance, including selectivity, error toleration, and efficiency. Extensive experiments confirm the superiority of this technique over recent state-of-the-art schemes.