{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T16:10:14Z","timestamp":1746115814645,"version":"3.40.4"},"reference-count":42,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2013,11,11]],"date-time":"2013-11-11T00:00:00Z","timestamp":1384128000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2016,4,25]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>An examination of the multidimensional range query in existing peer\u2010to\u2010peer (P2P) overlay networks indicates that multidimensional range queries are sensitive to underlying topologies; this is because partitioning and mapping of multidimensional data space are two interconnected parts of a process that must be carried out cooperatively. The first section focuses on how to preserve data localities, whereas the second section concerns how to accommodate and maintain data localities at the P2P overlay layer. There are many studies that have been conducted on the first section since 1966, and those works that are well accepted are mostly based on recursive decomposition, which forms a tree structure in nature. However, less effort has been made to provide comparable support from the P2P overlay layer. In our previous work, we proposed the Hierarchically Distributed Tree (HD Tree) in order to better support multidimensional range queries in the P2P overlay network. This paper further explores error\u2010resilient routing and load balancing strategies that can be employed in the HD Tree. We also provide a complete set of experimental results for all routing operations: Join and Leave of nodes, range queries at different levels of selectivity, and the dynamic load balancing scheme. Comparisons are made by conducting simulations under both the ideal and the error\u2010prone routing environment and within various ary HD Trees. The experimental results show that load balancing in the HD Tree can be adjusted dynamically and globally, and it is actually a trade\u2010off between distributing the basic load and the involvement of nodes in range querying. The experimental results also indicate that a maximum of 10 percent of routing nodes\u2019 failures do not have significant effects on the performance of range queries. However, a lower ary HD Tree appears to have better routing performance, whereas a higher ary HD Tree achieves a higher fault\u2010tolerant capacity. Nevertheless, the performance of range queries in a higher ary HD Tree can be further optimized if all possible routing options can be fully explored in the error\u2010prone routing environment. Copyright \u00a9 2013 John Wiley &amp; Sons, Ltd.<\/jats:p>","DOI":"10.1002\/cpe.3160","type":"journal-article","created":{"date-parts":[[2013,11,11]],"date-time":"2013-11-11T12:40:49Z","timestamp":1384173649000},"page":"1848-1869","source":"Crossref","is-referenced-by-count":0,"title":["Supporting multidimensional range queries in Hierarchically Distributed Tree"],"prefix":"10.1002","volume":"28","author":[{"given":"Yunfeng","family":"Gu","sequence":"first","affiliation":[{"name":"PARADISE Research Laboratory School of Information Technology and Engineering University of Ottawa Ottawa Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Azzedine","family":"Boukerche","sequence":"additional","affiliation":[{"name":"PARADISE Research Laboratory School of Information Technology and Engineering University of Ottawa Ottawa Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robson E.","family":"De Grande","sequence":"additional","affiliation":[{"name":"PARADISE Research Laboratory School of Information Technology and Engineering University of Ottawa Ottawa Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2013,11,11]]},"reference":[{"key":"e_1_2_10_2_1","doi-asserted-by":"crossref","unstructured":"KargerD LehmanE LeightonT LevineM LewinD PanigrahyR.Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web.In ACM Symposium on Theory of Computing El Paso TX USA May 04 \u2010 06 1997;654\u2013663.","DOI":"10.1145\/258533.258660"},{"key":"e_1_2_10_3_1","doi-asserted-by":"crossref","unstructured":"DabekF ZhaoB DruschelP KubiatowiczJ StoicaI.Towards a common API for structured peer\u2010to\u2010peer overlays.Peer\u2010to\u2010Peer Systems II (IPTPS 2003) Berkeley CA USA February2003;33\u201344.","DOI":"10.1007\/978-3-540-45172-3_3"},{"key":"e_1_2_10_4_1","doi-asserted-by":"crossref","unstructured":"KarpB RatnasamyS RheaS ShenkeS.Spurring adoption of DHTs with OpenHash a public DHT service.Peer\u2010to\u2010Peer Systems III (IPTPS 2004) Berkeley CA USA February2004;195\u2013205.","DOI":"10.1007\/978-3-540-30183-7_19"},{"key":"e_1_2_10_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2005.1610546"},{"issue":"4","key":"e_1_2_10_6_1","first-page":"161","article-title":"A scalable content addressable network","volume":"31","author":"Ratnasamy S","year":"2001","journal-title":"Proceeding ACM SIGCOMM, 2001"},{"key":"e_1_2_10_7_1","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1109\/TNET.2002.808407","article-title":"Chord: a scalable peer\u2010to\u2010peer lookup protocol for Internet applications","volume":"11","author":"Morris R","year":"2003","journal-title":"IEEE\/ACM Transactions"},{"key":"e_1_2_10_8_1","doi-asserted-by":"crossref","unstructured":"RowstronA DruschelP.Pastry: scalable distributed object location and routing for large\u2010scale peer\u2010to\u2010peer systems.In IFIP\/ACM International Conference on Distributed Systems Platforms (Middleware) (November 2001) Heidelberg Germany Nov 2001;329\u2013350.","DOI":"10.1007\/3-540-45518-3_18"},{"key":"e_1_2_10_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2003.818784"},{"key":"e_1_2_10_10_1","doi-asserted-by":"crossref","unstructured":"MaymounkovP MazieresD Kademlia: a peer\u2010to\u2010peer information system based on the XOR metric.Proceedings IPTPS MA USA February2002;53\u201365.","DOI":"10.1007\/3-540-45748-8_5"},{"key":"e_1_2_10_11_1","doi-asserted-by":"crossref","unstructured":"MalkhiD NaorM RatajczakD.Viceroy: a scalable and dynamic emulation of the butterfly.Proceedings ACM PODC 2002 CA USA July2002;183\u201392.","DOI":"10.1145\/571825.571857"},{"key":"e_1_2_10_12_1","unstructured":"(Available from:http:\/\/www.gnutellaforums.com.) Gnutella development forum. [Last accessed in January 2010]."},{"key":"e_1_2_10_13_1","unstructured":"(Available from:http:\/\/rfc\u2010gnutella.sourceforge.net\/Proposals\/Ultrapeer\/Ultrapeer.htm.) Gnutella ultrapeers. [Last accessed in January 2010]."},{"key":"e_1_2_10_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44702-4_4"},{"key":"e_1_2_10_15_1","unstructured":"(Available from:http:\/\/developer.berlios.de\/projects\/gift\u2010fasttrack.) Fasttrack P2P Technology. [Last accessed in January 2010]."},{"key":"e_1_2_10_16_1","unstructured":"(Available from:http:\/\/en.wikipedia.org\/wiki\/Kazaa.) Kazaa from Wiki. [Last accessed in January 2010]."},{"key":"e_1_2_10_17_1","unstructured":"(Available from:http:\/\/www.kazaa.com.) Kazaa Media Desktop. [Last accessed in January 2010]."},{"key":"e_1_2_10_18_1","unstructured":"(Available from:http:\/\/en.wikipedia.org\/wiki\/Fasttrack.) Fasttrack from Wiki. [Last accessed in January 2010]."},{"key":"e_1_2_10_19_1","unstructured":"(Available from:http:\/\/www.bittorrent.com.) Official BitTorrent website. [Last accessed in January 2010]."},{"key":"e_1_2_10_20_1","unstructured":"(Available from:http:\/\/www.bittorrent.org.) Official BitTorrent specification. [Last accessed in January 2010]."},{"key":"e_1_2_10_21_1","unstructured":"(Available from:http:\/\/www.overnet.org.) the overnet file\u2010sharing Network. [Last accessed in January 2010]."},{"key":"e_1_2_10_22_1","unstructured":"(Available from:http:\/\/en.wikipedia.org\/wiki\/Overnet.) the overnet from Wiki. [Last accessed in January 2010]."},{"key":"e_1_2_10_23_1","unstructured":"(Available from:http:\/\/www.edonkey2000.org.) official eDonkey200 website. [Last accessed in January 2010]."},{"key":"e_1_2_10_24_1","unstructured":"(Available from:http:\/\/en.wikipedia.org\/wiki\/EDonkey2000.) eDonkey2000 from Wiki. [Last accessed in January 2010]."},{"key":"e_1_2_10_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"e_1_2_10_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/356924.356930"},{"key":"e_1_2_10_27_1","unstructured":"(Available from:http:\/\/www.itl.nist.gov\/div897\/sqg\/dads\/HTML\/kdtree.html.)[Last accessed in January 2010]."},{"key":"e_1_2_10_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_10_29_1","unstructured":"MortonGM.A computer oriented geodetic data base and a new technique in file sequencing.Technical Report IBM Ltd Ottawa Canada 1966."},{"key":"e_1_2_10_30_1","doi-asserted-by":"crossref","unstructured":"OrensteinJA MerrettTH.A class of data structures for associative searching.In PODS \u201984: Proceedings of the 3rd ACM SIGACT\u2010SIGMOD Symposium on Principles of Database Systems April 1984 Waterloo Ontario Canada 1984;181\u2013190.","DOI":"10.1145\/588011.588037"},{"key":"e_1_2_10_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/93605.98742"},{"key":"e_1_2_10_32_1","unstructured":"HarveyN JonesMB SaroiuS TheimerM WolmanA.SkipNet: a scalable overlay network with practical locality properties.In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems USITS\u201903 Seatle WA US March2003;9\u201323."},{"key":"e_1_2_10_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/945721.945729"},{"key":"e_1_2_10_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1030194.1015507"},{"key":"e_1_2_10_35_1","doi-asserted-by":"crossref","unstructured":"CaiM FrankM ChenJ SzekelyP.MAAN: a multiattribute addressable network for grid information services.In Proceedings of the 4th International Workshop on Grid Computing Washington DC USA November2003;184\u2013191.","DOI":"10.1109\/GRID.2003.1261714"},{"key":"e_1_2_10_36_1","doi-asserted-by":"crossref","unstructured":"GanesanP YangB Garcia\u2010MolinaH.One torus to rule them all: multi\u2010dimensional queries in P2P systems.In WebDB \u201904: Proceedings of the 7th International Workshop on the Web and Databases Maison de la Chimie Paris France 2004;19\u201324.","DOI":"10.1145\/1017074.1017081"},{"key":"e_1_2_10_37_1","unstructured":"ShuY OoiBC TanK ZhouA.Supporting multi\u2010dimensional range queries in peer\u2010to\u2010peer systems.In 5th IEEE International Conference on Peer\u2010to\u2010Peer Computing 2005 P2P2005;173\u2013180."},{"volume-title":"SkipIndex: Towards a Scalable Peer\u2010to\u2010peer Index Service for High Dimensional Data","year":"2004","author":"Zhang C","key":"e_1_2_10_38_1"},{"key":"e_1_2_10_39_1","doi-asserted-by":"crossref","unstructured":"SchmidtC ParasharM.Flexible information discovery in decentralized distributed systems.Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing (HPDC\u201903) Seattle Washington USA 2003;226\u2013235.","DOI":"10.1109\/HPDC.2003.1210032"},{"key":"e_1_2_10_40_1","doi-asserted-by":"crossref","unstructured":"Sch\u00fcttT SchintkeF ReinefeldA.A structured overlay for multi\u2010dimensional range queries.Euro\u2010Par 2007 Parallel Processing Rennes France 2007;503\u2013513.","DOI":"10.1007\/978-3-540-74466-5_54"},{"key":"e_1_2_10_41_1","unstructured":"AspnesJ ShahG.Skip graphs.In Proceedings SODA January 2003 Baltimore Maryland USA 2003;384\u2013393."},{"key":"e_1_2_10_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2011.04.003"},{"key":"e_1_2_10_43_1","unstructured":"GuY.Hierarchically distributed tree.Ph.D Thesis University of Ottawa Canada. (In preparation)."}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.3160","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.3160","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T20:09:40Z","timestamp":1746043780000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.3160"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,11]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,4,25]]}},"alternative-id":["10.1002\/cpe.3160"],"URL":"https:\/\/doi.org\/10.1002\/cpe.3160","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"type":"print","value":"1532-0626"},{"type":"electronic","value":"1532-0634"}],"subject":[],"published":{"date-parts":[[2013,11,11]]}}}