一种最匹配模糊轨迹问题的查询方法

摘要

本发明公开了一种最匹配模糊轨迹问题的查询方法。该方法发明了一种新的匹配度衡量标准来衡量模糊轨迹之间的匹配程度。该方法先将值域空间划分成一系列的单元格，然后在每一个单元格内建立一个时间索引。在处理匹配查询时，该方法首先访问索引结构，计算每个模糊轨迹和查询轨迹之间匹配度的上界和下界；然后利用该上界和下界对不合格的模糊轨迹进行剪枝，从而得到一个候选答案集合；最后该方法计算每一个候选模糊轨迹的精确的匹配度，并判断该模糊轨迹是否是真正的查询结果。本发明充分利用了数据库和信息检索的现有研究和实现成果，基于已有的空间数据查询方法的扩展和融合可以非常方便快捷的提供最匹配模糊轨迹问题的查询能力，提供最好的性能。

说明书

技术领域

本发明涉及数据库系统、信息检索、空间索引和查询技术，特别是涉及一种最匹配模糊轨迹查询的查询处理方法。

背景技术

在实际应用中，产生了大量的轨迹数据。例如，GPS设备的广泛应用导致了大量的移动车辆和移动物体轨迹的产生。理想情况下，这样一条轨迹数据被建模为一个带有时间戳的地理位置的序列。但是，这种建模方法过于简单，不能考虑到位置信息的不确定性。

物体位置信息的不确定性有很多来源。例如，一个GPS设备读取的位置信息，本身即不是一个精确的地理位置，而是由一个精确的位置点（精度和维度）和一个误差范围表示的。此外，由于基于位置的隐私保护受到了越来越多的重视，很多位置信息在发布以前，即被泛化成一个不确定的区域。在这种情况下，一个移动物体的轨迹信息被建模为一个带有时间戳的位置区域的序列。并且，对应每个时间戳，用概率分布函数（pdf）来表示轨迹在该时刻位于相应位置区域中的概率分布情况。

模糊轨迹数据上的匹配度查询在现实生活中有着非常广泛的应用。对于模糊轨迹数据来说，处理匹配度查询的一个关键问题是，如何衡量两个模糊轨迹之间的匹配度。

国际上已有一些时间序列数据的匹配度衡量标准，例如动态时间规整算法（Discrete Time Warping、DTW），最长公共子串（Longest Common Subsequences、LCSS）等。但是这些方法都是针对确定型的时间序列数据提出的，不能够应用于不确定的轨迹数据。此外，这些衡量标准只适用于带有离散时间戳的数据，不能够应用于轨迹数据这样的考虑两个时间戳之间连续时间段的数据类型。一种直观的可以衡量模糊轨迹数据在连续时间段内的匹配度的衡量标准是欧几里德距离的数学期望。但是，欧几里德距离的数学期望对于不确定数据的歧义点非常敏感。所以对模糊轨迹来说，欧几里德距离的数学期望不是一个可靠的衡量标准。

在这种情况下，发明一套可以高效处理最匹配模糊轨迹问题的查询方法是十分重要的。

发明内容

本发明的目的在于提供一种最匹配模糊轨迹问题的查询方法。

本发明解决其技术问题采用的技术方案的步骤如下：

1）利用网格方法将值域空间划分成多个单元格，并利用所有单元格的边界将每一个模糊轨迹划分为轨迹片段；

2）在步骤1)中的每一个单元格内建立一个一维的时间索引；

3）在查询处理时，依此访问步骤1)中的所有单元格，并计算每一个模糊轨迹和查询轨迹之间匹配度的上界和下界；

4）利用步骤3)中的每一个模糊轨迹和查询轨迹之间匹配度的上界和下界，对不合格的模糊轨迹进行剪枝，从而得到一个候选答案集合；

5）计算步骤4)中的候选答案集合中的每一个候选模糊轨迹和查询轨迹之间的匹配度，并判断每一个候选模糊轨迹是否为真正的查询结果。

步骤1)利用网格方法将值域空间划分成多个单元格；所有单元格的边界将每一个模糊轨迹划分成了轨迹片段；每一个轨迹片段独立位于一个单元格内；每一个轨迹片段还对应一个时间区间，即为该轨迹片段处于相应单元格内的时间段。

步骤2)为步骤1)中得到每一个单元格，建立一个一维的时间索引，用来索引处于该单元格内的所有轨迹片段的时间区间。

步骤3)中依此访问步骤1)中的单元格，以及单元格中的轨迹片段，计算每一个模糊轨迹和查询轨迹之间匹配度的上界和下界。

步骤4)中找出步骤5)中所有模糊轨迹和查询轨迹之间的匹配度的上界中的最小值；然后，如果一个模糊轨迹和查询轨迹之间的匹配度的下界大于该最小值，则该模糊轨迹是不合格的模糊轨迹，将被剪枝掉。

步骤5)中计算步骤4)中的候选答案集合中的每一个候选模糊轨迹和查询轨迹之间的匹配度；如果一个候选模糊轨迹和查询轨迹之间的匹配度是所有候选模糊轨迹中最大的，则该候选模糊轨迹成为真正的查询结果。

本发明具有的有益效果是：

本发明充分利用了数据库和信息检索的现有研究和实现成果，基于已有的空间索引方法和查询方法的扩展和融合可以非常方便快捷的提供最匹配模糊轨迹问题的查询能力，提供最好的性能。本发明广泛适用于车辆交通指挥管理、城市日常人口流动的模式挖掘、以及基于匹配的网络日志的挖掘和商业数据挖掘。

附图说明

图1是索引结构示意图。

图2是轨迹片段示意图。

图3 是最匹配模糊轨迹问题的查询方法示意图。

具体实施方式

现结合附图和具体实施例对本发明作进一步说明。

本发明具体实施过程和工作原理，如图3所示

1）利用网格方法将值域空间划分成多个单元格，并利用所有单元格的边界将每一个模糊轨迹划分为轨迹片段；

2）在步骤1)中的每一个单元格内建立一个一维的时间索引；

3）在查询处理时，依此访问步骤1)中的所有单元格，并计算每一个模糊轨迹和查询轨迹之间匹配度的上界和下界；

4）利用步骤3)中的每一个模糊轨迹和查询轨迹之间匹配度的上界和下界，对不合格的模糊轨迹进行剪枝，从而得到一个候选答案集合；

5）计算步骤4)中的候选答案集合中的每一个候选模糊轨迹和查询轨迹之间的匹配度，并判断每一个候选模糊轨迹是否为真正的查询结果。

步骤1)利用网格方法将值域空间划分成单元格。如图2所示，所有单元格的边界将每一个模糊轨迹划分成了轨迹片段。如图2中，一个模糊轨迹被划分为4个轨迹片段。每一个轨迹片段独立位于一个单元格c内。每一个轨迹片段对应一个时间区间，即为该轨迹片段处于单元格c内的时间段。如图2中，第2个轨迹片段对应的时间区间为[t₂^-,t₂⁺]。同时，每一个轨迹片段还对应一个概率方程，P_X,c(t)，用来描述该模糊轨迹X处于单元格c内的概率随着时间的变化情况。

步骤2)中如图1所示，为步骤1)中得到每一个单元格，建立一个一维的时间索引，用来索引处于该单元格内的所有轨迹片段对应的时间区间。具体地，每一个单元格c还对应一个指针，指向存储所有处于单元格c中的轨迹片段的存储桶（bucket）。当一个存储桶不足以存储一个单元格c内的所有的轨迹片段时，需要用多于一个的存储桶来存储这些轨迹片段。特别地，时间区间相近的轨迹片段会被聚类在一起，并存储在一个存储桶内。这样，每一个存储桶同样对应一个时间范围，该时间范围是覆盖存储桶内所有轨迹的时间区间的最小的时间区间。然后，该方法采用一个一维R-tree作为时间索引，用来索引单元格c的所有存储桶对应的时间范围。

步骤3) 中依此访问步骤1)中的单元格，以及单元格中的轨迹片段。为了先访问包含和查询轨迹最匹配的轨迹片段的单元格，该查询方法按照每个单元格和查询轨迹Q的距离的升序将单元格放入一个最小堆H之中。每次访问一个单元格c，该查询方法从单元格c的存储桶中取出轨迹片段的信息，并计算每一个模糊轨迹和查询轨迹之间的匹配度的上界和下界。

在访问单元格中轨迹片段的过程中，该查询方法在内存中保存所有被访问到的模糊轨迹的匹配度的上界中的最小值。当所有没有被访问的单元格中的模糊轨迹的匹配度的下界大于这个最小值时，访问单元格的过程终止。

步骤4) 找出步骤3)中所有模糊轨迹和查询轨迹之间的匹配度的上界中的最小值。对于任意一条已经被访问到的模糊轨迹X，如果X和查询轨迹之间的匹配度的下界大于该最小值，模糊轨迹X是不合格的模糊轨迹，不可能成为查询的结果，所以被剪枝掉；如果X和查询轨迹之间的匹配度的下界小于或等于该最小值，模糊轨迹X可能成为查询的结果，将会被放入一个候选答案集合中。

步骤5) 中计算步骤4)中的候选答案集合中的每一个候选模糊轨迹和查询轨迹之间的匹配度。如果一个候选模糊轨迹和查询轨迹之间的匹配度是所有候选模糊轨迹中最大的，则该候选模糊轨迹成为真正的查询结果。