基于目标轨迹的函数连接算法研究

张冠男 张炜

摘 要：随着观测手段的增加，人们观测目标的能力得到增强，为了能够使这些观测到的数据得到更好的理解，我们提出了基于目标轨迹的函数连接算法。在关系数据库中，关系表的元组依据时空限制条件来与目标轨迹进行关联操作，进而能够得到更加丰富的可理解的信息。我们提出了函数连接的操作过程，给出了一种以时间空间以及属性值限制条件下的函数连接的过程。之后我们提出了循环函数连接算法。这种算法能够用来在数据库中进行大量的操作，完成数据库中大量数据的函数连接操作。我们提出了一种改进的策略来优化循环函数连接算法。最后我们给出了算法的复杂性分析和实验的分析。

关键字：函数连接；目标轨迹；压缩优化

中图分类号：TP311.13 文献标识号：A 文章编号：2095-2163（2014）05-

Research of Function Join based on Target Trajectory

ZHANG Guannan， ZHANG Wei

（School of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China）

Abstract： In order to obtain comprehensive information， which are acquired from different observing approaches， about interested objects， a trajectory based function join operation is studied. Tuples in data tables are associated based on trajectories according to spatial-temporal constraints. The paper proposes the operation of function join which shows how to do join operation in condition of spatial-temporal constraints and attribute constraints. This process helps to finish the operation in tuples. Nested loop join algorithm is proposed. This algorithm can be used in database. Then the paper also proposes an optimization method to improve the nested loop algorithm. At last the paper gives out the complexity analysis of the algorithm and the experiment.

Key words： Function Join； Target trajectory； Compression optimization

0 引 言

当今时代，为了清楚明彻地观察分析现实物理世界，人们采用了种类各异的信息数据收集方法。而为了能够收获具有更好理解力尺度的信息数据，就要通过不同方法针对所获得的信息数据进行重新的梳理解析，以求尽量多地得到感兴趣物体的各类属性信息并加以进一步地融合处理。例如，动物保护组织和生物学家往往使用不同种工具来观测野生动物[1]。正如位置跟踪设备、全球定位导航和无线电遥感器等设备即更经常地用于动物的运动轨迹跟踪。而配有红外触发的相机[2]也正用来探测野生物种的存在，并以此来估算种群密度等参数[3]。同样，种群的规模则要依靠飞行器从空中的俯拍观测[4]，而物种栖息地的采光，温度，湿度等数据依靠传感器网络的集成采集[5]。在调用这些数据收集的方法后，就能够得到同一种群的大量数据，比如图片、种群规模、运动轨迹、气候温度/湿度和栖息地生存条件等。如果能够将获得的这些数据通过某种方法进行有机地融合，这将对野生动物行为习惯的研究产生重大的推动以及帮助。

在军事侦查领域中，许多设备和复杂的系统正用于完成其对应的相关任务。因此雷达设备的需求也进入了上升阶段，多种不同的雷达系统已经或即将建造起来。这些雷达系统能够检测目标的方位，速度，经度和纬度等等，而其中的目标则包括汽车，船只，飞机等[6]。雷达警示接收器[7]或者被动雷达均能够有效收集目标发出的各种雷达信号[8]。频率信息，脉宽、脉冲能量波等许多雷达信号特征全部能由这两种雷达探测并捕获。如果能够将主动侦测到的目标信息与被动捕获到的信息进行一种技术结合，就将对人们分析目标特征带来较大便利及助益。

然而，由于这些信息是通过不同种观测方法收集得到的，目前并不存在一种直接独特的方法可对这些信息数据进行自动完善的关联。为了解决这一问题，文中给出了一种新颖的基于目标轨迹的函数连接算法。在算法中，目标的轨迹信息数据可作为索引，剩余的其他信息数据则通过建立的索引来和轨迹信息形成关联。在基于目标轨迹的函数连接算法中，基于时间和空间关系的条件则主要用于决定获得的轨迹信息是否与属性信息完成了关联。这其中，时空关系条件可以理解为在同一时间段内，多组数据在空间上是否相近。同时，与轨迹信息关联的其他信息数据均可看作被观察物体的属性信息数据。并且，除了时间空间关系，基于目标轨迹的函数连接算法还要满足人为给定的限制条件。例如，红外触发的相机能够探测一个扇形区域，但当且仅当需要分析在27～42度之间的区域信息时[9]，这种状况下的角度就成为了限制条件，而本文的研究目标也将随之变换为在给定范围做函数连接算法[10，11]。

对于所有和GPS获得的数据所关联的图像信息，限制条件则是野生动物的毛发颜色和图像中的种群大小。通过关联图像信息和GPS轨迹信息，生物学家即能得到更为精确的来自不同野生动物栖息地的种群密度估计。同样，通过被动雷达接收到的雷达信号能够和飞行器的轨迹相关联，相应条件则是在满足时空条件的前提下，信号方向恰好位于轨迹点集的内部。在满足相应给定的限制条件后，大量的信号数据信息就能够关联到轨迹信息当中。

这篇论文研究了基于目标轨迹的函数连接算法。研究首先给出了连接操作的定义，接着又给出了轨迹段数据和属性数据的元组匹配过程的设计。再以这个匹配过程为基础，相应地给出了循环连接算法。其后，为了改进这种算法，又相继提出了轨迹压缩的方法，同时也给出了压缩方法的准确率。最后，实验的结果则给出了同一数据规模下的不同的算法的效率。

1 问题的定义

定义1 一条轨迹段是一系列具有时间戳的连续的点，这些点有一个独特的标识，表示为 ，其中 表示物体在时间戳 的坐标是 。

在本部分章节当中，需要假定所有通过不同种侦测手段获得的数据都存储在关系数据库当中。在关系数据库中轨迹点集的关系模式可表示为 ，其中 是每个物体的特定标识， 是轨迹集合中点的坐标，而 则是每个点的时间戳属性。通过观测手段获得的数据集合的关系模式可标记为 ，其中 表示收集到的信息的属性特征， 代表相对于观测点（例如红外摄像头或者被动雷达的坐标位置）的空间参考信息， 即代表了获得属性信息的时间戳。在此，需要关注的一点是，轨迹点信息的观测时间戳和属性信息的观测时间戳是独立的，即多种设备的时间信息并不同步。

定义2 给定轨迹点集 ，数据信息集合 ，时间空间限制条件 ，另外的属性值限制条件为 ，基于目标轨迹的函数连接则可表示为，在限制条件 和 下，数据信息集合 与轨迹点集 做连接运算。具体地，运算公式可描述为：

（1）

其中，

针对时间空间关系限制条件 ，任意两个连续的坐标点 ，并且相应的时间戳 ，存在一系列关联结果 而且满足：

对 ；

同时，对 ，使 成为相对于 在 的空间参考信息，如果 并且 ， 即为真。

而对于属性值限制条件 来说，任意有独特标识 的轨迹点集 ，可令 表示 的时间段，则存在一系列结果集 ，满足对 ，条件为 ， 并且 。

在基于目标轨迹的函数连接定义中，研究采用了通用形式表现了时间空间限制条件和属性值限制条件。但这些条件却需要根据具体的实际应用来相应地确定。例如，假设O点表示摄像头的位置坐标，AO表示所有捕获的图像相对于O点的空间参考信息。通过分析图像的空间参考信息，就可以得到动物相对于当前摄像头的详细方位。并且，ON表示正北方向，动物图像的角度OA是以ON为起点，顺时针旋转所得到的角度，可以表示为Dir（O，A）=α。同样，基于轨迹点也可以计算得到每一个点相对于O点的角度。时间空间限制条件则可以定义为野生动物的方位恰好在某一对连续的轨迹信息点的情况。同时，当前图像的获取时间也要隶属于这两个轨迹点的时间戳之间。形式化表示即为Dir（O，p_1 ）≤α≤Dir（O，p_2）且t_1≤t≤t_2，其中p_1，p_2是两个连续的轨迹点，t_1，t_2是两个连续的时间戳。数据属性值的限制条件可以是一系列值的集合，也可以是一段连续的值，即一段范围。该限制条件可以设定于每一个属性值上，也可以设定在每一个轨迹点上。例如野生动物皮毛的颜色特征，以及每个图像中野生动物的最少数目。

2 函数连接算法处理过程

令 和 作为两个连续的轨迹点和时间戳信息。给定关系表 中某一个元组 ，首先检查属性值的限制条件。当 满足这些条件时，即需检查时间空间关系限制条件 。 的定义将要根据应用的实际情况，可以为线性函数，二次函数或者其他类型的函数。

属性值关系表中存储着所有属性值数据。在本文中，采用了线性函数满足时间空间限制条件以简化计算。由于这一组数据满足了时间空间限制条件和属性值限制条件，算法返回了一个新的连接后的元组。如果一个元组能够和一段轨迹满足连接条件，那么轨迹段的第一个时间点信息将会用于生成的新的元组M。实现过程即如算法1所示。

如果有超过一个属性值关系表可以和当前轨迹点关系表连接，那么属于这些关系表的每一条元组都将按照一定顺序与轨迹点进行比对。得到结果集的属性值的时间戳并不需要按照时间顺序排列，只要该属性元组满足了时间空间关系和属性值限制条件即可。例如，令 ， 和 分别是三个属性值关系表的一个元组， 和 则是 的两个连续的轨迹点。当这三个元组与轨迹段连接时，如果 不满足时间空间限制条件，那么连接的结果就可以表示为 。如果下一个位于 中的元组不满足连接条件，第二个关系表的元组却满足了关系条件，则连接结果就可以表示为 。而在三个属性值关系表的当前元组都和当前轨迹段完成了匹配连接之后，即可继续读取下一段轨迹段数据，并重新使用以上元组进行匹配连接。在连接的过程中，每一个属性值数据将只能读取一次。

算法1给出了匹配过程的细节。令k表示属性值关系表的总数，m表示最大的属性值关系表的元组总数。当前匹配算法的时间复杂度即为O（kmT）。其中，T表示检查时间空间关系限制条件和属性值限制条件的总时间。

3 循环函数连接算法

最直接的用于连接属性值数据和轨迹点集数据的连接算法就是循环函数连接算法。所有的轨迹点都是从轨迹点关系表中获取的。对每一个轨迹点关系表的轨迹段，循环函数连接算法即不断调用匹配过程来实现连接操作。算法可以通过排序的方法来进行优化，即通过对属性值的数据元组依照元组的时间戳进行排序来提升性能。而且由于数据都是通过侦测设备来获取的，因此所有的数据将都是按照时间顺序存储在数据库中。如果内存足够大，就能将所有的元组全部存放于其中时，循环连接算法将会非常地高效。否则，即使元组按照时间实现排序了，也会在算法运行时产生很多的磁盘I/O。一般来讲，轨迹点关系表元组的总数均要少于属性值关系表元组的总数，因此轨迹点即可设定于外层循环当中。算法2则给出了基于目标轨迹的循环函数连接算法。算法中，假定在轨迹点关系表中有n个元组，最长的轨迹包括c个段，那么循环连接算法需要调用匹配段过程的时间复杂度则为O（cn）。

接下来分析I/O代价。令B（T）表示轨迹点数据的数据块总数，B（D）表示属性值数据的数据块总数，M表示内存缓冲区的大小。假设B（T）<=B（D），如果（M-k）>B（T），则所有的轨迹段信息均可进入内存当中，这时I/O代价为 。如果M

4 循环连接算法改进策略

改进匹配方法的主要操作就是减少在一条轨迹段内的精确匹配次数，即减少时间空间函数的运行次数。给定一个物体o，一个侦测设备D，如果o围绕着D做匀速圆周运动时，就可以根据o相对于D的方位信息的起点和终点来估计任意时刻o点所在的方位信息。

更一般的情况下，考虑轨迹点集中k个连续的点 ，其中k>2，令 和 代表压缩后的轨迹段，用两个点来代替k个点，压缩比为k/2。假设O是观测设备， 和 表示起始点和终点相对于远点的方位信息，令 设为每一步的平均时间，总的时间则为 。给定元组r，相应的观测角度 和时间戳t。并根据假设元组r可以与轨迹段连接，当且仅当 满足轨迹段第i个夹角，其中 ， 。研究即可使用 和 作为轨迹段而在时间t来对匹配算法进行估算。

5 实验

本文给出了大量的实验来评估基于目标轨迹的函数连接算法，接下来又评估了循环函数连接算法以及其改进策略。而在给出了循环连接算法与优化版的循环连接算法的对比实验后，又制作了图表来显示数据规模与效率的关系。实验环境：PC机3.10GHz CPU，4G内存，Ubuntu 12.04系统。

图1即描述了每一个算法在不同的数据规模下的运行时间，利用这些时间即可得到图表来进一步显示时间和对比效率。结果图表主要呈现了不同算法的效率的曲线。

图1 改进后的算法效率的对比

Fig.1 Comparison of efficient with different algorithm

6 结束语

通过函数连接操作，能够将原本没有相同属性的关系表的元组实现连接操作。这种操作的发生则需要时间、空间限制条件以及属性值限制条件。循环连接算法的提出使得在大型数据库中完成这种连接操作成为可能。对于给出的循环连接的算法，又进行了算法的复杂性分析，同时也给出了大量的实验。实验结果表明，优化算法可以在一定程度上提升函数连接算法的效率。

参考文献：

[1]. Wildlife monitoring. http：//www.nps.gov/pore/ aturescience/ wildlife monitoring.htm. Accessed： 2014-01-05.

[2]. Camera traps. http：//worldwildlife.org/initiatives/ camera-traps. Accessed： 2014-01-05.

[3]. ROWCLIFFE J M， FIELD J， TURVEY S T， et al. Estimating animal density using camera traps without the need for individual recognition[J]. Journal of Applied Ecology， 2008，45（4）：1228–1236.

[4]. Gps wildlife tracking. http：//en.wikipedia.org/wiki/GPS wildlife tracking. Accessed： 2014-01-05.

[5]. AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al. Wireless sensor networks： a survey[J]. Computer Networks， 2002，38：393–422.

[6]. Radar. http：//en.wikipedia.org/wiki/Radar. Accessed： 2014-01-05.

[7]. Radar warning receiver. http：//en.wikipedia.org/wiki/Radar warning receiver. Accessed： 2014-01-05.

[8]. FABRIZIO G， COLONE F， LOMBARDO P， et al. Adaptive beamforming for high- frequency over-the-horizon passive radar[J]. IET radar， sonar & navigation， 2009，3（4）：384–405.

[9]. BECKER L， HINRICHS K， FINKE U. A new algorithm for computing joins with grid ?les[C]//Data Engineering， 1993. Proceedings. Ninth International Conference on， IEEE， 1993：190-197.

[10]. BENTLEY J L. Multidimensional binary search trees used for associative searching[J]. Com- munications of the ACM， 1975，18（9）：509–517.

[11]. KITSUREGAWA M， HARADA L， TAKAGI M. Join strategies on kd-tree indexed relations[C]//Data Engineering， 1989. Proceedings. Fifth International Conference on IEEE， 1989：85-93.