Study On Algorithms For Processing K-closest-pair Queries In Spatial Database

Currently, spatial database has been widely used in geographic information systems (GIS), medical imaging and computer-aided design and manufacturing (CAD /CAM) and other fields. Due to its large amount of spatial data and highly complex spatial objects and spatial queries, the study of spatial queries become focus of spatial database research.K closest pairs query can address the problem of finding the K closest pairs between two spatial datasets. The K-CPQ is a combination of join and nearest neighbor queries. Like a join query, all pairs of objects are candidates for the result. Like a nearest neighbor query, proximity metrics form the basis for pruning heuristics and the final ordering.K-CPQ are very useful in many applications that use spatial data for decision making and other demanding data handling operations.In this paper,we will study K closest pairs query in spaitial database with constraints to slove spatial data search and matching in space constraints.Firstly, this paper analyzes the characteristics of spatial data and spatial index structure, basic demand of space access mechanism, analyzes common space index technology,and mainly researches R-tree index structure,analysis the structure of the S-57 data;Secondly, fororganization and management of waterborne-spatial database,and based on the logical structure of waterborne-spatial database, and establish R-tree spatial index structure;Again, for purning strategy and updating strategy in the main tree of the K closest pairs query problem,the the K closest pairs query algorithm basing on the sorted distances recursive algorithm,the plane-sweep recursive algorithm and the plane-sweep iterative algorithm is given.These algorithms can dynamically adjust the distance threshold and prune the search path to avoid unnecessary computation;Finally, evaluate performance of three algorithms with theoretical analysis.