Page 221 - 《软件学报》2020年第10期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2020,31(10):3197−3215 [doi: 10.13328/j.cnki.jos.005810] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
支持 OR 语义的高效受限 Top-k 空间关键字查询技术

1
1
1
1,2
2
1
潘 晓 , 于启迪 , 马 昂 , 孙亚欣 , 吴 雷 , 郭景峰
1
(石家庄铁道大学 经济管理学院,河北 石家庄 050043)
2 (燕山大学 信息科学与工程学院,河北 秦皇岛 066004)
通讯作者: 潘晓, E-mail: smallpx@stdu.edu.cn

摘 要: 近些年,随着定位系统和移动设备的普及,空间文本对象的数量日益庞大,基于位置的地理信息服务在人
们的生活中发挥着越来越重要的作用.对于空间关键字查询搜索的研究亦如火如荼.然而,现有许多研究工作只适用
于 AND 语义,支持 OR 语义的搜索研究相对较少.当用户放松对关键字匹配的要求时,支持 OR 语义的搜索技术显得
尤为重要.针对这一问题,在聚集线性四分树的基础上,利用线性四分树上物理存储的 Morton 码与逻辑空间位置的
对应性,提出了基于虚拟网格的 VGrid 算法.该算法可同时支持 OR 语义和 AND 语义.最后,通过在真实数据集上进
行大量实验,验证了所提算法的有效性和高效性.
关键词: 倒排线性四分树;OR 语义;空间文本对象;空间关键字查询;移动计算
中图法分类号: TP311

中文引用格式: 潘晓,于启迪,马昂,孙亚欣,吴雷,郭景峰.支持 OR 语义的高效受限 Top-k 空间关键字查询技术.软件学报,
2020,31(10):3197–3215. http://www.jos.org.cn/1000-9825/5810.htm
英文引用格式: Pan X, Yu QD, Ma A, Sun YX, Wu L, Guo JF. Efficient algorithm of top-k spatial keyword search with OR
semantics. Ruan Jian Xue Bao/Journal of Software, 2020,31(10):3197−3215 (in Chinese). http://www.jos.org.cn/1000-9825/5810.
htm
Efficient Algorithm of Top-k Spatial Keyword Search with OR Semantics

1
1
1
2
1,2
1
PAN Xiao , YU Qi-Di , MA Ang , SUN Ya-Xin , WU Lei , GUO Jing-Feng
1 (School of Economics and Management, Shijiazhuang Tiedao University, Shijiazhuang 050043, China)
2 (School of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China)
Abstract: In recent years, with the popularization of positioning system and mobile devices, the numbers of spatial-textual objects
increase extraordinarily. Location-based services using geographical information play a critical role in daily lives. Spatial keyword search
has attracted more attention from academia and industry. However, many of the existing techniques can only be appliable on AND
semantics. There is relatively less research supporting OR semantics. When the users do not require the exact keyword matching, the
search technology that supports OR semantic is particularly important. To solve this problem, this study proposes a virtual grid-based
query algorithm VGrid. VGrid is an aggregate linear quadtree (AIL) based algorithm, utilizing the easy transformation between the
Morton codes and the spatial locations in the space. The algorithm can support both OR and AND semantics. Finally, a series of
experiments is conducted on a real dataset, and the effectiveness and efficiency of the proposed algorithm are verified.

∗ 基金项目: 国家自然科学基金(61472340, 61303017); 河北省自然科学基金(F2018210109); 河北省教育厅重点项目(ZD2018
040); 引进留学人员资助项目(C201822); 河北省基础研究团队项目(2019JT70803); 石家庄铁道大学第 4 届优秀青年科学基金
(Z661250444); 国家级大学生创新创业训练计划(201710107006, 201710107007)
Foundation item: National Natural Science Foundation of China (61472340, 61303017); Natural Science Foundation of Hebei
Province of China (F2018210109); Department of Education Key Project of Hebei Province (ZD2018040); Foundation of Introducing
Overseas Student (C201822); Basic Research Team Project of Hebei Province (2019JT70803); The 4th Outstanding Youth Foundation of
Shijiazhuang Tiedao University (Z661250444); College Innovative Training Program Foundation of China (201710107006,
201710107007)
收稿时间: 2018-03-21; 修改时间: 2018-07-19, 2018-09-27; 采用时间: 2019-01-08