Research Article
Efficient Top- Query Algorithms Using -Skyband Partition
@INPROCEEDINGS{10.1007/978-3-642-10485-5_21, author={Zhenqiang Gong and Guang-Zhong Sun and Jing Yuan and Yanjing Zhong}, title={Efficient Top- Query Algorithms Using -Skyband Partition}, proceedings={Scalable Information Systems. 4th International ICST Conference, INFOSCALE 2009, Hong Kong, June 10-11, 2009, Revised Selected Papers}, proceedings_a={INFOSCALE}, year={2012}, month={5}, keywords={Top- Queries -skyband Queries NRA Algorithm Dominate}, doi={10.1007/978-3-642-10485-5_21} }- Zhenqiang Gong
Guang-Zhong Sun
Jing Yuan
Yanjing Zhong
Year: 2012
Efficient Top- Query Algorithms Using -Skyband Partition
INFOSCALE
Springer
DOI: 10.1007/978-3-642-10485-5_21
Abstract
Efficient processing of top- queries has become a classical research area. Fagin et al. proposed the “middleware cost” for a top- query algorithm. In some scenario, there is no way to perform a random access, and Fagin et al. proposed NRA (No Random Access) algorithm for that. In this paper, we investigate the intrinsic relation between top- queries and -skyband queries. Based on that relation, we propose a novel algorithm DNRA (Dominate-NRA). The main idea of DNRA is to partition the original dataset into two sub-datasets depending on whether they belong to -skyband or not. We prove that DNRA performs no more sorted accesses than NRA on any dataset. Furthermore, we partition the dataset into sub-datasets ( is the number of objects in the dataset), and then we propose our algorithm ADNRA (Advanced-DNRA). The partition of the dataset is pre-computed, and we discuss two techniques to fulfill it. Extensive experiments show that our algorithms perform several orders of magnitude fewer accesses than NRA and that ADNRA performs significantly fewer accesses than DNRA on some datasets.
