Font Size: a A A

The Research On Nearest Neighbors Query Technologies In Spatial Network Databases

Posted on:2007-03-19Degree:MasterType:Thesis
Country:ChinaCandidate:S J HouFull Text:PDF
GTID:2178360212995419Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Nearest neighbor (NN) query technology is an important topic in the field of spatial databases. A k-NN query computes the k data objects that lie closest to a given query point. Due to the wide availability of positioning devices and the rise of location-based services, recently the research focus has shifted to static k-NN query in spatial network databases (SNDB) and continuous k-NN (CkNN) monitoring over mobile data.Firstly, this paper introduces the existing indexing technologies of spatial data; the related works of k-NN query and monitoring are also given.Secondly, this paper proposes a storage schema with two layers of index structures; the storage of network and points of interest data sets is divided. Its components are discussed; the expansibility of storage schema is analyzed. Again, incremental k-NN query algorithm (IkNNQA) is proposed, it can output the query results incrementally. Further, for the sake of query speed, this paper proposes a precomputation-based k-NN query algorithm (PkNNQA). They resolve the problem of static k-NN query in SNDB.Then, the problem of dynamic k-NN monitoring in SNDB is researched thoroughly; incremental k-NN monitoring algorithm (IkNNMA) and group k-NN monitoring (GkNNMA) algorithm are proposed. IkNNMA stores the shortest paths (from q) to the network nodes encountered during the NN search in the form of an expansion tree. It only updates from objects and edges falling in the expansion tree can alter the NN set of q; irrelevant updates are simply ignored. On the other hand, when the updates affect the result of q or when q moves to a new location, IkNNMA determines the part of the expansion tree that remains valid, and re-uses it to accelerate the computation of the new NNs of q. GkNNMA follows the shared execution paradigm to reduce theprocessing time. In particular, it groups together the queries that fall in the path between two consecutive intersections in the network, and produces their results by monitoring the NN sets of these intersections. It benefits the reduction of the problem from monitoring moving queries to monitoring static network nodes.Finally, based on these researches, these proposed algorithms are experimentally verified. Experiment results are given and analyzed.
Keywords/Search Tags:Location-Based Services, Spatial Databases, Index Structure, Nearest Neighbors, R-Tree
PDF Full Text Request
Related items