Scalable Information Systems. 4th International ICST Conference, INFOSCALE 2009, Hong Kong, June 10-11, 2009, Revised Selected Papers

Research Article

Efficient Top- Query Algorithms Using -Skyband Partition

Download
491 downloads
  • @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
Zhenqiang Gong1,*, Guang-Zhong Sun1,*, Jing Yuan1,*, Yanjing Zhong1,*
  • 1: University of Science and Technology of China
*Contact email: gzqiang@mail.ustc.edu.cn, gzsun@ustc.edu.cn, yuanjing@mail.ustc.edu.cn, zhongyj@mail.ustc.edu.cn

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.