Please use this identifier to cite or link to this item:

General Cost Models for Evaluating Dimensionality Reduction in High-Dimensional Spaces

Authors Lian, Xiang HKUST affiliated (currently or previously)
Chen, Lei View this author's profile
Issue Date 2009
Source IEEE transactions on knowledge and data engineering , v. 21, (10), 2009, OCT, p. 1447-1460
Summary Similarity search usually encounters a serious problem in the high-dimensional space, known as the "curse of dimensionality." In order to speed up the retrieval efficiency, most previous approaches reduce the dimensionality of the entire data set to a fixed lower value before building indexes (referred to as global dimensionality reduction (GDR)). More recent works focus on locally reducing the dimensionality of data to different values (called the local dimensionality reduction (LDR)). In addition, random projection is proposed as an approximate dimensionality reduction (ADR) technique to answer the approximate similarity search instead of the exact one. However, so far little work has formally evaluated the effectiveness and efficiency of GDR, LDR, and ADR for the range query. Motivated by this, in this paper, we propose general cost models for evaluating the query performance over the reduced data sets by GDR, LDR, and ADR, in light of which we introduce a novel (A) LDR method, Partitioning based on RANdomized Search (PRANS). It can achieve high retrieval efficiency with the guarantee of optimality given by the formal models. Finally, a B+-tree index is constructed over the reduced partitions for fast similarity search. Extensive experiments validate the correctness of our cost models on both real and synthetic data sets and demonstrate the efficiency and effectiveness of the proposed PRANS method.
ISSN 1041-4347
Rights © 2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
10840466.pdf 2296854 B Adobe PDF