邓 涛,陈红梅,王丽珍

（云南大学信息学院，昆明，650504）

随着移动互联网、全球定位等技术的蓬勃发展，百度地图、美团、滴滴等各类基于位置的服务应用不断涌现，用户可以通过位置及文本信息来获得各式各样便利的服务.在这些服务背后，往往都有一套有效的技术来支撑其服务质量，因此诸如空间关键字查询（Spatial⁃Keyword Query，SKQ）、空间轨迹分析、POI推荐这些基于空间数据的技术引起了大量研究兴趣［1-12］，其中SKQ［1-4］被广泛研究.在一般情况下，SKQ根据用户给出的一组查询关键字和空间约束，返回一组与查询关键字相关且满足空间约束的空间对象（一个空间对象通常由两部分组成：一个地理位置和一组描述关键字）.为了更好地捕获用户需求，Fang et al［13］提出一种新颖的SKQ：空间模式匹配（Spatial Pattern Matching，SPM）.

SPM允许用户通过空间模式表达查询需求.一个空间模式P是一个图G()V，E，其中，每个顶点vi是一个查询关键字wi（如学校，超市等），每条边ek=(vi，vj)表达两个顶点vi和vj之间的空间约束（如1 km以内）.SPM从空间对象集中查询满足空间模式P的所有匹配实例.一个匹配实例M是一个空间对象子集，其中的空间对象包含P中顶点的查询关键字，空间对象之间满足P中边的空间约束.

例如，用户A每天送孩子上学后再搭乘公交车上班，下班后再接孩子回家.他想要购买一套满足如下要求的住宅：（1）住宅与学校、车站邻近，但考虑到噪音问题，车站、学校至少应该与住宅距离500 m；（2）车站去往学校的途中应该有超市，即车站与学校同时与超市邻近，以便下……