Please use this identifier to cite or link to this item:
Title: Making the Pyramid technique robust to query types and workloads
Authors: Zhang, R.
Ooi, B.C. 
Tan, K.-L. 
Issue Date: 2004
Citation: 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.
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
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.


checked on Mar 20, 2019


checked on Mar 20, 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.