2016
Journal article
Open Access
Multidimensional range queries on hierarchical Voronoi overlays
Ferrucci L., Ricci L., Baraglia R., Mordacchini M., Albano M.
Computational Theory and Mathematics Distributed systems Theoretical Computer Science Range queries Computer Networks and Communications Applied Mathematics Voronoi
The definition of a support for multi-attribute range queries is mandatory for highly distributed systems. Even if several solutions have been proposed in the last decade, most of them do not meet the requirements of recent platforms, like IoT or smart cities. The paper presents an approach that builds a multidimensional Voronoi graph by exploiting the attributes of the objects published by a node. Our solution overcomes the curse of dimensionality issue affecting Voronoi Tessellations in high dimensional spaces by defining a Voronoi hierarchy. The paper formally defines the structure, analysis the complexity of the operations and presents experimental results.
Source: Journal of computer and system sciences (Print) 82 (2016): 1161–1179. doi:10.1016/j.jcss.2016.04.008
Publisher: Academic Press., New York,, Stati Uniti d'America
[1] L. Atzori, A. Iera, G. Morabito, The Internet of things: a survey, Comput. Netw. 54 (15) (2010) 2787-2805.
[2] F. Paganelli, D. Parlanti, A dht-based discovery service for the Internet of things, J. Comput. Netw. Commun. 2012 (2012).
[3] B. Flavio, A.M. Rodolfo, N. Preethi, J. Zhu, Fog computing: a platform for Internet of things and analytics, in: Big Data and Internet of Things: A Roadmap for Smart Environments, 2014, pp. 169-186.
[4] M. Cai, M. Frank, J. Chen, P. Szekely, MAAN: a multi-attribute addressable network for grid information services, in: GRID'03: Proc. of the 4th Int. Workshop on Grid Computing, IEEE Computer Society, Washington, DC, USA, 2003, p. 184.
[5] Y. Shu, B.C. Ooi, K.-L. Tan, A. Zhou, Supporting multi-dimensional range queries in peer-to-peer systems, in: IEEE International Conference on Peer-toPeer Computing, 2005, pp. 173-180.
[6] A.R. Bharambe, M. Agrawal, S. Seshan, Mercury: supporting scalable multi-attribute range queries, in: Proc. ACM SIGCOMM 2004 Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communication, ACM Press, 2004, pp. 353-366.
[7] T. Pitoura, N. Ntarmos, P. Triantafillou, Saturn: range queries, load balancing and fault tolerance in dht data systems, IEEE Trans. Knowl. Data Eng.
[8] J. Albrecht, D. Oppenheimer, A. Vahdat, D.A. Patterson, Design and implementation trade-offs for wide-area resource discovery, ACM Trans. Internet Technol. 8 (4) (2008) 1-44.
[9] H. Shen, C.-Z. Xu, Leveraging a compound graph-based dht for multi-attribute range queries with performance analysis, IEEE Trans. Comput. 61 (4) (2012) 433-447.
[10] S. Lodi, G. Moro, C. Sartori, Distributed data clustering in multi-dimensional peer-to-peer networks, in: Proceedings of the Twenty-First Australasian Conference on Database Technologies, vol. 104, Australian Computer Society, Inc., 2010, pp. 171-178.
[11] R. Giordanelli, C. Mastroianni, M. Meo, A self-organizing p2p system with multi-dimensional structure, in: Proceedings of the 8th ACM International Conference on Autonomic Computing, ACM, 2011, pp. 51-60.
[12] E. Carlini, L. Ricci, M. Coppola, Flexible load distribution for hybrid distributed virtual environments, Future Gener. Comput. Syst. 29 (6) (2013) 1561-1572.
[13] V. Bioglio, R. Gaeta, M. Grangetto, M. Sereno, Rateless codes and random walks for p2p resource discovery in grids, IEEE Trans. Parallel Distrib. Syst.
[14] S. Sioutas, T. Triantafillou, G. Papaloukopoulos, E. Sakkopoulos, K. Tsichlas, Y. Manolopoulos, Art: sub-logarithmic decentralized range query processing with probabilistic guarantees, IEEE Trans. Parallel Distrib. Syst. 31 (1) (May 2013) 71-109.
[15] H.V. Jagadish, B.C. Ooi, Q.H. Vu, BATON: a balanced tree structure for peer-to-peer networks, in: Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30-September 2, 2005, 2005, pp. 661-672.
[16] M.A. Arefin, M.Y.S. Uddin, I. Gupta, K. Nahrstedt, Q-tree: a multi-attribute based range query solution for tele-immersive framework, in: 29th IEEE International Conference on Distributed Computing Systems, ICDCS 2009, 22-26 June 2009, Montreal, Québec, Canada, 2009, pp. 299-307.
[17] S. Ramabhadran, S. Ratnasamy, J.M. Hellerstein, S. Shenker, Prefix hash tree: an indexing data structure over distributed hash tables, in: Proc. of the 23rd ACM Symposium on Principles of Distributed Computing, 2004.
[18] O. Beaumont, A. Marie Kermarrec, L. Marchal, E. Riviere, E. Lyon, Voronet: a scalable object network based on Voronoi tessellations, in: Proceedings of the 21st International Parallel and Distributed Processing Symposium, IPDPS 2007, Society Press, 2007.
[19] F. Banaei-Kashani, C. Shahabi, SWAM: a family of access methods for similarity-search in peer-to-peer data networks, in: CIKM'04: Proceedings of the Thirteenth ACM International Conference on Information and Knowledge Management, ACM, New York, NY, USA, 2004, pp. 304-313.
[20] M. Albano, M. Baldanzi, R. Baraglia, L. Ricci, Voraque: range queries on Voronoi overlays, in: Proceedings of 13th IEEE Symposium on Computers and Communications, July 2008.
[21] L. Rodrigues, F. Araujo, Geopeer: a location-aware p2p system, in: 3rd IEEE International Conference on Network Computing and Applications, NCA'04, 2004.
[22] E. Kranakis, H. Singh, J. Urrutia, Compass routing on geometric networks, in: Proceedings of 11th Can. Conf. on Computational Geometry, CCCG, August 1999.
[23] M. Mordacchini, L. Ricci, L. Ferrucci, R.B.M. Albano, Hivory: range queries on hierarchical Voronoi overlays, in: Proceedings of 10th IEEE P2P Computing Conference, Jul. 2010.
[24] I. Stoica, R. Morris, D. Liben-Nowell, D.R. Karger, M.F. Kaashoek, F. Dabek, H. Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for Internet applications, IEEE/ACM Trans. Netw. 11 (1) (2003) 17-32.
[25] S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Schenker, A scalable content-addressable network, in: Proc. SIGCOMM'01, ACM Press, New York, NY, USA, 2001, pp. 161-172.
[26] A.I.T. Rowstron, P. Druschel, Pastry: scalable, decentralized object location, and routing for large-scale peer-to-peer systems, in: Middleware 2001: Proc. of the IFIP/ACM Int. Conf. on Distributed Systems Platforms, Heidelberg, Springer-Verlag, London, UK, 2001, pp. 329-350.
[27] A. Andrzejak, Z. Xu, Scalable, efficient range queries for grid information services, in: R.L. Graham, N. Shahmehri (Eds.), Peer-to-Peer Computing, IEEE Computer Society, 2002, pp. 33-40.
[28] R. Baraglia, P. Dazzi, B. Guidi, L. Ricci, Godel: Delaunay overlays in p2p networks via gossip, in: IEEE P2P, 2012, pp. 1-12.
[29] J. Liebeherr, M. Nahas, W. Si, Application-layer multicasting with Delaunay triangulation overlays, IEEE J. Sel. Areas Commun. 20 (8) (2002) 1472-1488.
[30] F. Aurenhammer, Voronoi diagrams-a survey of a fundamental geometric data structure, ACM Comput. Surv. 23 (September 1991).
[31] D. Lee, S. Lam, Efficient and accurate protocols for distributed Delaunay triangulation under churn, in: IEEE International Conference on Network Protocols, ICNP 2008, IEEE, 2008, pp. 124-136.
[32] M. Ohnishi, R. Nishide, S. Ueshima, Incremental construction of Delaunay overlaid network for virtual collaborative space, in: Third International Conference on Creating, Connecting and Collaborating Through Computing, C5 2005, IEEE, 2005, pp. 75-82.
[33] H. Kato, T. Eguchi, M. Ohnishi, S. Ueshima, Autonomous generation of spherical p2p Delaunay network for global Internet applications, in: The Fourth International Conference on Creating, Connecting and Collaborating Through Computing, C5'06, IEEE, 2006, pp. 184-191.
[34] R. Baraglia, P. Dazzi, M. Mordacchini, L. Ricci, A peer-to-peer recommender system for self-emerging user communities based on gossip overlays, J. Comput. Syst. Sci. 79 (2) (2013) 291-308.
[35] K. Hong, D. Lillethun, U. Ramachandran, B. Ottenwälder, B. Koldehofe, Mobile fog: a programming model for large-scale applications on the Internet of things, in: Proceedings of the Second ACM SIGCOMM Workshop on Mobile Cloud Computing, MCC'13, ACM, New York, NY, USA, 2013, pp. 15-20.
[36] H. Samet, Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, 2006.
[37] L. Ferrucci, Un sistema gerarchico basato su voronoi per la risoluzione di query multiattributo, Master Thesis, University of Pisa etd-11102009-151747, December 2009.
[38] M. Jelasity, A. Montresor, G.P. Jesi, S. Voulgaris, The Peersim simulator, http://peersim.sf.net.
[39] B. Chun, D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawrzoniak, M. Bowman, Planetlab: an overlay testbed for broad-coverage services, SIGCOMM Comput. Commun. Rev. 33 (3) (Jul. 2003) 3-12 [Online], available http://doi.acm.org/10.1145/956993.956995.
[40] L. Wang, K. Park, R. Pang, V.S. Pai, L.L. Peterson, Reliability and security in the CoDeeN content distribution network, in: USENIX Annual Technical Conference, General Track, June 2004, pp. 171-184.
[41] K. Park, V.S. Pai, Comon: a mostly-scalable monitoring system for planetlab, SIGOPS Oper. Syst. Rev. 40 (1) (Jan. 2006) 65-74 [Online], available: http://doi.acm.org/10.1145/1113361.1113374.
[2] F. Paganelli, D. Parlanti, A dht-based discovery service for the Internet of things, J. Comput. Netw. Commun. 2012 (2012).
[3] B. Flavio, A.M. Rodolfo, N. Preethi, J. Zhu, Fog computing: a platform for Internet of things and analytics, in: Big Data and Internet of Things: A Roadmap for Smart Environments, 2014, pp. 169-186.
[4] M. Cai, M. Frank, J. Chen, P. Szekely, MAAN: a multi-attribute addressable network for grid information services, in: GRID'03: Proc. of the 4th Int. Workshop on Grid Computing, IEEE Computer Society, Washington, DC, USA, 2003, p. 184.
[5] Y. Shu, B.C. Ooi, K.-L. Tan, A. Zhou, Supporting multi-dimensional range queries in peer-to-peer systems, in: IEEE International Conference on Peer-toPeer Computing, 2005, pp. 173-180.
[6] A.R. Bharambe, M. Agrawal, S. Seshan, Mercury: supporting scalable multi-attribute range queries, in: Proc. ACM SIGCOMM 2004 Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communication, ACM Press, 2004, pp. 353-366.
[7] T. Pitoura, N. Ntarmos, P. Triantafillou, Saturn: range queries, load balancing and fault tolerance in dht data systems, IEEE Trans. Knowl. Data Eng.
[8] J. Albrecht, D. Oppenheimer, A. Vahdat, D.A. Patterson, Design and implementation trade-offs for wide-area resource discovery, ACM Trans. Internet Technol. 8 (4) (2008) 1-44.
[9] H. Shen, C.-Z. Xu, Leveraging a compound graph-based dht for multi-attribute range queries with performance analysis, IEEE Trans. Comput. 61 (4) (2012) 433-447.
[10] S. Lodi, G. Moro, C. Sartori, Distributed data clustering in multi-dimensional peer-to-peer networks, in: Proceedings of the Twenty-First Australasian Conference on Database Technologies, vol. 104, Australian Computer Society, Inc., 2010, pp. 171-178.
[11] R. Giordanelli, C. Mastroianni, M. Meo, A self-organizing p2p system with multi-dimensional structure, in: Proceedings of the 8th ACM International Conference on Autonomic Computing, ACM, 2011, pp. 51-60.
[12] E. Carlini, L. Ricci, M. Coppola, Flexible load distribution for hybrid distributed virtual environments, Future Gener. Comput. Syst. 29 (6) (2013) 1561-1572.
[13] V. Bioglio, R. Gaeta, M. Grangetto, M. Sereno, Rateless codes and random walks for p2p resource discovery in grids, IEEE Trans. Parallel Distrib. Syst.
[14] S. Sioutas, T. Triantafillou, G. Papaloukopoulos, E. Sakkopoulos, K. Tsichlas, Y. Manolopoulos, Art: sub-logarithmic decentralized range query processing with probabilistic guarantees, IEEE Trans. Parallel Distrib. Syst. 31 (1) (May 2013) 71-109.
[15] H.V. Jagadish, B.C. Ooi, Q.H. Vu, BATON: a balanced tree structure for peer-to-peer networks, in: Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30-September 2, 2005, 2005, pp. 661-672.
[16] M.A. Arefin, M.Y.S. Uddin, I. Gupta, K. Nahrstedt, Q-tree: a multi-attribute based range query solution for tele-immersive framework, in: 29th IEEE International Conference on Distributed Computing Systems, ICDCS 2009, 22-26 June 2009, Montreal, Québec, Canada, 2009, pp. 299-307.
[17] S. Ramabhadran, S. Ratnasamy, J.M. Hellerstein, S. Shenker, Prefix hash tree: an indexing data structure over distributed hash tables, in: Proc. of the 23rd ACM Symposium on Principles of Distributed Computing, 2004.
[18] O. Beaumont, A. Marie Kermarrec, L. Marchal, E. Riviere, E. Lyon, Voronet: a scalable object network based on Voronoi tessellations, in: Proceedings of the 21st International Parallel and Distributed Processing Symposium, IPDPS 2007, Society Press, 2007.
[19] F. Banaei-Kashani, C. Shahabi, SWAM: a family of access methods for similarity-search in peer-to-peer data networks, in: CIKM'04: Proceedings of the Thirteenth ACM International Conference on Information and Knowledge Management, ACM, New York, NY, USA, 2004, pp. 304-313.
[20] M. Albano, M. Baldanzi, R. Baraglia, L. Ricci, Voraque: range queries on Voronoi overlays, in: Proceedings of 13th IEEE Symposium on Computers and Communications, July 2008.
[21] L. Rodrigues, F. Araujo, Geopeer: a location-aware p2p system, in: 3rd IEEE International Conference on Network Computing and Applications, NCA'04, 2004.
[22] E. Kranakis, H. Singh, J. Urrutia, Compass routing on geometric networks, in: Proceedings of 11th Can. Conf. on Computational Geometry, CCCG, August 1999.
[23] M. Mordacchini, L. Ricci, L. Ferrucci, R.B.M. Albano, Hivory: range queries on hierarchical Voronoi overlays, in: Proceedings of 10th IEEE P2P Computing Conference, Jul. 2010.
[24] I. Stoica, R. Morris, D. Liben-Nowell, D.R. Karger, M.F. Kaashoek, F. Dabek, H. Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for Internet applications, IEEE/ACM Trans. Netw. 11 (1) (2003) 17-32.
[25] S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Schenker, A scalable content-addressable network, in: Proc. SIGCOMM'01, ACM Press, New York, NY, USA, 2001, pp. 161-172.
[26] A.I.T. Rowstron, P. Druschel, Pastry: scalable, decentralized object location, and routing for large-scale peer-to-peer systems, in: Middleware 2001: Proc. of the IFIP/ACM Int. Conf. on Distributed Systems Platforms, Heidelberg, Springer-Verlag, London, UK, 2001, pp. 329-350.
[27] A. Andrzejak, Z. Xu, Scalable, efficient range queries for grid information services, in: R.L. Graham, N. Shahmehri (Eds.), Peer-to-Peer Computing, IEEE Computer Society, 2002, pp. 33-40.
[28] R. Baraglia, P. Dazzi, B. Guidi, L. Ricci, Godel: Delaunay overlays in p2p networks via gossip, in: IEEE P2P, 2012, pp. 1-12.
[29] J. Liebeherr, M. Nahas, W. Si, Application-layer multicasting with Delaunay triangulation overlays, IEEE J. Sel. Areas Commun. 20 (8) (2002) 1472-1488.
[30] F. Aurenhammer, Voronoi diagrams-a survey of a fundamental geometric data structure, ACM Comput. Surv. 23 (September 1991).
[31] D. Lee, S. Lam, Efficient and accurate protocols for distributed Delaunay triangulation under churn, in: IEEE International Conference on Network Protocols, ICNP 2008, IEEE, 2008, pp. 124-136.
[32] M. Ohnishi, R. Nishide, S. Ueshima, Incremental construction of Delaunay overlaid network for virtual collaborative space, in: Third International Conference on Creating, Connecting and Collaborating Through Computing, C5 2005, IEEE, 2005, pp. 75-82.
[33] H. Kato, T. Eguchi, M. Ohnishi, S. Ueshima, Autonomous generation of spherical p2p Delaunay network for global Internet applications, in: The Fourth International Conference on Creating, Connecting and Collaborating Through Computing, C5'06, IEEE, 2006, pp. 184-191.
[34] R. Baraglia, P. Dazzi, M. Mordacchini, L. Ricci, A peer-to-peer recommender system for self-emerging user communities based on gossip overlays, J. Comput. Syst. Sci. 79 (2) (2013) 291-308.
[35] K. Hong, D. Lillethun, U. Ramachandran, B. Ottenwälder, B. Koldehofe, Mobile fog: a programming model for large-scale applications on the Internet of things, in: Proceedings of the Second ACM SIGCOMM Workshop on Mobile Cloud Computing, MCC'13, ACM, New York, NY, USA, 2013, pp. 15-20.
[36] H. Samet, Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, 2006.
[37] L. Ferrucci, Un sistema gerarchico basato su voronoi per la risoluzione di query multiattributo, Master Thesis, University of Pisa etd-11102009-151747, December 2009.
[38] M. Jelasity, A. Montresor, G.P. Jesi, S. Voulgaris, The Peersim simulator, http://peersim.sf.net.
[39] B. Chun, D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawrzoniak, M. Bowman, Planetlab: an overlay testbed for broad-coverage services, SIGCOMM Comput. Commun. Rev. 33 (3) (Jul. 2003) 3-12 [Online], available http://doi.acm.org/10.1145/956993.956995.
[40] L. Wang, K. Park, R. Pang, V.S. Pai, L.L. Peterson, Reliability and security in the CoDeeN content distribution network, in: USENIX Annual Technical Conference, General Track, June 2004, pp. 171-184.
[41] K. Park, V.S. Pai, Comon: a mostly-scalable monitoring system for planetlab, SIGOPS Oper. Syst. Rev. 40 (1) (Jan. 2006) 65-74 [Online], available: http://doi.acm.org/10.1145/1113361.1113374.
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:357247,
title = {Multidimensional range queries on hierarchical Voronoi overlays},
author = {Ferrucci L. and Ricci L. and Baraglia R. and Mordacchini M. and Albano M.},
publisher = {Academic Press., New York,, Stati Uniti d'America},
doi = {10.1016/j.jcss.2016.04.008},
journal = {Journal of computer and system sciences (Print)},
volume = {82},
pages = {1161–1179},
year = {2016}
}
0000-0002-8179-8215CNR ExploRA
DOIAlso available from
DOIAlso available from
www.sciencedirect.com
Repositório Científico do Instituto Politécnico do Porto