面向移動對象的連續區域查詢服務系統

黃鑫玉 景鵬

摘要：隨著移動終端的高速發展，產生了大量動態變化的時空數據，基于這些數據的數據挖掘應用越來越受到人們的重視.傳統的時空數據查詢及存儲方案難以針對海量、高更新頻率的流式時空數據提供高效、準確的連續區域查詢服務.為解決上述問題，本文實現了面向移動對象的連續區域查詢服務系統.通過建立多維度索引、查詢后更新的策略以及對漏查現象的特殊處理，提供精準、高效的連續區域查詢服務.同時提供可配置、可操縱的數據導出服務，將數據永久存儲至分布式文件系統中。

關鍵詞：移動對象;連續查詢;區域查詢;時空數據

隨著時空數據的迅猛增加，基于時空數據的數據挖掘應用越來越成為研究的熱點，需要提供高效、精準的數據查詢、更新及存儲策略.傳統方法不能滿足這些要求，主要體現在三個方面：首先，為適應多維度的查詢需求，需要在多個維度上建立索引，以實現高效的查詢;其次，需要針對時空數據海量及高更新頻率的特點，設計高效、準確的連續區域查詢策略，利用比網格劃分更為均衡的區域劃分方法，避免數據分布不均的情況;最后，需要定期將數據從內存數據庫中導出至分布式的存儲系統中，以用于其他相關的數據挖掘應用。

為解決上述問題，本文提出了面向移動對象的連續區域查詢服務系統，該系統有以下特點：

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-），女，湖北省鄂州市人，當前職務：業務經理，學歷：碩士，研究方向：數據挖掘。