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

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

2005-07-19

arxiv.org/abs/cs/0507050v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-491177