ADST: An order preserving scalable distributed data structure with constant access costs. 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.
References in zbMATH (referenced in 3 articles , 1 standard article )
Showing results 1 to 3 of 3.
- Ouksel, Aris M.; Moro, Gianluca: G-Grid: A class of scalable and self-organizing data structures for multi-dimensional querying and content routing in P2P networks (2004)
- Di Pasquale, Adriano; Nardelli, Enrico: A very efficient order preserving scalable distributed data structure (2001)
- Di Pasquale, Adriano; Nardelli, Enrico: ADST: An order preserving scalable distributed data structure with constant access costs (2001)