路网中空间关键字（连续）k近邻查询算法研究

As one of the enabling technologies for location-based services(LBSs), location-based queries (LBQs) have become a hot research topic. However, most of the existing LBQ methods only consider the location information of the query point and data objects, while ignoring the keyword similarity between them. Thus, these methods can not completely satisfy actual applications. Recently, the spatial keyword query, which is a combination of a keyword query and a spatial query, has been proposed by researchers. However, existing research works on spatial keyword query processing are almost limited in Euclidean space, which is a simplification of realistic scenarios. Since the query methods in Euclidean space can not be easily extended to handle queries in road networks, we mainly address the problem of processing spatial keyword queries in road networks. Firstly, by taking into account both the location information and the keyword information of the query point and objects, the road network structure and the data objects in it will be partitioned and organized efficiently, and an efficent road network index structure will be proposed. Secondly, a flexible similarity evaluation model will be presented, thus the users can freely choose the weights of network distance and keyword similarity, respectively. Thirdly, efficient query methods for processing (continuous) top-k spatial keyword queries in road networks will be proposed. Moreover, we will optimize the algorithms proposed, so as to improve the scalabity of the system and the timeliness of query results.

位置相关查询处理(LBQs)作为位置相关服务(LBSs)的支持性技术之一，已经成为一个研究热点问题。然而现有的位置相关查询算法多数仅仅考虑了查询点和待查询对象的位置信息，没有考虑待查询对象与查询的关键字相似程度，不能完全满足实际应用的需要。近年来，研究者提出了将这两种因素相结合的新型查询处理类型，即空间关键字查询。目前，已有的空间关键字查询研究成果大多局限于欧氏空间，属于对现实情况的简化。由于欧氏空间的相关算法不能通过简单的修改而应用到路网中，项目研究路网中空间关键字查询处理策略。综合考虑路网距离与关键字相似度这两个因素，对路网结构、路网上的对象进行合理的划分、组织，并提出适当的索引结构。提出灵活的相似度评价模型，使用户能够根据实际需要来设置路网距离、关键字相似程度这两个因素的权重。设计实现路网中空间关键字(连续)k近邻查询算法。优化所设计的算法，提高系统的可扩展性、查询结果时效性。

近年来，研究者提出了综合考虑查询点与待查询对象的位置信息和其关键字相似程度的空间关键字查询。已有的空间关键字查询研究成果大多局限于欧氏空间，属于对现实情况的简化。由于欧氏空间的相关算法不能通过简单的修改而应用到路网中，本项目重点研究了路网中空间关键字查询处理问题。经过3年的工作，完成了本项目的研究任务，提出了一系列研究成果。.1. 研究了路网中移动对象空间关键字连续top-k查询问题，提出了一种新颖的渐增监控查询方法（CMA）。该方法用一棵组合扩展树CEtree来界定查询的监控范围，通过识别、处理监控范围内、对查询结果有影响的查询点和移动对象的位置更新对相应的CEtree进行修正，以保证查询结果的持续有效性。实验结果表明，我们所提出算法的CPU处理时间明显少于参照的Naive算法。.2.重点研究了路网中的空间关键字Top-k查询连续监控问题。以往论文在讨论类似问题时，都局限于静止的空间关键字对象或者对象在道路上的移动是离散的，这里讨论的对象是可以在路网的各条道路上连续移动的，从而加大了查询处理的难度。为了有效地索引路网中的对象，我们在TPR-tree的基础上加入了对象的关键字信息，提出了一种新颖的、称为 TPRgt-tree的空中索引结构。实验结果表明，我们所提出的算法在时间性能和精度方面比参照的CMA算法都有着更好的表现。.3.首次研究了无线广播环境下路网连续最近邻查询处理问题。对路网结构、路网中的对象进行合理的划分、组织，提出了一种名为NVD-DI的线性分布式索引结构路网索引结构。借助于NVD-DI和所提出的客户端查询处理算法，每一个CNN查询均可在一个广播周期内完成。实验表明，所提出的NVD-DI-M算法的性能显著优于对比的DTM方法。.4 重点研究了无线广播环境下路网空间关键字k近邻查询处理问题，提出一种包含路网加权四叉树、各关键字四叉树和路网距离矩阵的空中索引结构(ESKAI)以方便查询的处理。重点讨论了kNN查询处理问题，提出了高效的查询处理算法。所提出的算法能综合利用路网距离信息和关键字信息高效地消减不存在查询结果对象的路网空间，提高查询处理的效率。ESKAI索引结构可推广至其他类型的查询，比如范围查询、Rank查询。实验表明所提出方法的访问时间和调谐时间分别为参照的IRRDA算法的25.13%和12.31%。