一种面向大规模空间文本数据的空间结构匹配算法  

A Spatial Structure Matching Algorithm for Large Spatial-Textual Datasets

作　　者：刘志丹 林维鑫 伍楷舜 LIU Zhi-Dan;LIN Wei-Xin;WU Kai-Shun(College of Computer Science and Software Engineering,Shenzhen University,Shenzhen,Guangdong 518060)

机构地区：[1]深圳大学计算机与软件学院,广东深圳518060

出　　处：《计算机学报》2022年第6期1261-1275,共15页Chinese Journal of Computers

基　　金：国家自然科学基金项目(62172284,61872248,U2001207);广东省自然科学基金项目(2020A1515011502,2017A030312008)资助.

摘　　要：为了支持各类基于位置的服务,人们提出了各种查询和搜索空间文本数据的方法和技术.传统的空间关键字查询和近期提出的空间模式匹配不支持用户定义查询关键字对象以及对象之间细致的空间结构关系,使得查询结果集庞大但无效结果偏多,不能满足用户高效且精确的查询需求.本文因此提出了一种新的查询模式——空间结构匹配查询(Spatial Structure Matching,SSM),允许用户定义一组查询关键字对象并指定任意两个对象之间的距离和方向约束.为了解决SSM查询问题,本文首先提出了一种基于多路连接的基准方法,将SSM查询问题分解为单个对象的关键字匹配,两个对象的边匹配和多个对象的聚合匹配.为了提高SSM查询效率,本文提出了基于扫描线算法的边匹配计算,利用对象的地理位置信息来降低边匹配计算开销.本文利用同时满足查询关键字,距离和方向约束的空间对象构造对象连接图,从而将SSM查询问题转换为在对象连接图上搜索与SSM查询结构同构的子图匹配问题,并且利用经典的子图同构匹配算法求解获得最终的查询结果.在四个大规模空间文本数据集上的实验结果表明,本文所提算法的查询效率远高于对比算法,返回的查询结果集精简有效且在查询时间上提升至少3倍.Many techniques have been proposed to query and search on the massive spatial-textual data for supporting various location-based services.Traditional spatial keyword query(SKQ)and the recent spatial pattern matching(SPM),however,cannot accurately capture users’query intention on the interested objects and their spatial relations,resulting in a huge number of irrelevant results.As a result,existing techniques still cannot well satisfy users’query requirements.Therefore,this paper proposes a novel query problem-Spatial Structure Matching(SSM),which allows the user to provide a set of keyword objects and meanwhile define the constraints on both distance and direction for any two concerned objects.To answer an SSM query,this paper firstly presents a multi-way join based baseline approach,which decomposes the SSM query into the keyword matching for each individual object,edge matching for a pair of objects,and aggregation matching for a set of objects.To improve the efficiency,we further propose a sweep-line based edge matching algorithm by exploiting the geographic locations of objects to filter out the pairs of objects that cannot meet distance constraints.In addition,we build an object-connection graph using the objects that meet all constraints,and transform the SSM query into a subgraph isomorphism problem,which searches the subgraphs with similar structure as SSM query over the object-connection graph.This problem is well solved by adopting a fast subgraph matching algorithm.Experiments based on four large real-world spatial-textual datasets demonstrate that the proposed approach significantly outperforms the compared approaches by providing refined and effective results,while reducing the query processing time by at least 3 times.

关 键 词：空间文本数据 空间查询 空间结构 扫描线 子图同构匹配 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]