Abstract
Top-k query processing techniques provide two main advantages for unstructured peer-to-peer (P2P) systems. First they avoid overwhelming users with too many results. Second they reduce significantly network resources consumption. However, existing approaches suffer from long waiting times. This is because top-k results are returned only when all queried peers have finished processing the query. As a result, query response time is dominated by the slowest queried peer. In this paper, we address this users’ waiting time problem. For this, we revisit top-k query processing in P2P systems by introducing two novel notions in addition to response time: the stabilization time and the cumulative quality gap. Using these notions, we formally define the as-soon-as-possible (ASAP) top-k processing problem. Then, we propose a family of algorithms called ASAP to deal with this problem. We validate our solution through implementation and extensive experimentation. The results show that ASAP significantly outperforms baseline algorithms by returning final top-k result to users in much better times.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
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.
References
Akbarinia, R., Martins, V., Pacitti, E., Valduriez, P.: Design and Implementation of Atlas P2P Architecture. In: Global Data Management, 1st edn. IOS Press (2006)
Akbarinia, R., Pacitti, E., Valduriez, P.: Reducing network traffic in unstructured p2p systems using top-k queries. Distributed and Parallel Databases 19(2-3), 67–86 (2006)
Akbarinia, R., Pacitti, E., Valduriez, P.: Best position algorithms for top-k queries. In: Proceedings of Int. Conf. on Very Large Data Bases (VLDB), pp. 495–506 (2007)
Androutsellis-Theotokis, S., Spinellis, D.: A survey of peer-to-peer content distribution technologies. ACM Computing Surveys 36(4), 335–371 (2004)
Arai, B., Das, G., Gunopulos, D., Koudas, N.: Anytime measures for top-k algorithms. In: Proceedings of Int. Conf. on Very Large Data Bases (VLDB), pp. 914–925 (2007)
Balke, W.-T., Nejdl, W., Siberski, W., Thaden, U.: Progressive distributed top k retrieval in peer-to-peer networks. In: Proceedings of Int. Conf. on Data Engineering (ICDE), pp. 174–185 (2005)
Bruno, N., Gravano, L., Marian, A.: Evaluating top-k queries over web-accessible databases. In: Proceedings of Int. Conf. on Data Engineering (ICDE), pp. 369–380 (2002)
Cao, P., Wan, Z.: Efficient top-k query calculation in distributed networks. In: Proceedings of Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 206–215 (2004)
Chaudhuri, S., Gravano, L.: Evaluating top-k selection queries. In: Proceedings of Int. Conf. on Very Large Databases (VLDB), pp. 397–410 (1999)
Chaudhuri, S., Gravano, L., Marian, A.: Optimizing top-k selection queries over multimedia repositories. IEEE Transactions on Knowledge Data Engineering 16(8), 992–1009 (2004)
Cuenca-Acuna, F.M., Peery, C., Martin, R.P., Nguyen, T.D.: Planetp: Using gossiping to build content addressable peer-to-peer information sharing communities. In: Proceedings of IEEE Int. Symp. on High-Performance Distributed Computing (HPDC), pp. 236–249 (2003)
Dedzoe, W.K., Lamarre, P., Akbarinia, R., Valduriez, P.: Asap top-k query processing in unstructured p2p systems. In: Proceedings of IEEE Int. Conf on Peer-to-Peer Computing (P2P), pp. 187–196 (2010)
Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. In: Proceedings of Symposium on Principles of Database Systems (PODS), pp. 102–113 (2001)
Feng, G., Jiang, Y., Chen, G., Gu, Q., Lu, S., Chen, D.: Replication strategy in unstructured peer-to-peer systems. In: Proceedings of IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1–8 (2007)
Gummadi, P.K., Saroiu, S., Gribble, S.D.: A measurement study of napster and gnutella as examples of peer-to-peer file sharing systems. Computer Communication Review 32(1), 82 (2002)
Güntzer, U., Balke, W.-T., Kießling, W.: Optimizing multi-feature queries for image databases. In: Proceedings of Int. Conf. on Very Large DataBases (VLDB), pp. 419–428 (2000)
Hose, K., Karnstedt, M., Sattler, K.-U., Zinn, D.: Processing top-n queries in p2p-based web integration systems with probabilistic guarantees. In: Proceedings of International Workshop on web and databases (WebDB), pp. 109–114 (2005)
Hristidis, V., Koudas, N., Papakonstantinou, Y.: Prefer: A system for the efficient execution of multi-parametric ranked queries. In: Proceedings of ACM. Int. Conf. on Management of Data (SIGMOD), pp. 259–270 (2001)
Jelasity, M., Montresor, A.: Epidemic-style proactive aggregation in large overlay networks. In: Int. Conference on Distributed Computing Systems (ICDCS), pp. 102–109 (2004)
Jelasity, M., Montresor, A., Jesi, G.P., Voulgaris, S.: The Peersim simulator, http://peersim.sf.net
Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: Symposium on Foundations of Computer Science (FOCS), pp. 482–491 (2003)
Michel, S., Triantafillou, P., Weikum, G.: Klee: A framework for distributed top-k query algorithms. In: Proceedings of Int. Conf. on Very Large Data Bases (VLDB), pp. 637–648 (2005)
Ooi, B.C., Shu, Y., Tan, K.-L.: Relational data sharing in peer-based data management systems. SIGMOD Record 32(3), 59–64 (2003)
Qin, L., Yu, J.X., Chang, L.: Diversifying top-k results. PVLDB 5(11), 1124–1135 (2012)
Ramaswamy, L., Chen, J., Parate, P.: Coquos: Lightweight support for continuous queries in unstructured overlays. In: Proceedings of IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1–10 (2007)
Schmid, S., Wattenhofer, R.: Structuring unstructured peer-to-peer networks. In: Proceedings of IEEE Int. Conf. on High Performance Computing (HiPC), pp. 432–442 (2007)
Shmueli-Scheuer, M., Li, C., Mass, Y., Roitman, H., Schenkel, R., Weikum, G.: Best-effort top-k query processing under budgetary constraints. In: Proceedings of Int. Conf. on Data Engineering (ICDE), pp. 928–939 (2009)
Tatarinov, I., Ives, Z.G., Madhavan, J., Halevy, A.Y., Suciu, D., Dalvi, N.N., Dong, X., Kadiyska, Y., Miklau, G., Mork, P.: The piazza peer data management project. SIGMOD Record 32(3), 47–52 (2003)
Terpstra, W.W., Kangasharju, J., Leng, C., Buchmann, A.P.: Bubblestorm: resilient, probabilistic, and exhaustive peer-to-peer search. In: SIGCOMM, pp. 49–60 (2007)
Tsoumakos, D., Roussopoulos, N.: Analysis and comparison of p2p search methods. In: Proceedings of Int. Conf. on Scalable Information Systems (Infoscale), p. 25 (2006)
Vlachou, A., Doulkeridis, C., Nørvåg, K.: Distributed top-k query processing by exploiting skyline summaries. Distributed and Parallel Databases 30(3-4), 239–271 (2012)
Vlachou, A., Doulkeridis, C., Nørvåg, K., Vazirgiannis, M.: On efficient top-k query processing in highly distributed environments. In: Proceedings of ACM. Int Conf. on Management of Data (SIGMOD), pp. 753–764 (2008)
Ye, M., Lee, W.-C., Lee, D.L., Liu, X.: Distributed processing of probabilistic top-k queries in wireless sensor networks. IEEE Trans. Knowl. Data Eng. 25(1), 76–91 (2013)
Zhao, K., Tao, Y., Zhou, S.: Efficient top-k processing in large-scaled distributed environments. Data and Knowledge Engineering 63(2), 315–335 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Dédzoé, W.K., Lamarre, P., Akbarinia, R., Valduriez, P. (2013). As-Soon-As-Possible Top-k Query Processing in P2P Systems. In: Hameurlain, A., Küng, J., Wagner, R. (eds) Transactions on Large-Scale Data- and Knowledge-Centered Systems IX. Lecture Notes in Computer Science, vol 7980. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40069-8_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-40069-8_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40068-1
Online ISBN: 978-3-642-40069-8
eBook Packages: Computer ScienceComputer Science (R0)