Aarhus University Seal / Aarhus Universitets segl

Lars Arge

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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Lars Arge
  • David Eppstein, University of California, Irvine, United States
  • Michael T. Goodrich, University of California, Irvine, United States
  • Department of Computer Science
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.
Original languageEnglish
Title of host publicationProceedings of 24th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
EditorsMarcos Aguilera, James Aspners
Number of pages7
PublisherAssociation for Computing Machinery
Publication year2005
Pages69-76
ISBN (print)1-59593-994-2
DOIs
Publication statusPublished - 2005
EventACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. PODS'05 - Las Vegas, United States
Duration: 17 Jul 200520 Jul 2005
Conference number: 24

Conference

ConferenceACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. PODS'05
Nummer24
LandUnited States
ByLas Vegas
Periode17/07/200520/07/2005

    Research areas

  • distributed data structures, octrees, peer-to-peer networks, quadtrees, skip lists, trapezoidal maps, ties

See relations at Aarhus University Citationformats

ID: 10650497