Research On Continuous Nearest Neighbor Queries Based On R-Tree In Spatial Databases

Spatial databases are being applied widely in many applications such as GIS (Geographic Information System), CAD/CAM and Physic Image etc. The nearest neighor query is one of the most important queries in spatial databases. As an example, someone in a vehicle driving in a highway could search for the nearest gas station.A more complex query, and not less important, is the continous nearest neighor where, in the example of a vehicle in a highway, the driver could ask for the nearest gas stations during a certain path on that highway. The result of this query is a set containing the nearest neighbor and the validity interval on the path.Spatial index technologhy is vital of quering efficiently in spatial databases, realizations of continuous nearest neighbor query depend on spatial index technologhy. The R-tree and its variants are the most popular spatial index technologhy. An R-tree is a height-balanced tree consisted of non-leaf node and leaf node, the minimum out-connected rectangle of real data object is stored in leaf node, the non-leaf node is formed according to the accumulation of its low-level nodes which contains all the out-connected rectangle.This subject analyzes some kinds of current continuous nearest neighor query. It is the most effective that the query algorithm based on R-tree of Y.tao etc. The main idea of this algorithm is to find the split points where there are changes of neighborhood; it only needs performing a single traversal in the R-tree index. However, the primary defect of this algorithm is that disk accesses are not optimal. The thesis mainly optimized the algorighm, proposed of the optimal algorithm, gave the pseudo code of the core algorithm and analyzed the execution procedure combining a specific example. At last the performance of the two algorithms was compared and analyzed through simulation experiment. The result shows that the optimal algorithm reduced the number of disk accesses without increasing CPU cost. So the original algorithm is optimized.