一种针对反向空间偏好top-k查询的高效处理方法

来源：软件学报杂志2017年第2期北京时间：

作者：李淼,谷峪,陈默,于戈

单位：李淼，东北大学 计算机软件与理论研究所, 辽宁 沈阳 11081911,谷峪，东北大学 计算机软件与理论研究所, 辽宁 沈阳 11081902,陈默，东北大学 计算中心, 辽宁 沈阳 11081903,于戈，东北大学 计算机软件与理论研究所, 辽宁 沈阳 110819;东北大学 计算中心, 辽宁 沈阳 11081904

摘要：随着地理位置定位技术的蓬勃发展，基于在线位置服务技术的应用也越来越多.提出一种查询类型——反向空间偏好top-k查询.类似于传统的反向空间top-k查询，对于给定的空间查询对象，该查询返回使该对象满足top-k属性得分的那些用户.但不同的是，该对象的属性不是自身具有的特性，而是通过计算该对象与其他偏好对象之间的空间关系（如距离）而确定.这种查询在市场分析等许多重要领域具有需求，例如，根据查询结果，分析出某个地区中某个设施受欢迎的程度.但是，由于大量空间对象的存在导致对象之间空间关系的计算代价非常高，如何实时地计算出对象的空间属性得分，给查询处理带来很大的挑战.针对该问题提出优化的查询处理算法包括：数据集剪枝、数据集批量处理、基于权重的用户分组等策略.通过理论分析和充分的实验验证，证明了所提出方法的有效性.与普通方法相比，这些方法能够大幅度提高查询处理的执行时间和I/O效率.

关键词：top-k查询;反向top-k查询;四叉树;分组;查询优化

基金资助：国家自然科学基金（61272179，61472071，61402093）；中央高校基本科研业务费专项资金（N141604001）