Font Size: a A A

Research On Continuous Visible Nearest Neighbor Query

Posted on:2015-02-15Degree:MasterType:Thesis
Country:ChinaCandidate:N SongFull Text:PDF
GTID:2268330425489914Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
Continuous visible nearest neighbor query is one of the most important query inthe space database queries techniques. It is widely used in many fields, such as thegeographical information system (GIS), computer aided design and manufacturing(CAD/CAM), intelligent identification system, and multimedia applications, etc. Atthe same time, with the rapid development of science and technology, therequirerments to the continuous visible nearest neighbor query efficiency in human’sproduction and daily life go higher and higher. For example, the visibility ofobstacles, and continuous path have been put forward higher requirements. Atpresent, the pruning strategy of continuous visible nearest neighbor query is limited,but the search scope is expanding constantly, so high efficiency of search oncontinuous nearest neighbor is also much more important.Beginning with studying PR-trees, which is the most commonly used inspatial index technology, the search algorithm, node insertion algorithm and nodedeletion algorithm are discussed on PR-trees. And the corresponding pseudo codesare given. And by using the related properties of PR-trees, different algorithmprocesses of PR-trees are optimized. It makes searching much more efficient andmore rapidly.The study of this thesis is related to two factors of the nearest neighbor queries:visibility and continuity. It is different from the traditional R-tree searching. Basedon practice, it combines them together and brings forward continuous visible nearestneighbor query(CVNN). Updated the pruning strategy and greatly improved theefficiency of query. The improved algorithm of CVNN, which is used in the PR tree,makes it more efficient in searching on continuous visible neighbor query and makesit easier to apply to different data structures.On account of different demands in real life, extending the query algorithm andpruning strategy to k nearest neighbor query, continuous visible nearest neighborquery and constrained nearest neighbor query. In this way it is to make them adapt to different requirements and environments. The proposed method has a good queryefficiency and scalability. The pseudo code corresponding and extension of theCVNN algorithm were given, which has a certain reference for the generalization ofCVNN algorithm.
Keywords/Search Tags:spatial database, PR-tree, visible, obstructed space
PDF Full Text Request
Related items