Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets

Simple item page
dc.creatorArge, Lars
dc.creatorEppstein, David
dc.creatorGoodrich, Michael T.
dc.date2005-07-19
dc.date.accessioned2026-07-07T03:23:14Z
dc.date.available2026-07-07T03:23:14Z
dc.descriptionWe 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.
dc.description8 pages, 4 figures. Appearing at 24th ACM SIGACT-SIGOPS Symp. Principles of Distributed Computing (PODC 2005), Las Vegas
dc.identifierhttps://arxiv.org/abs/cs/0507050
dc.identifierhttp://arxiv.org/abs/cs/0507050
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32866
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectComputational Geometry
dc.subjectData Structures and Algorithms
dc.subjectF.2.2
dc.titleSkip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets
dc.typetext

Files

Collections

arXiv