智慧搜索中的實體與關聯關系建模與挖掘

王曉陽，鄭驍慶，肖仰華

（復旦大學 計算機科學技術學院 上海市數據科學重點實驗室，上海 201203）

1 引言

自萬維網（World Wide Web）誕生以來，經歷半個多世紀的迅速發展與演化，其形式內容與應用模式都發生了顯著的變化。網絡應用模式從由專業人員開發、以高訪問量為目標的綜合門戶網站為主導的Web1.0時代，發展至眾人皆可參與、高度交互的社交媒體Web 2.0時期。萬維網正在向更高級的、以語義和智能技術應用為代表的Web3.0發展，更加強調通過綜合多源異質信息，以提供個性化的智能解答與服務。

與此同時，大數據概念及技術迅速滲入社會各層面。大數據的目標是從存在“噪聲”的海量多源異質異構數據中，自動高效地發掘有價值的信息。將大數據分析中技術共性部分抽取出來，加以擴展，開發新一代面向網絡空間的搜索引擎，推進搜索引擎向對象多元化、數據多樣化、信息融合化、解答智能化的方向發展，從而能夠提供契合用戶搜索意圖的智慧解決方案——“大搜索”的概念也應運而生[1]。

大搜索或稱“智慧搜索”，指的是根據搜索請求，在網絡空間中進行搜索，形成相應的智慧解決方案，最后返回以解決方案為搜索結果的過程。它與傳統搜索最大的不同在于：它的搜索內容和對象由傳統的文本信息擴展到了物體、信息和人物，以及他們之間的關聯關系；它要求從網絡空間中獲取智能解答方案而非簡單的返回相關網頁。

實現智慧搜索面臨以下挑戰。1）網絡空間的數據獲取與組織。當前網絡空間中所描述的實體對象（如人、物、概念、事件等）及關聯關系（如朋友、購買、參與等）的數量巨大、種類繁多。數據來源可包括互聯網、社交網絡、時空數據、企業、運營商等。智慧搜索需要融合多渠道、多模式的各種類型數據，挖掘和發現其中潛在的、有價值的信息，并且形成相應的知識框架及索引體系，以便于搜索、查詢與利用。2）用戶意圖的準確理解。用戶查詢輸入方式多樣，充滿了語義方面的歧義。這需要智慧搜索能夠洞察與理解用戶真實的搜索意圖，在海量、多源、異構、多態的數據中，利用他們之間語義關聯關系，實現實體對象及其關聯關系相關信息的有效搜索，提供最貼合用戶需求的搜索結果。3）滿足用戶查詢需求的智慧方案形成。傳統搜索引擎一般只能為用戶提供符合搜索要求的存在性信息（相關的網頁），而用戶的意圖具有多樣化、個性化等特點，需要根據其意圖形成一系列可供選擇的智慧解決方案。這需要實現搜索解答方案的智慧化，為用戶求解出智慧答案。因而如何根據用戶的搜索意圖，基于知識倉庫對有關知識進行求解，通過推理演算形成若干綜合的智慧解決方案則成為智慧搜索技術的關鍵所在。

應對上述智慧搜索技術的挑戰，一個重要的任務就是對實體對象及關聯關系進行建模，將網絡空間包含的各類實體關聯知識用有效的組織方式存儲，以支持智慧搜索。這里，“實體對象”或簡稱“實體”應被理解為廣義的對象，包含世界中客觀存在的事物以及人類思維空間中的概念，他們之間相互作用、制約，由此形成一定的“關聯關系”或簡稱“關聯”。實體可以是名人、城市、球隊、電影、地標性建筑、藝術品、概念、事件等，關聯則可以是人與人、概念與地點、人與物品以及地點與物品等之間存在的關系。利用實體以及他們之間的關聯，不僅可以提高搜索精度和優化搜索結果，還可以支撐語義分析、關聯分析、知識搜索和智能推薦等高層的服務。

簡單地說，實體對象與關聯關系建模就是要從網絡空間中抽取實體及關聯信息，形成知識庫。這是個工業界及學術界共同關心的問題，谷歌和百度的知識圖譜、搜狗的知立方都是這類知識庫的實例。表1顯示部分公開的知識圖譜及它們的規模。廣義上講，這個建模問題本質上是解決如何使用計算機進行大規模多源知識的獲取、組織和使用的問題。它的必要性表現在以下方面。

1)實體對象及關聯關系建模是跨越語義鴻溝的關鍵，背景知識缺乏是語義鴻溝難以跨越的一個重要原因。現有機器可讀的知識庫在質量上和完整性方面仍然難以達到人類語義理解的基本水平，但近年來研究開發的基于知識圖譜的知識庫，相對于傳統知識表示方法，在兼顧精準性的同時，在完整性方面取得了長足的進步，它為用戶意圖理解、語義消歧、信息整合等提供了必要的背景知識，使征服語義鴻溝又前進了一步。谷歌等搜索引擎已將基于知識圖譜的知識庫成功用于提高搜索結果準確性。

2)實體對象及關聯關系建模是知識有效運用的基礎。網絡空間所涉及的實體數巨大，已有的知識庫中實體數已達千萬量，關聯數則以億計，它們所形成的是典型的異構信息網絡。實體對象及關聯關系建模呈多模形態，常常需要用某種測度來表達實體及關系的出現頻率、強度等信息；需要用邊的方向表達關系的非對稱性；需要用概率體現數據源的不確定性等。上述特征對于實體對象及關聯關系模型提出更高的要求，設計良好的模型是其上進行高效查詢、更新和推理的基礎。

3）實體對象及關聯關系建模是搜索智慧化的前提。實體對象及關系模型相對于領域本體和傳統語義網絡而言，其實體覆蓋率更高，語義關系也更加全面而復雜。利用實體對象及關聯關系可以對搜索結果行系統的語義分析，將用戶查詢映射到知識庫的概念上，從而用于優化搜索結果。還可利用已知的實體對象及關系進行推理，產生新知識，這種能力是問題解答、自動服務生成、智慧方案形成等的技術前提。

表1 公開的知識圖譜

以下介紹與討論智慧搜索中實體對象及關聯關系建模相關的關鍵技術與方法，其技術之間的關系如圖1所示。

圖1 智慧搜索中實體對象及關聯關系建模關鍵技術關聯

2 知識圖譜

實體或概念是世界中客觀存在的事物，他們之間相互作用、制約，由此形成一定的關系。實體與關系建模本質上是解決如何使用計算機進行大規模多源知識的表示、獲取和使用的問題。目前，實體對象及其關系建模工作較多地圍繞知識圖譜展開。

知識圖譜是采用語義檢索技術從多種信息源收集與某一主題相關的實體或概念，以及他們之間的關聯所形成的網絡圖。圖中的節點對應實體或概念，圖中的弧對應實體或概念之間的關聯關系。

大搜索借助知識圖譜，通過深化現實世界中每個實體以及他們之間相互關系的理解，提高搜索精度和優化搜索結果。語言的歧義性會給搜索帶來了困難，例如當用戶輸入查詢詞“蘋果”，傳統搜索引擎無法理解用戶想要查詢的是水果還是公司。基于知識圖譜的智能搜索將所有這些可能性歸納分組，用戶僅需點擊其中一組即可看到針對特定含義的所有搜索結果。有了知識圖譜，搜索引擎可以更好地理解用戶的查詢，從而提供與該查詢更相關的內容，即根據不同的實體，展示最相關的事實。如圖 2所示，當用戶搜索“Marie Curie”（居里夫人）時，不僅可以看到與居里夫人相關的網頁，還可以看到有關居里夫人教育經歷、科學貢獻和社會關系等信息。利用知識圖譜還可以提供語義分析、關聯分析、知識搜索和智能推薦等知識服務。

圖2 知識圖譜優化搜索結果的例子（摘自Google搜索結果）

3 知識獲取

知識圖譜需要各種自動化知識獲取方法來補充相關的知識（即實體及其關系），其中存儲的知識越豐富，則解決問題的能力也越強。關聯信息發掘是一種面向任務的信息獲取方式，是指以一定的策略和方法去采集、獲取、發掘用戶需要的數據與信息的過程。關聯信息發掘的工作過程如下。首先，以已有的知識圖譜為引導，把所有可能的數據源都搜集起來，包括互聯網上的網站、社交網絡、網絡服務等，以及物聯網、視音頻監控的數據等，并且針對每一種數據源設計相應的數據獲取方式，如網絡爬蟲方式、API數據獲取方式等；之后，對所有數據源進行分類，類別層次是一個多層次多維度的分類過程，根據用戶需求的變化，數據源類別層次應能做相應調整；當接受到用戶的定向獲取任務時，根據用戶需求確定數據源的類別，并在相應類別的數據源中進行基于任務的數據獲取；最后，對所有數據源獲取的數據進行結果的綜合，包括去重、清洗、結果融合等，并把最終結果返回給用戶，并且對其中共性的內容用于更新已有知識圖譜。

例如：通過搜索意圖理解確定用戶關心“達芬奇”相關的信息，則在互聯網上獲取維基百科、FreeBase以及普通網頁上關于達芬奇的介紹、照片，與達芬奇相關的音視頻等信息，另外，通過深入分析，還可以把達芬奇的作品如“蒙娜麗莎”的相關信息、圖片，以及同時期的藝術家“米開朗基羅”的相關信息等一起獲取過來，之后再對獲取的信息進行去重、清洗等預處理操作，最后把處理后的數據返回給用戶。

關聯信息發掘的關鍵技術除了傳統數據集成任務所需的數據清洗、數據去重、數據融合、沖突消解和數據轉換等數據預處理技術外，還包括直接和間接信息發掘技術。

3.1 直接獲取

直接信息獲取來源包括：互聯網、物聯網、視頻監控、社交網絡、專業領域數據等。

1)互聯網數據獲取是指對互聯網中的大數據進行高度并行的自動采集，并迅速收集到系統中的數據獲取過程。互聯網數據獲取包括網頁類獲取和服務類數據獲取2種方式，其中，網頁類服務獲取主要采用網絡爬蟲自動獲取網頁上的內容，網絡爬蟲可以按照一定的策略自動在互聯網上蔓延以獲取更多相關信息；服務類數據獲取主要采用服務接口調用的方式獲得網絡服務數據。

2)物聯網數據獲取是指通過RFID數據采集技術或者無線傳感器網技術等方式獲取物聯網數據。RFID數據采集技術是通過標簽閱讀器和標簽接收器，定時或實時地收集人、物體、設備、環境、狀態等基本信息。無線傳感網技術是由許多在空間中分布的傳感節點組成的一種無線通信計算機網絡，這些傳感節點協作地監控不同位置的物理或環境狀況（如溫度、聲音、振動、壓力、運動或污染物），其應用涉及軍事、城市公共安全、公共衛生、安全生產、智能交通、智能家居、環境監控等領域。

3)視頻監控數據獲取是對于視頻監控系統和互聯網上的視頻數據進行收集并集成到系統中的過程。視頻監控系統一般擁有大量的視頻監控設備，視頻監控設備產生的視頻數據通過專用網絡實時傳輸至視頻監控系統的數據存儲設備上，對于已存儲的視頻數據可以通過其調用接口進行獲取。互聯網上的視頻一般具有特定的數據格式和相應的文本說明，可以通過網絡爬蟲利用合理的爬取策略來獲取視頻數據。

4)社交網絡數據獲取是指對于各類社交網站中的相關數據進行自動收集并迅速集成到系統的過程。社交網絡數據有表層和深層網絡數據2類，如科研合作網絡DBLP屬于表層網絡，而新浪微博屬于深層網絡。對于表層網絡中網頁信息的獲取,可以直接使用爬蟲程序對這些存儲信息的網頁進行解析，從標簽屬性值中抽取需要的信息。與表層網絡相反，深層網絡將頁面信息存儲在后臺數據庫中，只有通過查詢接口查詢才能由服務器動態生成并返回或者獲取權限后才能查看，并沒有超鏈接指向這些網頁，不能被傳統的搜索引擎索引到。因此，獲取這些數據主要包含2種方式：一是通過查詢接口查詢由服務器動態生成并返回查詢結果；二是僅對注冊用戶開放的信息，只有登錄后才可查看專有網絡信息。

5)專業領域數據獲取是根據需要，收集與某專業領域相關信息的過程。以醫療健康數據獲取為例，它是對于醫療健康相關的信息系統和互聯網上有關醫療健康的大數據進行高度并行的自動采集，迅速收集到系統中的數據獲取過程。醫療健康信息系統包括醫院信息系統、放射信息系統、實驗室信息系統、醫學影像存檔與通信系統、臨床信息系統、公關衛生信息系統、電子病歷信息系統等，而互聯網上有關醫療健康的數據有醫學新聞博文、專業期刊雜志等。

3.2 間接獲取

基于用戶的搜索需求，間接信息發掘通過與智慧搜索知識推演系統的交互，基于知識推演給出深層次的搜索任務，從而獲得更多面向任務的數據，并對獲取的數據進行融合，最終滿足用戶的搜索需求。

間接信息發掘主要包含以下步驟。

1)以用戶的搜索需求和直接數據獲取技術得到的數據作為輸入，將其提交給智慧搜索知識推演系統。

2)知識推演系統根據用戶的搜索需求和已經獲得的數據進行推演，如果該搜索需求仍不存在知識推演系統中，則將其返回給間接信息發掘系統。

3)間接信息發掘系統根據當前收集相關數據和查詢需求，發出新的查詢請求，并將收集到的數據返回給智慧搜索知識推演系統。

4)知識推演系統對用戶的搜索需求和獲得的信息進行推演，判斷其是否滿足用戶的搜索需求。如果滿足，則直接返回，推演結束；如果不滿足，則重復步驟2)到步驟4)，直到獲取的數據滿足用戶的搜索需求。

5)將滿足用戶搜索需求的結果返回給用戶。

例如，用戶搜索“2014年全球總體失業率是多少”。使用直接數據獲取技術會得到一些零散的與失業相關的數據，無法滿足用戶搜索需求。此時，間接信息發掘系統將用戶的搜索需求以及已經獲得零散數據提交給智慧搜索知識推演系統。知識推演系統推演得出全球的總體失業率可以通過綜合不同國家和地區的失業率數據得到，因此，將各國的失業率作為查詢需求返回給間接信息發掘系統。間接信息發掘系統進行查詢并將得到的數據返回給知識推演系統。系統推演發現，除了美國，其他各國2014年的失業率數據都可以得到。知識推演系統進一步推演得出通過查詢美國每個季度的失業率來綜合得到的美國年平均失業率。因此，將這一查詢請求提交給間接信息發掘系統。間接信息發掘系統進行查詢并將查詢得到的數據返回給知識推演系統。知識推演系統推演發現將所有數據融合即可得到滿足用戶搜索需求的數據。因此，知識推演系統將最終融合后的數據返回給間接信息發掘系統，間接信息發掘系統將結果返回用戶。

4 知識倉庫

知識圖譜包羅萬象，可以看成是比較初級和粗糙的知識。為了能夠支持高層的智能搜索、分析和推理服務，需要對知識圖譜中所包含的數據進一步深度加工。在知識圖譜中，一個實體可能存在著數量眾多的關聯關系，并且具備相同特征的實體又散布在圖譜的各處，而基于知識圖譜的具體處理和分析任務往往僅涉及部分子圖和某些實體的部分關系。如何在語義層面對知識圖譜中存儲的知識進一步的組織和建模成為最大程度地發揮知識圖譜作用的關鍵。這個層次的建模需要支持對知識圖譜中符合某一語義定義的實體進行快速聚合，并且能夠從多個維度對相關的實體集合進行分析，從而有利于發現各種規律或現象。此外，預先對知識圖譜中的數據從不同維度進行組織和聚合，從而形成知識倉庫，能夠加快完成各種查詢和分析的任務。

知識倉庫是在整個知識圖譜上，或者在滿足預先定義或動態生成模式所形成的目標對象和關聯對象所形成的子圖上，通過系統地加工、匯總和整理所得到的結構化數據環境。知識倉庫采用基于圖的索引和分布式處理等技術能夠對圖中的對象從不同維度（或屬性）和層次進行聚合（aggregate）、鉆取（roll up/drill down）和旋轉（pivot）等操作，以利于其上進行聯機分析處理、數據挖掘，進而快速有效地從大量數據中分析出有價值的資訊。如圖3所示，根據定義模式從知識圖譜中定位和收集目標人群及其關聯人群之后，可以通過地域、性別、年齡3個不同維度對目標人群和關聯人群所組成的網絡，結合其他相關信息進行焦點對象發現、多維度統計分析、對象行為預測、網絡結構相似度分析等。

圖3 基于知識倉庫多維分析的例子

5 查詢與推理

知識圖譜上的查詢處理是管理和使用知識圖譜的前提，也是獲取蘊含于知識圖譜中語義信息的基本操作。例如獲取概念間的語義距離，獲取一個或者一組實體的概念描述，獲取句子的主題，對多義詞進行消歧等任務，都可以轉化為在知識圖譜上的查詢操作。知識圖譜上的推理是從已知的知識產生新知識的過程。例如：從“配偶 ＋ 男性”推理出“丈夫”概念、從“應天是南京明朝時的名稱 ＋建康是南京古稱”推理出“應天和建康是同一城市在不同時期的稱謂”。推理可以用于補充知識圖譜的知識，也可以根據需要即時執行。

大數據是智慧搜索的處理對象，將搜索響應時間控制在合理的范圍之內是系統成功的關鍵因素之一。知識圖譜作為大數據的數據源之一，往往包含千萬量級的實體和關系。為了提高知識圖譜的查詢性能，需要將知識圖譜劃分成若干子圖，并且存儲在不同的設備，然后通過分布式處理、并行計算、查詢優化、索引技術來縮短查詢的完成時間。知識圖譜的推理一般采用基于規則的方法，規則既可以是基于數理邏輯學的邏輯規則，也可以是基于認知心理學的產生式規則。規則既可以人工定義，也可以通過學習獲得。由于知識來源于動態、開放的網絡，具有不可靠性，因而規則推理系統一般需要具備處理不確定推理的能力。

如果充分利用網頁鏈接關系蘊含的信息是Web搜索引擎超越傳統信息檢索系統的基礎，那么如何高效利用網絡空間巨規模實體關聯信息，將是智慧搜索取得成功的基礎。智慧搜索能帶來巨大的價值，不僅僅是因為利用了更多種類的數據或某一類型更大量的數據量，更主要在于其將充分發掘不同實體對象的跨域關聯信息。

實體關聯可以采用表和圖2種方式來表達。相比之下，圖更適合表達稀疏、高維、海量的關聯數據，表則會面臨極高的連接、查詢和存儲的開銷。因此，圖是智慧搜索系統面向網絡數據的一種最合理的表達抽象。智慧搜索支撐平臺主要需要提供巨規模實體關聯數據的存儲和處理能力。

6 知識更新與演化

知識的演化與更新是指知識在時間軸上不斷發展的一種動態變化，代表了知識的流動和變遷，即通過往知識倉庫中添加新節點，并與網絡中已有的節點進行連接，從而實現對知識的演化和更新。

例如，維基百科可以將用戶發布的知識作為一個新的節點，通過將這一節點加入已有的知識網絡，從而實現對知識庫中原有知識網絡結構的動態更新。又如，隨著計算機技術的發展，以前所未聞的可穿戴式計算機應運而生，從而賦予了移動式計算機新的技術內涵。可穿戴式計算機為可穿戴于身上外出進行活動的微型電子設備，對于這種以前未在知識網絡中出現的新知識，如何將其添加到知識庫中，從而實現知識的演化和更新呢？其實，可以根據可穿戴式計算機的定義，利用知識網絡中實體之間的關系，采用數據挖掘中的相關技術，如聚類技術，將其劃入相應的知識社區中，從而實現知識網絡的動態更新，最終更新知識庫系統。

知識更新演化過程既反映知識網絡的時序結構變遷，又體現知識和概念的內在涵義流變，演化模型是知識網絡內在作用模式及作用過程的抽象表達。對演化過程的探討既是分析知識網絡結構的基礎，也是探討知識熱點形成及創新趨勢形成的基礎。

7 數據存儲與計算平臺

數據存儲與計算支撐平臺用于存儲、管理泛在網絡空間的數據，支持智慧搜索的查詢、統計和分析處理，包括高效知識提取和秒級搜索匹配等。

支撐平臺的挑戰主要包括2個方面。1）數據普適化，包括文本數據、音視頻、地理數據、社交媒體關系數據、物聯網數據等，這些大規模的非結構化數據需要通用的存儲和計算模型來進行有效管理。2）查詢、挖掘和分析多樣復雜（如關鍵字查詢、大圖查詢、時空查詢、聚合查詢、聚類分類、時序挖掘等），且具有嚴格的反饋時間要求。對普適化網絡空間數據的存儲、組織和管理是保證實體關系、知識抽取、搜索匹配能力的核心問題。

關系數據庫管理系統和數據倉庫系統已經在過去幾十年中發展成為一項較為成熟的技術，主要用于管理結構化數據，無法有效存儲組織形式松散的網絡文本、多媒體等非結構化數據，并且由于大量的加鎖操作和日志登記限制了數據更新性能。隨著網絡檢索和大數據技術的快速發展，近些年在非結構化數據管理方面進一步形成了基于GFS和HDFS等分布文件系統的NoSQL家族，典型產品包括 HBase、Cassandra、MongoDB、Redis、Neo4J等，以及著名的Map-Reduce分布式計算框架。這些數據庫普遍采用列存的方式來達到更好的數據壓縮，數據庫集群具有較好的可伸縮性，并且提供了傳統搜索引擎所需的簡單索引。但是這些NoSQL數據庫無法有效支持新一代“智能搜索”，其主要原因如下。

1)智能搜索是一種情景敏感、基于語義內容的智能檢索，根據不同搜索需要以多層次多維度的方式快速定位數據，因此現有數據庫的數據索引和查詢優化需要以可兼容的方式擴充，為大搜索處理提供底層的定制支持。

2)現有數據庫主要基于單一的數據模式，例如圖模式、鍵值對模式以及關系模式等，分別對應著單一模式的數據。但是智能搜索集成了泛在網絡空間數據，因此需要在模式層進行整合，以更加高效的方式管理普適化的巨規模網絡數據。

3)智能搜索需要對網絡數據深加工，構建知識圖譜并在此基礎上發掘領域知識，需要執行大量的復雜挖掘和機器學習算法，大量的迭代處理無法在常規的NoSQL框架之下有效運行。隨著內存存儲能力的快速提升，可以在系統架構中引入內存計算框架來解決該類需求。

因此在智能搜索系統構建中，需要研發面向智能搜索的通用數據存儲與計算平臺，以分布式框架作為底層支撐，充分利用新型硬件效能（如內存計算、固態硬盤等，顯著降低數據掃描的I/O代價），更加合理地組織管理泛在網絡空間的異構數據，保證大搜索中各類復雜查詢、統計分析、數據挖掘、知識抽取的快速處理。

8 相關工作

互聯網上的搜索引擎已有20多年的歷史，從最初的人工歸類，到自動關鍵字搜索，一直到最近的知識性搜索服務。下面圍繞實體對象及關聯關系在網絡搜索中的應用，分析國內外研究現狀。

1)知識庫在網絡搜索中的使用

到目前為止，實體對象及其關系建模工作較多地圍繞知識圖譜（knowledge graph）展開。知識圖譜簡單地說就是一個“主謂賓”三元組的集合，其中“主”和“賓”是實體對象，“謂”是關聯關系。2012年 5月Google發布了其基于知識圖譜智能化搜索功能，通過對搜索進行系統的語義分析，使用戶的每個查詢關鍵詞都能映射到知識庫的概念上，從而用于優化搜索結果。知識圖譜相對于本體和傳統語義網絡而言，實體對象覆蓋率更高、語義關系也更加全面而復雜。目前學術界與工業界均呈現出一股構建和使用知識圖譜的熱潮。除Google之外，微軟、百度、搜狗等公司都推出了各自的知識圖譜，典型代表包括KnowItAll[2]、TextRunner[3]、Probase[4]、YAGO[5]、DBpedia[6]、Freebase[7]等。

當前知識圖譜的研究工作主要從構建與應用2個方面展開。知識圖譜構建從其數據源來看可分為2類：一類是萬維網的頁面，另一類是相對結構化的在線百科。以前者為來源的典型知識圖譜包括KnowItAll[2]、TextRunner[3]和 Probase[4]。KnowItAll基于規則模板抽取實體或概念之間的關系；TextRunner提出了自監督學習方法改善了KnowItAll需要人工定義規則的缺點；為了進一步提高關系抽取的準確性，Probase采用基于語義的迭代方法抽取出更多更準確的ISA關系。而以在線百科為數據來源的知識圖譜包括YAGO和DBpedia等。各類知識圖譜已經在各類應用中發揮威力。Google利用Freebase為用戶提供更加智能化的搜索結果[8]。微軟利用Probase理解Web表格[9]和查找話題[10]。蘋果公司利用知識圖譜進行智能問答[11]；利用YAGO增強地圖的實時性[12]；利用 DBpedia推薦音樂[13]、標簽識別[14]以及信息抽取[15,16]等。

國內也有研究團隊從事這方面的研究，比如中科院計算所在知識抽取方面做了大量的工作，有基于圖和圖上推斷的CIIGA方法[17]，在非結構化的文本中抽取實體并連接到知識庫中，可以對現有的知識庫做大量的補充。OpenKN[18,19]可用于取大量新的實體和概念，進而不斷對知識庫進行更新。

上述知識圖譜方面的工作，增加了搜索的智能性，在提高用戶體驗方面有著深遠的影響。知識圖譜的研究及開發也產生了大量的自然語言處理以及機器學習方面的理論和方法，極大地推進了領域的成長。文獻[20]的工作主要點在于利用數據融合等方法，提高知識圖譜的質量，在去除歧義、多名、錯誤等方面，有了長足的進步。但如Sarma等[21]和Kuzey等[22]指出，現行知識圖譜技術偏重已知的實體，對不斷涌現的新興實體及其關聯，尤其是事件性的關聯，仍沒有相應方法。

2)知識庫存儲及查詢相關研究

RDF作為語義萬維網技術的資源表示標準，許多知識圖譜都選擇RDF或者類似RDF的方式來表示知識。目前RDF查詢研究重點在于查詢語言的有效實現方法，但對查詢模型的語義缺乏必要考慮。早期RDF查詢多實現在關系數據庫系統之上，利用關系表存儲RDF數據，再將RDF查詢轉換為對應的SQL查詢。其中典型的查詢與存儲系統包括：Sesam[23]、Jena2[24]、3store[25]、RDFSuite[26]。近期的焦點在于進一步提升RDF查詢性能。如Eugene[27]使用RDF_MATCH 表函數，Abadi[28]利用垂直分片，Hexastore[29]通過常數倍的額外索引開來提升 RDF查詢性能。近RDF查詢研究的核心是SPARQL查詢語言，提高查詢性能關鍵是減少Join操作的開銷，MonetDB[30]和Hexastore[29]都提出了SPARQL的Join優化算法。Medha[31]則利用流方式在壓縮的RDF數據上生成最終結果而避免創建代價較高的中間連接表。Markus等[32]研究了SPARQL查詢的靜態優化問題，定義和分析了基本圖模式選擇的啟發式策略。Angela等[33]和Thomas[34~36]利用圖挖掘技術計算并記錄RDF圖中的頻繁最優路徑來估計不同Join順序的代價，用于查詢優化。Huang等[37]通過分割RDF數據和分解SPARQL查詢來提高查詢效率。Binna等[38]設計了內存數據庫SpiderStore來管理 RDF數據和快速執行SPARQL查詢。Weaver等[39]提出了并行的RDFS閉包計算方法，而Urbani等[40]使用MapReduce實現類似的計算。Myung 等[41]和 Rohlo 等[42]研究使用MapReduce實現SPARQL查詢。Manish Gupta等研究Top-k子圖的查詢[43]。

在國內，北京大學和中國人民大學在RDF數據管理方面做了較多研究工作。比如，gStore[44]是一種由圖作為存儲方式的能夠有效在動態RDF數據集上處理SPARQL查詢的方法，Zou等[45]提出了基于RDF數據的解決自然語言自動問答的方法，Yang等[46]提出了自動分割RDF數據的方法來提升查詢效率并同時考慮了減少數據冗余，Du等[47]研究了在集群環境下RDF數據分割和替換的策略，Bian等[48]還提出了基于實體屬性表單來補充知識庫中RDF數據的方法。

RDF本質上以“主謂賓”的方式表達實體之間的關聯關系。理論上，這個形式有很強的表達能力，但對復雜實體（比如事件性實體時）一般采用隱含式表達。比如，在“事件本體模型”[49]中，事件作為實體，和事件有關的實體與此事件實體的關聯（事件S涉及實體A）即可用“主謂賓”模式建立，而事件的時間、地點，則也作為實體與事件實體簡單關聯。Trame等[50]對怎樣用RDF表示事件有所討論，結論是簡單的RDF很難自然地表達事件。即使是時間這個屬性（也有把時間概念作為實體），基于RDF的表達也不夠自然[50]。智慧搜索對各類顯性及隱性實體必須用簡單的方法，使之與人類一般認知規則相配，以便查詢。

由于現行各類知識以簡單RDF形式存儲，故大量的圖查詢模型及技術可以應用知識庫查詢處理。目前大圖查詢研究工作主要圍繞可達性查詢、最短路徑或距離查詢、圖匹配查詢以及關鍵字查詢開展。這些研究一般剝離圖數據本身的領域背景，只在抽象的圖查詢模型上開展研究。圖算法固然在知識查詢方面有其作用，但當知識庫在簡單圖上進行擴充，得以表達事件類實體時，需要考慮在知識庫上的其他操作。

目前圖查詢算法大致有4類。1）可達性查詢。這一問題主要研究特定約束條件下的可達查詢，這些約束一方面使問題更為復雜，另一方面也為高效剪枝創造了條件。基本的約束是節點或邊上的標簽約束[51,52]和更為復雜的正則表達式約束[53]。2）最短距離或路徑查詢。當前主流方案都采用基于摘要（sketch）的框架。其基本思想是為每個節點創建固定大小的摘要，利用摘要估計節點之間的距離。目前有2類摘要方法：一是以到一組路標（landmark）節點的最短距離作為節點的摘要[54~58]；二是以節點在幾何空間中的坐標作為摘要[59,60]。這些方案以線性空間索引實現常量時間的查詢回答。第1類方法的研究側重于提高距離估計準確性。第2類方法的研究集中于幾何空間的選擇。Zhao等[59,60]先后提出基于歐式空間和雙曲空間最短距離查詢方案，并證實基于雙曲空間優于歐式空間。3）圖匹配查詢。這一問題的研究主要圍繞2個核心問題開展：非精確匹配意義下的子圖查詢、大圖上的子圖查詢。在非精確匹配方面，Fan等[61]率先提出基于圖模擬的圖匹配，將子圖匹配中邊到邊的嚴格映射放松為邊到給定長度內的路徑之間的映射。Zou等[62]進一步改進圖模擬高效算法。Ma等[63]則提出了強模擬以進一步強化匹配約束。為了處理大圖，Sun[64]、Ma[65]分別提出了相應的分布式子圖查詢方法和圖模擬算法從而支持快速大圖匹配。4）關鍵字查詢。這類問題是尋找圖中含有關鍵字的點和邊，各研究的差異主要在于返回子圖的結構約束不同，比如r半徑斯坦納（Steiner）圖[66]，r-極大團[67]。針對r半徑斯坦納圖，Li等[66]給出了一種基于圖劃分的快速查詢方法。Kargar[67]針對基r-極大團的圖上關鍵字查詢提出了一個返回top-k的近似算法。

3)數據立方模型

數據立方（data cube）的概念于1996年由Gray[68]引入數據分析領域。數據立方建立在關系數據庫之上，為分析者提供簡單易懂的概念模型和操作界面，把數據分析的操縱權從程序員手里奪走，交還給了分析用戶，為數據分析研究和產業做出了革命性的貢獻。對于這個成功，究其深層原因，是將數據以接近用戶習慣的認知方式呈現給用戶：將數據以多維度的形式，每個維度對應一類概念（如時間、空間），而每個概念又可以以不同粒度來觀察數據。

研究人員已將數據立方相關的概念用于其他分析工作。如Jiawei Han所帶領的研究團隊開展了文本數據的多粒度特性方面的研究[69,70]，支持文本數據多粒度分析，將大量的文本信息組織成層次結構，而后數據分析可以利用上卷、下鉆等操作在不同粒度上進行訪問。近期，該研究團隊又在圖數據上引入OLAP數據立方的概念，研究圖立方（graph OLAP和graph cube）[71,72]對圖數據分析的用途。

9 結束語

智慧搜索將會為人們帶來嶄新的搜索方式——知識服務，它是指從各種知識來源（包括知識圖譜和知識倉庫）中按照用戶的個性需求有針對性地提煉知識，并且用來解決用戶問題的高級階段信息服務過程。與傳統信息服務強調信息資源獲取（如文獻檢索）不同，知識服務側重于提供個性化、面向解決方案的服務。它根據用戶問題語義和上下文環境分析確定用戶的需求，通過多源信息和知識的重組與融合形成符合需要的知識產品。

實現大搜索的愿景，目前還面臨許多的挑戰，但同時也帶來眾多的研究機會。目前急需解決的難題包括：根據查詢的需求，從包括海量實體以及關系的泛在網絡空間中準確地獲取數據；全面和深度地理解用戶的真實搜索意圖；融合多渠道、多模式和實時復雜的數據，挖掘和發現其中潛在、有價值的信息；確保大搜索使用過程安全可信；根據用戶的搜索意圖，基于知識倉庫對關聯知識進行推理和求解，形成若干可行的智慧綜合解決方案。

大搜索是新一代具有“智慧”的搜索，能準確洞察和理解用戶的搜索意圖，在海量、多源、異構、多態、不確定的數據中，實現對與人物、物體和內容等相關信息的對象級搜索，為用戶提供最貼切的搜索結果。這勢必影響我國的社會、經濟和生活等各個方面，具有廣闊的應用前程。

[1] 方濱興,等.大搜索技術白皮書[M].北京:電子工業出版社,2015.FANG B X,et al.Big Search Technology White Paper[M].Beijing:Electronic Industry Press,2015.

[2]ETZIONI O,CAFARELLA M,DOWNEY D,et al.Web-scale information extraction in knowitall:(preliminary results)[A].Proceedings of the 13th International Conference on World Wide Web[C].ACM,2004.100-110.

[3]YATES A,CAFARELLA M,BANKO M,et al.Textrunner:open informationextractionontheweb[A].ProceedingsofHuman Language Technologies:The Annual Conference of the North American Chapter of the Association for Computational Linguistics:Demonstrations Association for Computational Linguistics[C].2007.25-26.

[4] WU W,LI H,WANG H,et al.Probase:a probabilistic taxonomy for text understanding[A].ACM SIGMOD International Conference on Management of Data[C].ACM,2012.481-492.

[5]SUCHANEK F M,KASNECI G,WEIKUM G.Yago:a core of semantic knowledge[A].16th International Conference on World Wide Web[C].ACM,2007.697-706.

[6] AUER S,BIZER C,KOBILAROV G,et al.Dbpedia:a Nucleus for a Web of Open Data[M].Springer Berlin Heidelberg,2007.

[7]BOLLACKER K,EVANS C,PARITOSH P,et al.Freebase:a collaboratively created graph database for structuring human knowledge[A].ACM SIGMOD International Conference on Management of Data[C].ACM,2008.1247-1250.

[8] SINGHAL A.Introducing the Knowledge Graph:Things,Not Strings Official Blog(of Google)[EB/OL].http://googleblog.blogspot.com/2012/05/introducing-knowledge-graph-things-not.html.Retrieved.

[9]WANG J,WANG H,WANG Z,et al.Understanding Tables on the Web Conceptual Modeling[M].Springer Berlin Heidelberg,2012.141-155.

[10]WANG Y,LI H,WANG H,et al.Toward Topic Search on the Web[R].Technical report,Microsoft Research,2010.

[11]Apple-Siri-frequently asked questions.Apple[EB/OL].http://www.siriuserguide.com/siri-faq/.

[12]HOFFART J,SUCHANEK F M,BERBERICH K,et al.YAGO2:exploring and querying world knowledge in time,space,context,and many languages[A].20th International Conference Companion on World Wide Web[C].ACM,2011.229-232.

[13]PASSANT A.Dbrec—music recommendations using DBpedia[A].The Semantic Web-ISWC 2010[C].Springer Berlin Heidelberg,2010.209-224.

[14]GARCIA A,SZOMSZOR M,ALANI H,et al.Preliminary results in tag disambiguation using DBpedia[A].Collective Knowledge Capturing and Representation[C].California,2009.

[15]Wu F,Weld D S.Automatically refining the wikipedia infobox ontology[A].17th International Conference on World Wide Web[C].ACM,2008.635-644.

[16]KASNECIG,RAMANATHM,SUCHANEKF,etal.The YAGO-NAGA approach to knowledge discovery[J].ACM SIGMOD Record,2009,37(4):41-47.

[17]LIN H,JIA Y,WANG Y,et al.Populating knowledge base with collective entity mentions:a graph-based approach[A].Advances in Social Networks Analysis and Mining(ASONAM),2014 IEEE/ACM International Conference on[C].IEEE,2014.604-611.

[18]JIA Y,WANG Y,CHENG X,et al.OpenKN:an open knowledge computational engine for network big data[A].Advances in Social Networks AnalysisandMining(ASONAM),2014IEEE/ACM International Conference on[C].IEEE,2014.657-664.

[19]王元卓,賈巖濤,趙澤亞,等.OpenKN——網絡大數據時代的知識計算引擎[J].CCF通訊,2014,10(11):30-35.WANG Y Z,JIA Y T,ZHAO Z Y,et al.OpenKN—— knowledge computing engine in the big data era[J].CCF Communication,2014,10(10):30-35.

[20]LI Q,LI Y L,GAO J,et al.Resolving conflicts in heterogeneous data by truth discovery and source reliability estimation[A].Proceedings of the 2014 SIGMOD[C].2014.

[21]SARMA D JAIN A A,YU C.Dynamic relationship and event discovery[A].Fourth ACM International Conference on Web Search and Data Mining[C].ACM,2011.207-216.

[22]KUZEY E,VREEKEN J,WEIKUM G.A fresh look on knowledge bases:Distilling named events from news[A].23rd ACM International Conference on Information and Knowledge Management[C].ACM,2014.1689-1698.

[23]BROEKSTRA J,KAMPMAN A,VAN HARMELEN F.Sesame:an architecture for storing and querying rdf data and schema information[J].Spinning the Semantic Web:Bringing the World Wide Web to Its Full Potential,2003,197.

[24]WILKINSON K,SAYERS C,KUNO H A,et al.Efficient RDF Storage and retrieval in Jena2[A].The First International Workshop on Semantic Web and Databases[C].2003,3:131-150.

[25]HARRIS S,GIBBINS N.3store:efficient bulk RDF storage[A].Workshop on Practical and Scalable Semantic Systems[C].2003.

[26]ALEXAKI S,CHRISTOPHIDES V,KARVOUNARAKIS G,et al.The ICS-FORTH RDFSuite:managing voluminous RDF description bases[A].SemWeb[C].Hong Kong,China,2001.

[27]CHONG E I,DAS S,EADON G,et al.An efficient SQL-based RDF querying scheme[A].31st International Conference on Very Large Data Bases VLDB Endowment[C].2005.1216-1227.

[28]ABADI D J,MARCUS A,MADDEN S R,et al.Scalable semantic web data management using vertical partitioning[A]. 33rd International Conference on Very Large Data Bases[C].2007.411-422.

[29]WEISS C,KARRAS P,BERNSTEIN A.Hexastore:sextuple indexing for semantic Web data management[J].Proceedings of the VLDB Endowment,2008,1(1):1008-1019.

[30]SIDIROURGOSL,GONCALVESR,KERSTEN M,etal.Column-store support for RDF data management:not all swans are white[J].Proceedingsofthe VLDB Endowment,2008,1(2):1553-1563.

[31]ATRE M,CHAOJI V,ZAKI M J,et al.Matrix bit loaded:a scalable lightweight join query processor for RDF data[A].19th International Conference on World Wide Web[C].ACM,2010.41-50.

[32]STOCKER M,SEABORNE A,BERNSTEIN A,et al.SPARQL basic graph pattern optimization using selectivity estimation[A].17th International Conference on World Wide Web[C].ACM,2008.595-604.

[33]MADUKO A,ANYANWU K,SHETH A,et al.Estimating the cardinality of RDF graph patterns[A].Proceedings of the 16th International Conference on World Wide Web[C].ACM,2007.1233-1234.

[34]NEUMANN T,WEIKUM G.RDF-3X:a RISC-style engine for RDF[J].Proceedings of the VLDB Endowment,2008,1(1):647-659.

[35]NEUMANN T,WEIKUM G.The RDF-3X engine for scalable management of RDF data[J].The VLDB Journal,2010,19(1):91-113.

[36]NEUMANN T,WEIKUM G.Scalable join processing on very large RDF graphs[A].Proceedingsofthe 2009 ACM SIGMOD International Conference on Management of Data[C].ACM,2009.627-640.

[37]HUANG J,ABADI D J,REN K.Scalable SPARQL querying of large RDF graphs[J].Proceedings of the VLDB Endowment,2011,4(11):1123-1134.

[38]BINNA R,GASSLER W,ZANGERLE E,et al.Spiderstore:exploiting main memory for efficient RDF graph representation and fast querying[A].Proceedings of Workshop on Semantic Data Management(SemData@VLDB)[C].2010.

[39]WEAVER J,HENDLER J A.Parallel Materialization of the Finite RDFs Closure for Hundreds of Millions of Triples[M].Springer Berlin Heidelberg,2009.

[40]URBANI J,KOTOULAS S,OREN E,et al.Scalable Distributed Reasoning Using MapReduce[M].Springer Berlin Heidelberg,2009.

[41]MYUNG J,YEON J,LEE S.SPARQL basic graph pattern processing with iterative MapReduce[A].Proceedings of the 2010 Workshop on Massive Data Analytics on the Cloud[C].ACM,2010.

[42]ROHLOFF K,SCHANTZ R E.High-performance,massively scalable distributed systems using the MapReduce software framework:the SHARD triple-store[A].Programming SupportInnovationsfor Emerging Distributed Applications[C].ACM,2010.

[43]GUPTA M,GAO J,YAN X F,et al.Top-Kinteresting subgraph discovery in information networks[A].2014 International Conference on Data Engineering[C].2014.

[44]ZOU L,?ZSU M T,CHEN L,et al.gStore:a graph-based SPARQL query engine[J].The VLDB Journal—the International Journal on Very Large Data Bases,2014,23(4):565-590.

[45]ZOU L,HUANG R,WANG H,et al.Natural language question answering over RDF:a graph data driven approach[A].Proceedings of the 2014 ACM SIGMOD International Conference on Management of data[C].ACM,2014.313-324.

[46]YANG T,CHEN J,WANG X,et al.Efficient S`PARQL query evaluation via automatic data partitioning[A].Database Systems for Advanced Applications[C].Wuhan,2013.

[47]DU F,BIAN H,CHEN Y,et al.Efficient SPARQL query evaluation in a database cluster[A].Big Data,2013 IEEE International Congress on[C].2013.165-172.

[48]BIAN H,CHEN Y,DU X,et al.MetKB:enriching RDF knowledge bases with web entity-attribute tables[A].22nd ACM International Conference on Conference on Information & Knowledge Management[C].ACM,2013.2461-2464.

[49]RAIMOND Y,et al.The event ontology[EB/OL].http://motools.sourceforge.net/event/event.html.2007.

[50]TRAME J,KE?LER C,KUHN W.Linked Data And Time–Modeling Researcher Life Lines By Events[M].Spatial Information Theory.Springer International Publishing,2013.

[51]JIN R,HONG H,WANG H,et al.Computing label-constraint reachability in graph databases[A].2010 ACM SIGMOD International Conference on Management of data[C].ACM,2010.123-134.

[52]XU K,ZOU L,YU J X,et al.Answering label-constraint reachability in large graphs[A].Proceedings of the 20th ACM International Conference on Information and Knowledge Management[C].ACM,2011.1595-1600.

[53]FAN W,LI J,MA S,et al.Adding regular expressions to graph reachability and pattern queries[A].Data Engineering(ICDE),2011 IEEE 27th International Conference on[C].2011.39-50.

[54]GUBICHEV A,BEDATHUR S,SEUFERT S,et al.Fast and accurate estimation of shortest paths in large graphs[A].Proceedings of the 19th ACM International Conference on Information and Knowledge Management[C].ACM,2010.499-508.

[55]POTAMIAS M,BONCHI F,CASTILLO C,et al.Fast shortest path distance estimation in large networks[A].18th ACM Conference on Information and Knowledge Management[C].ACM,2009.867-876.

[56]TRETYAKOV K,ARMAS-CERVANTES A,GARCíA-BA?UELOS L,et al.Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs[A].20th ACM International Conference onInformationandKnowledgeManagement[C].ACM,2011.1785-1794.

[57]DAS SARMA A,GOLLAPUDI S,NAJORK M,et al.A sketch-based distance oracle for Web-scale graphs[A].Proceedings of the Third ACM International Conference on Web Search and Data Mining[C].ACM,2010.401-410.

[58]GOLDBERG A V,HARRELSON C.Computing the shortest path:a search meetsgraph theory[A].Sixteenth AnnualACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics[C].2005.156-165.

[59]ZHAO X,SALA A,WILSON C,et al.Orion:shortest path estimation for large social graphs[J].Networks,2010,1:5.

[60]ZHAO X,SALA A,ZHENG H,et al.Fast and scalable analysis of massive social graph[J].arXiv preprint arXiv:1107.5114,2011.

[61]FAN W,LI J,MA S,et al.Graph pattern matching:from intractable to polynomial time[J].Proceedings of the VLDB Endowment,2010,3(1-2):264-275.

[62]ZOU L,CHEN L,?ZSU M T,et al.Answering pattern match queries in large graph databases via graph embedding[J].International Journal on Very Large Data Bases,2012,21(1):97-120.

[63]MA S,CAO Y,FAN W,et al.Capturing topology in graph pattern matching[J].Proceedings of the VLDB Endowment,2011,5(4):310-321.

[64]SUN Z,WANG H,WANG H,et al.Efficient subgraph matching on billion node graphs[J].Proceedings of the VLDB Endowment,2012,5(9):788-799.

[65]MA S,CAO Y,HUAI J,et al.Distributed graph pattern matching[A].21st International Conference on World Wide Web[C].2012.949-958.

[66]LI G,OOI B C,FENG J,et al.EASE:an effective 3-in-1 keyword search method for unstructured,semi-structured and structured data[A].ACM SIGMOD International Conference on Management of Data[C].2008.903-914.

[67]KARGAR M,et al.A.Keyword search in graphs:finding r-cliques[J].Proceedings of the VLDB Endowment,2011,4(10):681-692.

[68]GRAY J,CHAUDHURI S,Bosworth A,et al.Data cube:a relational aggregation operator generalizing group-by,cross-tab,and sub-totals[J].Data Mining and Knowledge Discovery,1997,1(1):29-53.

[69]LIN C X,DING B,HAN J,et al.Text cube:computing ir measures for multidimensional text database analysis[A].Data Mining,ICDM'08.Eighth IEEE International Conference on[C].2008.905-910.

[70]ZHANG D,ZHAI C,HAN J.Topic cube:topic modeling for OLAP on multidimensional text databases[A].SDM[C].2009,9:1124-1135.

[71]CHEN C,YAN X,ZHU F,et al.Graph OLAP:towards online analyticalprocessing on graphs[A].Eighth IEEE International Conference on Data Mining[C].2008.

[72]ZHAO P,LI X,XIN D,et al.Graph cube:on warehousing and OLAP multidimensional networks[A]. ACM SIGMOD International Conference on Management of data[C].2011.853-864.