|
28th Annual Conference on Current
Trends in
Theory and Practice of Informatics
|
|
November 24 - December 1, 2001
|
|
ADST: An Order Preserving Scalable Distributed Data Structure with Constant Access Costs
by Adriano Di Pasquale and Enrico Nardelli
Abstract:
Scalable Distributed Data Structures (SDDS) are access methods
specifically designed to satisfy the high performance requirements of
a distributed computing environment made up by a collection of
computers connected through a high speed network. In this paper we
propose an order preserving SDDS with a worst-case constant cost for
exact-search queries and a worst-case logarithmic cost for update
queries. Since our technique preserves the ordering between keys, it
is also able to answer to range search queries with an optimal
worst-case cost of O(k) messages, where k is the number of servers
covering the query range. Moreover, our structure has an amortized
almost constant cost for any single-key query.
Hence, our proposal is the first solution combining the advantages
of the constant worst-case access cost featured by hashing techniques
(e.g. LH*) and of the optimal worst-case cost for range queries
featured by order preserving techniques (e.g., RP* and DRT).
Furthermore, recent proposals for ensuring high-availability to an
SDDS can be easily combined with our basic technique. Therefore our
solution is a theoretical achievement potentially attractive for
network servers requiring both a fast response time and a high
reliability.
Finally, our scheme can be easily generalized to manage k-dimensional
points, while maintaining the same costs of the 1-dimensional case.