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

Efficient Algorithm of Top-k Spatial Keyword Search with OR Semantics

作　　者：潘晓 于启迪 马昂 孙亚欣 吴雷 郭景峰[2] 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 Information Science and Engineering,Yanshan University,Qinhuangdao 066004,China)

机构地区：[1]石家庄铁道大学经济管理学院,河北石家庄050043 [2]燕山大学信息科学与工程学院,河北秦皇岛066004

出　　处：《软件学报》2020年第10期3197-3215,共19页Journal of Software

基　　金：国家自然科学基金(61472340,61303017);河北省自然科学基金(F2018210109);河北省教育厅重点项目(ZD2018040);引进留学人员资助项目(C201822);河北省基础研究团队项目(2019JT70803);石家庄铁道大学第4届优秀青年科学基金(Z661250444);国家级大学生创新创业训练计划(201710107006,201710107007)。

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

关 键 词：倒排线性四分树 OR语义 空间文本对象 空间关键字查询 移动计算 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]