空间多样化约束下的移动k近邻查询

doi:10.12068/j.issn.1005-3026.2020.07.001

东北大学学报:自然科学版 ›› 2020, Vol. 41 ›› Issue (7): 913-919.DOI: 10.12068/j.issn.1005-3026.2020.07.001

• 信息与控制 • 下一篇

空间多样化约束下的移动k近邻查询

许鸿斐，谷峪，于戈

(东北大学计算机科学与工程学院，辽宁沈阳110169)

收稿日期:2019-06-01 修回日期:2019-06-01 出版日期:2020-07-15 发布日期:2020-07-15
通讯作者: 许鸿斐
作者简介:许鸿斐(1987-)，男，山西太原人，东北大学博士研究生; 谷峪(1981-)，男，辽宁鞍山人，东北大学教授，博士生导师；于戈(1962-)，男，辽宁大连人，东北大学教授，博士生导师.
基金资助:
国家重点研发计划项目(2018YFB1003404)；国家自然科学基金资助项目(61872070，61602103)；中央高校基本科研业务费专项资金资助项目(N171605001).

Moving k Nearest Neighbor Query with Spatial Diversity Constraints

XU Hong-fei， GU Yu， YU Ge

School of Computer Science & Engineering， Northeastern University， Shenyang 110169， China.

Received:2019-06-01 Revised:2019-06-01 Online:2020-07-15 Published:2020-07-15
Contact: YU Ge
About author:-
Supported by:
-

摘要/Abstract

摘要： 考虑为移动中的查询对象连续返回k个距离近并且满足空间多样化约束的对象，提出了空间多样化约束下的移动k近邻(SDC-MkNN)查询.在此，满足空间多样化约束代表对象之间的相互距离大于距离阈值.为了高效处理SDC-MkNN查询问题，提出了两种基于安全区域技术的算法.算法均通过减少重新计算查询结果的次数来提高查询效率.其中一种为精确算法EA，可连续返回精确的查询结果；另一种为近似算法ρAA，可连续返回具有近似率保障的近似查询结果.采用真实数据集验证了所提出算法的有效性.

关键词: 移动k近邻查询, 空间多样化, 安全区域, 基于位置的服务, 查询算法

Abstract: A new type of queries， named moving k nearest neighbor query with spatial diversity constraints(SDC-MkNN)， was proposed.When the query object is moving， this type of queries can continuously return the k nearest neighbors， and any two of the returned objects are satisfied with the spatial diversity constraints， which means the spatial distance between any two of the returned objects must be larger than the distance threshold.Based on the safe region technique， two algorithms were proposed to increase the query efficiency by reducing the frequency of the recomputation of query results.One is an exact algorithm(EA)， which can continuously return exact query results， and the other is an approximate algorithm(ρAA)， which can continuously return approximate query results with exact bounds.The proposed algorithms were verified by extensive experiments on a real dataset.The results confirm the superiority of the proposed algorithms over the baseline algorithm.

Key words: moving k nearest neighbor query, spatial diversity, safe region, location-based service, query processing algorithms

中图分类号:

TP311.13

许鸿斐，谷峪，于戈. 空间多样化约束下的移动k近邻查询[J]. 东北大学学报:自然科学版, 2020, 41(7): 913-919.

XU Hong-fei， GU Yu， YU Ge. Moving k Nearest Neighbor Query with Spatial Diversity Constraints[J]. Journal of Northeastern University Natural Science, 2020, 41(7): 913-919.

参考文献

[1]Nutanong S，Zhang R，Tanin E，et al.Analysis and evaluation of V^*-diagram:an efficient algorithm for moving KNN queries［J］.The VLDB Journal，2010，19(3):307-332.
[2]Li C W，Gu Y，Qi J Z，et al.Processing moving KNN queries using influential neighbor sets［J］.Proceedings of the VLDB Endowment，2014，8(2):113-124.
[3]Tang J Y，Sanderson M.Spatial diversity，do users appreciate it?［C］//Proceedings of the 6th Workshop on Geographic Information Retrieval.Zurich，2010:18-19.
[4]Zhang C Y，Zhang Y，Zhang W J，et al.Diversified spatial keyword search on road networks［C］//Proceedings of the 17th International Conference on Extending Database Technology.Athens，2014:367-378.
[5]Gu Y，Liu G L，Qi J Z，et al.The moving k diversified nearest neighbor query［J］.IEEE Transactions on Knowledge and Data Engineering，2016，28(10):2778-2792.
[6]Jain A，Sarda P，Haritsa J R.Providing diversity in k-nearest neighbor query results［C］//Proceedings of the 8th Advances in Knowledge Discovery and Data Mining.Sydney，2004:404-413.
[7]Abbar S，Amer-Yahia S，Indyk P，et al.Diverse near neighbor problem［C］//Proceedings of the 29th Symposium on Computational Geometry.Rio de Janeiro，2013:207-214.
[8]Lee K C，Lee W C，Leong H V.Nearest surrounder queries［J］.IEEE Transactions on Knowledge and Data Engineering，2010，22(10):1444-1458.
[9]Kucuktunc O，Ferhatosmanoglu H.λ-diverse nearest neighbors browsing for multidimensional data［J］.IEEE Transactions on Knowledge and Data Engineering，2013，25(3):481-493.
[10]Costa C F，Nascimento M A，Schubert M.Diverse nearest neighbors queries using linear skylines［J］.GeoInformatica，2018，22(4):815-844.
[11]Liu H P，Jin C Q，Yang B，et al.Finding top-k shortest paths with diversity［J］.IEEE Transactions on Knowledge and Data Engineering，2018，30(3):488-502.
[12]Yiu M L，Dai X Y，Mamoulis N，et al.Top-k spatial preference queries［C］//Proceedings of the 23rd IEEE International Conference on Data Engineering.Istanbul，2007:1076-1085.
[13]Li M，Chen L S，Cong G，et al.Efficient processing of location-aware group preference queries［C］//Proceedings of the 25th ACM International Conference on Information and Knowledge Management.Indianapolis，2016:559-568.
[14]Zhang Z，Jin P Q，Tian Y，et al.Efficient processing of spatial group preference queries［C］//Proceedings of the 24th International Conference on Database Systems for Advanced Applications.Chiang Mai，2019:642-659.
[15]Bao J，Zheng Y，Mokbel M F.Location-based and preference-aware recommendation using sparse geo-social networking data［C］//Proceedings of the 20th International Conference on Advances in Geographic Information Systems.Redondo Beach，2012:199-208.
[15]关守平，房少纯.一种新型的区间-粒子群优化算法［J］.东北大学学报(自然科学版)，2012，33(10):1381-1384.(Guan Shou-ping，Fang Shao-chun.A new interval particle swarm optimization algorithm［J］.Journal of Northeastern University(Natural Science)，2012，33(10):1381-1384.)

空间多样化约束下的移动k近邻查询

Moving k Nearest Neighbor Query with Spatial Diversity Constraints

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价