度量空间下的k最近对查询及变体处理研究

Query/Search 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. Existing k-closest pair queries focus on the Euclidean space, and utilize geometric characteristics to prune the search space. However, these geometric properties do not apply to the metric space; and in many practical applications (e.g., data mining), the proximity relationship between objects needs non-Euclidean distance (such as edit distance) to measure. This project aims at studying the k-closest pair query and its variants in metric spaces, based on the existing research on k-closest pair retrieval and metric queries. It considers the characteristics of metric spaces (e.g., triangle inequality), and aims to minimize the I/O cost and the number of distance computation during the query processing. The project mainly investigates a suite of query processing problems, including the metric k-closest pair query, the metric self-k-closest pair query, the metric k-closest pair query with distance constraints, the metric k-furthest pair query, the non-index-based metric k-closest pair query, the metric multi-way-k-closest pair query, and the metric exclusive closest pair join; designs, implements, and evaluates every query processing algorithms, and develops the 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最近对查询和度量查询研究基础上，结合度量空间特性（如三角不等式），以最小化I/O次数和距离计算次数为优化目标，展开一系列能满足实际应用需求的度量空间下的k最近对查询及变体处理研究，重点研究度量k最近对查询、度量自身k最近对查询、受限度量k最近对查询、度量k最远对查询、无索引度量k最近对查询、度量多路k最近对查询和度量独占最近对连接；设计、实现和评价各自查询处理算法，并开发相应的展示平台；力争在相关理论和技术上取得突破，为今后的实际应用奠定坚实基础。

在大数据时代，“数据在，找不到”现象日益严重，因而如何有效地索引与查询大数据成为了一个巨大的挑战。度量空间支持多种数据类型和任意（距离）度量方式，并不受数据对象的几何特性限制，在大数据智能查询方面具有重要的应用价值。本项目围绕度量空间索引与查询技术展开了深入地探索，重点研究了度量空间索引技术（如确定/不确定的度量空间数据索引等）、度量空间查询技术（如度量k最近对查询及变体、度量全k最近邻查询等）以及度量空间查询结果可用性分析（如度量概率区域查询上Why-not问题等），并搭建了一个社交图像检索与推荐系统。项目组圆满实现且超出了预期的研究成果，完全达到了预期的研究目标。共培养/毕业博士生8名，硕士生14名，本科生5名，并获国家奖学金10人次等奖励；在国内外顶级/重要学术期刊或会议VLDBJ、TKDE、TOIS、TFS、SIGMOD、VLDB、ICDE、DASFAA等发表/录用论文51篇，其中SCI检索31篇，EI检索50篇，CCF A类期刊或会议论文20篇，SCI他引90余次，Google Scholar他引200余次；（待）出版相关中英文学术专著3部；实审相关专利4项；部分成果受到了国内外知名专家（如欧洲科学院院士、ACM/IEEE Fellow、TODS主编、丹麦奥尔堡大学Christian S. Jensen教授，IEEE/AAAS Fellow、KAIS主编、美国路易斯安那大学拉斐特分校吴信东教授，IEEE Fellow、TKDE主编、澳大利亚新南威尔士大学林学民教授，IEEE/RSNZ Fellow、新西兰奥克兰理工大学Nikola Kasabov教授，IEEE Fellow、美国纽约州立大学李克勤教授，IEEE Fellow、美国明尼苏达大学David hung-Chang Du教授，IEEE Fellow、香港理工大学曹建农教授等）的关注/评价，应用于网易LOFTER与云音乐，被国内外学术专著、计算机科学专业博/硕士学位论文引用，并获CCF优秀博士学位论文奖（2017），浙江省优秀博士学位论文提名论文奖（2016）、浙江省优秀硕士学位论文奖（2016）、教育部科技进步一等奖（2016）、国家优秀青年科学基金项目（2015）和ICDE 2015优秀论文等。项目组的成果既丰富了度量空间数据管理方面的研究又促进了数据挖掘和多/跨媒体检索等相关领域的进一步发展。