A New Technique for Verifying the Consistency of Distributed R-Trees

Abstract

The ever-increasing of the large spatial datasets and the widely application of the complex computation have motivated the emergence of distributed algorithms to process spatial operations efficiently. The R-tree index is broadly used by researches as a distributed spatial structure for indexing and retrieval of spatial objects. However, a big challenge has arisen, that is, how to check the consistency of distributed R-Trees.  In the past few years researches have been published on both distributed R-Tree and verification of distributed systems. Though none of them has proposed a technique to check the consistency of distributed R-Trees. This article presents a new approach for verifying the consistency of distributed R-Trees, which is called RConsistency.  It allows collect information about the distributed R-Tree once it has been created.  RConsistency also collects information about the distribute R-Tree and can helps to reduce the overlapping and dead area. It can be used with any index similar to R-Tree, since the RConsistency algorithm uses the nodes organization of the R-Tree to collect consistency information.  The algorithm was used on DistGeo, a platform to process distributed spatial operations.  A graphic tool, named RConsistency Visualizer, was developed to show the output of the RConsistency algorithm.