路网下的连续聚合k最近邻查询及变体处理研究

Query is a fundamental problem in computer science, and exists in almost all computer applications; especially in the era of big data, efficient query processing and optimization technology is particularly important. Most existing aggregate k nearest neighbor queries focus on static/moving objects in the Euclidean space, and utilize geometric characteristics to prune the search space. However, these geometric properties do not apply to the road network, and in many practical applications (e.g., intelligent transportation, etc.), the query processing for moving objects in the road network is more realistic. This project aims at studying the continuous aggregate k near neighbor query and its variants in road networks, based on the existing research on aggregate k nearest neighbor search and its variants as well as moving objects queries in road networks. It considers the properties of the road network (e.g., the complex distance computation under the road network, real time, etc.), and aims to minimize the update and communication costs. The project mainly investigates a suite of query processing problems, including continuous aggregate k nearest neighbor query, continuous aggregate k nearest neighbor monitoring, continuous flexible aggregate k nearest neighbor retrieval, and continuous aggregate k farthest neighbor search, in the context of road networks; designs, implements, and evaluates every query processing algorithm, and develops its corresponding display platform/demo; and strives to achieve a breakthrough in relevant theories and technologies in order to lay a solid foundation for future practical applications.

查询是计算机科学的基本问题，存在于目前几乎所有的计算机应用领域；特别在大数据时代，高效的查询处理与优化技术显得尤为重要。现有的聚合k最近邻查询及变体主要针对欧氏空间下的静态/移动对象，并利用几何特性修剪查找空间；但这些几何特性不适用于路网环境，且在许多实际应用（如智能交通等）中，路网下的移动对象查询处理更具有现实意义。本项目拟在现有的聚合k最近邻查询及变体处理和路网下的移动对象查询处理的研究基础上，结合路网的特性（如路网距离计算复杂、实时性等），以最小化更新代价与通讯代价为优化目标，展开一系列能满足实际应用需求的路网下连续聚合k最近邻查询及变体处理研究，重点研究路网下的连续聚合k最近邻查询、连续聚合k最近邻监控、连续灵活聚合k最近邻查询、以及连续聚合k最远邻查询；设计、实现和评价各自查询处理算法，并开发相应的展示平台；力争在相关理论与方法上取得突破，为今后的实际应用奠定坚实基础。

在大数据时代，“数据在，找不到”现象日益严重，因而如何有效地查询大数据成为了一个巨大的挑战。移动计算、无线通信以及定位技术的快速发展使得跟踪并记录移动对象的位置成为可能。大量的应用领域（如地理信息系统、智能导航、交通管制、天气预报、军事、移动电子商务等）均迫切需要有效地查询这些移动数据对象。本项目围绕路网对象索引与查询技术展开了深入地探索，重点研究了路网对象索引技术（如路网下时间感知空间关键字索引、时间感知布尔空间关键字索引、概率数据索引等）、路网对象查询技术（如路网下聚合空间关键字查询、路网下反Top-k地理社交关键字查询处理技术、路网下连续聚合k最近邻监控处理等）和路网对象查询结果可用性分析（如路网下基于范围的Skyline查询Why-not问题、概率反Skyline查询上的Causality与Responsibility问题研究等），并搭建了反Top-k查询结果可用性分析平台，完全达到了预期的研究目标。共培养/毕业博士生5名，硕士生6名，本科生5名，并获国家奖学金9人次等奖励；在国内外顶级/重要学术期刊或会议TKDE、TOIS、VLDBJ、TFS、SIGMOD、VLDB、ICDE等发表/录用论文30篇，其中SCI检索21篇，EI检索30篇，CCF A类期刊或会议论文21篇，SCI他引70余次，Google Scholar他引140余次；（待）出版相关学术专著1部；实审相关专利5项；部分成果受到了国内外知名专家（如IEEE Fellow、澳大利亚昆士兰大学周晓方教授，IEEE/RSNZ Fellow、新西兰奥克兰理工大学Nikola Kasabov教授，ACM/IEEE Fellow、澳大利亚斯威本（Swinburne）科技大学Timos Sellis教授，IEEE Fellow、美国纽约州立大学李克勤教授，IEEE Fellow、香港理工大学曹建农教授等）的关注/评价，被国内外计算机科学专业博/硕士学位论文引用。成果在国内著名互联网公司网易集团旗下的产品中得到广泛应用，获教育部科技进步一等奖（2016）等。项目组的成果既丰富了路网下移动对象查询处理的研究又促进了基于位置的服务和移动计算等相关领域的进一步发展。