A very efficient order preserving scalable distributed data structure. (English) Zbl 0988.68661

Di Pasquale, Adriano; Nardelli, Enrico

Mayr, Heinrich C. (ed.) et al., Database and expert systems applications. 12th international conference, DEXA 2001, Munich, Germany, September 3-5, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2113, 186-199 (2001).

Summary: SDDSs (Scalable Distributed Data Structures) 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 present and discuss performances of ADST, a new order preserving SDDS with a worst-case constant cost for exact-search queries, a worst-case logarithmic cost for update queries, and an optimal worst-case cost for range search queries 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. Finally, our scheme can be easily generalized to manage k-dimensional points, while maintaining the same costs of the 1-dimensional case.
We report experimental comparisons between ADST and its direct competitors (i.e., LH*, DRT, and RP*) where it is shown that ADST behaves clearly better. Furthermore we show how our basic technique can be combined with recent proposals for ensuring high-availability to an SDDS. Therefore our solution is very attractive for network servers requiring both a fast response time and a high reliability.
For the entire collection see [Zbl 0970.68701].

MSC:

68U99	Computing methodologies and applications
68P15	Database theory

Keywords:

Scalable distributed data structure; message passing environment; multi-dimensional search

Software:

ADST