科创中国

本发明设计了并实现了路网上的高效空间关键字检索的方法,共提出三个方法,SNE,FITG和SG TRee,其中SG Tree的方法性能最好,是本次发明的主要方法。具体如下,SNE方法通过对路网上的每条边建立对应的签名,利用Dijkstra算法,通过网络扩展的方式遍历网络,效率较低。FITG方法结合了新颖的空间索引和文本倒排索引,根据先文本后空间的剪枝原则串行执行查询过程,效率提升很大。但是依然有不足之处,因此,我们又利用了空间索引和文本索引签名技术,提出了一个混合的索引SG Tree,该索引通过对空间索引G Tree的每个结点都建立的相应的签名,这应可以高效的检查该结点是否包含符合查询的目标,可以同时从空间和文本两个维度进行剪枝,极大的提高了查询效率。

本发明提出路网上空间关键字检索的方法，其中SG-Tree和FITG方法是本次发明的主要方法，性能比较好，而SNE则效率较为低下，其中SNE方法，对路网上的每条边都建立对应的签名，并通过Dijkstra算法扩展遍历网络。优选的，本方法利用CCAM结构存储路网以及顶点信息，并且为每条边按照空间文本信息建立对应的签名，方便查询的过程的检测该边上是否包含查询关键字。本发明还提供一种路网上空间关键字检索的方法FITG，该方法将空间索引和文本倒排索引结合，并根据先文本剪枝，后空间剪枝的原则串行执行查询过程。优选的，将在空间和文本索引分离开，以两个独立的索引相结合串联执行，在文本上展开剪枝能力。本发明还提供一种路网上空间关键字检索的方法SG-Tree，该方法对空间索引中的每个节点建立各自的签名，在查询过程中，判断树上的节点签名是否匹配查询签名，若不匹配，则剪掉对应的根节点及其子节点。

本发明属于空间文本索引领域，具体涉及一种利用空间索引树实现路网上的高效的空间关键字检索的方法。

背景技术

随着空间定位技术的飞速发展，移动设备(e.g，smartphones)在我们的日常生活中越来越普及，基于位置的服务也随之快速发展，其与人类的生活也越来越紧密。在日常生活中，每天通过移动设备会产生大量的带有地理位置标签的文本数据。例如，在基于位置搜索服务中(e.g，Google Maps,Yahoo！Maps etc)提供了一些目标位置信息并且带有简短的文本描述，人们可以通过这些应用程序发布带有地理位置的文本信息，其中涉及到空间关键字查询的技术。

当前的空间关键字查询大多是在欧氏距离空间的基础上，然而，对于这些巨大的空间文本数据库，一个关键的挑战在于如何建立有效的查询处理机制能实时响应用户的查询需求。以往的查询方法大都是在欧氏距离空间下。在现实生活中，人们的日常行为受到路网的约束，目标之间的欧氏距离不同于路网中的实际距离，在路网上的两个位置之间的网络距离可能比他们之间的欧氏距离大的多。比如，位于河流两岸的两个目标之间的欧氏距离远远小于它们之间的实际网络距离，这就导致在欧氏空间下得到的结果在实际中可能并不相近，因此，我们需要新的查询处理方法，能快速找到路网上距离最近且符合文本描述的目标，如图1所示。

以往的空间关键字的研究主要是集中在欧式空间下，并不能直接应用与路网上。而传统的路网上的空间关键字查询方法是通过网络扩展的方式，时间和空间复杂度较高。近年来，有部分工作研究路网上的空间关键字查询，虽然也取得了一些成果，但是这些技术并不能高效的实现路网上空间关键字查询技术，效率低下。例如，在论文Top k Spatial Keyword Queries On Road Networks中，作者第一次提出路网上的空间关键字查询，论文中提出一种层次结构的空间索引，并对路网建立一个空间层次树，利用层的优势实现高效剪枝。但是，该方法和其他方法都存在一个共同的缺点，即都不适合复杂或者路网数据非常的大的情况。它们的扩展性较差，时间空间复杂度较高。

发明内容

本发明提出路网上空间关键字检索的方法，其中SG-Tree和FITG方法是本次发明的主要方法，性能比较好，而SNE则效率较为低下，其中SNE方法，对路网上的每条边都建立对应的签名，并通过Dijkstra算法扩展遍历网络。

发明人：赵朋朋 方海林 许佳捷 周晓方 苏州大学坐落于素有“人间天堂”之称的历史文化名城苏州，是国家“211工程”“2011计划”首批入列高校，是教育部与江苏省人民政府共建“双一流”建设高校、国家国防科技工业局和江苏省人民政府共建高校，是江苏省属重点综合性大学。苏州大学前身是Soochow University（东吴大学，1900年创办），开现代高等教育之先河，融中西文化之菁华，是中国最早以现代大学学科体系举办的大学。在中国高等教育史上，东吴大学是最早开展研究生教育并授予硕士学位、最先开展法学（英美法）专业教育，也是第一家创办学报的大学。1952年中国大陆院系调整，由东吴大学之文理学院、苏南文化教育学院、江南大学之数理系合并组建苏南师范学院，同年更名为江苏师范学院。1982年，学校更复名苏州大学（Soochow University）。

本发明还提供一种路网上空间关键字检索的方法FITG，该方法将空间索引和文本倒排索引结合，并根据先文本剪枝，后空间剪枝的原则串行执行查询过程。

优选的，将在空间和文本索引分离开，以两个独立的索引相结合串联执行，在文本上展开剪枝能力。

本发明还提供一种路网上空间关键字检索的方法SG-Tree，该方法对空间索引中的每个节点建立各自的签名，在查询过程中，判断树上的节点签名是否匹配查询签名，若不匹配，则剪掉对应的根节点及其子节点。

优选的，对空间索引中的每个节点，都建立一个距离矩阵以存储边界点之间的最短距离，从而计算两端之间的最短路径，筛选出候选集后，对每个候选集建立当前列表。

优选的，本方法采用距离优先算法，将候选集的都按照距离查询位置的远近的顺序进行排序，优先计算距离查询位置较近的目标，其中，所述方法利用文本和空间两个维度同时进行剪枝。

本发明提出检索方法中，SG-Tree方法效率最高，是本发明的主要方法，该方法将空间索引和文本索引结合，提出了非常优秀的索引结构，能够同时实现空间和文本上的剪枝，极大的提升了查询效率。

当前专利在中国不属于公知技术，未经权利人许可不得实施，希望将科技成果转让给研发实力雄厚的企业，由受让人对科技成果实施转化。交易的是科技成果中的知识产权，可以包括专利权、专利申请权、技术秘密等。科技成果转让后，转让方获得转让费，不再是科技成果的所有人；受让方向转让方支付转让费，并成为科技成果的新的所有人。