Abstract
This paper addresses the efficient top-k queries in pure peer-to-peer (P2P) networks. Top-k receives much attention in the search engine and gains great success. However, processing top-k query in pure P2P network is very challenging due to unique characteristics of P2P environments, for example, skewed collection statistics, and higher communication costs. Inspired by the success of ranking algorithms in Web search engine, we propose a decentralized algorithm to answer top-k queries in pure peer-to-peer networks which makes use of local rankings, rank merging, and minimizes both answer set size and network traffic among peers.
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
Nejdl, W., Siberski, W., Thaden, U., Balke, W.-T.: Top-k Query Evaluation for Schema-based Peer-to-Peer Networks. In: Proceedings of third International Semantic Web Conference, Hiroshima, Japan, pp. 137–151. Springer, Heidelberg (2004)
HE, Y.-J., WANG, S., DU, X.-Y.: Efficient Top-k Query Processing in Pure Peer-to-Peer Network. Journal of Software 16, 540–552 (2005)
Balke, W.-T., Nejdl, W., Siberski, W., Thaden, U.: Progressive Distributed Top-k Retrieval in Peer-to-Peer Networks. In: Proceedings of International Conference on Data Engineering (ICDE 2005), Tokyo, Japan (2005)
Michel, S., Triantafillou, P., Weikum, G.: KLEE: A Framework for Distributed Top-k Query Algorithms. In: Proceedings of the 31th International Conference on Very Large Databases (VLDB), Norway, pp. 637–648 (2005)
Cuenca-Acuna, F.M., Peery, C., Nguyen, R.P.M.T.D.: Plantet: Infrastructure support for p2p information sharing. In: Technical Report DCS-TR-465, Department of Computer Science, Rutgers University (2001)
Lu, Z., Ling, B., Qian, W., et al.: A distributed ranking strategy in peer-to-peer based information retrieval systems. In: Yu, J.X., Lin, X., Lu, H., Zhang, Y. (eds.) APWeb 2004. LNCS, vol. 3007, pp. 279–284. Springer, Heidelberg (2004)
Tang, M.M.C., Xu, Z.: Peersearch: Efficient information retrieval in structured overlays. In: Proceedings Of HotNets-1 2002, ACM SIGCOMM (2002)
Lu, J., Callan, J.: Merging retrieval results in hierarchical peer-to-peer networks (poster description). In: Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 472–473 (2004)
Yu, B., Liu, J., Ong, C.S.: Scalable P2P information retrieval via hierarchical result merging.Technical report, Dep. of CS, University at Urbana-Champaign (2003)
Cao, P., Wang, Z.: Efficient top-K query calculation in distributed networks. In: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pp. 206–215. ACM Press, Canada (2004)
Theobald, M., Weikum, G., Schenkel, R.: Top-k Query Evaluation with Probabilistic Guarantees. In: Proceedings of the 30th VLDB Conference (VLDB), Toronto, Canada, pp. 248–659 (2004)
Yuwono, B., Lee, D.L.: Server ranking for distributed text retrieval systems on the internet. In: Proceedings of the 5th international conference on database systems for advanced applications, Victoria,Australia, pp. 41–49 (1997)
Rasolofo, Y., Abbaci, F., Savoy, J.: Approaches to collection selection and results merging for distributed information retrieval. In: Proceedings of the tenth international conference on Information and knowledge management, pp. 191–198. ACM Press, New York (2001)
Callan, J.P., Lu, Z., Croft, W.B.: Searching Distributed Collections with Inference Networks. In: Proceedings of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 21–28. ACM Press, New York (1995)
Gravano, L., Garcia-Molina, H.: Generalizing GLOSS to vector-space databases and broker hierarchies. In: Proceedings of the 21th International Conference on Very Large Databases (VLDB), pp. 78–89 (1995)
Cui, H., Wen, J.-R., Nie, J.-Y., Ma, W.-Y.: Query Expansion by Mining User Logs. IEEE transactions on knowledge and data engineering 15(4), 1–11 (2003)
Xu, J., Croft, W.B.: Cluster-based Language Models for Distributed Retrieval. In: Proceedings of the 22th International Conference on Research and Development in Information Retrieval, pp. 254–261 (1999)
Jansen, M., Spink, A., Saracevic, T.: Real Life, real users, and real needs: A study and analysis of user queries on the web. Information Processing and Management 36(2), 207–227 (2000)
Palmer, C.R., Steffan, J.G.: Generating Network Topologies That Obey Power Laws. In: Proceedings of Global Internet Symposium (2000)
The Gnutella protocol specification v0.6, http://rfcgnutellasourceforge.net
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, Q., Sun, Y., Zhang, X., Wen, X., Liu, Z. (2005). TOP-k Query Calculation in Peer-to-Peer Networks. In: Grumbach, S., Sui, L., Vianu, V. (eds) Advances in Computer Science – ASIAN 2005. Data Management on the Web. ASIAN 2005. Lecture Notes in Computer Science, vol 3818. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11596370_12
Download citation
DOI: https://doi.org/10.1007/11596370_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30767-9
Online ISBN: 978-3-540-32249-8
eBook Packages: Computer ScienceComputer Science (R0)