趙卓峰,丁維龍,張　帥

(1.北方工業(yè)大學(xué)云計(jì)算研究中心,北京 100144;2.大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室,北京 100144)

?

海量車(chē)牌識(shí)別數(shù)據(jù)集上基于時(shí)空劃分的旅行時(shí)間計(jì)算方法

趙卓峰1,2,丁維龍1,2,張帥1

(1.北方工業(yè)大學(xué)云計(jì)算研究中心,北京 100144;2.大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室,北京 100144)

城市路段旅行時(shí)間計(jì)算是智能交通領(lǐng)域的一個(gè)研究熱點(diǎn).車(chē)牌識(shí)別數(shù)據(jù)作為近年來(lái)新興的一種針對(duì)城市道路行駛車(chē)輛的實(shí)時(shí)監(jiān)測(cè)數(shù)據(jù),具有持續(xù)生成且數(shù)據(jù)量大、時(shí)間空間相關(guān)等特性.為了利用車(chē)牌識(shí)別數(shù)據(jù)集進(jìn)行高效、準(zhǔn)確的旅行時(shí)間計(jì)算,給出了基于車(chē)牌識(shí)別數(shù)據(jù)集的旅行時(shí)間計(jì)算定義,在此基礎(chǔ)上提出一種基于時(shí)空劃分的流水線式并行計(jì)算模型,并給出了該模型基于實(shí)時(shí)MapReduce的實(shí)現(xiàn).通過(guò)一組基于海量真實(shí)車(chē)牌識(shí)別數(shù)據(jù)集的實(shí)驗(yàn)表明,本文方法在億級(jí)車(chē)牌識(shí)別數(shù)據(jù)集上的旅行時(shí)間計(jì)算性能方面相對(duì)于直接基于Hadoop的實(shí)現(xiàn)可以提高3倍以上,同時(shí)具有適合細(xì)粒度劃分及受路網(wǎng)規(guī)模影響小的特點(diǎn).

旅行時(shí)間;時(shí)空劃分;流水線并行;實(shí)時(shí)MapReduce;車(chē)牌識(shí)別數(shù)據(jù)

1　引言

路段旅行時(shí)間作為城市交通出行信息的關(guān)鍵指標(biāo),是智能交通系統(tǒng)的重要基礎(chǔ),對(duì)其的研究一直是智能交通領(lǐng)域的熱點(diǎn).城市路段旅行時(shí)間可以直接用來(lái)評(píng)判城市道路的運(yùn)行狀況和擁堵水平,有效的旅行時(shí)間監(jiān)測(cè)與分析也可以為城市路網(wǎng)規(guī)劃、城市道路交通管理與控制、公眾出行路線選擇提供合理依據(jù).

以往,路段旅行時(shí)間主要采用基于樣本車(chē)輛監(jiān)測(cè)數(shù)據(jù)的測(cè)算方式,即采用樣本車(chē)輛的旅行時(shí)間來(lái)測(cè)算相關(guān)道路的旅行時(shí)間[1].目前,樣本車(chē)輛監(jiān)測(cè)數(shù)據(jù)的采集主要采用基于浮動(dòng)車(chē)的數(shù)據(jù)采集方式.浮動(dòng)車(chē)一般是指安裝了車(chē)載GPS定位裝置并行駛在城市主干道上的公交汽車(chē)和出租車(chē),它可以通過(guò)車(chē)載GPS和無(wú)線通信接口周期性的采集車(chē)輛行駛數(shù)據(jù)[2].但由于浮動(dòng)車(chē)數(shù)據(jù)涉及的樣本主要為特種車(chē)輛,其由于均具有特定的出行行為,因此會(huì)造成數(shù)據(jù)覆蓋面有限的問(wèn)題,同時(shí)GPS數(shù)據(jù)往往與道路路段關(guān)系不能直接匹配,數(shù)據(jù)質(zhì)量也缺乏保障,因此在計(jì)算路段旅行時(shí)間上存在一定的不足.

車(chē)牌識(shí)別技術(shù)是近年來(lái)新興的一種城市通行車(chē)輛信息采集技術(shù),它通過(guò)對(duì)部署在城市道路的攝像頭所采集的車(chē)輛圖像信息進(jìn)行識(shí)別來(lái)提取車(chē)輛的車(chē)牌信息,并在此基礎(chǔ)上形成包含車(chē)輛標(biāo)識(shí)、出現(xiàn)地點(diǎn)、時(shí)間等內(nèi)容的車(chē)牌識(shí)別數(shù)據(jù).相比浮動(dòng)車(chē)等車(chē)輛信息采集技術(shù),基于車(chē)牌識(shí)別數(shù)據(jù)的車(chē)輛信息采集技術(shù)具有工作連續(xù)性強(qiáng)、數(shù)據(jù)與道路關(guān)系精確度高、檢測(cè)樣本量大、覆蓋車(chē)輛范圍廣等優(yōu)點(diǎn)[3].因此,基于車(chē)牌識(shí)別數(shù)據(jù)的旅行時(shí)間計(jì)算成為當(dāng)前測(cè)算路段旅行時(shí)間的一個(gè)新途徑,對(duì)其的研究具有重要的應(yīng)用價(jià)值和學(xué)術(shù)意義.

基于車(chē)牌識(shí)別數(shù)據(jù)的路段旅行時(shí)間計(jì)算包括兩種情況,即基于實(shí)時(shí)車(chē)牌識(shí)別數(shù)據(jù)的實(shí)時(shí)旅行時(shí)間計(jì)算和基于歷史車(chē)牌識(shí)別數(shù)據(jù)的歷史旅行時(shí)間計(jì)算.其中,基于實(shí)時(shí)車(chē)牌識(shí)別數(shù)據(jù)的實(shí)時(shí)旅行時(shí)間計(jì)算按照一定的周期利用實(shí)時(shí)接收到車(chē)牌識(shí)別數(shù)據(jù)計(jì)算城市道路不同路段的實(shí)時(shí)旅行時(shí)間,其結(jié)果可用于實(shí)時(shí)路況信息服務(wù);基于歷史車(chē)牌識(shí)別數(shù)據(jù)的歷史旅行時(shí)間計(jì)算則主要針對(duì)已積累大量歷史車(chē)牌識(shí)別數(shù)據(jù)而尚未被利用計(jì)算旅行時(shí)間的情況,來(lái)批量處理得到城市道路不同路段歷史上的旅行時(shí)間數(shù)據(jù),其結(jié)果可被用來(lái)支持對(duì)出行規(guī)律、道路擁堵特點(diǎn)等的分析.本文重點(diǎn)解決后一種情況的旅行時(shí)間計(jì)算問(wèn)題.

由于車(chē)牌識(shí)別數(shù)據(jù)來(lái)源于對(duì)城市道路行駛車(chē)輛的實(shí)時(shí)監(jiān)測(cè),其包含車(chē)輛標(biāo)識(shí)、監(jiān)測(cè)時(shí)間、地理位置等時(shí)間、空間以及車(chē)輛對(duì)象相關(guān)的信息,具有典型的時(shí)空相關(guān)、時(shí)序連續(xù)、位置可測(cè)的特征.此外,考慮到隨著車(chē)牌識(shí)別攝像頭在城市道路大范圍部署,車(chē)牌識(shí)別數(shù)據(jù)集的規(guī)模將大大超過(guò)傳統(tǒng)采樣方法獲得數(shù)據(jù)集的規(guī)模.當(dāng)前,一個(gè)大型城市部署的帶車(chē)牌識(shí)別數(shù)據(jù)的攝像頭可達(dá)到5000個(gè),假設(shè)高峰期每個(gè)攝像頭車(chē)牌識(shí)別數(shù)據(jù)的采集頻率可達(dá)1條/秒,若每天的交通高峰折算率按0.33計(jì),則一年將累積車(chē)輛識(shí)別數(shù)據(jù)記錄數(shù)超過(guò)500億條,數(shù)據(jù)存儲(chǔ)量超過(guò)2T.這些數(shù)據(jù)可構(gòu)成規(guī)模龐大的車(chē)牌識(shí)別數(shù)據(jù)集,僅對(duì)如此龐大的數(shù)據(jù)集進(jìn)行順序掃描(按80M/s的速度計(jì))也需要近7個(gè)小時(shí).為此,為滿足基于車(chē)牌識(shí)別數(shù)據(jù)的路段旅行時(shí)間計(jì)算需求,迫切需要設(shè)計(jì)一種針對(duì)海量車(chē)牌識(shí)別數(shù)據(jù)集上旅行時(shí)間計(jì)算的高效方法.

本文主要針對(duì)海量車(chē)牌識(shí)別數(shù)據(jù)集上的路段旅行時(shí)間計(jì)算的需求,給出了基于車(chē)牌識(shí)別數(shù)據(jù)的路段旅行時(shí)間形式化定義,并按照該定義分析了海量車(chē)牌識(shí)別數(shù)據(jù)集上路段旅行時(shí)間計(jì)算的關(guān)鍵問(wèn)題.在此基礎(chǔ)上,利用車(chē)牌識(shí)別數(shù)據(jù)的時(shí)空相關(guān)、對(duì)象相關(guān)等特征,采取數(shù)據(jù)劃分和任務(wù)流水的思路,提出一種基于時(shí)空劃分的流水線式旅行時(shí)間并行計(jì)算模型,并給出了一種基于改進(jìn)的MapReduce模型的計(jì)算實(shí)現(xiàn)和基于真實(shí)車(chē)牌識(shí)別數(shù)據(jù)集的驗(yàn)證分析.

2　路段旅行時(shí)間計(jì)算問(wèn)題

2.1問(wèn)題定義

定義1受測(cè)道路路網(wǎng).受測(cè)道路路網(wǎng)指由部署在城市道路上監(jiān)測(cè)點(diǎn)及其之間涉及的路段構(gòu)成的道路結(jié)構(gòu),可表示為R=(N,S),其中N為道路監(jiān)測(cè)點(diǎn)集合,S為路段集合.

定義3路段.路段指連接兩個(gè)相鄰監(jiān)測(cè)點(diǎn)之間的一條道路,路段si可表示為兩個(gè)監(jiān)測(cè)點(diǎn)的有序?qū)?np,nq>,np和nq分別表示路段si的起始點(diǎn)和終止點(diǎn),si∈S.

時(shí)間區(qū)間δj指用于度量路段旅行時(shí)間的一個(gè)時(shí)間跨度,我們可以將給定的待測(cè)時(shí)間范圍內(nèi)按照時(shí)間周期劃分為不同的時(shí)間區(qū)間δj,所有的時(shí)間區(qū)間集合為δ.在現(xiàn)有的旅行時(shí)間研究中,一般選取每1小時(shí)、每15分鐘和每5分鐘三個(gè)時(shí)間周期進(jìn)行時(shí)間區(qū)間劃分以對(duì)路段旅行時(shí)間進(jìn)行度量[1].例如每15分鐘的時(shí)間周期中,將對(duì)0:00-0:15、0:15-0:20、……、23:45-24:00等一天中的96個(gè)時(shí)間區(qū)間進(jìn)行旅行時(shí)間計(jì)算.

根據(jù)單車(chē)旅行時(shí)間獲得路段旅行時(shí)間還可以通過(guò)求平均值或加權(quán)平均值的方法來(lái)計(jì)算,但這里考慮到實(shí)際車(chē)輛出行中的一些特殊因素,如車(chē)輛在路段中的臨時(shí)停留或路邊停車(chē)以及套牌車(chē)等,這些因素下得到的單車(chē)旅行時(shí)間都會(huì)有較大的失真,并會(huì)給平均值方法計(jì)算路段旅行時(shí)間的準(zhǔn)確性帶來(lái)一定的影響.為此,這里我們選擇中位數(shù)方法來(lái)獲得路段旅行時(shí)間,以屏蔽不合理的單車(chē)旅行時(shí)間帶來(lái)的影響.此外,這種方法下,路段旅行時(shí)間計(jì)算一般要求在特定時(shí)間區(qū)間內(nèi)通過(guò)該路段的車(chē)輛數(shù)(即計(jì)算得到的單車(chē)旅行時(shí)間數(shù))大于5輛,以避免由于車(chē)輛數(shù)過(guò)少而造成的中位數(shù)代表的旅行時(shí)間不精確問(wèn)題.在單車(chē)旅行時(shí)間數(shù)小于5條時(shí),將直接將前一時(shí)間周期計(jì)算得到的路段旅行時(shí)間作為當(dāng)前實(shí)際周期的路段旅行時(shí)間.

根據(jù)上述定義可以看出,相對(duì)于傳統(tǒng)基于浮動(dòng)車(chē)采樣數(shù)據(jù)的旅行時(shí)間計(jì)算方法需要進(jìn)行路段復(fù)合計(jì)算以及建立區(qū)分擁堵、非擁堵和路口排隊(duì)等情況的計(jì)算模型[4],基于車(chē)牌識(shí)別數(shù)據(jù)的路段旅行時(shí)間計(jì)算模型則相對(duì)簡(jiǎn)單和直觀,只是在路段所采集的車(chē)牌識(shí)別數(shù)據(jù)較少時(shí)可能存在一定的旅行時(shí)間計(jì)算誤差而不得不采取復(fù)制前一時(shí)間區(qū)間旅行時(shí)間的計(jì)算方式.實(shí)際上,在這種情況下,可以綜合浮動(dòng)車(chē)數(shù)據(jù)進(jìn)行旅行時(shí)間計(jì)算,而且此時(shí)由于路段車(chē)流量不大,不存在前述基于浮動(dòng)車(chē)采樣數(shù)據(jù)的旅行時(shí)間復(fù)雜計(jì)算情況.此外,基于車(chē)牌識(shí)別數(shù)據(jù)的路段旅行時(shí)間計(jì)算由于使用覆蓋范圍更廣的車(chē)牌識(shí)別數(shù)據(jù),相對(duì)與采樣性的浮動(dòng)車(chē)數(shù)據(jù),其數(shù)據(jù)規(guī)模會(huì)更大,因此如何在海量車(chē)牌識(shí)別數(shù)據(jù)集(億級(jí)數(shù)據(jù)記錄)基礎(chǔ)上計(jì)算符合上述定義的路段旅行時(shí)間成為一個(gè)亟待解決的關(guān)鍵問(wèn)題.

2.2問(wèn)題分析

如圖1所示,按照上述路段旅行時(shí)間計(jì)算定義,在計(jì)算時(shí)首先需要對(duì)車(chē)牌識(shí)別數(shù)據(jù)集中的所有車(chē)牌識(shí)別數(shù)據(jù)按照時(shí)間區(qū)間(假設(shè)有j個(gè)時(shí)間區(qū)間,如圖1橫坐標(biāo)δ1至δj,其中的點(diǎn)lix為一條車(chē)牌識(shí)別數(shù)據(jù))進(jìn)行劃分,對(duì)同一劃分中的數(shù)據(jù)(假設(shè)每個(gè)劃分中數(shù)據(jù)為k條)兩兩比對(duì),若兩條數(shù)據(jù)屬于同一輛車(chē)并且兩條數(shù)據(jù)中涉及的兩個(gè)監(jiān)測(cè)點(diǎn)(如圖縱坐標(biāo)n1和n2)是受測(cè)道路路網(wǎng)中的路段,則求出并保存該路段在該歷史時(shí)間區(qū)間的單車(chē)旅行時(shí)間(如圖1中l(wèi)11、l22等為同一車(chē)牌的數(shù)據(jù),即同一車(chē)輛);最后,再對(duì)所有路段的不同時(shí)間區(qū)間上全部單車(chē)旅行時(shí)間取中位數(shù),得到最終道路歷史旅行時(shí)間結(jié)果集,該算法的復(fù)雜度為O(j×k2).在實(shí)際情況中,當(dāng)需要計(jì)算一個(gè)大型城市一年的歷史數(shù)據(jù)(車(chē)牌識(shí)別數(shù)據(jù)上億甚至百億)、計(jì)算時(shí)間周期為5分鐘時(shí),j為105120,k最大約為150萬(wàn)左右.此外,上述計(jì)算還受到路網(wǎng)中路段數(shù)量的影響,當(dāng)受測(cè)路網(wǎng)中路段數(shù)達(dá)到1000時(shí),一年的路段旅行時(shí)間計(jì)算結(jié)果集數(shù)據(jù)條目數(shù)也將過(guò)億.輸入、緩存及產(chǎn)生如此大規(guī)模數(shù)據(jù),都將使得旅行時(shí)間計(jì)算的執(zhí)行時(shí)間將急劇增加.

為提高如上所述規(guī)模的車(chē)牌識(shí)別數(shù)據(jù)集基礎(chǔ)上路段旅行時(shí)間計(jì)算的性能,需要解決以下兩方面關(guān)鍵問(wèn)題:

(1)如何根據(jù)前述路段旅行時(shí)間問(wèn)題的定義并結(jié)合具有時(shí)空相關(guān)等特性的車(chē)牌識(shí)別數(shù)據(jù)特征設(shè)計(jì)旅行時(shí)間計(jì)算的并行化模式；(2)如何進(jìn)行有效的車(chē)牌識(shí)別數(shù)據(jù)劃分,以便于將原始數(shù)據(jù)和中間結(jié)果動(dòng)態(tài)分布到不同節(jié)點(diǎn)上處理,并可以盡量避免旅行時(shí)間計(jì)算過(guò)程中跨節(jié)點(diǎn)的數(shù)據(jù)訪問(wèn).

針對(duì)上述問(wèn)題,本文利用車(chē)牌識(shí)別數(shù)據(jù)的時(shí)空相關(guān)、對(duì)象相關(guān)等特征,采取數(shù)據(jù)劃分和任務(wù)流水的思路,提出一種基于時(shí)空劃分的流水線式并行處理模型來(lái)解決基于海量車(chē)牌識(shí)別數(shù)據(jù)的路段旅行時(shí)間高效計(jì)算問(wèn)題.

3　基于時(shí)空劃分的流水線式旅行時(shí)間并行計(jì)算模型

3.1模型描述

根據(jù)前文對(duì)路段旅行時(shí)間計(jì)算的分析可以看出,該計(jì)算的處理邏輯主要是針對(duì)不同時(shí)間區(qū)間的車(chē)牌識(shí)別數(shù)據(jù),先計(jì)算所有路段上的單車(chē)旅行時(shí)間再通過(guò)求單車(chē)旅行時(shí)間中位數(shù)來(lái)計(jì)算路段旅行時(shí)間.基于此,可以從時(shí)間和空間兩個(gè)角度來(lái)對(duì)原始車(chē)牌識(shí)別數(shù)據(jù)進(jìn)行劃分與組織,而計(jì)算過(guò)程可以區(qū)分為相關(guān)車(chē)牌識(shí)別數(shù)據(jù)加載、單車(chē)旅行時(shí)間計(jì)算、單車(chē)旅行時(shí)間中位數(shù)計(jì)算三個(gè)階段的子任務(wù).同時(shí),根據(jù)旅行時(shí)間計(jì)算定義可以看出,在具體計(jì)算過(guò)程中需要進(jìn)行車(chē)輛對(duì)象和空間關(guān)系(即一條路段所涉及的兩個(gè)監(jiān)測(cè)點(diǎn))的判定比對(duì).而為了減少后續(xù)分布式旅行時(shí)間計(jì)算過(guò)程中跨節(jié)點(diǎn)的數(shù)據(jù)傳輸,為此要求在數(shù)據(jù)劃分時(shí)能夠減少跨數(shù)據(jù)劃分分區(qū)的計(jì)算,特別是頂層的數(shù)據(jù)劃分方法應(yīng)盡量避免跨分區(qū)的計(jì)算.因此,在這里,針對(duì)旅行時(shí)間計(jì)算涉及的時(shí)間、空間和對(duì)象三個(gè)維度,在車(chē)牌識(shí)別數(shù)據(jù)劃分時(shí)應(yīng)首先從與后續(xù)單車(chē)旅行時(shí)間計(jì)算等無(wú)關(guān)的時(shí)間維度進(jìn)行劃分,以確保據(jù)此分布到各計(jì)算節(jié)點(diǎn)的數(shù)據(jù)不必為了相關(guān)計(jì)算而進(jìn)行跨節(jié)點(diǎn)的傳輸.

按照上述認(rèn)識(shí),我們?cè)O(shè)計(jì)了如圖2所示的基于時(shí)空劃分的流水線式路段旅行時(shí)間并行計(jì)算模型.在該模型中,車(chē)牌識(shí)別數(shù)據(jù)首先可以劃分為時(shí)間維上區(qū)分的數(shù)據(jù)組,每組數(shù)據(jù)都包含一定數(shù)量的不同時(shí)間區(qū)間的數(shù)據(jù)子集;進(jìn)一步某一時(shí)間區(qū)間的數(shù)據(jù)子集還可以根據(jù)所屬路段劃分為區(qū)域相關(guān)的數(shù)據(jù)子集,區(qū)域內(nèi)數(shù)據(jù)可以進(jìn)一步按照車(chē)輛數(shù)據(jù)對(duì)象進(jìn)行組織;在上述兩級(jí)數(shù)據(jù)劃分基礎(chǔ)上,由于相關(guān)車(chē)牌識(shí)別數(shù)據(jù)加載、單車(chē)旅行時(shí)間計(jì)算、單車(chē)旅行時(shí)間中位數(shù)計(jì)算三個(gè)子任務(wù)的計(jì)算結(jié)果間不具有直接的因果相關(guān)性,即每個(gè)子任務(wù)僅依賴于特定的中間結(jié)果,而不一定必須是其上游任務(wù)的輸出結(jié)果.因此路段旅行時(shí)間的計(jì)算可以對(duì)此三個(gè)子任務(wù)進(jìn)行階段化劃分,從而可以以流水線方式針對(duì)不同劃分的數(shù)據(jù)子集來(lái)完成路段旅行時(shí)間計(jì)算.此外,在按區(qū)域劃分?jǐn)?shù)據(jù)時(shí)除了先按路段劃分再按車(chē)輛對(duì)象組織外,還可以選擇先按車(chē)輛對(duì)象劃分再按路段組織,在文章后續(xù)部分我們將通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證這兩種劃分方式下旅行時(shí)間計(jì)算性能方面的差異并分析相關(guān)原因.

上述模型從總體層面看遵循了單控制流多數(shù)據(jù)流(SPMD,singleprocessandmultipledata)的并行模式[5],而在數(shù)據(jù)并行方面結(jié)合車(chē)牌識(shí)別數(shù)據(jù)的時(shí)空特征可以進(jìn)一步從時(shí)間維和空間維兩級(jí)劃分,在計(jì)算任務(wù)方面則可以利用旅行時(shí)間計(jì)算步驟的細(xì)分形成流水線式并行.

3.2基于實(shí)時(shí)MapReduce的模型實(shí)現(xiàn)

為實(shí)現(xiàn)上述基于時(shí)空劃分的流水線式路段旅行時(shí)間并行處理模型,采用我們之前提出的實(shí)時(shí)MapReduce計(jì)算模型[6]思路并在其基礎(chǔ)上來(lái)實(shí)現(xiàn)時(shí)空劃分的數(shù)據(jù)并行化及流水線式的計(jì)算任務(wù)并行化.實(shí)時(shí)MapRedcue計(jì)算模型的核心思想是通過(guò)在傳統(tǒng)MapReduce實(shí)現(xiàn)中引入中間結(jié)果的緩存機(jī)制和Map及Reduce任務(wù)的流水線式處理來(lái)提高M(jìn)apReduce模型的處理性能.

在本文中,我們按照上述時(shí)空劃分的流水線并行計(jì)算模型,通過(guò)設(shè)計(jì)適于時(shí)空劃分處理的分布式HashB樹(shù)緩存數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)化本地中間結(jié)果的高并發(fā)讀寫(xiě)性能,并進(jìn)一步通過(guò)定義路段旅行時(shí)間計(jì)算的流水線處理階段來(lái)實(shí)現(xiàn)階段化的流水線式MapReduce處理以提高旅行時(shí)間計(jì)算性能.

具體的模型實(shí)現(xiàn)機(jī)制如下:

(1)基于分布式HashB樹(shù)的數(shù)據(jù)緩存

對(duì)于旅行時(shí)間計(jì)算中涉及的海量歷史車(chē)牌識(shí)別數(shù)據(jù),我們采用HashB樹(shù)來(lái)進(jìn)行內(nèi)存中的緩存.在該結(jié)構(gòu)中,首先為支持時(shí)間區(qū)間劃分采用時(shí)間區(qū)間作為Key,相同時(shí)間區(qū)間的車(chē)牌識(shí)別數(shù)據(jù)在Hash表的同一項(xiàng)中用B樹(shù)組織;其次,監(jiān)測(cè)點(diǎn)作為空間劃分基礎(chǔ)并用來(lái)組織最終的車(chē)牌識(shí)別數(shù)據(jù),每個(gè)監(jiān)測(cè)點(diǎn)的車(chē)牌識(shí)別數(shù)據(jù)在B樹(shù)的葉節(jié)點(diǎn)用鏈表按照時(shí)間順序進(jìn)行組織.

對(duì)于計(jì)算過(guò)程中產(chǎn)生的大量單車(chē)旅行時(shí)間計(jì)算結(jié)果,我們同樣采用類(lèi)似的結(jié)構(gòu)來(lái)進(jìn)行緩存,主要區(qū)別就是將上述HashB樹(shù)中葉節(jié)點(diǎn)由監(jiān)測(cè)點(diǎn)識(shí)別數(shù)據(jù)替換為特定車(chē)輛在不同路段的旅行時(shí)間鏈表.

此外,在緩存機(jī)制方面,進(jìn)一步還可利用B樹(shù)在平均搜索性能和平衡性方面的特征,使用多路搜索方式提升了B樹(shù)的并發(fā)查詢性能,并且利用讀寫(xiě)開(kāi)銷(xiāo)估算和緩沖區(qū)信息改造外存SSTable文件讀寫(xiě)策略和內(nèi)外存替換機(jī)制.由于篇幅所限,更多的計(jì)算中間結(jié)果緩存機(jī)制細(xì)節(jié)可以參見(jiàn)我們之前在文獻(xiàn)[7]中給出的介紹.

(2)階段化流水線處理

針對(duì)旅行時(shí)間計(jì)算處理邏輯中涉及的相關(guān)車(chē)牌識(shí)別數(shù)據(jù)加載、單車(chē)旅行時(shí)間計(jì)算、單車(chē)旅行時(shí)間中位數(shù)查找三個(gè)子任務(wù),可采用兩次MapReduce迭代以及Map和Reduce階段的流水線控制機(jī)制來(lái)實(shí)現(xiàn)階段化流水線處理.其中,第一次MapReduce處理中的Map函數(shù)完成車(chē)牌識(shí)別數(shù)據(jù)的劃分讀入和如前所述的數(shù)據(jù)結(jié)構(gòu)組織,得到形如的鍵值對(duì),Reduce函數(shù)根據(jù)路段信息對(duì)中間結(jié)果按照車(chē)牌號(hào)進(jìn)行重組織得到形為的鍵值對(duì);第二次MapReduce處理中的Map函數(shù)僅計(jì)算單車(chē)路段旅行時(shí)間而不做數(shù)據(jù)變換,Reduce函數(shù)進(jìn)行所有單車(chē)旅行時(shí)間中位數(shù)查找,最后得到鍵值對(duì).一個(gè)路段旅行時(shí)間計(jì)算結(jié)果示例形如<201310020830+LD0014[JCD06,JCD07],360>,該示例表示在2013年10月2號(hào)8點(diǎn)30分到8點(diǎn)45分的時(shí)間區(qū)間,0014號(hào)路段(即監(jiān)測(cè)點(diǎn)JCD06到監(jiān)測(cè)點(diǎn)JCD07的路段)的旅行時(shí)間為360s.通過(guò)上述描述可以看到,基于區(qū)域路段的劃分方式下旅行時(shí)間計(jì)算通過(guò)兩次循環(huán)對(duì)監(jiān)測(cè)點(diǎn)Map列表中的key值進(jìn)行兩兩比對(duì),判斷是否為路段基礎(chǔ)表中數(shù)據(jù).然后通過(guò)對(duì)于路段兩個(gè)上下游監(jiān)測(cè)點(diǎn)對(duì)應(yīng)的過(guò)車(chē)記錄列表進(jìn)行對(duì)比,找出相同車(chē)輛及其通過(guò)的時(shí)間,并將得到的屬性值整合成的鍵值對(duì)形式,其算法時(shí)間復(fù)雜度為O(n×m2),其中m為全路網(wǎng)中路段監(jiān)測(cè)點(diǎn)數(shù)目,n為一個(gè)時(shí)間區(qū)間下通過(guò)一個(gè)監(jiān)測(cè)點(diǎn)的車(chē)輛數(shù).

4　實(shí)驗(yàn)與分析

4.1實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)環(huán)境采用的是在五臺(tái)服務(wù)器上搭建的集群環(huán)境,并在其上部署我們基于Hadoop擴(kuò)展了中間結(jié)果緩存和流水線處理機(jī)制后的路段旅行時(shí)間計(jì)算實(shí)現(xiàn).其中,Master節(jié)點(diǎn)配置為4核CPU、4G內(nèi)存,master節(jié)點(diǎn)同時(shí)也被當(dāng)作計(jì)算節(jié)點(diǎn);另外四臺(tái)Slave節(jié)點(diǎn)配置為2核CPU、4G內(nèi)存,作為計(jì)算節(jié)點(diǎn).此外,每臺(tái)服務(wù)器的有效容量為80G,集群總存儲(chǔ)容量為400G.實(shí)驗(yàn)中采用的數(shù)據(jù)為北京市一千多個(gè)帶識(shí)別功能的攝像頭2012-10-17到2013-01-04這80天采集到的真實(shí)車(chē)牌識(shí)別數(shù)據(jù),總數(shù)據(jù)量近5億條.

為了從性能對(duì)比、關(guān)鍵參數(shù)影響和擴(kuò)展性三方面對(duì)本文提出的旅行時(shí)間計(jì)算方法進(jìn)行驗(yàn)證分析,以及考察旅行時(shí)間計(jì)算中路段數(shù)目(代表受測(cè)路網(wǎng)規(guī)模)、車(chē)牌識(shí)別數(shù)據(jù)記錄數(shù)和Hadoop集群節(jié)點(diǎn)數(shù)三個(gè)參數(shù)對(duì)旅行時(shí)間計(jì)算的不同影響,我們?cè)O(shè)計(jì)了如下的一組實(shí)驗(yàn):實(shí)驗(yàn)1考察在5個(gè)計(jì)算節(jié)點(diǎn)、路段數(shù)目固定為210的情況下,分別測(cè)試從5000萬(wàn)到4億等不同數(shù)量的車(chē)牌識(shí)別數(shù)據(jù)集下5分鐘、15分鐘和1小時(shí)三個(gè)時(shí)間周期路段旅行時(shí)間計(jì)算性能情況.并選取直接基于Hadoop實(shí)現(xiàn)的旅行時(shí)間計(jì)算方法(LMR)[8]作為比較對(duì)象,與本文方法(CMR)進(jìn)行性能比較.

實(shí)驗(yàn)2對(duì)兩種數(shù)據(jù)二次劃分方式進(jìn)行對(duì)比,(1)CMR方法中最終采取的先按路段劃分再按車(chē)輛對(duì)象組織方式(記為RegionList方式),(2)先按車(chē)輛對(duì)象劃分再按路段組織方式(記為VehicleList方式).實(shí)驗(yàn)在5個(gè)計(jì)算節(jié)點(diǎn)、路段數(shù)目不變的情況下,通過(guò)輸入不同數(shù)量的車(chē)牌識(shí)別數(shù)據(jù),考察兩種劃分方式下路段旅行時(shí)間計(jì)算性能差異.

實(shí)驗(yàn)3考察受測(cè)路網(wǎng)中的路段數(shù)目對(duì)路段旅行時(shí)間計(jì)算方法性能的影響.選取20天的車(chē)牌識(shí)別數(shù)據(jù)(約1億條)作為原始計(jì)算數(shù)據(jù)集,在5個(gè)計(jì)算節(jié)點(diǎn)下,對(duì)受測(cè)路網(wǎng)中的路段數(shù)目從10到210進(jìn)行調(diào)整,并分別測(cè)試5分鐘、15分鐘和1小時(shí)三個(gè)時(shí)間周期下的計(jì)算性能情況.

4.2實(shí)驗(yàn)結(jié)果分析

(1)計(jì)算性能對(duì)比分析

通過(guò)實(shí)驗(yàn)1得到如圖3所示結(jié)果.從圖中可看出,隨著參與計(jì)算的車(chē)牌識(shí)別數(shù)據(jù)集數(shù)據(jù)量的增加,兩種計(jì)算方法的計(jì)算時(shí)間均呈線性增加.但CMR方法在計(jì)算效率上比LMR方法有較高的提升,并且CMR方法受時(shí)間周期差異的影響比LMR方法小很多,5分鐘、15分鐘和1小時(shí)三個(gè)不同時(shí)間周期下計(jì)算時(shí)間的差異均在100秒以內(nèi).

此外,從圖中還可以看到,LMR方法在計(jì)算時(shí)間周期越短(即時(shí)間段劃分粒度越細(xì))的情況下,計(jì)算時(shí)間越長(zhǎng),5分鐘周期下的計(jì)算時(shí)間最長(zhǎng),而CMR方法恰好相反,在計(jì)算時(shí)間周期變短的情況下,計(jì)算時(shí)間反而會(huì)略微減少,5分鐘周期下的計(jì)算時(shí)間最短.究其原因,主要因?yàn)楫?dāng)計(jì)算時(shí)間周期較小時(shí),需要計(jì)算旅行時(shí)間的時(shí)間區(qū)間數(shù)量會(huì)大幅增加,使得Hadoop運(yùn)行態(tài)中的Map和Reduce任務(wù)大增并帶來(lái)較大的任務(wù)執(zhí)行調(diào)度代價(jià),傳統(tǒng)LMR方法由于未根據(jù)車(chē)牌識(shí)別數(shù)據(jù)進(jìn)行劃分優(yōu)化,執(zhí)行中需要大量的Map和Reduce任務(wù)間的同步等待,從而使得小時(shí)間周期下的計(jì)算時(shí)間變長(zhǎng).而CMR方法通過(guò)時(shí)空劃分和流水線執(zhí)行避免了無(wú)必要Map和Reduce任務(wù)間由于數(shù)據(jù)依賴的同步等待,同時(shí)優(yōu)化了執(zhí)行效率,這樣單個(gè)Map和Reduce任務(wù)一次處理的數(shù)據(jù)量(受時(shí)間區(qū)間大小影響)成為影響計(jì)算時(shí)間的主要因素,因此使得短時(shí)間周期下的計(jì)算時(shí)間反而變短.由此可見(jiàn),CMR方法更能適應(yīng)細(xì)粒度時(shí)間周期的旅行時(shí)間計(jì)算.

(2)不同數(shù)據(jù)劃分方式的對(duì)比分析

通過(guò)圖4所示的實(shí)驗(yàn)2結(jié)果可以看出,兩種不同的數(shù)據(jù)劃分方法下的旅行計(jì)算時(shí)間均隨數(shù)據(jù)量增加線性增長(zhǎng),但是隨著數(shù)據(jù)量增加,在計(jì)算效率上先按路段劃分再按車(chē)輛對(duì)象組織(RegionList)的劃分方式比先按車(chē)輛對(duì)象劃分再按路段組織(VehicleList)的劃分方式表現(xiàn)出更好的性能.通過(guò)分析可以看出,在單車(chē)旅行時(shí)間求解步驟中的第一種劃分方式的計(jì)算復(fù)雜度主要依賴全路網(wǎng)中監(jiān)測(cè)點(diǎn)數(shù)目和一個(gè)時(shí)間區(qū)間下通過(guò)一個(gè)監(jiān)測(cè)點(diǎn)的車(chē)輛數(shù),而第二種劃分方式的計(jì)算復(fù)雜度則依賴于一個(gè)時(shí)間區(qū)間下一輛車(chē)經(jīng)過(guò)檢測(cè)點(diǎn)數(shù)目和全路網(wǎng)中車(chē)輛數(shù).由于實(shí)際情況中,全路網(wǎng)中車(chē)輛數(shù)的量級(jí)明顯大于其它參數(shù)的量級(jí),因此先按路段劃分再按車(chē)輛對(duì)象組織的區(qū)域劃分方式能更好的適應(yīng)路網(wǎng)中存在大規(guī)模車(chē)輛的情況.

(3)關(guān)鍵參數(shù)影響對(duì)比分析

由實(shí)驗(yàn)3我們得到如圖5所示的實(shí)驗(yàn)結(jié)果.從實(shí)驗(yàn)結(jié)果可看出,隨著受測(cè)路網(wǎng)中路段數(shù)目的增加,本文CMR計(jì)算方法的計(jì)算時(shí)間基本平滑,而LMR方法則在路段數(shù)增大時(shí)表現(xiàn)出計(jì)算時(shí)間線性增長(zhǎng)的趨勢(shì).這表明CMR計(jì)算方法的計(jì)算性能基本不受路段數(shù)目的影響,當(dāng)我們?cè)黾邮軠y(cè)路網(wǎng)規(guī)模(即增加路段數(shù))時(shí),并不影響旅行時(shí)間計(jì)算的計(jì)算性能.其中的主要原因在于,路段數(shù)在旅行時(shí)間計(jì)算中主要影響是會(huì)增大計(jì)算中間結(jié)果的規(guī)模,CMR方法由于采用基于分布式Hash B樹(shù)緩存結(jié)構(gòu)優(yōu)化了中間結(jié)果的處理,因此其受路段數(shù)變化的影響較小.

5　相關(guān)工作

旅行時(shí)間計(jì)算一直是智能交通研究中的一個(gè)熱點(diǎn)問(wèn)題.文獻(xiàn)[3]利用十余個(gè)道路交叉口的車(chē)牌識(shí)別數(shù)據(jù),應(yīng)用假設(shè)檢驗(yàn)的方法研究城市快速路及主干道的旅行時(shí)間.然而上述工作使用的采樣數(shù)據(jù)僅為1小時(shí)內(nèi)數(shù)據(jù),數(shù)據(jù)量較小,在考慮城市所有路段旅行時(shí)間計(jì)算時(shí),這種分布估計(jì)方法很難適用.文獻(xiàn)[8]通過(guò)Hadoop實(shí)現(xiàn)了基于海量車(chē)牌識(shí)別數(shù)據(jù)的城市道路旅行時(shí)間實(shí)測(cè)計(jì)算,支持自定義路段集下不同時(shí)間區(qū)間的道路旅行時(shí)間計(jì)算.但該工作中并未根據(jù)車(chē)牌識(shí)別數(shù)據(jù)的時(shí)空特性進(jìn)行專門(mén)設(shè)計(jì),僅直接運(yùn)用Hadoop給出了旅行時(shí)間計(jì)算的樸素實(shí)現(xiàn).文獻(xiàn)[9]將MapReduce分布式計(jì)算框架應(yīng)用于道路交通流量統(tǒng)計(jì)計(jì)算中,證明了利用Hadoop技術(shù)進(jìn)行交通數(shù)據(jù)存儲(chǔ)和處理是合理、可行、高效的,但該工作僅適用于簡(jiǎn)單的數(shù)據(jù)統(tǒng)計(jì)計(jì)算,對(duì)于旅行時(shí)間計(jì)算這種需考慮到數(shù)據(jù)時(shí)空特性的計(jì)算還需對(duì)現(xiàn)有MapReduce模型進(jìn)行相應(yīng)修改才能提高計(jì)算效率.

近年來(lái),很多研究者根據(jù)不同應(yīng)用需求對(duì)MapReduce模型及其開(kāi)源實(shí)現(xiàn)Hadoop進(jìn)行改進(jìn),以適應(yīng)不同類(lèi)型大數(shù)據(jù)的處理需求.文獻(xiàn)[10]設(shè)計(jì)并實(shí)現(xiàn)了G-Hadoop,在此平臺(tái)上可以應(yīng)用MapReduce編程框架在多個(gè)集群上進(jìn)行并行計(jì)算.與本文思路相似,文獻(xiàn)[11]按照重用MapReduce處理過(guò)程中中間結(jié)果的思路設(shè)計(jì)了一種Hadoop擴(kuò)展實(shí)現(xiàn)的HaLoop,HaLoop提供了在MapReduce基礎(chǔ)上表達(dá)循環(huán)式處理的編程模型以及可保證多次循環(huán)中任務(wù)可以調(diào)度到同一節(jié)點(diǎn)的執(zhí)行調(diào)度器,基于這種設(shè)計(jì)MapReduce處理過(guò)程中的中間結(jié)果可以被緩存與重用.同樣,文獻(xiàn)[12]在集中式處理基礎(chǔ)上,設(shè)計(jì)了一個(gè)支持可擴(kuò)展的并行分布式流處理系統(tǒng),也能響應(yīng)流式數(shù)據(jù)上的連續(xù)的查詢請(qǐng)求.為了提升MapReduce對(duì)迭代執(zhí)行類(lèi)的程序的支持能力,文獻(xiàn)[13]設(shè)計(jì)了一種擴(kuò)展的MapReduce框架,與HaLoop工作的不同之處在于該框架還支持對(duì)Map任務(wù)的異步執(zhí)行同時(shí)允許每次迭代不必充分創(chuàng)建Map/Reduce任務(wù).Spark[14]是近兩年興起的一類(lèi)新的分布式計(jì)算框架,其采用基于內(nèi)存的方式來(lái)提升迭代式MapReduce作業(yè)的計(jì)算效率,在中間結(jié)果處理的設(shè)計(jì)思路上與我們的工作有相似之處,但是本文工作的主要特點(diǎn)是在計(jì)算中結(jié)合交通數(shù)據(jù)特征融入具有時(shí)空特性的數(shù)據(jù)模型進(jìn)行優(yōu)化,更適于實(shí)現(xiàn)基于時(shí)空劃分的旅行時(shí)間流水線式計(jì)算.

綜上,現(xiàn)有的相關(guān)工作大都集中在通用的計(jì)算平臺(tái),在時(shí)空對(duì)象數(shù)據(jù)劃分及執(zhí)行優(yōu)化方面缺乏從交通數(shù)據(jù)及其計(jì)算特征方面的針對(duì)性設(shè)計(jì),因此不能直接用來(lái)解決具有周期性批數(shù)據(jù)處理特點(diǎn)的旅行時(shí)間計(jì)算問(wèn)題.相對(duì)于上述工作,本文則是利用車(chē)牌識(shí)別數(shù)據(jù)的時(shí)空特性并參考上述相關(guān)工作,重點(diǎn)通過(guò)數(shù)據(jù)的時(shí)空劃分和計(jì)算任務(wù)的流水線設(shè)計(jì)實(shí)現(xiàn)對(duì)旅行時(shí)間計(jì)算模型進(jìn)行優(yōu)化,以達(dá)到提高旅行時(shí)間計(jì)算性能的目的.

6　結(jié)束語(yǔ)

海量車(chē)牌識(shí)別數(shù)據(jù)集上的旅行時(shí)間計(jì)算是當(dāng)前智能交通應(yīng)用建設(shè)中一個(gè)新的探索.本文針對(duì)該問(wèn)題,定義了基于車(chē)牌識(shí)別數(shù)據(jù)的旅行時(shí)間計(jì)算概念,提出一種基于時(shí)空劃分的流水線式并行計(jì)算模型,并給出了該模型基于實(shí)時(shí)MapReduce的實(shí)現(xiàn).通過(guò)一組基于海量真實(shí)車(chē)牌識(shí)別數(shù)據(jù)集的實(shí)驗(yàn)表明,相對(duì)于傳統(tǒng)的旅行時(shí)間計(jì)算方式,本文方法表現(xiàn)出了較高的性能,同時(shí)具有適合細(xì)粒度劃分及受路網(wǎng)規(guī)模影響小等特點(diǎn).下一步的工作包括在百億記錄級(jí)模擬數(shù)據(jù)上的實(shí)驗(yàn)測(cè)試以及時(shí)空并行計(jì)算模型在其它交通應(yīng)用中的適用性驗(yàn)證與分析.

[1]朱愛(ài)華.基于浮動(dòng)車(chē)數(shù)據(jù)的路段旅行時(shí)間預(yù)測(cè)研究[D].北京:北京交通大學(xué),2008.

Zhu Aihua.Research on link travel time prediction method based on data collected by floating car[D].Beijing Jiaotong University,2008.(in Chinese)

[2]廖律超,等.一種支持軌跡大數(shù)據(jù)潛在語(yǔ)義相關(guān)性挖掘的譜聚類(lèi)方法[J].電子學(xué)報(bào),2015,43(5):956-964.

Liao Lvchao,et al.A spectral clustering method for big trajectory data mining with latent semantic correlation[J].Acta Electronica Sinica,2015,43(5):956-964.(in Chinese)

[3]姜桂艷,等.基于車(chē)牌識(shí)別數(shù)據(jù)的交通擁堵識(shí)別方法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2011,43(4):131-135.Jang Jiayan,et al.Traffic congestion identification method based on license plate recognition data[J].Journal of Harbin Institute of Technology,2011,43(4):131-135.(in Chinese)

[4]劉好德.基于浮動(dòng)車(chē)數(shù)據(jù)的城市交通狀態(tài)判別與行程時(shí)間計(jì)算[R].同濟(jì)大學(xué),博士后出站報(bào)告,2010.

Liu Haode.Estimation of urban traffic status and prediction of travel time based on floating car data[R].Research Report for Post-Doctor,Tongji University,2010.(in Chinese)

[5]朱定局.并行時(shí)空模型[M].北京:科學(xué)出版社,2009.

Zhu Dingjun.Parallel Space-Time Model[M].Beijing,Science Press,2009.(in Chinese)

[6]亓開(kāi)元,趙卓峰,房俊,馬強(qiáng).針對(duì)高速數(shù)據(jù)流的大規(guī)模數(shù)據(jù)實(shí)時(shí)處理方法[J].計(jì)算機(jī)學(xué)報(bào),2012,35(3):477-490.Qi Kaiyuan,Zhao Zhuofeng,Fang Jun.Real-time processing for high speed data stream over large scale data[J].Chinese Journal of Computers,2012,35(3):477-490.(in Chinese)

[7]亓開(kāi)元,韓燕波,趙卓峰,等.支持高并發(fā)數(shù)據(jù)流處理的MapReduce中間結(jié)果緩存.計(jì)算機(jī)研究與發(fā)展,2013,50(1):111-121.

Qi Kaiyuan,Han Yanbo,Zhao Zhuofeng,et al.MapReduce intermediate result cache for concurrent data stream processing[J].Journal of Computer Research and Development,2013,50(1):111-121.(in Chinese)

[8]張帥,趙卓峰,丁維龍.基于MapReduce的城市道路旅行時(shí)間實(shí)測(cè)計(jì)算[J].計(jì)算機(jī)與數(shù)字工程,2014,42(9):1542-1546.

Zhang Shuai,Zhao Zhuofeng,Ding Weilong.Urban road trip time measured calculation based on mapReduce[J].Computer & Digital Engineering,2014,42(9):1542-1546. (in Chinese)

[9]廖飛,黃晟,龔德俊.基于Hadoop的城市道路交通流量數(shù)據(jù)分布式存儲(chǔ)與挖掘分析研究[J].公路與汽運(yùn),2013,27(5):82-86.

Liao Fei,Huang Sheng,Gong Dejun.Distributed storage and data mining analysis of urban road traffic based on hadoop[J].Highways & Automotive Applications,2013,27(5):82-86.(in Chinese)

[10]Lizhe Wang,et al.G-Hadoop:MapReduce across distributed data centers for data-intensive computing[J].Future Generation Computer Systems,2013,29(3):739-750.

[11]Yingyi Bu,Bill Howe,Magdalena Balazinska,et al.The haLoop approach to large-scale iterative data analysis[J].VLDB Journal,2012,21(2):169-190.

[12]張鵬,劉慶云,譚建龍,等.流水行云:支持可擴(kuò)展的并行分布式流處理系統(tǒng)[J].電子學(xué)報(bào),2015,43(4):639-646.

Zhang Peng,Liu Qingyun,Tan Jianlong,et al.SPSPS:A scalable parallel-distributed stream processing system[J].Acta Electronica Sinica,2015,43(4):639-646.(in Chinese)

[13]Yanfeng Zhang,et al.iMapReduce:A distributed computing framework for iterative computation[J].Journal of Grid Computing,2012,10:47-68.

[14]Matei Zaharia.An Architecture for fast and general data processing on large clusters[R].University of California,Berkeley,Technical Report No.UCB/EECS-2014-12,2014.

趙卓峰男,1977年5月出生,山東濟(jì)南人.博士,現(xiàn)為北方工業(yè)大學(xué)云計(jì)算研究中心副研究員、副主任.研究方向?yàn)樵朴?jì)算、流數(shù)據(jù)處理、服務(wù)計(jì)算、智能交通.

E-mail:edzhao@ncut.edu.cn

丁維龍男,1983年3月出生,山東泰安人.博士,現(xiàn)為北方工業(yè)大學(xué)云計(jì)算研究中心助理研究員.主要研究方向?yàn)榱鲾?shù)據(jù)處理、流計(jì)算及分布式系統(tǒng).

E-mail:dingweilong@ncut.edu.cn

A Travel Time Calculation Method Based on Spatio-Temporal Data Partition of Large-Scale License Plate Recognition Data Set

ZHAO Zhuo-feng1,2,DING Wei-long1,2,ZHANG Shuai1

(1.CloudComputingResearchCenter,NorthChinaUniversityofTechnology,Beijing100144,China; 2.BeijingKeyLaboratoryonIntegrationandAnalysisofLarge-ScaleStreamData,Beijing100144,China)

The calculation of travel time of city roads is an important issue in the domain of the intelligent transportation system research.License plate recognition data is one kind of monitoring data for vehicles running on urban roads,which has some new features,such as high volume,high velocity and spatio-temporal correlation.In order to achieve travel time calculations on massive license plate recognition data collection,we present the formal definition of travel time calculation based on license plate recognition data set,and propose a pipelined parallel computing model based on spatio-temporal data partition.Moreover,the implementation of the computing model is given based on a real-time MapReduce computing system.The corresponding experiments based on real license plate recognition data set show that,the computing performance on million-level data sets of our method can achieve three times increasing compared to traditional travel time calculation methods.Meanwhile our method is more suitable for fine-grained partition and large scale traffic network.

travel time;spatio-temporal partition;parallel pipeline;real-time mapreduce;large-scale license plate recognition data

2014-11-24;

2015-10-19；責(zé)任編輯：馬蘭英

北京市自然科學(xué)基金(No.4131001,No.4162021);北京市屬高等學(xué)校創(chuàng)新團(tuán)隊(duì)建設(shè)項(xiàng)目(No.IDHT20130502)；北方工業(yè)大學(xué)?？蒲谢?/p>

TP301

A

0372-2112 (2016)05-1227-07

電子學(xué)報(bào)URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.031