Abstract
Top-k query has been widely studied recently in many applied fields. Fagin et al. [3] proposed an efficient algorithm, the Threshold Algorithm (i.e. TA), to process top-k queries. However, in many cases, TA does not terminate even if the final top-k results have been found for some time. Based on these, we propose a novel algorithm: Density Threshold Algorithm (i.e. DTA), which is designed to minimize the useless accesses of a top-k query, and introduce a novel indexing structure, Density Index, to support our algorithms. However, we proved the DTA is not instance optimal in Fagin’s notion and we also propose an instance optimal algorithm named Selective-Density Threshold Algorithm (i.e. S-DTA). Finally, extensive experiments show that our algorithms have significant improvement on the efficiency, compared with the TA algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ilyas, I., Beskales, G., Soliman, M.A.: A Survey of Top-k Query Processing Techniques in Relational Database Systems. ACM Computing Surveys (2008)
Yuan, J., Sun, G.-Z., Tian, Y., Chen, G., Liu, Z.: Selective-NRA Algorithms for Top-k Queries. In: Li, Q., Feng, L., Pei, J., Wang, S.X., Zhou, X., Zhu, Q.-M. (eds.) APWeb/WAIM 2009. LNCS, vol. 5446, pp. 15–26. Springer, Heidelberg (2009)
Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. In: PODS (2001)
Güntzer, U., Balke, W.T., Kieβling, W.: Optimizing Multi-Feature Queries for Image Databases. In: 26th VLDB (2000)
Gong, Z., Sun, G.-Z., Yuan, J., Zhong, Y.: Efficient top-k query algorithms using K-skyband partition. In: Mueller, P., Cao, J.-N., Wang, C.-L. (eds.) INFOSCALE 2009. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol. 18, pp. 288–305. Springer, Heidelberg (2009)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)
Gong, Z.Q., Sun, G.Z., Chen, D.Q.: Parallel Algorithms for Top-k Query Processing (unpublished)
Ilyas, I., Shah, R., Aref, W., Vitter, J., Elmagarmid, A.: Rank-Aware Query Optimization. In: ACM SIGMOD (2004)
Fagin, R.: Combining fuzzy information from multiple systems. J. Comput. System Sci. 58(1) (1999)
Chen, D.Q., Sun, G.Z., Gong, Z.Q., Yuan, J.: Efficient Approximate Top-k Query Algorithm Using Cube Index (unpublished)
Fagin, R., Kumar, R., Sivakumar, D.: Comparing Top K Lists. In: ACM-SIAM SODA (2003)
Chaudhuri, S., Dalvi, N., Kaushik, R.: Robust Cardinality and Cost Estimation for Skyline Operator. In: ICDE (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, D., Sun, GZ., Gong, N.Z., Zhong, X. (2011). Efficient Top-K Query Algorithms Using Density Index. In: Zeng, D. (eds) Applied Informatics and Communication. ICAIC 2011. Communications in Computer and Information Science, vol 224. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23214-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-23214-5_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23213-8
Online ISBN: 978-3-642-23214-5
eBook Packages: Computer ScienceComputer Science (R0)