黃鑫玉 景鵬

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

關(guān)鍵詞：移動對象;連續(xù)查詢;區(qū)域查詢;時空數(shù)據(jù)

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

為解決上述問題，本文提出了面向移動對象的連續(xù)區(qū)域查詢服務(wù)系統(tǒng)，該系統(tǒng)有以下特點：

1）為提供高效的查詢服務(wù)，針對時空數(shù)據(jù)查詢中最常用的兩種查詢需求，區(qū)域查詢及根據(jù)用戶ID進行查詢，實現(xiàn)在區(qū)域及用戶ID兩個維度上建立索引的時空數(shù)據(jù)存儲方案。

2）針對流式時空數(shù)據(jù)海量及高更新頻率的特點，采用先查詢再處理更新的策略，確保查詢的精度。

3）實現(xiàn)可配置、可操控的定時導(dǎo)出功能，定期將更新的數(shù)據(jù)存儲至分布式文件系統(tǒng)中永久存儲，以保存數(shù)據(jù)用于其他的基于時空數(shù)據(jù)的數(shù)據(jù)挖掘應(yīng)用。

1 系統(tǒng)的體系結(jié)構(gòu)

面向移動對象的連續(xù)區(qū)域查詢服務(wù)系統(tǒng)主要分為3層結(jié)構(gòu)，分別為數(shù)據(jù)層、服務(wù)層和交互觸發(fā)層，各層結(jié)構(gòu)的組成及功能如下：

1）數(shù)據(jù)層：負責(zé)管理系統(tǒng)中的時空數(shù)據(jù)，包括管理內(nèi)存中數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)和用于永久存儲時空數(shù)據(jù)的分布式數(shù)據(jù)文件存儲系統(tǒng)（HDFS）兩個部分。

2）服務(wù)層：系統(tǒng)服務(wù)的邏輯實現(xiàn)層，包括數(shù)據(jù)更新服務(wù)、數(shù)據(jù)查詢服務(wù)、數(shù)據(jù)導(dǎo)出服務(wù)，分別負責(zé)為新產(chǎn)生的時空數(shù)據(jù)建立索引并存入內(nèi)存，根據(jù)查詢請求查詢相關(guān)數(shù)據(jù)，定期將內(nèi)存中的數(shù)據(jù)導(dǎo)出至分布式數(shù)據(jù)文件存儲系統(tǒng)。

3）交互觸發(fā)層：包括請求處理和定時導(dǎo)出功能的觸發(fā)兩個部分.請求處理部分負責(zé)處理系統(tǒng)接收到的查詢、更新、導(dǎo)出等請求，定時導(dǎo)出功能的觸發(fā)，負責(zé)定時觸發(fā)數(shù)據(jù)導(dǎo)出服務(wù)，同時接收、處理用戶對數(shù)據(jù)導(dǎo)出功能的配置及操縱命令。

2 關(guān)鍵技術(shù)

2.1 時空數(shù)據(jù)的緩存

對于不同的時空數(shù)據(jù)形式，區(qū)域劃分的方式可以各不相同.對于移動通信的信令數(shù)據(jù)，用戶的位置標記為基站的位置，區(qū)別于傳統(tǒng)的網(wǎng)格劃分方法，對于移動通信的信令數(shù)據(jù)，按照基站對區(qū)域進行劃分，可以很好地避免數(shù)據(jù)分布不均的情況。

2.2 連續(xù)的區(qū)域查詢

首先對本文所處理的連續(xù)區(qū)域查詢的語義進行進一步明確.查詢請求的輸入是表示所查詢區(qū)域的位置信息，連續(xù)輸出該區(qū)域內(nèi)的所有用戶，要求輸出的結(jié)果為盡可能準確的最新數(shù)據(jù).由此連續(xù)查詢分為查詢階段和連續(xù)查詢更新階段。

2.3 數(shù)據(jù)導(dǎo)出

文件系統(tǒng)中需要存儲所有的時空數(shù)據(jù)，在數(shù)據(jù)更新操作中增加對舊數(shù)據(jù)的處理.增加存儲舊數(shù)據(jù)的緩存.同樣根據(jù)舊數(shù)據(jù)的userID查找用戶的原始位置信息，對于原位置信息不存在的用戶，執(zhí)行插入操作，對于原位置信息已經(jīng)存在的用戶，將舊數(shù)據(jù)加入到緩存中，再刪除舊數(shù)據(jù)，插入新數(shù)據(jù)。數(shù)據(jù)導(dǎo)出需要將bucket中的數(shù)據(jù)和緩存中的數(shù)據(jù)都導(dǎo)出文件系統(tǒng)中。

3 系統(tǒng)演示

3.1 實驗環(huán)境與數(shù)據(jù)

演示系統(tǒng)的環(huán)境配置：一臺Linux系統(tǒng)的主機用于完成數(shù)據(jù)更新及連續(xù)區(qū)域查詢?nèi)蝿?wù)，機器的配置如下：四顆Dual-Core AMD OpteronTM Processor 865 CPU，頻率1.8 GHz，內(nèi)存32 GB，硬盤900 GB，Ubuntu Server 64 bit 10.04.4 LTS操作系統(tǒng)。另有三臺主機用于實現(xiàn)數(shù)據(jù)的分布式永久存儲.搭建有基于Hadoop的MAP-REDUCE并行計算環(huán)境。

采用兩組數(shù)據(jù)對系統(tǒng)的功能及性能進行測試，第一組為真實的移動信令數(shù)據(jù)，第二組為一個公開的移動對象軌跡生成程序MOTO生成的GPS數(shù)據(jù)，利用該程序可以生成較大規(guī)模的數(shù)據(jù)。數(shù)據(jù)集的具體信息如表1所示

3.2區(qū)域查詢及個體位置查詢

本系統(tǒng)通過請求處理模塊處理應(yīng)用發(fā)送來的http查詢請求，并將結(jié)果封裝為JSON格式返回。上層應(yīng)用僅需解析JSON數(shù)據(jù)，即可使用查詢結(jié)果.為了將結(jié)果進行更好的展示，設(shè)計了查詢結(jié)果的顯示界面。

結(jié)果的顯示分為兩個部分，地圖一側(cè)，用紅點標注用戶的位置，另一側(cè)的表格中顯示包括區(qū)域ID、用戶ID、位置坐標及時間戳等詳細信息.這些信息隨著新的時空數(shù)據(jù)的到來實時進行更新。

3.3數(shù)據(jù)導(dǎo)出功能的配置及控制

本文實現(xiàn)可配置可控制的數(shù)據(jù)導(dǎo)出服務(wù).可以通過向定時導(dǎo)出觸發(fā)器發(fā)送命令配置URL地址，文件在文件系統(tǒng)中的路徑、導(dǎo)出功能的時間間隔，同時可以控制導(dǎo)出觸發(fā)器的啟動、暫停及恢復(fù)。

4 總結(jié)

本文介紹了一種面向移動對象的連續(xù)區(qū)域查詢服務(wù)系統(tǒng)，它實現(xiàn)了對時空數(shù)據(jù)的連續(xù)區(qū)域查詢，并支持可配置、可操縱的定時導(dǎo)出功能.針對時空數(shù)據(jù)的特點，設(shè)計數(shù)據(jù)的存儲結(jié)構(gòu)，建立多維度索引，采用先查詢再處理更新的策略，以實現(xiàn)準確、高效的區(qū)域查詢.并通過多組實驗對系統(tǒng)的功能及性能進行了展示。

參考文獻

[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-），女，湖北省鄂州市人，當(dāng)前職務(wù)：業(yè)務(wù)經(jīng)理，學(xué)歷：碩士，研究方向：數(shù)據(jù)挖掘。