ADST: An order preserving scalable distributed data structure with constant access costs.(English)Zbl 1052.68592

Pacholski, Leszek (ed.) et al., SOFSEM 2001: Theory and practice of informatics. 28th conference on current trends in theory and practice of informatics, Piešt’any, Slovak Republic, November 24 – December 1, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42912-3). Lect. Notes Comput. Sci. 2234, 211-222 (2001).
Summary: 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.
For the entire collection see [Zbl 0983.00059].

MSC:

 68P05 Data structures