【作者】 侯士江；

【导师】 刘国华；

【作者基本信息】 燕山大学 ， 计算机应用技术， 2006， 硕士

【摘要】 最近邻(NN)查询技术是空间数据库领域中一个重要的研究课题。k-NN查询计算距离一个给定的查询点最近的k个对象。由于定位装置的广泛应用和定位服务的增加,对空间网络数据库中静态k-NN查询、移动数据的连续k-NN监视技术的研究已经成为空间数据库领域的热点课题。本文首先介绍了现有的空间数据索引技术,对k-NN查询及监视技术的研究现状进行了分析。其次,提出了一个空间网络数据两层存储模式,将网络与兴趣数据集分开存储,并讨论了其各个组件,对其易于扩展性进行了分析。再次,提出了增量k-NN查询算法(IkNNQA),实现了查询结果的真正增量输出。更进一步,为了提高查询速度,提出了基于“预计算”的k-NN查询算法(PkNNQA)。它们共同解决了空间网络数据库中静态的k-NN查询问题。然后,对空间网络数据库中动态的k-NN监视问题进行了深入研究,提出了增量监视算法(IkNNMA)和群组监视算法(GkNNMA)。IkNNMA以扩展树的形式存储在NN搜索期间遇到的网络节点的最短路径,只更新使查询q的NN集发生改变的落在扩展树之内的对象和边的更新,不相关的更新被忽略;另一方面,当更新影响到q的结果或者当q移动到一个新的位置时,IkNNMA保持扩展树的有效部分并加以利用来加速q的新的NNs的计算。而GkNNMA采用共享策略减少处理时间,它将落在网络两个连续的交叉点间的路径上的查询聚集起来,通过监视这些交叉点的NN集来生成结果,从而将监视移动查询转化为监视静态的网络节点,精简了问题。最后,基于上述研究成果,对提出的算法进行了实验验证,给出了实验结果并对其进行了分析。更多还原

【Abstract】 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.更多还原