|
|
|
     |
                                     |
Return to Spatial and Nearest Neighbor Queries
In this paper, we present a novel index structure, called delta- tree, to speed up processing of high-dimensional K-nearest neighbor (KNN) queries in main memory environment. The delta-tree is a multi-level structure where each level represents the data space at different dimensionalities: the number of dimensions increases towards the leaf level which contains the data at their full dimensions. The remaining dimensions are obtained using Principal Component Analysis, which has the desirable property that the first few dimensions capture most of the information in the dataset. Each level of the tree serves to prune the search space more efficiently as the reduced dimensions can better exploit the small cache line size. Moreover, the distance computation on lower dimensionality is less expensive. We also propose an extension, called delta+- tree, that globally clusters the data space and then further partitions clusters into small regions to reduce the search space. We conducted extensive experiments to evaluate the proposed structures against existing techniques on different kinds of datasets. Our results show that the delta+-tree is superior in most cases.
@inproceedings {DBLP:conf/sigmod/CuiOTS03, author = {Bin Cui and Beng Chin Ooi and Jianwen Su and Kian-Lee Tan}, booktitle = {SIGMOD Conference}, title = {Contorting High Dimensional Data for Efficient Main Memory Processing.}, pages = {479-490}, year = {2003}, url = {db/conf/sigmod/sigmod2003.html#CuiOTS03}, ee = {http://www.acm.org/sigmod/sigmod03/eproceedings/papers/r17p05.pdf}, crossref = {conf/sigmod/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} }  ©2004 Association for Computing Machinery |
