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

项目名称： 度量空间下的k最近对查询及变体处理研究

项目编号： No.61379033

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 高云君

作者单位： 浙江大学

项目金额： 76万元

中文摘要： 查询/搜索是计算机科学的基本问题，存在于目前几乎所有的计算机应用领域；特别是在大数据时代，高效的查询处理与优化技术显得尤为重要。现有的k最近对查询主要针对欧氏空间，并利用几何特性修剪查找空间；但这些几何特性不适用于度量空间，且在许多实际应用（如数据挖掘）中，对象不能由欧氏空间模型表示，其邻近关系可能用非欧氏距离（如编辑距离）度量。本项目拟在现有k最近对查询和度量查询研究基础上，结合度量空间特性（如三角不等式），以最小化I/O次数和距离计算次数为优化目标，展开一系列能满足实际应用需求的度量空间下的k最近对查询及变体处理研究，重点研究度量k最近对查询、度量自身k最近对查询、受限度量k最近对查询、度量k最远对查询、无索引度量k最近对查询、度量多路k最近对查询和度量独占最近对连接；设计、实现和评价各自查询处理算法，并开发相应的展示平台；力争在相关理论和技术上取得突破，为今后的实际应用奠定坚实基础。

中文关键词： 度量空间；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

英文关键词： Metric Space；k-Closest Pair Query；Index；Query Processing；Database Usability