黃鑫玉 景鵬

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

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

隨著時(shí)空數(shù)據(jù)的迅猛增加，基于時(shí)空數(shù)據(jù)的數(shù)據(jù)挖掘應(yīng)用越來越成為研究的熱點(diǎn)，需要提供高效、精準(zhǔn)的數(shù)據(jù)查詢、更新及存儲策略.傳統(tǒng)方法不能滿足這些要求，主要體現(xiàn)在三個(gè)方面：首先，為適應(yīng)多維度的查詢需求，需要在多個(gè)維度上建立索引，以實(shí)現(xiàn)高效的查詢;其次，需要針對時(shí)空數(shù)據(jù)海量及高更新頻率的特點(diǎn)，設(shè)計(jì)高效、準(zhǔn)確的連續(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)有以下特點(diǎn)：

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

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

3）實(shí)現(xiàn)可配置、可操控的定時(shí)導(dǎo)出功能，定期將更新的數(shù)據(jù)存儲至分布式文件系統(tǒng)中永久存儲，以保存數(shù)據(jù)用于其他的基于時(shí)空數(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ù)層：負(fù)責(zé)管理系統(tǒng)中的時(shí)空數(shù)據(jù)，包括管理內(nèi)存中數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)和用于永久存儲時(shí)空數(shù)據(jù)的分布式數(shù)據(jù)文件存儲系統(tǒng)（HDFS）兩個(gè)部分。

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

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

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

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

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

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

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

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

文件系統(tǒng)中需要存儲所有的時(shí)空數(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 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

演示系統(tǒng)的環(huán)境配置：一臺Linux系統(tǒng)的主機(jī)用于完成數(shù)據(jù)更新及連續(xù)區(qū)域查詢?nèi)蝿?wù)，機(jī)器的配置如下：四顆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)。另有三臺主機(jī)用于實(shí)現(xiàn)數(shù)據(jù)的分布式永久存儲.搭建有基于Hadoop的MAP-REDUCE并行計(jì)算環(huán)境。

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

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

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

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

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

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

4 總結(jié)

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

參考文獻(xiàn)

[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ù)挖掘。