實體識別問題的相關研究

摘要：隨著信息技術的發展，信息時代已經全面到來了。在信息“量”爆炸性增長的同時，近年來，“質”的問題也已經引起了產業界和研究人員的關注。“劣質”數據極大地降低了信息的可用性，提供給用戶不精確的、缺失的、冗余的、陳舊的甚至是錯誤的信息，無法給用戶帶來正確的知識，并可能誤導用戶做出錯誤的決策，從而給用戶造成損失。數據質量有六個主要維度：精確性、完整性、時效性、一致性、相關性和實體同一性。綜述了數據質量中實體同一性方面的相關工作，并針對特定的技術展開討論。

關鍵詞：數據質量； 實體識別； 臟數據

中圖分類號：TP311 文獻標識碼：A文章編號：2095-2163（2013）02-0001-06

0引言

隨著信息技術的飛速發展，其應用已經遍及國民經濟和社會實踐的各個領域，由此宣示了信息時代的全面到來。在信息“量”爆炸性增長的同時，近年來，有關其“質”的系列問題也已經引起了產業界和學術圈的關注和重視。“劣質”的數據在很大程度降低了信息的可用性，可能給用戶提供模糊、缺失、冗余、陳舊甚至是錯誤的信息，不但無法給用戶帶來正確的知識，并有可能誤導用戶做出錯誤的決策，從而給用戶造成損失。數據統計表明，“劣質”數據每年給美國企業能帶來超過6 000億美元的經濟損失；而美國零售行業的數據庫中每年的錯誤價格數據信息都會給消費者帶來約25億美元的財產損耗。國內雖然還未見公開的統計數據，但是“劣質”數據帶來虧失的個案確也頻有發生。根據資訊公司TechTarget 中國的報告，某家大型電信公司因為“劣質”數據的問題曾將包括信號發射塔和50億美元的預算錯誤地發放到了獨立審計師手中；根據新華網的報道，央行征信系統的錯誤記錄也屢屢造成金融消費者的權益受損。然而，更有甚者，事實正在表明，“劣質”數據并非特例，而是普遍存在的。又有統計表明，美國一個典型企業中，數據的錯誤比率一般在1～5%之間，而在某些企業中該比率甚至超過了30%；據估計，美國的醫療系統中，大多數時候（約13.6%-81%），在臨床診斷時，需要的數據都是缺失的。國內暫時沒有較為可信的統計數據，但根據哈爾濱工業大學海量數據計算研究中心團隊對其合作伙伴共享數據的抽樣分析，國家海洋信息中心的數據總共約有10～20%存在缺失問題，而醫藥行業的數據總量則約有10%的部分存在各種類型的質量問題，基于此，則有理由相信，“劣質”數據在國內也已經成為一個不可忽視的普遍存在。因此，針對各種不同的數據類型，建立相應的數據質量管理的理論與方法，為對應的數據管理軟件及其應用系統提供對數據質量進行保障、改善、控制的能力則成為當下一個亟待解決的問題。

數據質量并沒有公認、統一的定義，已有的研究工作一般用定義在數據上的測度來進行直觀描述。文獻[1]從六個維度定義數據質量，給出了迄今為止較為公認的定義標準。這六個主要維度包括：精確性（accuracy）、完整性（completeness）、時效性（timeliness）、一致性（consistency）、實體同一性（entity identity）及相關性（relevancy）。其中，精確性是指數據描述同現實世界事物屬性之間的接近程度；完整性是指數據集合中數據的完整程度；時效性則指描述現實世界事物的數據的新舊程度；一致性則指數據內部的矛盾程度；實體同一性指的是描述同一個現實世界事物的數據的冗余程度；相關性指的是數據同應用需求的契合程度。文獻[2]是對數據質量和數據清洗方面早期開展工作的系統綜述。本文全面總結了數據質量中實體同一性方面的相關工作，而且又針對其中的相關技術展開了完整的討論。

1實體識別問題

在實體同一性的研究中，實體識別可看作是提高數據質量的一個重要步驟，主要的研究工作均集中于此。實體識別問題的定義比較早，而且也提出了較多的方法和框架。研究工作發端于文獻[3]，文獻[4]則從統計學角度，形式化地定義了實體識別問題的任務，并從統計角度分析其性質。文獻[5]是在數據處理領域較早地提出了實體識別問題。文獻[6]是新近的關于實體識別問題研究的一篇綜述。具體地說，實體識別問題的任務就是要尋獲數據中描述同一實體的若干元組。解決實體識別問題的常用方法有兩類。第一類是實體匹配+實體消解，該方法通過逐對比較實體來判定實體之間的兩兩關系，再利用匹配結果的消解方法得到實體識別問題的結果；第二類方法是利用統計模型直接求解實體識別結果。

從形式化定義的角度，實體同一性研究的最終目的是要解決如下問題：給定一個數據實體的集合D和一個真實世界的物理實體集合O，求解一個集合D的劃分P（其中，P是由一系列D的不相交子集合構成的集合，且P中所有集合并的結果與D相同）以及P與O之間的一一對應關系。直觀地說，P中的每一個集合與O中的物理實體一一對應，而P中與物理實體o對應的集合D（o）由D中所有描述o的數據實體構成。文中，將此問題稱為實體解析問題。在實體解析問題中，需要確定兩方面的信息。

（1）哪些數據實體描述的是同一個物理實體；

（2）給定的某個數據實體描述哪個物理實體。

在實際應用中，通常來說，我們只能獲得數據實體集合D，而很難獲得物理實體的集合O。即使在O事先給定的情況下，判斷D與O之間的對應關系仍然非常困難，也就是說，評價給定實體解析算法的優劣是非常困難的，這個問題在數據量大的情況下尤為嚴重。因此，絕大多數的研究工作轉而考慮如下的問題定義方式。給定數據實體集合D，計算一個集合D的劃分P，P中的每個集合都表示描述同一物理實體的某些數據實體集合。也就是說，該問題只要求將表示同一物理實體的那些數據實體放入一個集合，而不要求建立P與O之間的關系。該問題則稱作實體識別問題。實體識別問題的定義使得在實際應用中找到好的實體識別方法仍然很困難，一個主要的原因是驗證某個實體識別算法的優劣是非常難的。這是因為，當將一個D中的子集合交給專家用戶判斷時，即使這位專家能夠判斷是否該集合的所有數據實體都描述同一物理實體，但是判斷D中是否還有其他數據實體也描述該物理實體則是幾乎無法做到的。直接推理可知，專家用戶需要遍歷D中的所有元素，并逐一作出判斷，這在數據量大的情況下幾乎是不可能的。因此，進一步簡化，很多研究工作考慮如下的問題定義。給定D中的兩個數據實體，判斷這兩者是否描述同一個物理實體，該問題在本文中可稱作實體匹配問題。雖然上述三個問題的定義不同，但其解決的本質問題是一樣的，因此，絕大多數的研究工作并不特別標明正在解決的是哪一個問題，而是根據實際具體需求，借助不同的方法學，針對適合的問題定義，給出系統化的解決方案。接下來，在不產生歧義的情況下，文中將用實體識別問題總稱這三類研究問題，并依據求解問題的不同方法學來對相應工作展開綜合論述。

2實體識別問題的研究進展及討論

2.1實體識別的綜述工作

實體識別是提高數據實體同一性方面質量的一個重要步驟，最早的關于實體識別問題的研究是獨立于數據可用性概念的。到目前為止，之前的研究工作已經提出了解決該問題的很多方法和框架。通常來說，解決實體識別問題需要匹配及消解過程，在其它的論文中也被稱作“清洗/合并”。述以直觀可知，在關系數據中，實體匹配就是比較兩個數據實體是否有可能表示一個物理實體，消解過程就是對匹配結果作出最優的識別結果解釋。較早的系統化研究實體識別問題的工作是文獻[4]。最近的相關方面的綜述工作可參見文獻[6-9]。

2.2實體識別的效率問題

實體識別是數據質量領域廣泛研究的問題之一，針對不同的應用場景，人們已經提出了很多實體識別算法。然而，幾乎所有的實體識別算法都是平方級別的。一般來說，平方級別的算法是多項式時間表示的，通常可視作有效的算法，但是，在數據量較大，甚至是海量數據的時候，平方級別的算法在實際應用中也是不可接受的。實際的應用經常需要效果為線性甚至亞線性時間代價的算法。但是，算法效率為線性甚至亞線性層次的問題卻只是寥寥可數，而對于實體識別問題來說，還未研發得到這樣的方法，并且也有推斷這樣的方法可能并不存在。已有工作嘗試從另外的角度提高實體識別過程的效率問題，其思想是通過盡量少地匹配實體對來達到節省時間代價、提高實體識別效率的目的。這方面的工作還不是很多。其中的進展之一是，利用將數據分塊的思想，實體識別問題可以通過僅匹配塊內實體的方法進行求解，該方法可以顯著提高實體識別過程的效率。文獻[10]提出并討論了兩種簡單的數據分塊方法，第一種方法是利用簡單的規則將數據分塊，然后完成整個塊內實體間的比較；另一種方法是利用有效的語義信息將數據劃分為不相交的數據實體塊。該工作給出的兩種方法都不適用于實際情況下的實體識別問題。就各自特點而言，第一種方法在提高實體識別效率的同時會降低實體識別的精度，這是研究中不希望發生的；第二種方法可以在提高效率的同時保證識別精度，然而該方法所利用的語義信息卻很難得到。文獻[11]在真實數據上對比了一系列的實體識別方法，著重比較了這些方法的實現效率。文獻[12]針對實體識別問題，考慮用云計算的方法來提高實體識別的效率。文獻[13]比較一系列實體識別方法的應用框架，從數據處理原理的視角比較識別方法。其中，利用局部敏感哈希技術將數據分塊并通過僅計算塊內數據實體的關系的方法是求解實體識別問題的一個較為有效的方法，但該方法僅適用于具備局部敏感哈希條件的情況，在該類情況下既能保證識別精度，又可提高實體識別的效率。利用分塊的方法處理一般情況的實體識別問題時，由于很難找到完備的數據分塊策略，多是采用如下方法：將每塊數據實體的識別結果傳遞到其它塊上，并迭代地計算整個數據上的實體識別結果，不斷地提高識別精度。另一種思路是，基于鄰居排序的方法，針對不同屬性對關系元組進行多次排序，利用固定長度的窗口，分別順序地掃描依據不同屬性排序得到的元組序列，在同一窗口內匹配實體并判別描述同一物理實體的數據實體，并綜合多個序列的結果，以求得最終的實體識別結果。

2.3實體識別的增量計算

實體識別是一個時間代價非常高的過程，如果能夠有效地重復利用已經計算出來的識別結果，那么對實體識別過程的效率是一個很大的改進。文獻[14]提出了一種針對實體識別規則變化的情況的實體識別方法，該方法考慮如何利用已有的識別結果，深入地研究實體識別問題，形式化地定義了實體識別問題在不同背景下的性質，并利用這些性質共享已有的識別結果、提高識別精度。文獻[15]從另外的角度出發，針對top-k計數查詢提出了“一邊求解查詢一邊識別實體”的方法。算法的基礎在于，一般的查詢涉及到的數據實體數量較小，算法沒有必要在所有數據實體上運行實體識別算法，僅需要處理查詢結果中涉及到的實體。該方法的難點在于，識別查詢結果中的實體可能需要查詢結果之外的數據實體，而快速得到查詢結果以外的相關數據實體也是一件困難的事情。

2.4多種實體識別方法的集成比較

實體識別的方法已然蔚為可觀，但是至今仍然沒有一定的研究成果能夠同時從處理效率和精度方面對這些已有的方法進行較為詳細和全面的比較。更進一步地說，即使針對某個特定的實體識別方法，在給定正確結果的情況下，評價實體識別方法的質量和表現也仍然是一個非常難的問題，既沒有公認的評測基準，也沒有公認的評價測度。文獻[16]比較了定義在字符串屬性值上的各種相似性度量函數，提出了一些建立比較基準的指導方法，但是并沒有給出具體的實現方法。文獻[17]針對關系數據和XML數據提出了比較實體識別問題各種算法的基準的實現思路，對其中具體部件的實現方法給出了詳細的討論。文獻[18]針對實體識別的結果進行評估，考慮在給定原始數據及其實體識別結果的情況下，評價該識別結果優劣的方法。該工作對實體識別問題進行了深入地分析和討論，給出了一個基于“合并”和“分裂”操作的評價測度，該測度可以很好地度量實體識別結果的優劣。文獻[18]對給出的度量進行了形象、直觀的分析，討論了兩種操作的可置換性，并分析了提出的測度與準確率、召回率的關系，同時介紹了常用的幾種測度轉化為文中測度的方法。文獻[19]集成了多種實體識別的系統，而且根據上下文信息，即應用背景信息，建立統計模型，利用統計推斷的方法來判斷在給定參數的情況下使用哪個實體識別方法，并給出集成方法的性能分析。

2.5半結構化數據上的實體識別

半結構化數據上的實體識別問題與基本的實體識別問題有如下區別：在實體匹配方面，由于半結構化數據中包含結構信息，因此，匹配方法需要針對樹結構進行處理；在實體劃分和匹配結果消解方面也因樹形拓撲結果而存在相應不同，但目前并沒有工作詳細、深入地探討該問題。文獻[20]解決了利用哈希方法解決樹結構數據匹配的問題，其思想是利用局部敏感哈希技術。該工作針對樹結構提出了新的距離測度，并討論了文中的測度與傳統的樹編輯距離的區別。

2.6相似查詢和相似連接

相似查詢和相似連接是定義在數據實體集合上的兩個基本操作，是實體識別過程的重要步驟，其實現是利用定義在屬性值上的相似性函數來判定兩個數據實體之間的關系。這兩個操作的執行效率問題是各類研究中一直關注的重點。文獻[21]首次提出將相似連接作為數據庫的一個基本操作來進行研究的全新思路。文獻[22]針對字符串屬性值，利用已有的倒排索引加速相似查詢的執行，并且著重探討了如何縮減所需索引的空間大小問題。文獻[23]針對生物數據庫中經常出現的長字符串，提出了基于定長字符串搜索和變長字符串搜索的方法處理長字符序列的相似查詢。當數據實體的某一屬性帶有一個附加的引用表信息時，比如中國所有省會的名稱列表，在該屬性上進行的基于字符串的近似查詢相當于從字符串到表中信息的近似匹配，文獻[24]提出了一種新方法，將要查詢的字符串利用引用表擴展，得到若干與查詢字符串近似的字符串，然后用這些字符串進行更加精準的近似匹配。文獻[25]考慮相似連接操作，研究了基于集合測度的相似連接操作的實現算法，并且提出了面向Jaccard距離的相似連接處理策略，可將數據實體序信息引入相似連接的處理過程中，再結合前綴、后綴過濾技術，提高了相似連接操作的效率。文獻[26]研究了高維數據相似連接的問題，利用哈希技術提出了LSS算法，并基于圖形處理器的特性給出了高效的實現方法。

很多工作利用n-gram索引處理字符串相似連接的問題，并驗證了該索引可以大大提高連接過程的效率，但是固定長度的索引在實際應用中卻會帶來效率的低下。文獻[27-29]是相似查詢的最新工作，針對字符串屬性值，研究了基于n-gram索引的相似匹配。其基本思想是：首先根據字符串屬性值建立n-gram索引，然后在執行相似查詢時，將字符串之間的距離條件轉化為對應的n-gram集合上的條件，并且利用計算索引集合間交集數量的方法求解相似查詢的結果。其中，文獻[28]將傳統的2-gram方法拓展為n-gram方法，提高了相似查詢的精度。文獻[27]提出了定長的字符串索引的優化存儲方法。文獻[29]提出了利用索引進行字符串相似查詢的高效算法，針對在一個字符串集合中查找與給定字符串相似的字符串集合的問題，并基于多種相似函數，給出高效的實現算法，同時也討論了如何將該算法與已有的過濾策略相結合。

2.7基于規則的實體識別方法

利用相似函數度量數據實體之間的相似性是解決實體識別問題的重要思路，然而，大多數時候，無法在現實世界中找到一個完美的相似性度量函數來衡量實體之間的相似性。因此，另外一個思路是利用語義規則引入額外的專家用戶信息，引導實體識別過程。結合語義規則的方法可以修正相似函數產生的誤差，提高識別的精度，該方法的極限情況是完全用語義規則來解決實體識別問題。基于邏輯編程，文獻[30]提出了用聚集約束處理數據中的冗余錯誤問題，即實體識別問題。文獻[31]提出了一個邏輯框架解決實體識別問題，一般的基于語義規則的方法效率都比較低，該方法通過控制語義規則的運行范圍，力圖在識別效率和精確度之間找到適合的折衷策略。有時，語義規則信息是對哪些數據實體不可能描述同一個物理實體進行的描述，也就是否定規則，文獻[32]基于否定規則對實體識別問題的影響進行了研究。文獻[33]首次提出了記錄匹配規則，給出了形式化的定義，并在其上研究了推理問題，使得識別系統可以根據專家給出的若干匹配規則自動推理得出大部分有用的匹配規則。該工作為利用語義規則進行實體識別的方法提供了基礎，解決了實際應用中如何獲得規則的問題，并利用推理系統將規則彼此聯系起來，使之成為一個有機的整體。文獻[34]實現了一個基于字符串轉換規則的記錄匹配框架，字符串轉換規則可以看作是對字符串上傳統相似度量定義的補足，利用轉換后的字符串判斷相似性，可以提高實體識別過程的精確度。文獻[35]研究了如何從用戶示例中學習字符串轉換規則的問題。文獻[36]考慮一類特殊的數據清洗任務，如對于用戶的地址信息、電腦的型號信息進行清洗。這些任務有如下特點：基于字符串相似性并不能對數據實體進行很好的區分。例如，不同電腦的型號很多時候只差一個數字，而字符串屬性值即使極為不相似卻也有可能表述的是同一個物理實體，如地址信息中的簡寫形式。這樣的問題會引起已有的基于近似匹配方法的失效，原因是識別算法對于具體的實體中某些屬性的內容結構并沒有精確的描述和深刻的理解。字符串轉換操作可以很好地解決該問題，文獻[36]利用字符串轉換規則描述特殊屬性值上內容的結構，提出了一個可編程的邏輯框架，該框架支持用戶用上下文無關文法定義轉換規則，來解釋字符串屬性值之間的內部結構，最后利用轉換規則提取出標準化的屬性值進行匹配。既然距離函數和字符串轉換規則在實體識別問題中起到了很大的作用，那么自動地學習距離函數及字符串轉換函數就成了一個研究問題。文獻[35]考慮從數據中學習字符串轉換規則的問題，提出了形式化的定義，其直觀的想法是從預先給出的轉換規則中找到一個盡量小的規則集合，要求該集合能夠完成給定數據中的字符串轉換操作。該問題被證明是不可解的，文獻[35]給出了啟發式的方法來發現這些規則，并用實驗驗證了方法的有效性。文獻[37]研究了學習距離函數的問題，基于機器學習方法，提出了結合多個屬性上的相似函數計算實體之間相似性的方法。文獻[38]利用基于馬爾科夫鏈的方法，自動地發現實體相似性度量函數。

2.8基于統計方法的實體識別

文獻[39]針對一個公開的出版物信息數據庫，考慮其中的作者重名問題，提出了一個基于LDA（Latent Dirichlet Allocation）的擴展模型，對識別問題進行抽象，并利用統計推斷的方法實現實體識別過程。通常的統計方法都需要設置參數或者給定訓練數據，文獻[40]提出了一種兩階段的統計學習方法，可完全自動地執行實體識別過程，其思想是將第一階段數據實體上兩兩匹配結果中較好的一部分抽取出來，并將其作為第二階段的支持向量機方法的訓練數據。該工作基于最近鄰方法和支持向量機方法分別給出了對應的實體識別算法。文獻[41]和[42]利用機器學習方法自動地發現描述同一數據實體的不同屬性值，從而提高了識別過程的精度。

3結束語

針對關系數據，研究工作者已經在實體識別問題上做出了巨大的努力，關系數據上的實體識別技術已基本趨向成熟。但是，如果從精確度和效率角度同時衡量已有的方法，現有的技術離真正付諸應用還有一定差距，尤其是針對大數據的對應的實體識別技術還比較少。并且，針對復雜結構數據上的實體識別問題的研究還不多，適用于復雜數據的實體識別技術也很少見。另外，作為一個獨立的課題研究，實體識別問題與數據質量領域其它維度之間的關系及交互影響還有待進一步的深入探索。

參考文獻：

[1]WANG R， STRONG D. Beyond accuracy： what data quality means to data consumers[J]. Journal of Management Information Systems， 1996，12（4）： 5-34.

[2]RAHM E， DO H H. Data cleaning： problems and current approaches [J]. IEEE Data Engineering Bulletin， 2000， 23（4）： 3-13.

[3]NEWCOMBE H B， KENNEDY J M， AXFORD S J， et al. Automatic linkage of vital records [J]. Science， 1959， 130（3381）： 954-959.

[4]FELLEGI I P， SUNTER A B. A theory for record linkage [J]. Journal of the American Statistical Association， 1969， 64（328）： 1183-1210.

[5]HERN NDEZ M A， STOLFO S J. The merge/purge problem for large databases [C] //ACM SIGMOD Record. New York： ACM， 1995， 24（2）： 127-138.

[6]ELMAGARMID A K， IPEIROTIS P G， VERYKIOS V S. Duplicate record detection： a survey [J]. IEEE Transactions on Knowledge and Data Engineering， 2007， 19（1）： 1-16.

[7]LIM E P， SRIVASTAVA J， PRABHAKAR S， et al. Entity identification in database integration [J]. Information Sciences， 1996， 89（1）： 1-38.

[8]BRIZAN D G， TANSEL A U. A survey of entity resolution and record linkage methodologies [J]. Communications of the IIMA， 2006， 6（3）： 41-50.

[9]KOUDAS N， SARAWAGI S， SRIVASTAVA D. Record linkage： similarity measures and algorithms [C] //Proceedings of the 2006 ACM SIGMOD international conference on Management of data. New York： ACM， 2006： 802-803.

[10]KIRSTEN T， KOLB L， HARTUNG M， et al. Data partitioning for parallel entity matching [J]. Proceedings of the VLDB Endowment， 2010， 3（2）：1-12.

[11]K PCKE H， THOR A， RAHM E. Evaluation of entity resolution approaches on real-world match problems [J]. Proceedings of the VLDB Endowment， 2010， 3（1-2）： 484-493.

[12]VERNICA R， CAREY M J， LI C. Efficient parallel set-similarity joins using MapReduce [C] //Proceedings of the 2010 international conference on Management of data. New York： ACM， 2010： 495-506.

[13]K PCKE H， RAHM E. Frameworks for entity matching： A comparison [J]. Data Knowledge Engineering， 2010， 69（2）： 197-210.

[14]WHANG S E， GARCIA-MOLINA H. Entity resolution with evolving rules [J]. Proceedings of the VLDB Endowment， 2010， 3（1-2）： 1326-1337.

[15]SARAWAGI S， DESHPANDE V S， KASLIWAL S. Efficient top-k count queries over imprecise duplicates [C] //Proceedings of the 12th International Conference on Extending Database Technology： Advances in Database Technology. New York： ACM， 2009： 450-461.

[16]COHEN W W， RAVIKUMAR P， FIENBERG S E. A comparison of string distance metrics for name-matching tasks [C] //Proceedings of the IJCAI-2003 Workshop on Information Integration on the Web， 2003： 73-78.

[17]WEIS M， NAUMANN F， BROSY F. A duplicate detection benchmark for XML （and relational） data [C] //Proceedings of Workshop on Information Quality for Information Systems （IQIS）， 2006.

[18]MENESTRINA D， WHANG S E， GARCIA-MOLINA H. Evaluating entity resolution results [J]. Proceedings of the VLDB Endowment， 2010， 3（1-2）： 208-219.

[19]CHEN Z， KALASHNIKOV D V， MEHROTRA S. Exploiting context analysis for combining multiple entity resolution systems [C] //Proceedings of the 35th SIGMOD international conference on Management of data. New York： ACM， 2009： 207-218.

[20]TATIKONDA S， PARTHASARATHY S. Hashing tree-structured data： methods and applications [C] //Proc of IEEE ICDE’10. Piscataway， NJ： IEEE， 2010： 429-440.

[21]CHAUDHURI S， GANTI V， KAUSHIK R. A primitive operator for similarity joins in data cleaning [C] //Proc of IEEE ICDE'06. Piscataway， NJ： IEEE， 2006： 5-5.

[22]BEHM A， JI S， LI C， et al. Space-constrained gram-based indexing for efficient approximate string search [C] //Proc of IEEE ICDE'09. Piscataway， NJ： IEEE， 2009： 604-615.

[23]PAPAPETROU P， ATHITSOS V， KOLLIOS G， et al. Reference based alignment in large sequence databases [J]. Proceedings of the VLDB Endowment， 2009， 2（1）： 1-12.

[24]CHAUDHURI S， GANTI V， XIN D. Mining document collections to facilitate accurate approximate entity matching [J]. Proceedings of the VLDB Endowment， 2009， 2（1）： 395-406.

[25]XIAO Chuan， WANG Wei， LIN Xuemin， et al. Efficient similarity joins for near-duplicate detection [J]. ACM Transactions on Database Systems （TODS）， 2011， 36（3）： 15-30.

[26]LIEBERMAN M D， SANKARANARAYANAN J， SAMET H. A fast similarity join algorithm using graphics processing units [C] //Proc of IEEE ICDE’08. Piscataway， NJ： IEEE， 2008： 1111-1120.

[27]YANG Xiaochun， WANG Bin， LI Chen. Cost-based variable-length-gram selection for string collections to support approximate queries efficiently [C] //Proceedings of the 2008 ACM SIGMOD international conference on Management of data. New York： ACM， 2008： 353-364.

[28]LI Chen， WANG Bin， YANG Xiaochun. VGRAM： Improving performance of approximate queries on string collections using variable-length grams [C] //Proceedings of the 33rd international conference on Very large data bases. San Francisco， CA： Morgan Kaufmann， 2007： 303-314.

[29]LI Chen， LU Jiaheng， LU Yiming. Efficient merging and filtering algorithms for approximate string searches [C] //Proc of IEEE ICDE’08. Piscataway， NJ： IEEE， 2008： 257-266.

[30]CHAUDHURI S， DAS SARMA A， GANTI V， et al. Leveraging aggregate constraints for deduplication [C] //Proceedings of the 2007 ACM SIGMOD international conference on Management of data. New York： ACM， 2007： 437-448.

[31]ARASU A， R C， SUCIU D. Large-scale deduplication with constraints using dedupalog [C] //Proc of IEEE ICDE′09. Piscataway， NJ： IEEE， 2009： 952-963.

[32]WHANG S E， BENJELLOUN O， GARCIA-MOLINA H. Generic entity resolution with negative rules [J]. The International Journal on Very Large Data Bases， 2009， 18（6）： 1261-1277.

[33]FAN Wenfei， JIA Xibei， LI Jianzhong， et al. Reasoning about record matching rules [J]. Proceedings of the VLDB Endowment， 2009， 2（1）： 407-418.

[34]ARASU A， CHAUDHURI S， KAUSHIK R. Transformation-based framework for record matching [C] //Proc of IEEE ICDE’08. Piscataway， NJ： IEEE， 2008： 40-49.

[35]ARASU A， CHAUDHURI S， KAUSHIK R. Learning string transformations from examples [J]. Proceedings of the VLDB Endowment， 2009， 2（1）： 514-525.

[36]ARASU A， KAUSHIK R. A grammar-based entity representation framework for data cleaning [C] //Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. New York： ACM， 2009： 233-244.

[37]CHEN Z， KALASHNIKOV D V， MEHROTRA S. Adaptive graphical approach to entity resolution [C] //Proceedings of the 7th ACM/IEEE-CS joint conference on Digital libraries. New York： ACM， 2007： 204-213.

[38]SINGLA P， DOMINGOS P. Entity resolution with markov logic [C] //Proc of IEEE ICDM’06. Piscataway， NJ： IEEE， 2006： 572-582.

[39]SHU Liangcai， LONG Bo， MENG Weiyi. A latent topic model for complete entity resolution [C] //Proc of IEEE ICDE'09. Piscataway， NJ： IEEE， 2009： 880-891.

[40]CHRISTEN P. Automatic record linkage using seeded nearest neighbour and support vector machine classification [C] //Proc. of SIGKDD. New York， USA：ACM， 2008.

[41]DONG X， HALEVY A， MADHAVAN J. Reference reconciliation in complex information spaces [C] //Proceedings of the 2005 ACM SIGMOD international conference on Management of data. New York： ACM， 2005： 85-96.

[42]SINGLA P， DOMINGOS P. Collective object identification [C] //Proceedings of the 19th international joint conference on Artificial intelligence. San Francisco， CA： Morgan Kaufmann， 2005： 1636-1637.1