Please use this identifier to cite or link to this item:
|Title:||Making the Pyramid technique robust to query types and workloads|
|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. 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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Oct 18, 2018
WEB OF SCIENCETM
checked on Oct 10, 2018
checked on Oct 13, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.