Title

Bounded Approximation: A New Criterion For Dimensionality Reduction Approximation In Similarity Search

Keywords

Bounded approximation; Dimensionality reduction; Nonlinear transformation; Similarity search; Spherical range search

Abstract

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. © 2006 IEEE.

Publication Date

6-1-2008

Publication Title

IEEE Transactions on Knowledge and Data Engineering

Volume

20

Issue

6

Number of Pages

768-783

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/TKDE.2008.30

Socpus ID

42949088491 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/42949088491

This document is currently not available here.

Share

COinS