大數(shù)據(jù)探索式搜索研究

杜小勇，陳峻，陳躍國

（1.中國人民大學 教育部數(shù)據(jù)工程與知識工程教育部重點實驗室，北京 100872；2.中國人民大學 信息學院，北京 100872）

1 引言

關于大數(shù)據(jù)的討論，除了被廣泛認可的海量(volume)、異構(variety)、快變(velocity)3V特性[1]外，人們更關注于大數(shù)據(jù)的價值(value)?，F(xiàn)階段，主要通過2種技術手段來體現(xiàn)大數(shù)據(jù)的價值：數(shù)據(jù)服務(data serving)和數(shù)據(jù)分析。

1.1 數(shù)據(jù)服務與數(shù)據(jù)分析

數(shù)據(jù)服務是指將大數(shù)據(jù)組織管理起來，提供高效的數(shù)據(jù)查詢與信息檢索服務。數(shù)據(jù)查詢主要面向結構化類型的數(shù)據(jù)，采用基于鍵值對模型的NoSQL數(shù)據(jù)庫技術，以行鍵、列名、版本號來確定數(shù)據(jù)的邏輯單元，并通過行鍵、列名和版本等信息來進行基于鍵值的數(shù)據(jù)查詢。由于NoSQL數(shù)據(jù)庫弱化了數(shù)據(jù)事務一致性準則（采用最終一致性），數(shù)據(jù)索引相對簡單，事務類型單一，適于并行化處理，其在一定規(guī)模的集群下能夠達到較高的數(shù)據(jù)讀寫吞吐率。信息檢索是指從大規(guī)模的數(shù)據(jù)集中快速查找滿足用戶需求的資料或數(shù)據(jù)片段的過程[2]。用戶通過關鍵詞（或自然語言語句）來表達信息需求。為了快速得到反饋，必須預先構建好數(shù)據(jù)索引。完成檢索后，結果要根據(jù)與查詢的相關度進行排序。無論數(shù)據(jù)查詢還是信息檢索，一般都采用“提交問題—返回結果”的一次性交互模式，查詢處理利用索引，快速定位滿足用戶需求的數(shù)據(jù)。因此，數(shù)據(jù)服務對數(shù)據(jù)價值的利用是最直接的。

數(shù)據(jù)分析是指用適當?shù)慕y(tǒng)計分析方法對大量數(shù)據(jù)進行分析或建模，然后提取有用信息并形成結論，進而輔助人們決策的過程[3]。在這個過程中，用戶會有一個明確的目標，通過“數(shù)據(jù)清理、轉換、建模、統(tǒng)計”等一系列復雜的操作，獲得對數(shù)據(jù)的洞察，從而協(xié)助用戶進行決策。常見的數(shù)據(jù)分析有在線聯(lián)機分析處理(OLAP分析)與深度分析。OLAP分析一般采用SQL查詢語句對結構化數(shù)據(jù)進行多維度的聚集查詢處理；而深度分析則采用了復雜度較高的數(shù)據(jù)挖掘和機器學習中的一些方法，可以處理結構化數(shù)據(jù)甚至是非結構化數(shù)據(jù)。數(shù)據(jù)分析一般基于大量數(shù)據(jù)和較為復雜的運算模型，其結果信息量通常很大，適用于宏觀決策。而對于細節(jié)層面信息的獲取，數(shù)據(jù)分析缺乏如索引和訪問控制等方面的技術支持。

表1總結歸納了數(shù)據(jù)服務和數(shù)據(jù)分析2種方式的特點：1）在用戶信息需求層面，這2種手段都要求用戶有明確的信息需求，相比數(shù)據(jù)分析，數(shù)據(jù)服務的信息需求更加單一；2）在搜索對象層面，數(shù)據(jù)服務的對象是數(shù)據(jù)集合內(nèi)的某些元素，而數(shù)據(jù)分析的對象是整個數(shù)據(jù)集或其子集；3）在觀察角度層面，數(shù)據(jù)服務的角度是微觀的，數(shù)據(jù)分析的角度是宏觀的；4）在用戶目的層面，數(shù)據(jù)服務是側重于查詢資料和數(shù)據(jù)片段，而數(shù)據(jù)分析的目的側重于決策支持；5）在交互模式層面，數(shù)據(jù)服務與數(shù)據(jù)分析主要是一次性的交互模式。但在交互式場景中，它們也會遇到查詢調(diào)整的問題，用戶通過多輪的交互來滿足信息需求，而各輪之間卻是獨立的查詢或者分析任務。

表1 各類大數(shù)據(jù)價值挖掘方式比較

1.2 數(shù)據(jù)探索

以上2種方式分別從2個角度發(fā)掘大數(shù)據(jù)的價值，數(shù)據(jù)服務強調(diào)從微觀層面獲取滿足用戶需求的精準信息，數(shù)據(jù)分析強調(diào)從宏觀層面為用戶提供數(shù)據(jù)洞察，進而提供決策支持。這2種方式能有效幫助用戶解決很多常見問題，發(fā)現(xiàn)大數(shù)據(jù)固有的價值。但仍然存在諸多場景（例如學習、調(diào)研），單純的微觀層面的信息獲取和宏觀層面的數(shù)據(jù)分析都不能有效協(xié)助用戶去發(fā)現(xiàn)和探索數(shù)據(jù)中的價值，用戶更需要的是一種可以在微觀層面和宏觀層面進行自由切換的、深入淺出的、交互式的探索數(shù)據(jù)價值的方式。下面的旅行規(guī)劃問題是一個典型的例子。

小明第一次去某地旅游，為了旅途順利，想事先規(guī)劃一下。他大致思路如下。第1步，要選擇交通方式；第2步，要調(diào)研當?shù)刂档皿w驗的地方，如景點和小吃等；第3步，需要確定住宿；第4步，要設計規(guī)劃住宿地點到景點的交通路線。以上過程沒有明確的先后順序，但都需瀏覽、對比大量信息。在持續(xù)的瀏覽過程，他的某個決定隨時可能誘發(fā)其他某個環(huán)節(jié)的更改，進而引發(fā)全局的調(diào)整，比如更換住宿地點，那么交通路線需要重新設計。在這個過程中，小明需要不斷地重復“搜索—思考”的過程來完成這次旅行規(guī)劃。

結合上述例子，小明起初的目標是比較模糊的，他需要在不斷獲取信息的過程來調(diào)整搜索目標。此外，小明需要系統(tǒng)提供額外的信息進行引導，引導的過程中，目標隨時可能改變，這種改變的動機可能出自于獲取必要信息，也可能出于好奇心。出于這樣的目的，探索式搜索(exploratory search)的概念應運而生。

探索式搜索主要是針對目標可變的、持續(xù)的、多角度的搜索任務，其搜索過程是有選擇的、有策略的和反復進行的[4]。它將以找到信息為目的的傳統(tǒng)信息檢索模式變?yōu)橐园l(fā)現(xiàn)、學習和決策為目的的信息搜尋模式。這樣的搜索模式結合了大量的分析與人機交互過程，適合于人們從數(shù)據(jù)中發(fā)現(xiàn)和學習更多的內(nèi)容。在某些領域，數(shù)據(jù)的探索式搜索也被稱為數(shù)據(jù)探索。

目前，隨著大數(shù)據(jù)研究的興起，探索式搜索這種交互式的分析和探索數(shù)據(jù)價值的方式，逐漸引起人們的重視[5]。很多數(shù)據(jù)類型已經(jīng)有了探索式搜索的應用研究，如媒體數(shù)據(jù)[6]、網(wǎng)頁[7]、圖數(shù)據(jù)[8]、異構信息網(wǎng)絡[9]、關系型數(shù)據(jù)[10]、RDF知識庫[11]等。在這些應用中，尤其是面向大數(shù)據(jù)的探索式搜索方面，還有很多問題等待研究者們進行深入的研究。

2 探索式搜索

最近幾年，探索式搜索逐漸獲得相關領域研究者們的關注。數(shù)據(jù)庫領域頂級會議SIGMOD于2014年針對探索式搜索舉辦了首次研討會，與會專家從多個角度討論了探索式搜索的重要性與必要性，并將探索式搜索與以往的交互模式做了區(qū)分[12]。次年，SIGMOD會議再次針對探索式搜索的技術實現(xiàn)舉辦了研討會，與會專家從系統(tǒng)實現(xiàn)層面討論了探索式搜索所需要克服的技術挑戰(zhàn)[13]。

探索式搜索的概念是于2006年被數(shù)字圖書館領域的權威學者Marchionini在ACM通信上首次明確提出的[4]。而對于探索式搜索的討論最早源于2005年，馬里蘭大學的幾位專家主導舉辦了有關探索式搜索界面設計的交叉學科研討會，該研討會召集了人機交互、信息檢索、信息搜尋以及信息可視化等領域的專家，探討這門交叉學科的界面設計、評價方法以及認知過程[14]。此后，一系列研討會在相關頂尖會議上舉辦，如2006年SIGIR[15]討論了如何評估探索式搜索系統(tǒng)，2007年SIGCHI[16]討論滿足探索式搜索界面設計的要求以及面臨的挑戰(zhàn)。

2.1 探索式搜索的定義

Marchionini將人類對信息的需求從低到高分為3個層次[4]：1）探尋基本的事實，輔助解決一個短期的任務；2）聯(lián)系相關概念，幫助人們理解某個現(xiàn)象或者執(zhí)行某項較為復雜的任務；3）整合相關策略與知識，幫助成為某個領域的專家。為了支持后2個層次的需求，用戶需要通過不斷的交互過程，調(diào)整自己的信息搜尋目標，全方位多角度地了解相關領域的信息。因此，交互模式需要獲得更大的突破。

然而，“提交查詢—返回結果”的一次性交互模式仍是眾多數(shù)據(jù)庫和信息檢索系統(tǒng)所采用的交互模式（如圖1所示），用戶只需提出一個查詢，即可獲得與該查詢相關的結果。事實上，很多信息系統(tǒng)的實際應用卻經(jīng)常伴隨著多次的交互過程，用戶經(jīng)常要花費大量精力去反復瀏覽、對比和分析反饋查詢結果，用戶體驗糟糕。其本質(zhì)原因在于：1）用戶不夠了解數(shù)據(jù)域(data domain)，抽象而成的查詢不夠準確；2）一次性交互模式不能很好地適應用戶在檢索過程中對信息需求的多樣性與動態(tài)性，并且忽略了查詢過程的上下文語境等因素[17]，無法很好地協(xié)助用戶與系統(tǒng)交互。

為了改善上述缺陷，信息檢索引入了迭代式查詢的理念，幫助用戶逐步縮小查詢范圍，最終定位到他們所需的信息。但是，很多情況下，用戶并沒有明確的搜索目標，對知識的好奇是他們搜索的動機，他們需要在搜索過程中被引導，從而明確他們的目標?；谶@樣的背景，探索式搜索的概念被提出來了。

根據(jù)Marchionini[4]與White[17]給出的定義，探索式搜索由問題上下文與搜索進程2個相輔相成的主體構成，其問題上下文由用戶的信息需求驅動，這種需求是開放式的、持續(xù)的、多角度的；其搜索進程由用戶的行為組成，這種行為是有選擇的、有策略的和反復多次進行的。

2.2 探索式搜索的模型

通過分析用戶的信息需求，Marchionini[4]將用戶的搜索任務分為3類（如圖2所示）：1）查閱(lookup)：通過構建一個簡單、有效的查詢，在特定數(shù)據(jù)域中完成基本的信息檢索；2）學習(learn)：通過多次迭代查詢，對反饋的結果進行查閱、對比，最終整合吸收；3）調(diào)研(investigate)：通過多輪多次迭代查詢，不斷關聯(lián)此前學習到的知識，加以輔助，進一步對反饋的結果進行更深層次的探索。這些任務之間存在不同程度的交集，查閱作為最基本的搜索任務，經(jīng)常被其他兩項搜索任務所涵蓋，而學習是調(diào)研的重要組成部分。探索式搜索的目的是為了更好地解決學習與調(diào)研2項搜索任務。

圖1 基于“提交查詢—返回結果”的一次性交互模式

圖2 搜索任務

對于探索式搜索用戶群體而言，其最大的特點是因缺乏對背景知識的了解，沒能形成明確的搜索目標，其搜索的興趣點是被當前的查詢結果和與當前結果緊密關聯(lián)的數(shù)據(jù)內(nèi)容所引導和轉移的。與此同時，若用戶對某個興趣點感興趣，其隨時可以深入該興趣點，進一步挖掘信息。

為此，White[17]將探索式搜索抽象成為2個重要的過程：1）探索式瀏覽(exploratory browsing)；2）集中式搜索(focused searching)。探索式瀏覽的目的是為了更加開放地探索數(shù)據(jù)，在用戶未確定他們真正的搜索意圖前，探索式瀏覽會有策略地提供用戶更多的相關知識，幫助用戶在海量的數(shù)據(jù)中找到他們感興趣的內(nèi)容。集中式搜索目的是為了讓用戶更加深入地探索數(shù)據(jù)，當用戶確定他們某個階段的興趣點，集中式搜索會協(xié)助用戶不斷深入該領域，幫助用戶挖掘細節(jié)。

如圖3所示，為了讓用戶獲取更多的知識，以上2種模式會交替出現(xiàn)在整個搜索進程中，用戶隨時可以從某個興趣點轉移到另外一個興趣點。這種交替模式促進了用戶與系統(tǒng)間的良性交互，系統(tǒng)在搜索過程中更加了解用戶的習慣與特點，從而提供更相關的興趣點與更準確的內(nèi)容。此外，用戶的搜索目的也會隨著搜索進程的推進不斷波動，最終趨于穩(wěn)定。

圖3 探索式搜索模型

2.3 探索式搜索的特點

結合Marchionini[4]與White[17]的觀點，探索式搜索有以下幾項特點。1）搜索過程是長期的：用戶的每次搜索會話都應該被記錄下來，系統(tǒng)會分析利用這一連串會話，對用戶的行為進行分析，從而更好地協(xié)助用戶去探索數(shù)據(jù)；2）信息需求是開放式的、持續(xù)的、多角度的，用戶具備好奇的屬性，好奇會導致他們的信息需求在搜索進程中不斷發(fā)生變化，他們的搜索意圖也將會隨著搜索進程的推進而不斷波動，這種變化將會讓用戶了解更多面的信息；3）探索與發(fā)現(xiàn)是重點，相比基本的查閱，探索式搜索強調(diào)發(fā)現(xiàn)更多相關的內(nèi)容，從而幫助用戶更加全面地了解某個話題。相比表1另外2種傳統(tǒng)價值發(fā)現(xiàn)的方式，探索式搜索強調(diào)用戶的充分參與，在搜索進程中，該方式會為用戶提供大量相關信息，引導用戶明確信息需求，并拓展用戶知識面。因此，該方式更適合人們從數(shù)據(jù)中發(fā)現(xiàn)和學習更多的內(nèi)容。

探索式搜索涉及多方面的技術挑戰(zhàn)，既包括大數(shù)據(jù)的高效管理與查詢執(zhí)行等系統(tǒng)層面的技術，也涉及用戶與系統(tǒng)間交互的創(chuàng)新與突破，如人機交互、數(shù)據(jù)可視化等。下一節(jié)將從系統(tǒng)的角度分析探索式搜索系統(tǒng)需要應對的具體挑戰(zhàn)與關鍵技術。

3 系統(tǒng)框架、挑戰(zhàn)與關鍵技術

White[17]歸納了探索式搜索系統(tǒng)的幾大要素。1）查詢構建：協(xié)助用戶構建查詢，并支持查詢的快速重構；2）分類詳情：對返回結果的進行分類，方便用戶進行篩選；3）搜索上下文：記錄搜索進程的上下文，理解用戶行為；4）可視化支持：提供可視化支持，便于用戶更加直觀地了解數(shù)據(jù)；5）輔助學習：提供充分的信息，協(xié)助用戶在搜索的過程中學習、理解知識；6）社交化操作：提供社交化的功能，提升用戶的參與感與興趣；7）會話記錄：記錄用戶的行為，方便用戶推進自己的搜索進程；8）任務管理：支持多會話、多用戶的場景。

根據(jù)上述觀點，參考現(xiàn)有研究的思路，設計了一個探索式搜索系統(tǒng)的參考框架，包括人機交互層、查詢處理層和數(shù)據(jù)管理層（如圖4所示）。在設計的過程中，采用了組件化的思想，其中，人機交互層涵蓋了交互界面組件、社交化組件以及可視化組件；查詢處理層涵蓋了查詢構造組件、查詢執(zhí)行組件以及結果重構組件；數(shù)據(jù)管理層涵蓋了會話管理組件、數(shù)據(jù)管理組件以及元數(shù)據(jù)管理組件。每個組件都有各自的功能與特點，組件之間相輔相成。

3.1 人機交互層

人機交互層是用戶與系統(tǒng)直接對話的平臺，好的人機交互層設計能讓用戶與系統(tǒng)之間的信息交換過程更加有效。因此，探索式搜索系統(tǒng)需要在人機交互層引入必要的交互元素，協(xié)助用戶更準確表達、獲取自己的信息需求。

圖4 探索式搜索系統(tǒng)框架

3.1.1 交互界面組件

交互界面組件的設計需要關注以下幾點：1）交互界面各個元素的設計需要秉持用戶友好的準則，盡量降低用戶的學習成本；2）探索式搜索是一個長期的搜索進程，用戶需要知道自己所處搜索進程的確切位置；3）需要協(xié)助用戶快速地構建查詢，并能提供高效的查詢重構方案，降低用戶輸入代價，提高查詢構建的準確性；4）需要提供與當前查詢結果緊密關聯(lián)的數(shù)據(jù)內(nèi)容，發(fā)散用戶的興趣。

目前，交互界面方面已經(jīng)有很多工作。Agapie等[18]認為長查詢利于系統(tǒng)返回相關結果，但用戶一般習慣輸入短查詢，為此，他設計了一種交互式查詢輸入系統(tǒng)。該系統(tǒng)隨著用戶輸入查詢的長短，輸入框的顏色發(fā)生變化，以此提高用戶輸入長查詢的概率。SearchPanel[19]的作者觀察到用戶在搜索的過程中，會重復性地訪問同個內(nèi)容，于是他們基于Chrome設計了一個插件，該插件記錄用戶的瀏覽過程，幫助用戶管理他們的搜索進程。Querium[20]系統(tǒng)是一個探索式學術搜索系統(tǒng)，該系統(tǒng)在用戶界面設計方面集成了很多交互式的元素，包括提供搜索記錄、結果篩選、查詢提示等功能，有效地協(xié)助用戶找到他們所需的論文。Querium系統(tǒng)在交互的實時性上也提供很多借鑒，如圖5所示，該系統(tǒng)在每條答案右側提供了支持與反對2個按鈕，用戶在點擊之后，系統(tǒng)會根據(jù)用戶的選擇情況，實時更新答案列表，這讓用戶與系統(tǒng)之間的交互性更強。

3.1.2 社交化組件

社交化組件強調(diào)幫助用戶進行協(xié)同搜索(collaborative search)，并基于用戶社交行為為用戶提供更加精準的內(nèi)容推薦。

圖5 Querium查詢結果

一些大型搜索任務（如醫(yī)學領域的搜索）不是單個用戶能完成的，往往需要支持多名用戶協(xié)同搜索。Golovchinsky等[21]認為協(xié)同搜索可以融合不同用戶的個人見解、經(jīng)驗、專業(yè)領域知識等，從而發(fā)揮群體優(yōu)勢。在團隊協(xié)作下，用戶彼此的交流能幫助用戶更加明確個人的信息需求。此外，用戶可以在協(xié)同搜索的過程中共享他人的搜索結果、吸收他人的知識。SearchTogether[22]是一個協(xié)同搜索領域較早的原型系統(tǒng)，該系統(tǒng)支持團隊式的搜索，大型的搜索任務可以被拆分成多個子任務，團隊成員可以在搜索的進程中交互交流，并共享搜索成果。

除團隊式的協(xié)同搜索外，系統(tǒng)可以提供其他形式的社交元素，讓用戶在搜索進程中激發(fā)更多的興趣。目前，社交媒體包括微博、Twitter在這方面有諸多工作可以借鑒。以微博為例，微博為每條內(nèi)容提供收藏、轉發(fā)、評論以及點贊等社交化元素，這些元素不僅能吸收用戶的智慧，還能讓用戶對這些信息有其他維度的認知。與此同時，微博能通過分析用戶的社交圈，為用戶推薦其他感興趣的內(nèi)容。這種社交化的模式可以最大程度地發(fā)揮用戶群體的智慧，非常適合探索式搜索的理念。

3.1.3 可視化組件

可視化組件能加強用戶對信息的認知，使用戶能夠目睹、探索以至快速理解大量的信息。據(jù)研究表明，人類從外界獲得的信息約80%以上來自于視覺系統(tǒng)[23,24]，當數(shù)據(jù)以圖像的形式展現(xiàn)時，用戶往往能夠一眼洞悉數(shù)據(jù)背后所隱含的價值，而這種價值可能在其他形式下不易發(fā)覺。例如，圖6是Google知識圖譜的一個查詢，當用戶輸入達芬奇，系統(tǒng)自動反饋與達芬奇相關的實體，實體間關系的強弱、遠近在可視化地展示下，更適合用戶從視覺上獲取容易被忽略的信息。因此，為了更有效地探索數(shù)據(jù)價值，數(shù)據(jù)的可視化分是不可或缺的重要手段與工具[25]。

圖6 Google知識圖譜

目前，可視化研究領域主要關注文本可視化、網(wǎng)絡可視化、時空數(shù)據(jù)可視化以及多維數(shù)據(jù)可視化的研究[26]。然而，可視化技術與探索式搜索的結合還不深入，但已經(jīng)逐漸有各方面的嘗試。如圖5所示，Querium系統(tǒng)提供了一個位于返回結果左側的可視化插件。該插件以直方圖的形式直觀地反應了結果與最近幾個查詢的關聯(lián)程度。Polaris[27]系統(tǒng)將多維數(shù)據(jù)進行可視化展示，讓用戶對多維數(shù)據(jù)有更加直觀地認識。VizDeck[28]是一個自動化的可視化組件管理工具，可以通過分析查詢結果，給出適合的可視化方案，幫助用戶獲取更多隱含信息。

3.2 查詢處理層

探索式搜索對信息的獲取也是通過查詢來實現(xiàn)的。因為目標不確定是探索式搜索的重要特點，因此查詢層需要提供更多的功能支持交互層。

3.2.1 查詢構造組件

查詢構造組件支持交互層的查詢推薦與查詢重構。查詢推薦在傳統(tǒng)的搜索引擎中已得到充分的運用，每當用戶輸入部分關鍵詞，系統(tǒng)會快速地補齊缺失的語義，并在下拉框內(nèi)提供多條查詢建議，降低了用戶的操作代價。

當前查詢?nèi)舨粷M足用戶的意圖，用戶會開始下一輪的查詢，但用戶往往缺乏對數(shù)據(jù)的了解，因此系統(tǒng)需要支持用戶快速重構查詢。目前，Web與數(shù)據(jù)庫領域都有相關研究。在數(shù)據(jù)庫中，用戶常常因為不熟悉表之間的關聯(lián)結果，導致SQL查詢的構建連接操作時存在問題，DataPlay[29]對關系型數(shù)據(jù)的表結構進行了圖形化展示，方便用戶調(diào)整SQL語句。此外，為了獲取準確的信息，用戶需要在查詢的基礎上加上限制條件，但往往因為缺乏對數(shù)據(jù)的了解，導致難以提供準確的限制條件，Qarabaqi[30]對于上述情況提出了一個交互式框架，協(xié)助用戶逐步構建準確的查詢。Tran等[31]發(fā)現(xiàn)有些用戶很難將他們的信息需求抽象成查詢，但當他們獲取到一些有關信息之后，可以順利重構查詢。

3.2.2 查詢執(zhí)行組件

獲取查詢之后，查詢執(zhí)行組件會返回查詢結果與相關內(nèi)容。因為探索式搜索是個長期的過程，系統(tǒng)可以有效地關聯(lián)用戶的搜索進程，進而提升返回結果的準確性。Shokouhi[32]在文中指出，短查詢?nèi)菀桩a(chǎn)生歧義，但通過分析用戶的搜索記錄，搜索結果會更加精準。與此同時，通過關聯(lián)用戶的操作行為，系統(tǒng)會對用戶的搜索意圖具備更深層次的理解，從而優(yōu)化得搜索結果[33～35]。

此外，為了引導用戶進一步探索數(shù)據(jù)，相關內(nèi)容的推薦不可或缺。對于信息推薦而言，數(shù)據(jù)挖掘、機器學習有大量工作值得借鑒。例如，YmalDB[36]通過對關系數(shù)據(jù)庫查詢結果的分析，推薦出用戶可能感興趣屬性值對的組合，作為查詢結果的附加信息呈現(xiàn)給用戶，以引導用戶進一步探索數(shù)據(jù)庫中的數(shù)據(jù)?，F(xiàn)階段，像百度、Google以及Bing這些大型搜索引擎都提供了類似的功能，用戶不但可以在獲取與查詢有關的文檔，還能探索與結果相關的內(nèi)容。

3.2.3 結果重構組件

傳統(tǒng)搜索引擎返回給用戶的是與查詢最為相關的多個文檔，但用戶仍然需要花很多的精力在文檔內(nèi)找尋他們想要的信息。因此，為了讓用戶更加直觀地獲取信息，系統(tǒng)需要將返回的結果加以抽取、重構，以更加結構化的方式展示給用戶。目前，大量的信息抽取與信息集成領域的工作與該組件密切相關。MobEx[37]是一個基于移動設備的探索式搜索系統(tǒng)，該系統(tǒng)通過Web端結果獲取頁面信息之后，通過信息抽取的方式將文本信息以圖的形式展現(xiàn)給了用戶，類似的系統(tǒng)還有微軟的人立方。

與此同時，用戶在瀏覽過程中會不斷擴大、縮小他們的瀏覽深度，這要求系統(tǒng)對返回結果進行分類，從而為人機交互層提供輔助用戶快速篩選反饋結果的信息。目前，很多系統(tǒng)提供了類似功能，如Hippalus[38]系統(tǒng)通過分析返回結果，將內(nèi)容以多級層次的形式展現(xiàn)給用戶，用戶可以通過篩選層次以及分類來快速定位到他們所需要的信息。除此之外，返回結果的元數(shù)據(jù)也可以作為分類的依據(jù)，如學術搜索引擎會將論文的年份、學科以及作者等數(shù)據(jù)作為分類信息，幫助用戶快速過濾掉無關的內(nèi)容。

3.3 數(shù)據(jù)管理層

高性能查詢處理是探索式搜索能被廣大用戶接受的前提。與此同時，系統(tǒng)同時需要具備良好的可擴展性。為了滿足上述需求，數(shù)據(jù)管理層的設計尤為關鍵。

3.3.1 會話管理組件

會話管理組件管理用戶在搜索進程中的行為，系統(tǒng)會在用戶的搜索進程中記錄用戶每個操作以及用戶瀏覽的信息。雖然用戶在探索初期的目的不太明確，但通過分析用戶的操作上下文，系統(tǒng)能猜測用戶的大致目標與興趣，從而更加高效地引導用戶。為了支持記錄與分析功能，會話層需要同時支持不斷記錄和實時分析用戶的操作行為。

3.3.2 數(shù)據(jù)管理組件

數(shù)據(jù)管理組件不同于會話管理組件，沒有數(shù)據(jù)持久化的事務性要求，因此，快速的獲取信息以及支持小規(guī)模數(shù)據(jù)量的分析是數(shù)據(jù)管理層需要面對的挑戰(zhàn)。目前，有部分研究通過數(shù)據(jù)預取(data prefetching)降低查詢時間。該技術通過分析用戶當前查詢的內(nèi)容，提前載入未來可能需要的數(shù)據(jù)，進而降低用戶在下個查詢時所需要的I/O開銷，該技術已在空間數(shù)據(jù)查詢[39]得到驗證。除此之外，若用戶可以接受一定范圍內(nèi)的誤差，查詢近似(query approximation)是可采取的技術之一，該技術通過采樣數(shù)據(jù)[40～44]犧牲部分精度，目的是為了快速返回近似結果，幫助用戶對數(shù)據(jù)有初步的了解。

4 知識庫的探索式搜索

近年來，信息抽取和數(shù)據(jù)集成等技術發(fā)展迅速，催生了大量大規(guī)模的RDF(resource description framework)注1注1 http://www.w3.org/RDF/。數(shù)據(jù)集。如 DBPedia注2注2 http://dbpedia.org/。、Freebase注3注3 http://www.freebase.com/。、OpenCyc注4注4 http://opencyc.org/。、Wikidata注5注5 http://wikidata.org/。、YAGO[45]等。目前常見的RDF數(shù)據(jù)查詢檢索方法有2種：使用關鍵詞查詢RDF數(shù)據(jù)或者利用SPARQL注6注6 http://www.w3.org/TR/rdf-sparql-query/。查詢語言檢索RDF數(shù)據(jù)。但SPARQL查詢受限于用戶對RDF數(shù)據(jù)的了解程度，而關鍵詞查詢語義表達能力太弱，無法對RDF數(shù)據(jù)給出結構層面的約束。面對結構復雜、規(guī)模龐大的RDF數(shù)據(jù)庫，用戶通常很難明確自己的信息需求，很難通過簡單的查詢檢索到理想的數(shù)據(jù)。探索式搜索的提出能有效地協(xié)助用戶解決上述問題，用戶通過多輪的交互和探索過程，可以逐步調(diào)整搜索目標，進而從龐大復雜的RDF數(shù)據(jù)庫中找到感興趣的數(shù)據(jù)。在這節(jié)中，以RDF知識庫上的探索式搜索為例，探討探索式搜索所要面臨的一些挑戰(zhàn)性問題和解決這些問題的關鍵技術。

4.1 RDF知識庫

RDF是由WWW提出的對萬維網(wǎng)(world wide web)上信息進行描述的一個框架，它為Web上的各種應用提供信息描述規(guī)范[46]。RDF用主語、謂詞、賓語的三元組形式來描述Web上的資源。其中，主語一般用統(tǒng)一資源標識URI(uniform resource identifiers)表示W(wǎng)eb上的信息實體（或者概念）；謂詞描述實體所具有的相關屬性；賓語為對應的屬性值。這樣的表述方式使RDF可以用來表示W(wǎng)eb上的任何被標識的信息[47]。

此外，人們還提出了關聯(lián)數(shù)據(jù)(linking open data)注7注7 http://linkeddata.org/。的概念，用于將不同組織機構發(fā)布的數(shù)據(jù)關聯(lián)起來，形成規(guī)模更為龐大的RDF數(shù)據(jù)集。據(jù)統(tǒng)計數(shù)據(jù)顯示，關聯(lián)數(shù)據(jù)的規(guī)模在近幾年快速增加，已經(jīng)從2011年的295個數(shù)據(jù)增加到2014年的1 014個注8注8 http://lod-cloud.net/。。很多海量的RDF數(shù)據(jù)集由于包含了大量來自不同領域的實體以及實體之間的關聯(lián)信息，也常被稱為RDF知識庫（或知識圖譜）。一些應用開始借助RDF知識庫所能提供的知識，支持實體搜索、語義搜索、問答系統(tǒng)等應用，谷歌的Knowledge Graph就是其中一個典型的例子。

4.2 知識庫探索的挑戰(zhàn)與關鍵技術

面對規(guī)模龐大的RDF知識庫，用戶通常難以明確自己的信息需求。然而，在探索式搜索的協(xié)助下，用戶可以逐步調(diào)整和改進搜索目標，更有效地從龐大復雜的RDF知識庫中找到感興趣的數(shù)據(jù)。在交互過程中，用戶還可以深入了解RDF數(shù)據(jù)的結構（包括數(shù)據(jù)間的關聯(lián)）、數(shù)據(jù)的分布、數(shù)據(jù)的豐富度等有價值的信息，也能夠發(fā)現(xiàn)一些因各種原因造成的數(shù)據(jù)質(zhì)量問題。

4.2.1 人機交互

用戶交互界面是RDF知識庫探索系統(tǒng)研制的一個重要環(huán)節(jié)，該環(huán)節(jié)可以根據(jù)應用層的不同需求進行個性化的設計。用戶界面設計的好壞直接影響到系統(tǒng)的易用性，在追求功能的同時，需要保證界面的直觀簡潔，第3節(jié)所提到一些研究成果可以作為系統(tǒng)實現(xiàn)的參考。在另一方面，搜索結果的可視化也是需要研究的內(nèi)容，針對RDF圖數(shù)據(jù)的特點，使用一些信息可視化技術展示查詢結果以及數(shù)據(jù)之間的關聯(lián)，促進用戶對查詢結果的理解，降低查詢結果上下文語境理解的難度，以增強RDF知識庫數(shù)據(jù)可視化的交互式數(shù)據(jù)分析的功能。

4.2.2 查詢處理

現(xiàn)階段，人們對海量RDF知識庫的存儲、信息查詢以及分析等方面已經(jīng)做了大量的研究工作[47]。然而，目前的解決方案存在的一個較大問題是缺少表達能力強且簡單易用的RDF數(shù)據(jù)查詢方法。關鍵詞查詢目的是在RDF數(shù)據(jù)庫中，找到包含所有關鍵詞的、結構緊湊的子圖/樹。其雖然靈活度大、實用性強，卻很難保障結果的查準率和查全率。而且關鍵詞查詢語義表達能力弱，不能對RDF圖數(shù)據(jù)給出結構上的約束。在另一方面，結構化的SPARQL查詢力圖在數(shù)據(jù)庫中找到滿足SPARQL查詢條件的子圖，其有著較為復雜的語法定義，需要用戶熟悉它的語法規(guī)則并了解RDF數(shù)據(jù)的模式信息（如謂詞和前綴等），才能夠使用該語言查詢RDF數(shù)據(jù)，這對于一些包含簡單模式的垂直應用尚可。但對于謂詞數(shù)量繁多的、面向開放領域的海量RDF數(shù)據(jù)集而言，SPARQL語言對于普通用戶甚至專業(yè)開發(fā)人員都不具備良好的實用性。為此，需要研究針對RDF知識庫的探索式搜索所需要的基本操作，設計新的基本原語。

在設計基本原語的過程中，需要結合RDF數(shù)據(jù)與探索式搜索的特點。在每次交互過程中，系統(tǒng)能夠分析出上幾次交互的查詢結果的特征，以及和這些結果緊密關聯(lián)的相關數(shù)據(jù)的特征。在此基礎上，識別用戶可能進一步感興趣的數(shù)據(jù)內(nèi)容，簡明合理地向用戶展示查詢結果和與其緊密關聯(lián)的用戶潛在感興趣的數(shù)據(jù)內(nèi)容，以引導用戶改進和調(diào)整查詢目標，探索新的關聯(lián)信息。這其中會存在一些基于頂點、路徑、子圖的圖數(shù)據(jù)探索和分析操作，他們可以抽象成為RDF數(shù)據(jù)的一些基本原語。對于每個基本原語，需要明確定義其輸入數(shù)據(jù)的形式、所執(zhí)行的基本運算操作、輸出結果的形式，并研究相應的計算復雜性。在此基礎上，還要研究不同基本原語之間的關聯(lián)關系，研究如何在不同基本原語之間建立邏輯上的關聯(lián)，以及如何通過基本原語的組合，邏輯上形成一個完整的探索式搜索會話過程，作為探索式搜索系統(tǒng)的基礎交互模型。

4.2.3 數(shù)據(jù)管理

在海量RDF數(shù)據(jù)上進行探索式搜索是本項目面臨的最大挑戰(zhàn)。圖數(shù)據(jù)處理的算法復雜性通常遠高于關系數(shù)據(jù)處理的復雜性，且算法需要經(jīng)常隨機讀取數(shù)據(jù)。即便是當前一些包含上億三元組的RDF數(shù)據(jù)集，已經(jīng)是超大規(guī)模的圖數(shù)據(jù)。單節(jié)點的基于外存模式的很多圖數(shù)據(jù)處理算法都遠不能滿足在這樣的數(shù)據(jù)集上交互式查詢處理的性能需求（亞秒級）。因此，需要從體系結構的角度研究支撐海量RDF數(shù)據(jù)探索式搜索的數(shù)據(jù)存儲與索引策略，而現(xiàn)有的圖數(shù)據(jù)庫[48～51]、MPP分析型數(shù)據(jù)庫[52～54]、分布式內(nèi)存數(shù)據(jù)庫[55～58]等相關工作均可以作為借鑒。

目前，分布式圖數(shù)據(jù)庫系統(tǒng)是針對大規(guī)模RDF數(shù)據(jù)管理常用的技術手段，典型的有Pregel[48]、GraphLab[49]、GraphX[50]、Trinity[51]等。但是，在分布式的計算環(huán)境下，很多圖算法因計算同步很容易造成過多的消息傳遞，影響性能。如Pregel、GraphLab以及GraphX都是基于BSP計算模型[59]，它們將圖數(shù)據(jù)分析過程分解成一系列超步，計算以圖的頂點為中心，并利用超步的狀態(tài)傳遞中間計算結果、同步節(jié)點間的計算，獲得了高性能、擴展性好的大規(guī)模圖數(shù)據(jù)分析解決方案。然而，這些方法都是針對全圖的離線分析，在大規(guī)模數(shù)據(jù)的情況下無法提供實時地返回分析結果。Trinity則通過內(nèi)存云的引入，使用鍵值對方式分布式存儲圖數(shù)據(jù)，并借助內(nèi)存數(shù)據(jù)存取來提升圖數(shù)據(jù)隨機訪問的性能，進而支持一些高性能的圖數(shù)據(jù)在線查詢處理。

因此，以分布式的方式存儲和處理海量RDF數(shù)據(jù)是提高大規(guī)模圖數(shù)據(jù)處理可擴展性的一條重要途徑。此外，內(nèi)存數(shù)據(jù)管理方法的使用也是性能提升的重要保障。因為探索過程中會涉及到很到信息片段，高效的索引支持是必須的。與此同時，存儲管理方面的優(yōu)化，如數(shù)據(jù)壓縮、存儲格式都會是提升性能的重要方式[58]。

4.3 原型系統(tǒng)SEED

目前，筆者在人機交互層面與查詢處理層做了一些嘗試，基于前期研究，現(xiàn)已實現(xiàn)了一個原型系統(tǒng)SEED。該系統(tǒng)采用實體集合擴展的方法來探索RDF知識庫，用戶通過交互界面輸入若干個實體，該系統(tǒng)可以挖掘實體在知識庫中存在的語義關聯(lián)，獲得該實體集合的共同特征，進而獲取所有其他的相關實體，并將語義關系呈現(xiàn)給用戶。如用戶輸入數(shù)據(jù)庫領域的專家Jim Gray、Edgar F Codd、Charles Bachman與Michael Stonebraker，系統(tǒng)會返回所有該領域的專家，并提供實體集合的語義關系(如subject-category:database researches)，幫助用戶快速獲取知識。

SEED的架構（如圖7所示）與第3節(jié)所描述的框架一致，包含了人機交互層、查詢處理層與數(shù)據(jù)管理層。人機交互層為用戶提供可視化的界面，方便用戶探索知識庫。查詢處理層涵蓋2個模塊，實體集合擴展模塊和實體關系預測模塊。為了高效地探索知識庫，數(shù)據(jù)管理層需要引入索引。

圖7 SEED系統(tǒng)架構

用戶在探索知識庫時，可能會發(fā)現(xiàn)知識庫信息不完善的缺陷?；谏鲜鲈?，系統(tǒng)為用戶提供了糾錯的功能，目前已提供知識庫信息補全的功能，用戶可以結合自己的背景知識和系統(tǒng)的推薦信息進行添加操作。如圖8所示，當用戶在左側實體列表中點擊Michael Stonebraker時，右側會即時返回該實體與全部語義關系之間的聯(lián)系，加號表示該實體與語義關系所形成的三元組不存在于數(shù)據(jù)庫，因獲取數(shù)據(jù)集的時候，Michael Stonebraker未獲得圖靈獎，但SEED通過分析相關實體的語義關系，可以預測Michael Stonebrake獲得圖靈獎的概率，為用戶的操作提供相應的推薦。

此外，為了充分了解各個實體的信息，用戶可以通過點擊實體，獲取與該實體直接聯(lián)系的實體，這些實體與相應的關系將以有向圖的方式展示給用戶（如圖9所示）。

5 結束語

圖8 SEED系統(tǒng)糾錯功能

圖9 實體關聯(lián)展示

探索式搜索是適合大數(shù)據(jù)價值挖掘的新手段。本文在對比了傳統(tǒng)的數(shù)據(jù)價值發(fā)掘方式基礎上，著重介紹了探索式搜索的概念與模型，并總結了探索式搜索的特點與需要面臨的挑戰(zhàn)。隨后，基于組件化思想，設計了探索式搜索系統(tǒng)的系統(tǒng)框架，包括人機交互層、查詢處理層以及數(shù)據(jù)管理層，分別闡述了各個組件的功能要求，并綜述相關工作。本文最后以RDF知識庫為例，梳理知識庫探索式搜索在各個層面需要應對的挑戰(zhàn)與關鍵技術，并簡要介紹了筆者的原型系統(tǒng)。探索式搜索作為一個新的研究方向，仍然有大量的問題與挑戰(zhàn)需要深入的研究與突破。下一步，將借鑒現(xiàn)有的前沿研究成果，在支持大規(guī)模知識庫探索式搜索的關鍵技術上取得突破。

[1] MENG X F,CI X.Big data management:concepts,techniques and challenges[J].Journal of Computer Research and Development,2013,50(1):146-169.

[2]MANNING C,RAGHAVAN P,SCHüTZE H.Introduction to Information Retrieval[M].Cambridge University Press,2008.

[3]JUDD C,MCCLELLAND G,RYAN C.Data Analysis:a Model comparison approach[M].Routledge Press,2009.

[4] MARCHIONINI G. Exploratory search: from finding to understanding[J].Communication of theACM,2006,49(4):41-46.

[5]HECHT B,CARTON S,QUADERI M,et al.Explanatory semantic relatedness and explicit spatialization for exploratory search[A].SIGIR[C].2012.415-424.

[6]ROITMAN H,YOGEV S,TSIMERMAN Y,et al.Exploratory search over social-medical data[A].CIKM[C].2011,2513-2516.

[7] BOZZON A,BRAMBILLA M,CERI S,et al.Exploratory search in multi-domain information spaces with liquid query[A].WWW[C].2011.189-192.

[8] HAM F,PERER A.Search,show context,expand on demand:supporting large graph exploration with degree-of-interest[J].IEEE Transaction on Visualization and Computer Graphics,2009,15(6):953-960.

[9] DUNNE C,RICHE N,LEE B,et al.GraphTrail:analyzing large multivariate,heterogeneous networks while supporting exploration history[A].CHI[C].2012.1663-1672.

[10]YOGEV S,ROITMAN H,CARMEL D,et al.Towards expressive exploratory search over entity-relationship data[A].WWW[C].2012.83-92.

[11]MIRIZZI R,RAGONE A,SCIASCIO E.Like breadcrumbs in the forest:a tool for semantic exploratory search[A].EDBT/ICDT Workshop on Linked Web Data Management[C].2011.32-33.

[12]KOUTRIKA G,LAKSHMANAN L,RIEDEWALD M,et al.Report on the first international workshop on exploratory search in databases and the Web[J].SIGMOD Record,2014,43(2):49-52.

[13]IDREOS S,PAPAEMMANOUIL O,CHAUDHURI S.Overview of data exploration techniques[A].SIGMOD[C].2015.277-281.

[14]WHITE R,KULES B,BEDERSON B.Exploratory search interfaces:categorization,clustering and beyond[J].SIGIR Forum,2005,39(2):52-56.

[15]WHITE R,MURESAN G,MARCHIONINI G.Report on ACM SIGIR 2006 workshop on evaluating exploratory search systems[J].SIGIR Forum,2006,40(2):52-60.

[16]WHITE R,DRUKER S,MARCHIONINI G,et al.Exploratory search and HCI:designing and evaluating interfaces to support exploratory search interaction[A].SIGCHI[C].2007.2877-2880.

[17]WHITE R,ROTH R.Exploratory search:beyond the query-response paradigm[M].Morgan&Claypool Publishers,2009.

[18]AGAPIE E,GOLOVCHINSKY G,QVARFORDT P.Leading people to longer queries[A].CHI[C].2013.3019-3022.

[19]TRETTER S,GOLOVCHINSKY G,QVARFORDT P.SearchPanel:a browser extension for managing search activity[A].EuroHCIR[C].2013.51-54.

[20]GOLOVCHINSKY G,DIRIYE A,DUNNIGAN T.The future is in the past:designing for exploratory search[A].IIiX[C].2012.52-61.

[21]GOLOVCHINSKY G,QVARFORDT P,PICKENS J.Collaborative information seeking[J].IEEE Computer Society,2009,42(3):47-51.

[22]MORRIS M,HORVITZ E.SearchTogether:an interfacefor collaborative web search[A].UIST[C].2007.3-12.

[23]REN L.Research on Interaction Techniques in Information Visualization[D].Beijing:ChineseAcademy of Sciences.2009.

[24]CARD K,MACKINLAY D,SHNEIDERMAN B.Readings in Information Visualization:Using Vision to Think[M].San Francisco:Morgan-Kaufmann Publishers,1999.

[25]KEIM D.Information visualization and visual data mining[J].IEEE Transaction on Visualization and Computer Graphics,2002,8(1):1-8.

[26]REN L,DU Y,MA S,ZHANG XL,et al.Visual analytics towards big data[J].Journal of Software,2014,25(9):1909-1936.

[27]STOLTE C,TANG D,HANRAHAN P.Polaris:a system for query,analysis and visualization of multi-dimensional relational databases[J].IEEE Transactions on Visualization and Computer Graphics, 2002.8(1)

[28]KEY A,HOWE B,PERRY D,et al.VizDeck:self-organizing dashboards for visual analytics[A].SIGMOD[C].2012.681-684.

[29]ABOUZIED A,HELLERSTEIN J,SILBERSCHATZ A.Playful query specification with dataplay[J].Proceedings of the Very Large Data Bases Endowment,2012,5(12):1938-1941.

[30]QARABAQIB,RIEDEWALD M.User-drivenrefinementof imprecise queries[A].ICDE[C].2014.916-927.

[31]TRAN Q,CHAN CY,PARTHASARATHY S.Query by output[A].SIGMOD[C].2009.535-548.

[32]SHOKOUHI M,SLOAN M,BENNETT PN,et al.Query suggestion and data fusion in contextual disambiguation[A].WWW[C].2015.971-980.

[33]GAO J,YUAN W,LI X,et al.Smoothing click through data for Web search ranking[A].SIGIR[C].2009.355-362.

[34]GUO F,LIU C,KANNAN A,et al.Click chain model in Web search[A].WWW[C].2009.11-20.

[35]AGICHTEIN E,BRILL E,DUMAIS S.Improving Web search ranking by incorporating user behavior information[A].SIGIR[C].2006.19-26.

[36]DROSOU M,PITOURA E.YmalDB:exploring relational databases via result-driven recommendations[J].Proceedings of the Very Large Data Bases Endowment,2013,22(6):849-874.

[37]SCHMEIER S.Exploratory search on mobile devices[D].German Research Center for Artificial Intelligence and Saarland University.2013.

[38]PAPADAKOS P,TZITZIKAS Y.Hippalus:preference-enriched faceted exploration[A].EDBT/ICDT Workshops[C].2014.167-172.

[39]TAUHEED F,HEINIST,SCHURMANN F,etal.SCOUT:prefetching for latent structure following queries[J].Proceedings of the Very Large Data Bases Endowment,2012,5(11):1531-1542.

[40]SIDIROURGOS L,KERSTEN M L,BONCZ PA.Scientific discovery through weighted sampling[A].Big Data Conference[C].2013.300-306.

[41]SIDIROURGOS L,KERSTEN M L,BONCZ P A.SciBORQ:scientific data management with bounds on runtime and quality[A].Biennial Conference on Innovative Data Systems Research(CIDR)[C].2011.296-301.

[42]ACHARYA S,GIBBONSP,POOSALA V,etal.Theaqua approximate query answering system[A].SIGMOD[C].1999.574-576.

[43]AGARWAL S,MILNER H,KLEINER A,et al.Knowing when you're wrong:building fast and reliable approximate query processing systems[A].SIGMOD[C].2014.481-492.

[44]AGARWAL S,MOZAFARI B,PANDA A,et al.BlinkDB:queries with bounded errors and bounded response times on very large data[A].EuroSys[C].2013.29-42.

[45]HOFFART J,SUCHANEK F,BERBERICH K,et al.YAGO2:exploring and querying world knowledge in time,space,context,and many languages[A].WWW[C].2011.229-232.

[46]RDF model and syntax specification[S].1999.

[47]DU F,CHEN Y G,DU X Y.Survey of RDF query processing techniques.Journal of Software,2013,24(6):1222-1242.

[48]MALEWICZ G,AUSTERN M,BIK A,et al.Pregel:a system for large-scale graph processing[A].SIGMOD[C].2010.135-146.

[49]LOW Y C,GONZALEZ J,KYROLA A,et al.Distributed GraphLab:a framework for machine learning in the cloud[J].Proceedings of the Very Large Data Bases Endowment,2012,5(8):716-727.

[50]GONZALEZ J E,XIN RS,DAVE A,et al.GraphX:graph processing in a distributed dataflow framework[A].OSDI[C].2014.599-613.

[51]SHAO B,WANG H,LI Y.Trinity:a distributed graph engine on a memory cloud[A].SIGMOD[C].2013.505-516.

[52]CHANG L,WANG ZW,M A T,et al.HAWQ:a massively parallel processing SQL engine in hadoop[A].SIGMOD[C].2015.1223-1234.

[53]LI J Z,GAO H,LUO J Z,et al.InfiniteDB:a pc-cluster based parallel massive database management system[A].SIGMOD[C].2007.899-909.

[54]Cloudera Impala[EB/OL].http://www.cloudera.com/.

[55]DIACONU C,FREEDMAN C,ISMERT E,et al.Hekaton:SQL server‘s memory-optimized OLTP engine[A].SIGMOD[C].2013.1243-1254.

[56]SAP HANA[EB/OL].http://www.saphana.com/.

[57]MonetDB[EB/OL].http://www.monetdb.org/.

[58]ANTOVAL,EL-HELWA,SOLIMAN M,et al.Optimizing queries over partitioned tables in MPPsystems[A].SIGMOD[C].2014.373-384.

[59]VALIANT L.A bridging modelforparallelcomputation[J].Communication onACM,1990,33(8):103-111.