面向移动对象的连续区域查询服务系统

黄鑫玉 景鹏

摘要：随着移动终端的高速发展，产生了大量动态变化的时空数据，基于这些数据的数据挖掘应用越来越受到人们的重视.传统的时空数据查询及存储方案难以针对海量、高更新频率的流式时空数据提供高效、准确的连续区域查询服务.为解决上述问题，本文实现了面向移动对象的连续区域查询服务系统.通过建立多维度索引、查询后更新的策略以及对漏查现象的特殊处理，提供精准、高效的连续区域查询服务.同时提供可配置、可操纵的数据导出服务，将数据永久存储至分布式文件系统中。

关键词：移动对象;连续查询;区域查询;时空数据

随着时空数据的迅猛增加，基于时空数据的数据挖掘应用越来越成为研究的热点，需要提供高效、精准的数据查询、更新及存储策略.传统方法不能满足这些要求，主要体现在三个方面：首先，为适应多维度的查询需求，需要在多个维度上建立索引，以实现高效的查询;其次，需要针对时空数据海量及高更新频率的特点，设计高效、准确的连续区域查询策略，利用比网格划分更为均衡的区域划分方法，避免数据分布不均的情况;最后，需要定期将数据从内存数据库中导出至分布式的存储系统中，以用于其他相关的数据挖掘应用。

为解决上述问题，本文提出了面向移动对象的连续区域查询服务系统，该系统有以下特点：

1）为提供高效的查询服务，针对时空数据查询中最常用的两种查询需求，区域查询及根据用户ID进行查询，实现在区域及用户ID两个维度上建立索引的时空数据存储方案。

2）针对流式时空数据海量及高更新频率的特点，采用先查询再处理更新的策略，确保查询的精度。

3）实现可配置、可操控的定时导出功能，定期将更新的数据存储至分布式文件系统中永久存储，以保存数据用于其他的基于时空数据的数据挖掘应用。

1 系统的体系结构

面向移动对象的连续区域查询服务系统主要分为3层结构，分别为数据层、服务层和交互触发层，各层结构的组成及功能如下：

1）数据层：负责管理系统中的时空数据，包括管理内存中数据的数据结构和用于永久存储时空数据的分布式数据文件存储系统（HDFS）两个部分。

2）服务层：系统服务的逻辑实现层，包括数据更新服务、数据查询服务、数据导出服务，分别负责为新产生的时空数据建立索引并存入内存，根据查询请求查询相关数据，定期将内存中的数据导出至分布式数据文件存储系统。

3）交互触发层：包括请求处理和定时导出功能的触发两个部分.请求处理部分负责处理系统接收到的查询、更新、导出等请求，定时导出功能的触发，负责定时触发数据导出服务，同时接收、处理用户对数据导出功能的配置及操纵命令。

2 关键技术

2.1 时空数据的缓存

对于不同的时空数据形式，区域划分的方式可以各不相同.对于移动通信的信令数据，用户的位置标记为基站的位置，区别于传统的网格划分方法，对于移动通信的信令数据，按照基站对区域进行划分，可以很好地避免数据分布不均的情况。

2.2 连续的区域查询

首先对本文所处理的连续区域查询的语义进行进一步明确.查询请求的输入是表示所查询区域的位置信息，连续输出该区域内的所有用户，要求输出的结果为尽可能准确的最新数据.由此连续查询分为查询阶段和连续查询更新阶段。

2.3 数据导出

文件系统中需要存储所有的时空数据，在数据更新操作中增加对旧数据的处理.增加存储旧数据的缓存.同样根据旧数据的userID查找用户的原始位置信息，对于原位置信息不存在的用户，执行插入操作，对于原位置信息已经存在的用户，将旧数据加入到缓存中，再删除旧数据，插入新数据。数据导出需要将bucket中的数据和缓存中的数据都导出文件系统中。

3 系统演示

3.1 实验环境与数据

演示系统的环境配置：一台Linux系统的主机用于完成数据更新及连续区域查询任务，机器的配置如下：四颗Dual-Core AMD OpteronTM Processor 865 CPU，頻率1.8 GHz，内存32 GB，硬盘900 GB，Ubuntu Server 64 bit 10.04.4 LTS操作系统。另有三台主机用于实现数据的分布式永久存储.搭建有基于Hadoop的MAP-REDUCE并行计算环境。

采用两组数据对系统的功能及性能进行测试，第一组为真实的移动信令数据，第二组为一个公开的移动对象轨迹生成程序MOTO生成的GPS数据，利用该程序可以生成较大规模的数据。数据集的具体信息如表1所示

3.2区域查询及个体位置查询

本系统通过请求处理模块处理应用发送来的http查询请求，并将结果封装为JSON格式返回。上层应用仅需解析JSON数据，即可使用查询结果.为了将结果进行更好的展示，设计了查询结果的显示界面。

结果的显示分为两个部分，地图一侧，用红点标注用户的位置，另一侧的表格中显示包括区域ID、用户ID、位置坐标及时间戳等详细信息.这些信息随着新的时空数据的到来实时进行更新。

3.3数据导出功能的配置及控制

本文实现可配置可控制的数据导出服务.可以通过向定时导出触发器发送命令配置URL地址，文件在文件系统中的路径、导出功能的时间间隔，同时可以控制导出触发器的启动、暂停及恢复。

4 总结

本文介绍了一种面向移动对象的连续区域查询服务系统，它实现了对时空数据的连续区域查询，并支持可配置、可操纵的定时导出功能.针对时空数据的特点，设计数据的存储结构，建立多维度索引，采用先查询再处理更新的策略，以实现准确、高效的区域查询.并通过多组实验对系统的功能及性能进行了展示。

参考文献

[1]Mokbel M F，Xiong X，Aref W G.SINA：Scalable incremental processing of continuous queries in spatio-temporal databases[C]//Proceedings of the 2004 ACM SIGMOD international conference on Management of data.ACM，2004：623-634.

[2]Xuan K，Zhao G，Taniar D，et al.Continuous range search query processing in mobile navigation[C]//Parallel and Distributed Systems，2008.ICPADS'08.14th IEEE International Conference on.IEEE，2008：361-368.

[3]Dittrich J，Blunschi L，Salles M A V.Indexing moving objects using short-lived throwaway indexes[C]//SSTD，Aalborg，Denmark，2009.Berlin：Springer，2009，5644：189–207

[4]Šidlauskas D，Ross K A，Jensen C S，et al.Thread-level par-allel indexing of update intensive moving-object work-loads[C]//LNCS 6849：Lecture Notes in Computer Sci-ence（2011），SSTD，Minneapolis，MN，USA，2011.Ber-lin：Springer，2011：186–204

[5]Šidlauskas D，Šaltenis S，Jensen C S.Parallel Main-Memory Indexing for Moving-Object Query and Update Work-loads[C]// SIGMOD International Conference on Manage-ment of Data，New York，USA，2012.2012：37-48.

作者简介：黄鑫玉（1991.06-），女，湖北省鄂州市人，当前职务：业务经理，学历：硕士，研究方向：数据挖掘。