Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2005-07-19
Computer Science
Distributed, Parallel, and Cluster Computing
8 pages, 4 figures. Appearing at 24th ACM SIGACT-SIGOPS Symp. Principles of Distributed Computing (PODC 2005), Las Vegas
Scientific paper
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.
Arge Lars
Eppstein David
Goodrich Michael T.
No associations
LandOfFree
Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-491177