HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/2918
Title: A general cost model for dimensionality reduction in high dimensional spaces
Authors: Lian, Xiang
Chen, Lei
Keywords: Query processing
General cost model
Data dimensionality
Tree index
Issue Date: 2007
Citation: Proceedings IEEE 23rd International Conference on Data Engineering (ICDE 2007), 15-20 April 2007, Istanbul, p. 66-75
Abstract: 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, previous approaches usually 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)). However, so far little work has formally evaluated the effectiveness and efficiency of both GDR and LDR for range queries. Motivated by this, in this paper, we propose a general cost model for both GDR and LDR, in light of which we introduce a novel LDR method, PRANS. It can achieve high retrieval efficiency with the guarantee of optimality given by the formal model. Finally, a B+-tree index is constructed over the reduced partitions for fast similarity search. Extensive experiments validate the correctness of our cost model on both real and synthetic data sets, and demonstrate the efficiency and effectiveness of the proposed PRANS method.
Rights: © 2007 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.
URI: http://hdl.handle.net/1783.1/2918
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
general.pdf396KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.