動(dòng)態(tài)數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)的表示及搜索方法①

陳 瓊, 李 良, 劉釗岐

(中電?？导瘓F(tuán)有限公司, 杭州 311100)

在大數(shù)據(jù)時(shí)代, 人與人、人與物, 乃至物與物之間的關(guān)系日趨復(fù)雜多樣, 如何從海量數(shù)據(jù)中挖掘出所關(guān)心的信息, 并且以友好、可理解的形式展現(xiàn)出來, 是很多應(yīng)用場景非常關(guān)心的問題. 可視化技術(shù)起源于20世紀(jì)80年代出現(xiàn)的科學(xué)計(jì)算可視化(visualization in scientific computing), 它是指利用計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)圖像處理、計(jì)算機(jī)信號(hào)處理等方法對(duì)數(shù)據(jù)、信息、知識(shí)的內(nèi)在結(jié)構(gòu)進(jìn)行表達(dá)[1]. 進(jìn)入21世紀(jì), 單一的可視化已不能滿足人們?nèi)找嬖鲩L的對(duì)于挖掘數(shù)據(jù)中存在的關(guān)聯(lián)關(guān)系的需求, 可視化逐漸發(fā)展為一個(gè)涉及數(shù)據(jù)挖掘、人機(jī)交互、計(jì)算機(jī)圖形學(xué)等的交叉學(xué)科[2]. 在表現(xiàn)人人、人物, 乃至物物之間的數(shù)據(jù)關(guān)聯(lián)關(guān)系時(shí), 數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)是常見, 也是直觀的可視化手段. 但是目前的數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)表示方法, 一般都是靜態(tài)的、一次性的, 適用于需要表現(xiàn)的實(shí)體較少, 關(guān)系較為簡單的情形. 當(dāng)實(shí)體較多, 之間的關(guān)聯(lián)較為復(fù)雜時(shí), 傳統(tǒng)方法無論從后臺(tái)的處理能力角度, 還是前端的用戶體驗(yàn)角度, 都較難滿足復(fù)雜的表達(dá)數(shù)據(jù)關(guān)聯(lián)的需要. 并且, 從用戶角度出發(fā),用戶往往是在已知幾個(gè)人、物的情況下, 希望得到這些人、物之間的直接或者間接的關(guān)聯(lián)關(guān)系, 從而進(jìn)一步得到圍繞這些已知人、物的關(guān)聯(lián)網(wǎng)絡(luò)關(guān)系. 本文提出一種可動(dòng)態(tài)擴(kuò)展的引導(dǎo)式交互數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)的表示及搜索方法和以此實(shí)現(xiàn)的系統(tǒng), 能夠較好地解決這些問題.

1 概念和實(shí)現(xiàn)框架

1.1 數(shù)據(jù)關(guān)聯(lián)的概念和理論

數(shù)據(jù)關(guān)聯(lián)技術(shù)來自對(duì)語義網(wǎng)研究, 演化的結(jié)果是數(shù)據(jù)網(wǎng)絡(luò). 關(guān)聯(lián)數(shù)據(jù)是指網(wǎng)絡(luò)中發(fā)布和連接的有結(jié)構(gòu)數(shù)據(jù)的一組最佳實(shí)踐[3]. 語義網(wǎng)中關(guān)聯(lián)數(shù)據(jù)技術(shù)的出現(xiàn), 改變了傳統(tǒng)的構(gòu)造、發(fā)布、訪問和集成數(shù)據(jù)的方式[4], 它采用資源描述框架(RDF)作為基本數(shù)據(jù)模型,制定了關(guān)于數(shù)據(jù)表示和鏈接的規(guī)范[5].

“一圖勝千言”這句諺語告訴我們: 一張圖傳達(dá)的信息等同于相當(dāng)多文字的堆積描述[6]. 為更好地顯示關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)特征和進(jìn)行相關(guān)的計(jì)算, 一般會(huì)使用圖論相關(guān)的理論對(duì)關(guān)系網(wǎng)絡(luò)建模, 表示社會(huì)網(wǎng)絡(luò)中人人、人物或者物物的拓?fù)浣Y(jié)構(gòu)和屬性信息. 國際上對(duì)社會(huì)關(guān)系網(wǎng)絡(luò)的關(guān)聯(lián)模型及其可視化研究是一個(gè)熱點(diǎn)[7–10]. 丁楠等[11]提出了一種基于關(guān)聯(lián)數(shù)據(jù)技術(shù)進(jìn)行多源政府信息聚合的模型, 徐長志等[12]對(duì)關(guān)聯(lián)數(shù)據(jù)的空間關(guān)聯(lián)進(jìn)行了探討, 王柳等[13]對(duì)學(xué)者社交網(wǎng)絡(luò)提出了一種關(guān)聯(lián)模型, 王晰巍等[14]對(duì)社交網(wǎng)絡(luò)輿情的圖譜構(gòu)建提出了一種方法, 杜曉林[15]則對(duì)大規(guī)模社會(huì)網(wǎng)絡(luò)的可視化算法進(jìn)行了研究.

社會(huì)關(guān)系網(wǎng)絡(luò)具有聚類特征, 社會(huì)網(wǎng)絡(luò)的聚類系數(shù)一般遠(yuǎn)高于隨機(jī)生成的網(wǎng)絡(luò)的聚類系數(shù)值, 從而形成所謂社團(tuán)結(jié)構(gòu)[16]. 從圖論的角度看, 社團(tuán)結(jié)構(gòu)是網(wǎng)絡(luò)的節(jié)點(diǎn)集合, 該集合節(jié)點(diǎn)間的連接較為稠密, 而其外節(jié)點(diǎn)的連接則較為稀疏. 社會(huì)關(guān)系網(wǎng)絡(luò)的這種聚類特征,是數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)的動(dòng)態(tài)擴(kuò)展, 在引導(dǎo)式交互中逐步發(fā)掘出周邊有價(jià)值的關(guān)聯(lián)信息的理論保證.

雖然社會(huì)關(guān)系網(wǎng)絡(luò)異常復(fù)雜, 但通常來說個(gè)人之間的關(guān)聯(lián)具有“最小世界”特征. 20世紀(jì)60年代,Travers等論證了“六度空間”或曰“最小世界”理論, 即人們相互之間聯(lián)系的距離大概為 6 個(gè)人[17]. 六度空間是社會(huì)網(wǎng)絡(luò)中“小世界”主要特征, 說明在現(xiàn)代超大規(guī)模的社會(huì)關(guān)系網(wǎng)絡(luò)中, 人與人之間的平均最短距離遠(yuǎn)少于網(wǎng)絡(luò)中成員的數(shù)量[18]. 這種特征為在數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)中進(jìn)行代價(jià)有限的搜索提供有價(jià)值的信息提供了理論基礎(chǔ).

1.2 數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)的技術(shù)實(shí)現(xiàn)框架

數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)分析與可視化的實(shí)現(xiàn)框架如圖1所示, 可以分為4個(gè)階段.

圖1 數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)實(shí)現(xiàn)框架

(1)數(shù)據(jù)獲取: 依據(jù)不同的應(yīng)用場景, 采用各類技術(shù)手段獲得數(shù)據(jù), 例如在智慧城市場景, 通常需要通過數(shù)據(jù)交換獲得來自不同部門的數(shù)據(jù), 在如網(wǎng)絡(luò)輿情場景, 則常常使用抓取工具獲得網(wǎng)上海量信息.

(2)數(shù)據(jù)預(yù)處理: 對(duì)所關(guān)心的數(shù)據(jù)進(jìn)行選擇過濾,并對(duì)數(shù)據(jù)進(jìn)行清洗, 將數(shù)據(jù)轉(zhuǎn)變成“干凈”的數(shù)據(jù), 然后對(duì)數(shù)據(jù)格式進(jìn)行轉(zhuǎn)化, 變成統(tǒng)一的格式.

(3)數(shù)據(jù)挖掘: 使用合適的算法, 針對(duì)不同的領(lǐng)域主題進(jìn)行規(guī)則下的挖掘, 使得數(shù)據(jù)具有面向不同主題的結(jié)構(gòu).

(4)可視化: 針對(duì)不同應(yīng)用和不同主題, 采用適當(dāng)?shù)募夹g(shù)和可視化形式, 對(duì)數(shù)據(jù)集進(jìn)行可視化; 對(duì)關(guān)聯(lián)規(guī)則結(jié)果的可視化, 可以使得數(shù)據(jù)關(guān)聯(lián)分析的結(jié)果直觀易懂, 讓用戶能夠?qū)梢暬Y(jié)果做出解釋和評(píng)估, 從而形成有價(jià)值的信息和知識(shí).

2 系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

2.1 動(dòng)態(tài)數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)表示方法的系統(tǒng)設(shè)計(jì)

針對(duì)前述對(duì)社會(huì)網(wǎng)絡(luò)等應(yīng)用場景的可視化需求,本文提出一種數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖的表示方法和系統(tǒng), 使得用戶在已知某個(gè)數(shù)據(jù)(通常是某個(gè)人、物等實(shí)體)的情況下, 能夠通過引導(dǎo)式交互互動(dòng)的辦法, 逐步擴(kuò)展關(guān)聯(lián)網(wǎng)絡(luò)圖, 利用前述社會(huì)關(guān)系網(wǎng)絡(luò)的社團(tuán)性聚類特征,通過有限的步驟, 挖掘出圍繞該數(shù)據(jù)實(shí)體周邊的有價(jià)值信息.

本系統(tǒng)通過后端建立數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)模型, 響應(yīng)來自前端的請求并返回結(jié)果; 前端根據(jù)用戶的操作, 生成操作命令并向后端請求數(shù)據(jù), 并在收到后端返回?cái)?shù)據(jù)后根據(jù)數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)模型繪制和更新數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖;該數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖在用戶的操作下能夠不斷動(dòng)態(tài)擴(kuò)展.本方法及系統(tǒng)理論上能夠支持無限多元素的實(shí)體關(guān)系網(wǎng)絡(luò), 并且能夠擴(kuò)展不同類型的實(shí)體、關(guān)系和實(shí)體聚合. 本方法和系統(tǒng)能夠非常直觀、友好地展現(xiàn)復(fù)雜的數(shù)據(jù)關(guān)聯(lián)圖譜, 極大地方便數(shù)據(jù)分析人員工作.

數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)表示系統(tǒng)前后端交互流程如圖2.

圖2 動(dòng)態(tài)擴(kuò)展的前后端交互流程

(1)系統(tǒng)后端建立數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖模型, 模型的元素包括實(shí)體、關(guān)系和實(shí)體聚合;

(2)用戶選擇實(shí)體類型并通過關(guān)鍵字模糊匹配查詢, 在系統(tǒng)后端返回的實(shí)體候選列表中選擇實(shí)體;

(3)系統(tǒng)前端將所選擇的實(shí)體發(fā)給后端;

(4)系統(tǒng)后端根據(jù)數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖模型, 將該實(shí)體直接關(guān)聯(lián)的實(shí)體、關(guān)系和實(shí)體聚合返回給前端, 同時(shí)也返回該實(shí)體的屬性;

(5)系統(tǒng)前端顯示該實(shí)體及其屬性, 并根據(jù)數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖模型生成和該實(shí)體直接關(guān)聯(lián)的實(shí)體、關(guān)系和實(shí)體聚合的網(wǎng)絡(luò)圖, 同時(shí)更新所返回的新增實(shí)體與現(xiàn)有實(shí)體的關(guān)聯(lián)網(wǎng)絡(luò)連接;

(6)用戶點(diǎn)擊構(gòu)成當(dāng)前數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖中可選中的任何元素, 可選中的實(shí)體包括實(shí)體或者實(shí)體聚合;

a)如選中的為實(shí)體, 則執(zhí)行步驟(3)–(6);

b)如選中的為實(shí)體聚合, 則執(zhí)行步驟(7)–(10).

(7)系統(tǒng)前端將所選擇的實(shí)體聚合發(fā)給后端;

(8)系統(tǒng)后端將構(gòu)成該實(shí)體聚合實(shí)體列表返回前端;

(9)前端顯示該實(shí)體聚合的實(shí)體組成列表;

(10)用戶選擇實(shí)體列表中某個(gè)實(shí)體, 執(zhí)行步驟(3)–(6);

用戶可反復(fù)執(zhí)行步驟(3)–(10), 則數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖不斷動(dòng)態(tài)擴(kuò)展.

在前述的數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖模型, 元素包括實(shí)體, 關(guān)系和實(shí)體聚合; 其中實(shí)體可以包括普通屬性, 也可以包含列表屬性. 在前述的關(guān)系表示實(shí)體之間的有向關(guān)系,這種關(guān)系可以單向, 也可以雙向. 在前述的實(shí)體聚合用于在同類實(shí)體較多時(shí), 將多個(gè)同類實(shí)體表示為一個(gè)實(shí)體聚合. 在前述的步驟(5), 前端將當(dāng)前選中的實(shí)體聚焦, 并顯示其普通屬性和列表屬性. 在顯示與當(dāng)前選中實(shí)體直接關(guān)聯(lián)的實(shí)體時(shí), 如果存在同類實(shí)體, 則顯示實(shí)體聚合. 在前述的步驟(9), 前端將當(dāng)前選中的實(shí)體聚合聚焦, 并顯示其所組成的實(shí)體列表供選擇. 如果實(shí)體聚合組成的實(shí)體個(gè)數(shù)小于等于N(N可定義為2或者其他值), 則展開該實(shí)體聚合包括的所有實(shí)體列表. 在前述的數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖可以根據(jù)用戶的點(diǎn)擊交互不斷擴(kuò)展, 數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖會(huì)在擴(kuò)展后自動(dòng)平衡到最佳位置; 在前述的數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖中的可選中元素可以自由拖動(dòng), 數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖會(huì)在拖動(dòng)后自動(dòng)平衡到最佳位置.

2.2 動(dòng)態(tài)數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)搜索方法的系統(tǒng)設(shè)計(jì)

上述數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)的表示方法可以不斷動(dòng)態(tài)擴(kuò)展, 但用戶更需要提供一種搜索方法, 在已知兩個(gè)或者兩個(gè)以上的實(shí)體的情況下, 希望得到這幾個(gè)已知實(shí)體的關(guān)系. 根據(jù)前述的“最小世界”理論, 這幾個(gè)懷疑有關(guān)聯(lián)的實(shí)體, 可通過代價(jià)有限的搜索步驟得到其關(guān)聯(lián)關(guān)系. 通過后端建立數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)模型, 采用分布式計(jì)算擴(kuò)展關(guān)聯(lián)節(jié)點(diǎn)、并計(jì)算最小連通圖算法, 計(jì)算搜索端點(diǎn)之間的關(guān)聯(lián)關(guān)系, 響應(yīng)來自前端的搜索請求并返回結(jié)果; 前端根據(jù)后端返回?cái)?shù)據(jù)生成數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖, 其中包括搜索端點(diǎn). 本方法為用戶在知道兩個(gè)或多個(gè)實(shí)體, 并且想知道它們之間直接或者間接關(guān)系時(shí), 提供有效的搜索手段, 并且通過直觀、友好的方式展現(xiàn)出來.

本搜索系統(tǒng)的前后端交互流程如圖3所示.

圖3 搜索的前后端交互流程

(1)系統(tǒng)后端建立數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖模型;

(2)用戶選擇實(shí)體類型并通過關(guān)鍵字模糊匹配查詢, 在系統(tǒng)后端返回的實(shí)體候選列表中選擇實(shí)體;

(3)系統(tǒng)前端將用戶選擇的實(shí)體記錄并顯示, 作為關(guān)系搜索的端點(diǎn). 用戶可繼續(xù)重復(fù)步驟(2)到步驟(3),從而選擇多個(gè)實(shí)體作為搜索端點(diǎn);

(4)在所選擇的搜索端點(diǎn)大于等于兩個(gè)時(shí), 用戶可以開始實(shí)體關(guān)系搜索;

(5)系統(tǒng)前端將所選擇的搜索端點(diǎn)集合發(fā)回后端;

(6)系統(tǒng)后端根據(jù)數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖模型, 計(jì)算實(shí)體搜索端點(diǎn)集合之間的關(guān)聯(lián)網(wǎng)絡(luò)圖;

(7)系統(tǒng)后端將結(jié)果數(shù)據(jù)發(fā)給前端;

(8)系統(tǒng)前端根據(jù)后端返回?cái)?shù)據(jù)生成關(guān)聯(lián)網(wǎng)絡(luò)圖,關(guān)聯(lián)網(wǎng)絡(luò)圖中包含搜索端點(diǎn); 若某兩個(gè)搜索端點(diǎn)之間不存在關(guān)系, 則告知用戶;

(9)用戶繼續(xù)操作該關(guān)聯(lián)網(wǎng)絡(luò)圖中的任意元素, 包括搜索端點(diǎn), 其操作方式和第2.1節(jié)相同.

步驟(6)采用分布式計(jì)算擴(kuò)展關(guān)聯(lián)節(jié)點(diǎn)并計(jì)算最小連通圖算法, 其主線程與WorkAgent及WorkQueue關(guān)系如圖4, 其主進(jìn)程具體步驟如圖5.

圖4 主線程/WorkAgent

圖5 主進(jìn)程流程

(1)系統(tǒng)主進(jìn)程將實(shí)體節(jié)點(diǎn)插入WorkQueue中, 在搜索開始時(shí), WorkQueue實(shí)體節(jié)點(diǎn)只有前端選擇的搜索端點(diǎn)集合; WorkQueue是一個(gè)工作隊(duì)列.

(2)系統(tǒng)主進(jìn)程根據(jù)系統(tǒng)計(jì)算性能, 開啟多個(gè)WorkAgent, 每一個(gè)WorkAgent都是獨(dú)立工作的, 可以采用多線程或分布式計(jì)算技術(shù).

(3) 主進(jìn)程啟動(dòng)定時(shí)器.

定時(shí)流程完成如下工作, 如圖6所示.

圖6 定時(shí)流程

(1)取WorkQueue中的全部節(jié)點(diǎn);

(2)包括所有搜索端點(diǎn)在內(nèi)的最小連通圖判斷, 如果不能構(gòu)成最小連通圖, 則執(zhí)行步驟(3), 如果可以構(gòu)成最小連通圖, 則執(zhí)行步驟(6);

(3)判斷是否滿足可配置設(shè)定的停止條件, 如果不滿足停止條件, 則執(zhí)行步驟(4), 如果滿足, 則執(zhí)行步驟(6);

(4)將本次計(jì)算的節(jié)點(diǎn)插入已經(jīng)構(gòu)建的關(guān)系圖并保存;

(5)設(shè)置并等待下一次定時(shí)計(jì)算;

(6)對(duì)所有WorkAgent發(fā)送停止信號(hào), 搜索結(jié)束.

在定時(shí)流程工作步驟(3)中所述的停止條件, 可以配置, 停止條件可以包括:

(1)節(jié)點(diǎn)總數(shù), 超過設(shè)定的查詢節(jié)點(diǎn)總數(shù)即停止;

(2)查詢深度, 超過設(shè)定的從搜索端點(diǎn)開始的查詢深度即停止;

(3)查詢時(shí)間, 超過設(shè)定的查詢時(shí)間即停止.

主線程啟動(dòng)的WorkAgent完成如下工作, 如圖7.其中, 虛線表示步驟5是其他線程(主線程)發(fā)給本線程(WorkAgent線程)的信號(hào), 實(shí)線表示本線程中的步驟.

圖7 WorkAgent流程

(1)根據(jù)權(quán)重從WorkQueue中選擇一個(gè)權(quán)重最高的未查詢過節(jié)點(diǎn);

(2)查詢該節(jié)點(diǎn)的關(guān)聯(lián)節(jié)點(diǎn);

(3)標(biāo)記查出的關(guān)聯(lián)節(jié)點(diǎn)權(quán)重;

(4)將這些節(jié)點(diǎn)插入到WorkQueue.

重復(fù)步驟(1)到步驟(2), 直到接收到主進(jìn)程的停止信號(hào). 在WorkAgent工作步驟中所述的權(quán)重, 可以靜態(tài)配置或者動(dòng)態(tài)計(jì)算. 如果以靜態(tài)配置方式, 則可以根據(jù)不同的節(jié)點(diǎn)間關(guān)系類型設(shè)定權(quán)重大小.

3 動(dòng)態(tài)數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)的實(shí)例和應(yīng)用實(shí)驗(yàn)

本數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)表示和搜索系統(tǒng)中使用的實(shí)體、關(guān)系和實(shí)體聚合可以根據(jù)不同的應(yīng)用場景實(shí)例化為不同的實(shí)際對(duì)象, 其中較能體現(xiàn)本方法和系統(tǒng)的是應(yīng)用在從單純的人與人的社會(huì)網(wǎng)絡(luò)拓展出的, 包括人、物、企事業(yè)單位等多種實(shí)體、較為復(fù)雜的數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò).

3.1 動(dòng)態(tài)數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)的表示實(shí)例

數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)的實(shí)體元素包括人員、汽車、房產(chǎn)、學(xué)校等; 關(guān)系包括配偶雙向關(guān)系、父親/母親單向關(guān)系、車主單向關(guān)系、房主單向關(guān)系、工作單位單向關(guān)系等; 實(shí)體聚合包括孩子聚合、房產(chǎn)聚合、車產(chǎn)聚合等. 具體用戶操作, 其在前端上的體現(xiàn)可以如下所述.

用戶根據(jù)關(guān)鍵字模糊匹配搜索某種類型的實(shí)體,如對(duì)“人員”類實(shí)體進(jìn)行搜索, 關(guān)鍵字為“張”. 也可針對(duì)企業(yè)、房屋、車輛等其他任何種類實(shí)體進(jìn)行搜索. 系統(tǒng)后端返回模糊匹配后的“人員”實(shí)體列表, 如圖8所示.

選擇所關(guān)心的實(shí)體作為入口, 例如“張國強(qiáng)”, 則系統(tǒng)顯示和該實(shí)體直接關(guān)聯(lián)的實(shí)體及其關(guān)系, 如果同類實(shí)體較多, 則顯示實(shí)體聚合, 如圖9所示. “張國強(qiáng)”作為當(dāng)前聚焦實(shí)體, 在右邊的屬性/列表欄顯示和其相關(guān)的屬性, 包括簡單屬性, 如姓名、性別等, 也可包括列表屬性, 如其遷徙記錄等. 在“張國強(qiáng)”實(shí)體周圍, 顯示和它直接相關(guān)的實(shí)體, 并用有向線表示實(shí)體之間的關(guān)系, 如與“韓昌鳳”是雙向的“配偶”關(guān)系, 與“巴**童裝廠”是單向的“工作單位”關(guān)系等. 如果同類實(shí)體較多,則顯示實(shí)體聚合, 比如有兩套房, 則顯示房產(chǎn)聚合; 有兩個(gè)孩子, 則也顯示聚合; 實(shí)體聚合上的數(shù)字表示實(shí)體個(gè)數(shù), 例如車產(chǎn)實(shí)體聚合上的8表示“張國強(qiáng)”擁有8輛車.

圖9 關(guān)聯(lián)網(wǎng)絡(luò)示意圖1 (點(diǎn)擊“張國強(qiáng)”)

點(diǎn)擊當(dāng)前顯示的任何一個(gè)實(shí)體, 則顯示該實(shí)體屬性,并擴(kuò)展出該實(shí)體直接關(guān)聯(lián)的實(shí)體、關(guān)系和實(shí)體聚合. 比如點(diǎn)擊“韓昌鳳”實(shí)體, 則當(dāng)前聚焦實(shí)體變?yōu)椤绊n昌鳳”, 在右邊的屬性/列表欄顯示和其相關(guān)的屬性, 關(guān)系網(wǎng)絡(luò)圖擴(kuò)展顯示“韓昌鳳”的直接關(guān)聯(lián)的實(shí)體和實(shí)體聚合, 如圖10.

圖10 關(guān)聯(lián)網(wǎng)絡(luò)示意圖2 (點(diǎn)擊“韓昌鳳”)

點(diǎn)擊當(dāng)前顯示的任何一個(gè)實(shí)體聚合, 則顯示該實(shí)體聚合的列表. 例如點(diǎn)擊“張國強(qiáng)”所屬的車輛實(shí)體聚合, 在右邊屬性/列表欄顯示所有該實(shí)體聚合的車輛列表, 如圖11所示.

圖11 關(guān)聯(lián)網(wǎng)絡(luò)示意圖3 (點(diǎn)擊車輛實(shí)體聚合)

選擇該列表中的實(shí)體, 則顯示實(shí)體, 如選擇車輛“浙E2***6”, 則顯示該車輛, 并在右邊屬性/列表欄顯示該車輛的相關(guān)屬性, 包括簡單屬性和列表屬性, 如違章記錄等. 如圖12所示.

圖12 關(guān)聯(lián)網(wǎng)絡(luò)示意圖4 (點(diǎn)擊“浙E2***6”)

繼續(xù)類似步驟, 點(diǎn)擊不同實(shí)體或者實(shí)體聚合, 則關(guān)聯(lián)網(wǎng)絡(luò)圖可以不斷地?cái)U(kuò)展, 從而動(dòng)態(tài)擴(kuò)展表示不同實(shí)體之間的關(guān)聯(lián)關(guān)系, 并構(gòu)成關(guān)聯(lián)網(wǎng)絡(luò)圖, 一種狀態(tài)如圖13所示. 理論上, 通過用戶的不斷交互式, 該關(guān)聯(lián)網(wǎng)絡(luò)圖可以無限地?cái)U(kuò)展.

圖13 關(guān)聯(lián)網(wǎng)絡(luò)示意圖5 (不斷交互式擴(kuò)展)

3.2 數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)搜索的應(yīng)用實(shí)例

在更多情況下, 用戶已知幾個(gè)不同的實(shí)體, 可以是人、物、企事業(yè)單位等, 需要發(fā)掘出這些人或物的直接或者間接的關(guān)聯(lián). 用戶根據(jù)關(guān)鍵字模糊匹配搜索某種類型的實(shí)體, 重復(fù)操作, 選擇兩個(gè)或以上, 作為搜索端點(diǎn). 在本例中先對(duì)“人員”類實(shí)體進(jìn)行以 “張”為關(guān)鍵字的搜索, 并在結(jié)果列表內(nèi)選擇“張國強(qiáng)”, 此時(shí)前端顯示“張國強(qiáng)”作為搜索端點(diǎn); 類似的, 對(duì)“企業(yè)”類實(shí)體進(jìn)行搜索, 并選擇“巴**童裝廠”; 對(duì)“車輛”類實(shí)體進(jìn)行搜索, 并選擇“浙E7***Y”. 此時(shí)共有3個(gè)搜索端點(diǎn), 如圖14.

圖14 人、企、車3個(gè)(類)搜索端點(diǎn)

點(diǎn)擊搜索按鈕, 開始實(shí)體關(guān)系搜索, 前端顯示包括3個(gè)搜索端點(diǎn)在內(nèi)的數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖, 其中圖標(biāo)內(nèi)帶五角星的即搜索端點(diǎn), 如圖15所示. 從圖中可見,“張國強(qiáng)”和“巴**童裝廠”關(guān)聯(lián)是直接的, 前者的工作單位為后者; 而“浙E7***Y”與其他兩個(gè)搜索端點(diǎn)的關(guān)系是間接的, 它是“巴**童裝廠”的法人“李燕峰”的配偶“朱月娥”的車產(chǎn). 本搜索方法把3個(gè)搜索端點(diǎn)之間直接或者間接的關(guān)系直觀的通過數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)圖實(shí)現(xiàn)出來.

圖15 搜索端點(diǎn)結(jié)果的數(shù)據(jù)關(guān)聯(lián)展示

點(diǎn)擊當(dāng)前任何一個(gè)元素, 則操作和前述數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)表示方法一致. 圖16是點(diǎn)擊“朱月娥”實(shí)體的情形,圖17是繼續(xù)點(diǎn)擊“李俊”實(shí)體的情形. 此關(guān)聯(lián)網(wǎng)絡(luò)圖可不斷擴(kuò)展, 其中3個(gè)搜索端點(diǎn)“張國強(qiáng)”“巴**童裝廠”和“浙E7***Y”的圖標(biāo)一直帶五角星符號(hào).

圖16 數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)擴(kuò)展1 (點(diǎn)擊“朱月娥”)

圖17 數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)擴(kuò)展2 (點(diǎn)擊“李俊”)

3.3 應(yīng)用實(shí)驗(yàn)

在實(shí)驗(yàn)室對(duì)本方法和系統(tǒng)進(jìn)行實(shí)驗(yàn)測試. 表1是實(shí)驗(yàn)系統(tǒng)的配置情況. 本系統(tǒng)采用Java語言編寫, 數(shù)據(jù)庫采用了MySQL, 每個(gè)實(shí)體類型被設(shè)計(jì)為一張單表.通過模擬程序生成測試數(shù)據(jù), 測試數(shù)據(jù)被模擬為不同的實(shí)體類型, 并根據(jù)模擬程序隨機(jī)生成不同實(shí)體之間的關(guān)聯(lián)關(guān)系. 當(dāng)數(shù)據(jù)總量增加時(shí), 每個(gè)不同實(shí)體類型的數(shù)據(jù)量同比例增加, 其關(guān)聯(lián)關(guān)系也同比例增加. 實(shí)體類型即模擬上述的人員、汽車、房產(chǎn)、學(xué)校等, 關(guān)聯(lián)關(guān)系即模擬上述的配偶雙向關(guān)系、父親/母親單向關(guān)系、車主單向關(guān)系、房主單向關(guān)系、工作單位單向關(guān)系等.

表1 實(shí)驗(yàn)環(huán)境配置

表2是實(shí)驗(yàn)中數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)如第3.1節(jié)所述擴(kuò)展表示的每次單步擴(kuò)展的平均時(shí)間. 從該表可看出, 隨著數(shù)據(jù)總量增加, 單步擴(kuò)展平均時(shí)間也有所增加, 但變化不算大. 由于每次單步的擴(kuò)展實(shí)際上是一次關(guān)系式數(shù)據(jù)表查詢, 在建立適當(dāng)索引的情況下, 數(shù)據(jù)總量的增加, 即每個(gè)單表同比例增加, 在實(shí)驗(yàn)的數(shù)據(jù)范圍內(nèi)對(duì)查詢影響不太大. 而實(shí)體類型數(shù)量對(duì)單步擴(kuò)展平均時(shí)間影響不明顯.

表2 數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)表示單步擴(kuò)展平均時(shí)間

表3是實(shí)驗(yàn)中數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)如第3.2節(jié)所述關(guān)聯(lián)搜索的平均時(shí)間. 從測試結(jié)果可以看出, 隨著數(shù)據(jù)總量增加, 搜索的平均時(shí)間有明顯的增加, 但與關(guān)系類型數(shù)量增加沒有明顯關(guān)系. 增大前述WorkAgent的數(shù)量, 則會(huì)對(duì)搜索速度有明顯改善.

表3 數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)表示查詢平均時(shí)間

3.4 在實(shí)際工程中的應(yīng)用

本數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)系統(tǒng)中使用的實(shí)體、關(guān)系和實(shí)體聚合可以根據(jù)不同的應(yīng)用場景實(shí)例化為不同的實(shí)際對(duì)象, 因此可以廣泛地適應(yīng)不同應(yīng)用場景的要求. 基于本方法和系統(tǒng)開發(fā)的具體應(yīng)用已經(jīng)被使用到很多落地工程項(xiàng)目中.

例如在某智慧/平安城市項(xiàng)目中, 使用本系統(tǒng)可如上面數(shù)據(jù)關(guān)聯(lián)的應(yīng)用實(shí)例所描述, 幫助管理部門生動(dòng)形象、可互動(dòng)的獲得其關(guān)心的人、物、單位的周邊關(guān)系, 并且在已知幾個(gè)可能有關(guān)的人、物、單位時(shí), 通過數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)的搜索得到其實(shí)際直接或者間接關(guān)系.

再如, 在某智慧城市管理項(xiàng)目中, 以及在某城域物聯(lián)專網(wǎng)項(xiàng)目中, 其實(shí)體或?qū)嶓w聚合可以是城市管理中的管理人員、城市部件、關(guān)聯(lián)單位等, 通過類似的手段, 可以很好幫助用戶提高管理效率, 提升管理體驗(yàn).

4 結(jié)論與展望

本文提出和實(shí)現(xiàn)了一種動(dòng)態(tài)引導(dǎo)式交互的數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)表示和搜索方法和系統(tǒng), 能夠在數(shù)據(jù)實(shí)體較多、關(guān)聯(lián)關(guān)系較復(fù)雜時(shí), 幫助用戶通過引導(dǎo)式交互、生動(dòng)形象地獲得其關(guān)心的實(shí)體的周邊關(guān)系, 并且在已知幾個(gè)實(shí)體時(shí)候, 發(fā)掘出它們之間可能存在的直接或者間接的關(guān)系. 本文所描述的方法和系統(tǒng)已經(jīng)在多個(gè)實(shí)際項(xiàng)目中獲得使用, 取得了較好的實(shí)際效果.