动态目标移动数据管理技术研究

许桂明 孙文俊

中国电子科技集团公司第二十八研究所 江苏 210007

0 引言

对于实时处理信息系统而言，准确全面快速地获取信息的同时还需要能够对获取的动态信息进行有效的管理和利用，并能从更高层次上挖掘信息后面的知识。在时域空域全方位的预警监控过程中，信息系统积累了海量的动态目标移动位置数据。由于移动目标数量庞大，位置变更频繁，造成数据频繁更新或数据过时失效，使用传统的数据库技术和数据挖掘技术难以对这些数据进行有效的管理和利用。当前，在实时信息系统所拥有的数据中，很大一部分是动态目标运动信息，然而：(1)动态目标运动信息没有得到有效的组织与管理。目标的移动信息不能根据时间和空间约束条件进行基于位置的检索；(2)动态目标运动信息没有得到更进一步的挖掘利用。利用有效的挖掘手段，从微观上说，可以通过目标历史行为预判其下一步运动轨迹，或者通过目标行为来辅助进行目标属性的识别判定。从宏观上说，也可以分析得到相关域的目标时空分布特征。然而在实际应用场景中，缺乏对这些动态目标运动信息的分析与挖掘，甚至经常会由于数据积累过快，大量有价值的目标历史运动数据被毫不犹豫地删除。

1 移动对象数据库概述

移动对象数据库是以存储和管理随着时间变化的移动目标为目标，是从二十世纪末期开始，在空间数据库、时态数据库以及时空数据库的基础上发展起来的一个比较新的研究领域，主要应用于交通管理领域。已有的研究主要集中于移动对象数据模型、移动对象数据索引结构与查询技术等方面。一些研究机构开发了原型系统以佐证其研究理论成果。目前，各大数据库厂商比如ORACLE、IBM等，在其数据库产品中提供了相关的时空数据管理功能，但是市场上尚没有可以应用的成熟的移动对象数据库产品。本文研究如何应用移动数据库相关的概念来管理动态目标运动信息，为进一步的实际应用提供参考。

海量数据的有效应用之一是数据挖掘。数据挖掘技术的目标是从大量、不完全、有噪声、模糊、随机的数据中，提取隐含在其中的，人们事先不知道但又是潜在有用的信息的过程。近年来，数据挖掘的研究对象已经从事务型数据库扩展到空间数据库、时空数据库、移动对象数据库等。时空数据挖掘，以经典的数据挖掘理论为基础，主要受到空间数据挖掘和时态数据挖掘研究的影响，并同时还受到时空数据表示和存取方式的限制。通过各种时空数据挖掘技术对移动目标历史数据进行挖掘，可以实现对目标的运动趋势的预测，以及辅助判定目标的属性。

2 数据建模

移动对象数据模型是移动对象数据库的核心，也是时空数据挖掘的基础。移动对象的数据模型是描绘现实中移动对象、移动对象之间的时空联系以及语义约束的模型。以往的研究中提出了多种时空对象模型，主要有基于版本的时空数据模型、基于事件的时空数据模型、基于对象的移动对象数据模型等几个派系。

在某实时系统中，动态目标以批为单位进行处理，每批目标被视为时空中的一个点，在二维平面上进行无约束的运动，该实时信息系统中动态目标数据形式化定义如下：设D为动态目标数据集，D={d}，其中d为其中一批目标。设 d={id,F,P}，其中，id为目标惟一标识符；F为目标的属性集，P为目标运动行为点迹集合，或者称为目标是动态时空属性集。设F={f}，f为目标的一个属性。动态目标的属性包括大小、形状、数量、颜色等，所有属性都是离散的。设f={}，其中，f(ai)=wi，表示目标特征f的值等于ai的概率为 wi。设 P={p}，其中，p为一个目标移动位置点，p=，t为位置点录取时间，lon为位置点录取位置经度，lat为位置点录取位置纬度。

参考O. Wolfson等人提出的MOST模型，将目标位置点p扩充为p=，其中，f(t)为目标位置随时间变化的函数。因为目标位置是变化频繁，而目标的运动函数变化会少很多。在允许一定误差的条件下，可以以低得多的频率更新目标信息。

3 移动对象数据库关键技术

3.1 索引处理技术

如果要实现基于时间范围与位置范围的查询，必须对移动对象数据库建立具有相应功能的索引结构。在移动对象数据库中，移动对象都不断地更新它们的位置，在大多数情况下其更新频率远远高于查询频率，因此，理想的移动对象索引不仅需要能够支持快速的查询，更应该具备高效的更新能力。迄今为止，研究人员提出了一系列时空对象索引技术。按照索引的数据时间范围，索引方法可以历史位置索引和当前位置索引；按照索引的数据类型，索引方法可以分为基于离散数据的索引方法和基于连续数据的索引方法；按照移动对象所处环境不同，索引方法可以分为无约束环境和有约束环境的索引方法等等。为了增加索引更新效率，可以采取基于缓冲(基于内存缓冲或者基于磁盘缓冲)的方法进行批量插入和批量删除操作。

在这里，简单介绍一下R-Tree索引结构。其它各种时空数据索引，大多是在 R-Tree基础上进行改进得到。R-Tree是B-Tree在二维空间的扩展，是一种典型的空间索引技术，结构见图1。

R-Tree的节点元素是二元组{oi , MBRi}，其中，oi表示对象标识(叶子节点)或者指向子树根节点的指针，MBRi表示该目标在数据空间内的最小包含矩形框。树的性质与B-Tree相似，具有自动平衡、空间利用率高、适合外存存储等。但是有一点重要的区别，如图1左所示，中间节点的矩形框存在重叠，导致查询可能有多条路径。

图1 R-Tree平面示意图与结构示意图

动态目标索引属于连续数据类型的无约束运动索引，因此可以将基于历史位置的索引和基于当前与将来位置的索引分开创建以支持不同的查询任务。(1)基于历史位置的索引，只执行插入工作，因为数据量大，需要庞大的存储空间，以文件的形式存在。已有的基于历史位置的索引结构如RT-Tree，在现有空间数据索引技术上添加时间信息，难以进行时间片查询；MR-Tree、HR-Tree、MV3R-Tree等，将时间作为独立的维度处理，能有效支持时间片查询，但是空间消耗大。为了节省空间，参考系统的实际需求，设计相应的数据选择与数据过期策略，比如只索引关注目标的信息，另外根据时间范围进行分区索引，等等。(2)基于当前与将来位置的索引。这类索引会存储并更新移动对象当前位置及位置随时间变化的函数，即目标的MOST模型，所以可以查询将来一定时间内的位置信息。典型的基于当前与将来的索引有TPR-Tree，LGU结构以及BX-Tree等。TPR-Tree在R-Tree的基础上，另外存储最小矩形框四边的当前速度。TPR-Tree支持对现在和将来的查询，其中间节点元素可以表达为，其中，V=，四个变量分别表示最小矩形四边的运动速度，而叶子节点可以表示为，其中V=，两个变量分别表示为目标在两个方向上的速度。LGU结构在TPR-Tree上加入辅助结构以提高插入、删除与检索的效率。

3.2 查询处理技术

动态目标的查询，需满足属性值约束、时空约束两类条件，比如查询某区域范围一周内某类目标活动情况等。因移动对象的查询类型根据查询的空间谓词不同，时间谓词以及对象所在空间的不同分为不同的类型。

按空间谓词不同，移动对象的查询可以分为：(1)范围查询，即查询一定时间段内给定区域的所有对象，是最基本的应用，最广泛的查询类型；(2)邻近查询，即查询某时间段哪些对象距离给定目标点最近。邻近查询中最通常的类型是K邻近查询(KNN)，即查找最靠近查询点的K个对象。(3)连续查询，即指在某个时间区域内查询符合条件的目标集。在该时间区域内，由于移动对象位置的改变，查询结果随着数据的不断更新也要不断的改变；(4)密度查询，即查找在某段时间内移动对象密集的空间区域，或找到移动对象在某个时刻点的密集区域。

按时间谓词不同，移动对象的查询可以分为历史查询、当前查询和将来查询，分别对应三种时态的数据，使用不同类型的索引支持。(1)对于历史查询和当前查询，R树的点查询和范围查询算法是比较有效的，因此这些索引基本上沿用R树的传统查询处理方法；(2)对于将来查询，需要使用基于将来位置的索引，而查询的准确程度则取决于索引中使用的预测模型。针对历史数据和当前数据的范围查询，因为结果确定，所以处理比较简单，各种移动对象索引对它们的处理方式大同小异；而将来范围查询，由于带有预测性质，难度大大增加，因此成为人们研究的焦点。

移动对象查询根据移动对象所在的空间分为欧氏几何空间的查询和网络空间中的查询，分别对应于有约束的目标运动与无约束的目标运动，其距离度量分别为欧几何距离与网络距离(网络上两点间的最短路径距离)。某实时系统中动态目标的运动可近似于二维平面上的无约束运动。

现有研究主要以K近邻思想为主进行相应的扩展。这里简单介绍一下TPR-Tree上的KNN查询。TPR-Tree是最基本的基于当前与将来的移动对象索引结构，其它类型索引上的查询可以参照TPR-Tree上的算法改进得到。

首先，定义设对象 o1，o2之间在 t时刻的距离为d(o1,o2,t)；同时设对象o与矩形框MBR在t时刻的最小最大距离分别为min(o,MBR,t)和max(o,MBR,t)。距离的计算为欧式距离，公式略。确定查询时间间隔为 t，查询结果为{}，表示在t1至t2时间范围内，目标o是属于查询对象的最近K个邻居之内。设查询对象为o，只对当前目标进行查询的思想为：根据与查询对象的最小距离，对TPR-Tree所有层上的节点进行排序。深度周游 TPR-Tree，在访问的过程中更新查询对象的k近邻列表。这其中最重要的是高效的剪枝策略，尽量避免无效的子树周游。如果要对某个时间范围进行查询，则需要对时间范围进行分片，对其中的所有时刻进行如上查询，最后综合得到查询结果。

4 移动对象数据库的实现

当前仅有少数学者和研究机构实现了用于试验理论或算法效果的移动对象数据库原型系统(比如O. Wolfson等人实现的DOMINO)，尚没有可以应用的移动对象数据库产品。已有的研究提出了多种实现结构，包括层次型结构，即在传统的关系型数据库管理系统上加入一个时空层，来承担时空数据操作与传统关系型数据操作之间的翻译及查询优化等工作，限于关系型数据库的局限，这种方式基本不可取；另一种是扩展性结构，在对象关系数据库管理系统上进行内核层次的时空数据扩展，包括各种索引结构、查询实现等，这种方式是比较自然而清晰的，但是会缺少数据库本身提供的查询优化支持。

如今主流的数据库产品逐步提供了对象扩展功能，ORACLE提供了 Cartridge技术，以及空间数据管理扩展模块Oracle Spatial和时间序列模块Oracle Timeseries。如今移动对象数据库的各种研究尚在开展阶段，存在很多问题，难以实现完备的移动对象数据库管理系统，但是借助如 Oracle等厂商提供的工具的支持，可以借鉴研究中的合理的思想，进行相应的扩展，以更好地管理和利用海量的动态目标运动数据。

5 总结

本文论述了移动对象数据库的数据模型，研究了移动对象数据库包括索引处理技术与查询处理技术等关键技术，并对移动数据库的具体实现进行了阐述，对有效管理实时系统中动态目标应用产生的海量数据具有一定的意义。

[1]Ouri Wolfson, Bo Xu, S. Chamberlam, Moving Objects Databases: Issues and Solutions. In: Proc. of 10th Intl. Conf. on Scientific and Statistical Database Management.1998.

[2]Ouri Wolfson, Moving Objects Information Management:The Database Challenge In Proceedings of the 5th International Workshop on Next Generation Information Technologies and Systems.2002.

[3]Mohamed F. Mokbel, Xiaopeng Xiong, Walid G. Aref, et al.PLACE: A Query Processor for Handling Real-time Spatiotemporal Data Streams. In: Nascimento, Mario A, zsu eds. 30th International Conference on Very Large Databases. Toronto,Canada. 2004. St. Louis, SA: Morgan Kaufmann Publishers Inc.1377～1380.

[4]T.Sellis,Chorochronos:research on spatiotemporal database systems.In:Trevor Bench-Capon, Giovanni Soda, A Min Tjoa.10th International Conference on Database and Expert Systems Applications. Florence, Italy. 1999. Springer Verlag :Springer-Verlag Telos.452～456.

[5]A.Guttman. R-Trees:A Dynamic Index Structure for Spatial Searching, Proc. ACM SIGMOD. 1984.