Journal of Software:2020.31(10):3197-3215

(石家庄铁道大学 经济管理学院, 河北 石家庄 050043;石家庄铁道大学 经济管理学院, 河北 石家庄 050043;燕山大学 信息科学与工程学院, 河北 秦皇岛 066004)
Efficient Algorithm of Top-k Spatial Keyword Search with OR Semantics
PAN Xiao,YU Qi-Di,MA Ang,SUN Ya-Xin,WU Lei,GUO Jing-Feng
(School of Economics and Management, Shijiazhuang Tiedao University, Shijiazhuang 050043, China;School of Economics and Management, Shijiazhuang Tiedao University, Shijiazhuang 050043, China;School of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China)
Chart / table
Similar Articles
Article :Browse 35   Download 37
Received:March 21, 2018    Revised:September 27, 2018
> 中文摘要: 近些年,随着定位系统和移动设备的普及,空间文本对象的数量日益庞大,基于位置的地理信息服务在人们的生活中发挥着越来越重要的作用.对于空间关键字查询搜索的研究亦如火如荼.然而,现有许多研究工作只适用于AND语义,支持OR语义的搜索研究相对较少.当用户放松对关键字匹配的要求时,支持OR语义的搜索技术显得尤为重要.针对这一问题,在聚集线性四分树的基础上,利用线性四分树上物理存储的Morton码与逻辑空间位置的对应性,提出了基于虚拟网格的VGrid算法.该算法可同时支持OR语义和AND语义.最后,通过在真实数据集上进行大量实验,验证了所提算法的有效性和高效性.
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.
文章编号:     中图分类号:TP311    文献标志码:
基金项目:国家自然科学基金(61472340,61303017);河北省自然科学基金(F2018210109);河北省教育厅重点项目(ZD2018 040);引进留学人员资助项目(C201822);河北省基础研究团队项目(2019JT70803);石家庄铁道大学第4届优秀青年科学基金(Z661250444);国家级大学生创新创业训练计划(201710107006,201710107007) 国家自然科学基金(61472340,61303017);河北省自然科学基金(F2018210109);河北省教育厅重点项目(ZD2018 040);引进留学人员资助项目(C201822);河北省基础研究团队项目(2019JT70803);石家庄铁道大学第4届优秀青年科学基金(Z661250444);国家级大学生创新创业训练计划(201710107006,201710107007)
Foundation items: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)
Reference text:


PAN Xiao,YU Qi-Di,MA Ang,SUN Ya-Xin,WU Lei,GUO Jing-Feng.Efficient Algorithm of Top-k Spatial Keyword Search with OR Semantics.Journal of Software,2020,31(10):3197-3215