Please use this identifier to cite or link to this item: https://doi.org/10.1109/ICDE.2004.1320007
Title: Making the Pyramid technique robust to query types and workloads
Authors: Zhang, R.
Ooi, B.C. 
Tan, K.-L. 
Issue Date: 2004
Source: Zhang, R., Ooi, B.C., Tan, K.-L. (2004). Making the Pyramid technique robust to query types and workloads. Proceedings - International Conference on Data Engineering 20 : 313-324. ScholarBank@NUS Repository. https://doi.org/10.1109/ICDE.2004.1320007
Abstract: The effectiveness of many existing high-dimensional indexing structures is limited to specific types of queries and workloads. For example, while the Pyramid technique and the iMinMax are efficient for window queries, the iDistance is superior for kNN queries. In this paper, we present a new structure, called the P +-tree, that supports both window queries and kNN queries under different workloads efficiently. In the P +-tree, a B +-tree is employed to index the data points as follows. The data space is partitioned into subspaces based on clustering, and points in each sub-space are mapped onto a single dimensional space using the Pyramid technique, and stored in the B +-tree. The crux of the scheme lies in the transformation of the data which has two crucial properties. First, it maps each subspace into a hypercube so that the Pyramid technique can be applied. Second, it shifts the cluster center to the top of the pyramid, which is the case that the Pyramid technique works very efficiently. We present window and kNN query processing algorithms for the P +-tree. Through an extensive performance study, we show that the P +-tree has considerable speedup over the Pyramid technique and the iMinMax for window queries and outperforms the iDistance for kNN queries.
Source Title: Proceedings - International Conference on Data Engineering
URI: http://scholarbank.nus.edu.sg/handle/10635/41759
DOI: 10.1109/ICDE.2004.1320007
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

38
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

17
checked on Nov 19, 2017

Page view(s)

61
checked on Dec 17, 2017

Google ScholarTM

Check

Altmetric


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