Abstract
Incremental access can be essential for top-k queries, as users often want to sift through top answers until satisfied. In this paper, we propose the progressive rank (PR, for short) algorithm, a new non-blocking top-k query algorithm that deals with data items from remote sources via unpredictable, slow, or bursty network traffic. By accessing remote sources asynchronously and scheduling background processing reactively, PR hides intermittent delays in data arrival and produces the first few results quickly. Experiments results show that PR is an effective solution for producing fast query responses in the presence of slow and bursty remote sources, and can be scaled well.
This research is partly supported by the National High Technology Research and Development Plan (863 plan) of China under Grants No.2004AA112020 and No.2003AA111020.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bruno, N., Gravano, L., Marian, A.: Evaluating top-k queries over web-accessible databases. In: ICDE (2002)
Balke, W.-T., Nejdl, W., Siberski, W., et al.: Progressive Distributed Top-k Retrieval in Peer-to-Peer Networks. In: ICDE 2005 (2005)
Babcock, B., Olston, C.: Distributed Top-K Monitoring. In: SIGMOD (2003)
Chang, K.C.-C., Hwang, S.-W.: Minimal probing: supporting expensive predicates for top-k queries. In: SIGMOD (2002)
Carey, M.J., Kossmann, D.: On saying “Enough already!” in SQL. In: SIGMOD (1997)
Crovella, M.E., Taqqu, M.S., Bestavros, A.: Heavy-tailed probability distributions in the world wide web, chapter A practical guide to heavy tails: statistical techniques and applications, pp. 3–26. Chapman Hall, Boca Raton (1998)
Cao, P., Wang, Z.: Efficient top-k query calculation in distributed networks. In: PODS (2004)
Fagin, R.: Combining fuzzy information from multiple systems. J. Comput. System Sci. 58, 83–99 (1999)
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: VLDB (2000)
Güntzer, U., Balke, W.-T., Kieβling, W.: Towards efficient multi-feature queries in heterogeneous environments. In: ITCC (2001)
Hwang, S., Chang, K.C.-C.: Optimizing Access Cost for Top-k Queries over Web Sources: A Unified Costbased Approach. In: ICDE (2005)
Hellerstein, J.M., Haas, P.J., Wang, H.J.: Online Aggregation. In: Proceedings of the ACM International Conference on Management of Data, In SIGMOD (1997)
Marian, A., Gravano, L., Bruno, N.: Evaluating Top-k Queries over Web-Accessible Databases. TODS 29(2) (2004)
Michel, S., Triantafillou, P., Weikum, G.: KLEE: A Framework for Distributed Top-k Query Algorithms. In: VLDB (2005)
Nepal, S., Ramakrishna, M.V.: Query processing issues in image (multimedia) databases. In: ICDE (1999)
Urhan, T., Franklin, M.J.: XJoin: Getting Fast Answers From Slow and Burst Networks. Technical Report CS-TR-3994, UMIACS-TR-99-13, Computer Science Department, University of Maryland (February 1999)
Wilschut, A.N., Apers, P.M.G.: Pipelining in Query Execution. In: Databases, Parallel, Architectures, and their applications, Miami (1990)
Yu, C., Philip, G., Meng, W.: Distributed Top-N Query Processing with Possibly Uncooperative Local Systems. In: Aberer, K., Koubarakis, M., Kalogeraki, V. (eds.) VLDB 2003. LNCS, vol. 2944, Springer, Heidelberg (2004)
Zipf, G.K.: Human Behavior and the Principle of Least Effort. Addison-Wesley Press, Reading (1949)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Deng, B., Jia, Y., Yang, S. (2006). Efficient Non-Blocking Top-k Query Processing in Distributed Networks. In: Li Lee, M., Tan, KL., Wuwongse, V. (eds) Database Systems for Advanced Applications. DASFAA 2006. Lecture Notes in Computer Science, vol 3882. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11733836_65
Download citation
DOI: https://doi.org/10.1007/11733836_65
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33337-1
Online ISBN: 978-3-540-33338-8
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
