SYMPOSIUM MINISYMPOSIA

MINISYMPOSIUM ABSTRACT

Data structures in the family of R-trees are among the most promising for 2-dimensional spatial data management and the ones most of researchers in the field are focusing on. Indeed, they are also implemented in commercial DBMSs.

In fact, an R-tree can be used to efficiently manage segments and rectangles in the 2-dimensional space, but also, using the Minimum Bounding Rectangle (MBR) technique, arbitrary curves and regions.

A recently developed approach to obtain higher performances from computing systems is based on the use of a network of workstations, where an application is running using the main memory and the high speed of the network to obtain an overall throughput that cannot be reached with a single machine.

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.

Depending on the overall data organization scheme it is considered one obtains the distributed counterpart of search structure known for single machine environments. Examples already known in the literature are LH* for linear hashing, RP* for B-trees, DRT for binary search trees, and the lazy k-d-tree.

In this paper we focus on the family of R-trees, with the objective of studying how it can be extended to such a distributed framework. More specifically, the overall data organization scheme we consider in this paper is an R+ tree: due to its policy of never having overlapping regions in its inner nodes, it appears to be the best choice for implementing a distributed R-tree.

In fact, if more than one node is overlapping with a point to be inserted, a distributed coordination protocol is required to decide which server has to answer and to let the client knows the outcome of such a decision. But, in the interest of keeping a high level of performance, it is desirable that such a decision is taken without interaction among servers.

Therefore an algorithmic problem comes out, namely the one of deciding among of the rectangles that at any given moment partially cover the plane, which one has to extend itself to take the new point so that the constraint of not overlapping regions is satisfied and it is avoided the risk it will not be satisfied in the future.

In this paper we formulate this problem as an intersection graph problem, and give, for some special cases, a characterization for which we produce a polynomial algorithm. We also conjecture the problem is NP-complete in the general case.

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