Please use this identifier to cite or link to this item:
Title: Querying high-dimensional data in single-dimensional space
Authors: Yu, C.
Bressan, S. 
Ooi, B.C. 
Tan, K.-L. 
Keywords: Edge
High-dimensional data
Single-dimensional space
Window and KNN queries
Issue Date: 2004
Citation: Yu, C., Bressan, S., Ooi, B.C., Tan, K.-L. (2004). Querying high-dimensional data in single-dimensional space. VLDB Journal 13 (2) : 105-119. ScholarBank@NUS Repository.
Abstract: In this paper, we propose a new tunable index scheme, called iMinMax(θ), that maps points in high-dimensional spaces to single-dimensional values determined by their maximum or minimum values among all dimensions. By varying the tuning "knob", θ, we can obtain different families of iMinMax structures that are optimized for different distributions of data sets. The transformed data can then be indexed using existing single-dimensional indexing structures such as the B +-trees. Queries in the high-dimensional space have to be transformed into queries in the single-dimensional space and evaluated there. We present efficient algorithms for evaluating window queries as range queries on the single-dimensional space. We conducted an extensive performance study to evaluate the effectiveness of the proposed schemes. Our results show that iMinMax(θ) outperforms existing techniques, including the Pyramid scheme and VA-file, by a wide margin. We then describe how iMinMax could be used in approximate K-nearest neighbor (KNN) search, and we present a comparative study against the recently proposed iDistance, a specialized KNN indexing method.
Source Title: VLDB Journal
ISSN: 10668888
DOI: 10.1007/s00778-004-0121-9
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Jan 16, 2019


checked on Jan 16, 2019

Page view(s)

checked on Dec 29, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.