面向空间数据的空间模式匹配研究

发布时间：2020-03-22 16:41

【摘要】：随着移动终端,如手机,平板电脑等的普及,和位置传感器、定位及导航系统的广泛应用,产生了大量带有地理位置信息的空间数据,也催生了大量对基于位置的服务的需求。比如,百度地图中的导航功能,大众点评中离我最近的餐厅功能等都给用户带来了便捷。针对如何利用空间查询技术对海量空间数据进行存储和分析,并最终支持用户日益个性化、多样化的查询需求,如何进行高效的空间关键词查询(Spatial Keyword Query)显得至关重要。常见的空间关键词查询分为范围查询和最近邻查询,尽管这两类查询已经带来了大量便利,但这两类查询仍然存在一个问题:无法精确捕捉用户意图。比如,现有的空间关键词查询算法不能处理对于不同对象之间的关系有限制的需求,也不能处理多个查询对象且任意两个对象间距离区间都不同的需求。针对此问题,本文围绕空间模式匹配(Spatial Pattern Matching)展开研究。本文的主要研究工作有:(1)改进了现有的空间查询模型,使用基于图的空间模式对查询条件进行建模。空间模式是简单图,图的每个顶点对应了一个对象,图的每条边对应了顶点间距离区间和相互关系。对于同一个模式,本文使用现有的空间查询mCK算法和本文设计的适用于SPM的算法找出匹配,对比这两个匹配,可以看出,空间模式能够更加精准地捕捉和满足用户需求。(2)改进了适用于图模式匹配问题的算法来进行空间模式匹配,同时,基于多路连接的思想设计了 MSJ算法,MSJ通过动态规划简化模式中的距离关系,并采用剪枝策略进一步优化,实验表明MSJ算法更高效。(3)针对当用户给定的空间模式要求较宽松时,找到的匹配过多对用户进行选择造成了负担的情况,设计了评估函数用于评价不同匹配的质量,并提出了快速排序算法IncMatch能够在不求出全部匹配的情况下增量搜索并返回最佳的匹配。(4)针对用户给定的空间模式限制过多,导致模式无法在空间数据库中找到匹配的情况,引入最大可行子模式的概念来衡量匹配程度,并分别基于Aporiori思想和MARGIN思想设计了两种算法APM和MPM来找出最大可行子模式,进而找到对应于最大可行子模式的部分匹配。
【图文】：

实例图,实例,算法,节点

定义２－３邋（ｃｕｔ［２】）如果ｌａｔｔｉｃｅ中一对节点（０？，，尺）满足Ｃ７？是／？的孩子，且／？频逡逑繁而Ｃ／？不频繁，则（以，７？）构成一个Ｍ。逡逑以图２－５（ｂ）为例，Ｌ是图Ｇ的ｌａｔｔｉｃｅ：邋Ｌ包含７个节点，最底层的节点是逡逑空图，最顶层的节点代表Ｇ，每对父子节点都用虚线相连。假设图２－５（ｂ）中虚逡逑线圈出的图是频繁图，而图Ｇ不频繁，则这对节点是一个ｃｕｔ邋（图中用加粗实逡逑线标出）。逡逑ＭＡＲＧＩＮ的基本思路如下：首先不断删除Ｇ中的一条边直到得到一逡逑个频繁子图义Ａ和的孩子Ｃ７？形成初始ｃｕｔ，然后对（Ｃ７？，／？）调用算法逡逑ＥｘｐａｎｄＣｕｔＲ从而发现该ｃｕｔ附近的其他ｃｕｔ，递归地对新发现的所有ｃｕｔ调逡逑用ＥｘｐａｎｄＣｕｔ１２１，直到没有新的ｃｕｔ被发现。找到所有ｃｕｔ后，对这些ｃｕｔ中逡逑的频繁节点进行比较，找到其中的最大子图，该子图（可能有多个最大频繁子逡逑图）即为Ｇ的最大频繁子图。逡逑％逦ｃ0＞逡逑／逦ｃ，邋＞逦＼邋ｃ逦＼逡逑ｐ逦ｐ邋Ｐ］邋ｐ２逦＼逦＞邋ｉ邋＾逡逑（ａ）逦（ｂ）逦Ｐ＊逦Ｓ丨？邋？逦＆逡逑（Ｃ＞逦（ｄ）逡逑——Ｉｎｆｒｅｑｕｅｎｔ邋ｓｕｂｇｒａｐｈ逦——Ｆｒｅｑｕｅｎｔ邋ｓｕｂｇｒａｐｈ逡逑图２－６：邋ＥｘｐａｎｄＣｕｔ算法实例逡逑以图２－６为例

面向空间数据的空间模式匹配研究

图３－３：邋ＰＪ中候选对图解逡逑
【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP311.13

【相似文献】