面向大數(shù)據(jù)集成的實(shí)體識(shí)別框架及關(guān)鍵技術(shù)的研究.pdf

1、現(xiàn)代互聯(lián)網(wǎng)每日產(chǎn)生大量的數(shù)據(jù)，引發(fā)了對(duì)大規(guī)模數(shù)據(jù)的處理的需求。面對(duì)海量的數(shù)據(jù)，提出了新形式的分布式文件存儲(chǔ)系統(tǒng)，并且基于文件系統(tǒng)之上提出了并行的計(jì)算方式解決大數(shù)據(jù)帶來的計(jì)算效率的挑戰(zhàn)。最具代表的是Google提出的MapReduce并行編程框架，使得很多基于大數(shù)據(jù)的最常見計(jì)算能夠在大規(guī)模計(jì)算集群中得以高效的實(shí)現(xiàn)。實(shí)體識(shí)別(Entity Resolution)是指在判斷一個(gè)或多個(gè)數(shù)據(jù)源中兩個(gè)不同記錄是否描述相同實(shí)體，它有時(shí)也被稱作記錄連接

2、(Record Linkage)，在數(shù)據(jù)集成中被用于數(shù)據(jù)清洗(Data Clean)、去重(Deduplication)和相似連接(Similarity Joins)等集成操作中。實(shí)體識(shí)別技術(shù)可被廣泛應(yīng)用于人口普查、引文識(shí)別、Web搜索、數(shù)據(jù)清洗以及剽竊檢驗(yàn)等諸多領(lǐng)域。然而隨著數(shù)據(jù)集規(guī)模的日益增大，集中式處理幾百GB數(shù)據(jù)時(shí)已經(jīng)出現(xiàn)性能瓶頸，更不用說TB、PB級(jí)別。由于實(shí)體識(shí)別本身可以采用并行計(jì)算模型進(jìn)行處理，因此采用MapReduce分

3、布式計(jì)算模型能夠很好地處理大規(guī)模數(shù)據(jù)集上的實(shí)體識(shí)別問題，提高執(zhí)行效率。
　　本文提出了基于MapReduce的實(shí)體識(shí)別框架VEER，其中包含三個(gè)處理階段。第一個(gè)階段VEER從一組數(shù)據(jù)源中發(fā)現(xiàn)所有滿足閾值的相似記錄對(duì)。這個(gè)工作是基于相似連接算法的。第二個(gè)階段劃分所有的相似記錄對(duì)，形成相似子圖集合。第三個(gè)階段利用ICAR原則合并每個(gè)相似子圖中的實(shí)體。VEER框架允許實(shí)體識(shí)別任務(wù)從任何一個(gè)階段開始運(yùn)行，以適應(yīng)不同需求的應(yīng)用。為了提高實(shí)體

4、識(shí)別框架對(duì)大數(shù)據(jù)的處理效率，本文重點(diǎn)研究了分布式相似連接算法和任務(wù)調(diào)度策略兩個(gè)問題。針對(duì)分布式相似連接，本文提出了基于前綴與位置信息的過率算法，通過降低記錄間匹配數(shù)量提高執(zhí)行效率。針對(duì)本框架的不同處理階段，本文分別提出了面向負(fù)載均衡和子圖構(gòu)建的任務(wù)調(diào)度算法，從而提高M(jìn)apReduce任務(wù)的執(zhí)行效率。本文基于Hadoop系統(tǒng)和VEER框架實(shí)現(xiàn)了實(shí)體識(shí)別原形系統(tǒng)。該原型系統(tǒng)在為用戶提供了友好的交互界面同時(shí)，能夠有效地提高相似連接的的過濾性能

5、和集群的利用率。
　　對(duì)于本文提出的基于MapReduce框架的相似連接算法和調(diào)度策略，本文在VEER實(shí)體識(shí)別原型系統(tǒng)上采用DBLP和Citeseerx的真實(shí)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)。通過實(shí)驗(yàn)，我們比較了不同相似連接算法在時(shí)間代價(jià)以及集群的利用率上的性能。實(shí)驗(yàn)結(jié)果表明本文的算法能夠穩(wěn)定地的運(yùn)行在集群中，每個(gè)單點(diǎn)的執(zhí)行負(fù)載基本相同，整體的運(yùn)行效率隨著數(shù)據(jù)規(guī)模的增加會(huì)有顯著提高。本文的VEER實(shí)體識(shí)別工具能夠很好地執(zhí)行MapReduce集群調(diào)