东北大学学报（自然科学版）

东北大学学报:自然科学版 ›› 2015, Vol. 36 ›› Issue (10): 1412-1416.DOI: 10.3969/j.issn.1005-3026.2015.10.010

• 信息与控制 • 上一篇    下一篇

面向组近邻的Top-k空间偏好查询

陈默1， 杨丹2， 谷峪3， 于戈1,3   

  1. (1. 东北大学 计算中心， 辽宁 沈阳110819； 2. 辽宁科技大学 软件学院， 辽宁 鞍山114051； 3. 东北大学 信息科学与工程学院， 辽宁 沈阳110819)
  • 收稿日期:2014-09-30 修回日期:2014-09-30 出版日期:2015-10-15 发布日期:2015-09-29
  • 通讯作者: 陈默
  • 作者简介:陈默(1983-)，女，辽宁沈阳人，东北大学讲师，博士； 于戈(1962-)，男，辽宁大连人，东北大学教授，博士生导师.`
  • 基金资助:
    国家自然科学基金资助项目(61402093，61402213); 中央高校基本科研业务费专项资金资助项目(N141604001， N120316001).

Top-k Spatial Preference Query for Group Nearest Neighbor

CHEN Mo1， YANG Dan2， GU Yu3， YU Ge1,3   

  1. 1. Computing Center， Northeastern University， Shenyang 110819， China; 2. Software College， University of Science and Technology Liaoning， Anshan 114051， China; 3. School of Information Science & Engineering， Northeastern University， Shenyang 110819， China.
  • Received:2014-09-30 Revised:2014-09-30 Online:2015-10-15 Published:2015-09-29
  • Contact: YANG Dan
  • About author:-
  • Supported by:
    -

RichHTML

1

PDF (PC)

770

摘要： 空间偏好查询是当前空间查询研究中的一类热点问题，而现有的空间偏好查询不能有效支持面向组用户的位置服务应用.为此，提出一类新型空间偏好查询——面向组近邻的Top-k空间偏好查询 (Top-k spatial preference query for group nearest neighbor).该查询通过查找特征对象的λ子集组近邻最终为用户返回评分值最高的前k个λ子集.为了高效执行这一查询，给出了两种查询算法:TSPQ-G及TSPQ-G*.其中TSPQ-G*在TSPQ-G的基础上，通过空间剪枝及高效的特征对象索引树遍历策略大幅减少I/O代价，进而有效提高了该查询的执行效率.实验采用多个数据集验证了所提算法在不同参数设置下的有效性.

关键词: 空间偏好, 位置服务, 组近邻, 剪枝, 查询

Abstract: Spatial preference query is a popular focus of the current research on spatial queries. However， the present spatial preference queries cannot be used in the location-based services for group users. To solve this problem， a novel type of spatial preference query， namely， Top-k spatial preference query for group nearest neighbor (TSPG) was proposed， which retrieves the k λ-subsets with the highest score through finding λ-subsets group nearest neighbors of the feature objects. Two algorithms， namely， TSPQ-G and TSPQ-G* were designed for efficient query processing. Based on the TSPQ-G， the TSPQ-G* was developed by performing spatial pruning strategies and efficient traversal strategies of feature objects index， which effectively reduces I/O cost and improves query efficiency. Experimental results on several datasets demonstrated the effectiveness of the proposed algorithms for different setups.

Key words: spatial preference, location-based service, group nearest neighbor, pruning, query

中图分类号: