SYMPOSIUM MINISYMPOSIA

MINISYMPOSIUM ABSTRACT

Applications dealing with spatial data manages very large amounts of k-dimensional points. A key research issue in order to provide efficient implementations of these applications is the design of a efficient distributed data structures for searching in a k-dimensional space. The fundamental queries for a data structure for k-d points are: exact match, partial match, range. It is also important that the structure is able to scale up to adapt itself to a growing number of points.

A cost-effective approach to this objective, taking advantage from the striking advance of communication technology, is to set up distributed applications running on a network of workstations. The technological framework we make reference to is the so called network computing: fast communication networks, in the order of 10-100MB/sec, and many powerful and cheap workstation, in the order of 50-100 MIPS. Many organizations have this kind of computing power: large organizations have easily a cumulative amount of main memory in the order of tenths of GB.

The distributed environment we make reference to is constituted by a set of sites (processor or nodes) connected by a network. Every site in the network is either a server, that manages data, or a client, that requests access to data. Each server manages data items belonging to some parts of the data domain. Sites communicate by sending and receiving point-to-point messages. We assume network communication is free of errors. Every server can store a single block (called bucket) of at most b data items, for a fixed number b. The overall data organization scheme we consider is a search tree: servers manage both nodes containing data items (leaf odes) and nodes guiding the search process (internal nodes).

New servers can be added as the volume of data increases to maintain the performance level. The clients are not, in general, up-to-date with the evolution of the structure, in the sense they have some local indexing structure, but do not know, in general, the overall status of the data structure. Different clients may therefore have different and incomplete views of the data structure.

The theoretical study of the characteristics of scalable distributed search trees conducted by Kröll e Widmayer showed that if all the hypothesis used to efficiently manage search structures in the single processor case are carried over to a distributed environment then a lower bound of W(Ön) holds for the height of balanced search trees, where n is the number of servers in the structure.

In the RBST some of these hypothesis, related to the way the search proces is exectued, are relaxed, yielding a cost of O(log² n) messages for search and update operations.

In this paper, we relax some other hypothesis, related to the kind of synchronization between servers and clients of the structure, and show that a distributed search trees can be maintained balanced in a distributed environment so that search and update operations can be executed with O(logn) messages. Hence we present the first balanced distributed search structure to be fully dinamic and order-preserving.

Getting More Information

To obtain more information about the meeting send e-mail to: fscc98@pax.st.usm.edu.

Return to Minisymposia
Return to PAX
Return to USM

USM
inquire@delphi.st.usm.edu
Updated
http://pax.st.usm.edu