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