面向大规模基于位置服务的高效索引与空间查询处理技术

Location Based Services (LBS) have gained a wide range of applications, including life, transportation and integrated urban management. These applications enrich the way people obtain information and make it easier for them to locate, search, browse and share information. Efficient indexing and spatial query processing techniques are needed to handle large-scale LBS querying that has high concurrency, continuity and diversity features. With large-scale LBS querying as application background, this project investigates efficient indexing and query processing techniques. We design a novel spatial index based on Voronoi Diagram and virtual grid to support efficient spatial querying and large-scale LBS applications. Upon this spatial index, we study efficient techniques for processing both discontinuous and continuous spatial neighborhood queries. We also investigate the accuracy, efficiency and scalability of these techniques. Moreover, we research efficient techniques for processing both discontinuous and continuous spatial keyword queries. Finally, with accuracy, efficiency and scalability as the evaluation criteria, we will validate the performance of the proposed index and query processing techniques on real-world datasets and in real applications. The future results of this project have significant theoretical and reference values in developing and promoting more new LBS applications.

基于位置的服务(LBS)在生活、交通、城市综合管理等诸多领域都获得了广泛应用，丰富了人们获取信息的途径，方便人们定位、查找、浏览和分享信息。大规模LBS查询应用的高并发性、连续性和多样性，迫切需要支撑这种应用的高效索引与空间查询处理技术。本项目以大规模LBS查询为应用背景，研究高效索引与查询处理技术：利用Voronoi Diagram和虚拟网格技术，构造适应大规模LBS查询应用的空间索引结构，为空间查询处理提供基础和支撑；基于建立的索引结构，设计空间近邻和连续空间近邻查询处理等算法，保证查询响应的准确性、快速性和可扩展性；研究空间关键词查询和连续空间关键词查询处理机制，提高LBS应用处理实时空间关键词查询的效率。通过真实数据集实验分析和真实环境应用，验证索引与查询处理算法的正确性、高效性和可扩展性。研究结果对促进基于位置服务在更多新型应用领域的发展和普及具有重要的理论意义和参考价值。

本项目面向大规模基于位置服务(LBS)的应用场景，研究支撑这种大规模LBS应用所需的空间索引和查询处理技术。主要完成的工作有：设计基于 Voronoi Diagram与虚拟网格相结合的GridVoronoi索引，建立虚拟网格单元与Voronoi Cell的之间的相交/包含关系，达到利用虚拟网格单元快速定位查询点所在的Voronoi Cell，然后利用Voronoi Diagram的特性快速定位查询点的空间近邻的目标。基于该索引结构，设计了高效的空间最近邻查询、K近邻查询相关的算法。在受限空间网络上，设计GridRoad算法，利用虚拟网格和子道路的包含关系，建立虚拟网格单元和道路上的兴趣点(POI)的映射关系，解决了已有方法无法快速定位查询点所在的道路的问题，大大提升了公路网上空间最近邻查询处理的效率，服务于公路网上的大规模LBS应用。