许建秋，梁珺秀，秦小麟

（南京航空航天大学计算机科学与技术学院，江苏 南京 211106）

1 引言

随着智能电话及汽车导航系统等含 GPS技术的设备广泛普及，每天都有大量的移动对象位置数据采集，目前，针对移动对象的查询主要包含k近邻查询、范围查询、反向 k近邻查询和轨迹相似查询[1～4]等。

越来越多的应用把移动对象轨迹数据与对象的文本属性关联起来，得到时空文本属性随时间变化的移动对象。目前，针对包含文本属性的移动对象提出了语义轨迹[5]、活动轨迹[6]、符号轨迹[7]等，衍生出应用广泛的关于时空文本的移动对象查询[8～10]，即结合时空查询和文本查询以寻求最优结果的混合查询，如可以作为路径推荐的活动轨迹相似查询（ATSQ,activity trajectory similarity query）[6]、k近邻关键字查询[11]、符号空间轨迹混合查询[12]等。

在某些应用场景下，人们更倾向于提出给定模式的查询，如“查找在15:00～18:00，距离查询轨迹最近的前 k个从 P4出发经过若干景点后先经过P1后经过 P2的移动对象”。其中，P表示景点，查询中提出的由P4出发先经过P1和P2是有顺序要求的，且时间在给定的查询范围内，这种含有顺序的文本属性请求被称为给定模式，目前还未有上述查询请求的研究成果发表。将这种位置随时间变化且包含文本信息到时间区间映射的轨迹称为时空标签轨迹，将这类查询定义为基于时空标签轨迹的k近邻模式匹配查询。与现有查询相比，k近邻模式匹配查询存在以下特点：1) 模式匹配能处理较复杂的文本属性查询请求；……