Skip-webs: efficient distributed data structures for multi-dimensional data sets

ABSTRACT

We present a framework for designing efficient distributed data structures for multi-dimensional data. Our structures, which we call skip-webs, extend and improve previous randomized distributed data structures, including skipnets and skip graphs. Our framework applies to a general class of data querying scenarios, which include linear (one-dimensional) data, such as sorted sets, as well as multi-dimensional data, such as d-dimensional octrees and digital tries of character strings defined over a fixed alphabet.We show how to perform a query over such a set of n items spread among n hosts using O(log n/log log n) messages for one-dimensional data, or O(log n) messages for fixed-dimensional data, while using only O(log n) space per host. We also show how to make such structures dynamic so as to allow for insertions and deletions in O(log n) messages for quadtrees, octrees, and digital tries, and O(log n/log log n) messages for one-dimensional data. Finally, we show how to apply a blocking strategy to skip-webs to further improve message complexity for one-dimensional data when hosts can store more data.

REFERENCES

• 1: Aris Anagnostopoulos , Michael T. Goodrich , Roberto Tamassia, Persistent Authenticated Dictionaries and Their Applications, Proceedings of the 4th International Conference on Information Security, p.379-393, October 01-03, 2001
• 2: James Aspnes , Jonathan Kirsch , Arvind Krishnamurthy, Load balancing and locality in range-queriable data structures, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011785]
• 3: James Aspnes , Gauri Shah, Skip graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 4: Baruch Awerbuch , Christian Scheideler, Peer-to-peer systems for prefix search, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.123-132, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872053]
• 5: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 6: David Eppstein , Michael T. Goodrich , Jonathan Z. Sun, The skip quadtree: a simple dynamic data structure for multidimensional data, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064138]
• 7: Prasanna Ganesan , Gurmeet Singh Manku, Optimal routing in Chord, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 8: M. T. Goodrich, R. Tamassia, N. Triandopoulos, and R. Cohen. Authenticated data structures for graph and geometric searching. In Proc. RSA Conference 'Cryptographers' Track, pages 295--313. Springer, LNCS 2612, 2003.
• 9: Nicholas J. A. Harvey , J. Ian Munro, Brief announcement: deterministic skipnet, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.152-152, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872057]
• 10: N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman. SkipNet: A scalable overlay network with practical locality properties. In USENIX Symp. on Internet Technologies and Systems, Lecture Notes in Computer Science, 2003.
• 11: F. Kaashoek and D. R. Karger. Koorde: A simple degree-optimal distributed hash table. In 2nd Int. Workshop on Peer-to-Peer Systems, 2003.
• 12: G. S. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed hashing in a small world. In 4th USENIX Symp. on Internet Technologies and Systems, 2003.
• 13: Gurmeet Singh Manku , Moni Naor , Udi Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007368]
• 14: M. Naor and U. Wieder. Know thy neighbor's neighbor: Better routing in skip-graphs and small worlds. In 3rd Int. Workshop on Peer-to-Peer Systems, 2004.
• 15: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 16: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 17: Antony I. T. Rowstron , Anne-Marie Kermarrec , Miguel Castro , Peter Druschel, SCRIBE: The Design of a Large-Scale Event Notification Infrastructure, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.30-43, November 07-09, 2001
• 18: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 19: Yinglian Xie , David O'Hallaron , Michael K. Reiter, A Secure Distributed Search System, Proceedings of the 11 th IEEE International Symposium on High Performance Distributed Computing HPDC-11 20002 (HPDC'02), p.321, July 24-26, 2002
• 20: Kevin C. Zatloukal , Nicholas J. A. Harvey, Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 21: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

General Terms:
Algorithms, Design

Keywords:
distributed data structures, octrees, peer-to-peer networks, quadtrees, skip lists, trapezoidal maps, tries