CPU-GPU異構(gòu)環(huán)境下的大規(guī)模商品知識查詢處理
2021-03-14 20:42方創(chuàng)新宋浩林煜明周婭
方創(chuàng)新 宋浩 林煜明 周婭
摘要：知識圖譜是將無結(jié)構(gòu)的知識進(jìn)行結(jié)構(gòu)化表示和組織的有效途徑，已經(jīng)成為支持眾多智能應(yīng)用的基 礎(chǔ)設(shè)施.然而，與商品相關(guān)的知識通常呈現(xiàn)出海量性、異質(zhì)性和層次性的特點(diǎn)，這對現(xiàn)有基于關(guān)系模型和圖 模型的知識查詢處理方法提出了挑戰(zhàn).針對商品知識的這些特點(diǎn)，本文設(shè)計(jì)與實(shí)現(xiàn)了一種利用CPU和 GPU協(xié)同計(jì)算的商品知識查詢處理方法.首先，為了充分發(fā)揮GPU的并行計(jì)算能力，提出了一種基于稀 疏矩陣的商品知識存儲策略，并針對商品知識進(jìn)行存儲優(yōu)化;其次，根據(jù)稀疏矩陣的存儲結(jié)構(gòu)設(shè)計(jì)了一種 查詢轉(zhuǎn)換方式，將SPARQL查詢轉(zhuǎn)化為對應(yīng)的矩陣計(jì)算，并將連接查詢算法擴(kuò)展到GPU上進(jìn)行加速.為 了驗(yàn)證所提出方法的有效性，我們在LUBM數(shù)據(jù)集和一個半合成的商品數(shù)據(jù)集上進(jìn)行了一系列的實(shí)驗(yàn).結(jié) 果表明，本文提出的方法，不僅在海量商品知識下相對于現(xiàn)有RDF查詢引擎在檢索效率上有較大提升，而 且在通用的RDF標(biāo)準(zhǔn)數(shù)據(jù)集上也能取得較好的檢索性能，并驗(yàn)證了 GPU加速查詢處理的有效性.
關(guān)鍵詞：商品知識;異構(gòu)環(huán)境;RDF數(shù)據(jù);查詢處理
中圖分類號：TP392?????? 文獻(xiàn)標(biāo)志碼：A?????? DOI： 10.3969/j.issn.1000-5641.2021.05.014
Query processing of large-scale product knowledge in a
CPU-GPU heterogeneous environment
FANG Chuangxin， SONG Hao， LIN Yuming， ZHOU Ya
（Guangxi Key Laboratory of Trusted Software， Guilin University of Electronic Technology，
Guilin Guangxi 541004， China）
Abstract： Knowledge graphs are an effective way to structurally represent and organize unstructured knowledgeare; in fact， these graphs are commonly used to support many intelligent applications. However， product-related knowledge is typically massive in scale， heterogeneous， and hierarchical; these characteristics present a challenge for traditional knowledge query processing methods based on relational and graph models. In this paper， we propose a solution to address these challenges by designing and implementing a product knowledge query processing method using CPU and GPU collaborative computing. Firstly， in order to leverage the full parallel computing capability of GPU， a product knowledge storage strategy based on a sparse matrix is proposed and optimized for the scale of the task. Secondly， based on the storage structure of the sparse matrix， a query conversion method is designed， which transforms the SPARQL query into a corresponding matrix calculation， and extends the join query algorithm to the GPU for acceleration. In order to verify the effectiveness of the proposed method， we conducted a series of experiments on an LUBM dataset and a semisynthetic dataset of products. The experimental results
收稿日期：2021-08-07
基金項(xiàng)目：國家自然科學(xué)基金（62062027， U181126（4）;廣西自然科學(xué)基金（2018GXNSFDA281049， 2020GXNSFA A15901（2）;廣西創(chuàng)新驅(qū)動發(fā)展專項(xiàng)資金（桂科AA1904600（4）;桂林市重點(diǎn)研發(fā)計(jì)劃（202001030（4）;桂林電 子科技大學(xué)研究生教育創(chuàng)新計(jì)劃資助項(xiàng)目（2021YCXS07（5）;廣西可信軟件重點(diǎn)實(shí)驗(yàn)室研究課題 （kx20202（1）
通信作者：林煜明，男，教授，碩士生導(dǎo)師，研究方向?yàn)楹Ａ繑?shù)據(jù)管理和知識圖譜.E-mail： ymlin@guet.edu.cn
showed that the proposed method not only improves retrieval efficiency for large-scale product knowledge datasets compared with existing RDF query engines， but also achieves better retrieval performance on a general RDF standard dataset.
Keywords： product knowledge; heterogeneous environment; RDF data; query processing
0引 言
知識圖譜是利用圖模型來描述知識和建模事物間關(guān)聯(lián)關(guān)系的大規(guī)模語義網(wǎng)絡(luò)，是大數(shù)據(jù)時代知 識表示的重要方式之一，也是眾多智能應(yīng)用的基礎(chǔ)支撐設(shè)施.例如，基于金融知識圖譜的會計(jì)欺詐風(fēng) 險(xiǎn)識別[1]、金融產(chǎn)品推薦等.這種結(jié)構(gòu)化的知識表示能夠?qū)?shí)體信息表達(dá)成更接近人類認(rèn)知世界的 形式，通過知識圖譜能夠更好地組織、管理和理解互聯(lián)網(wǎng)上的信息.大部分知識圖譜使用資源描述框 架（Resource Description Framework， RDF）來描述事物和關(guān)系，是一種以三元組形式來描述網(wǎng)絡(luò)資源 信息的表示方式，其格式為“（主語，謂語，賓語）”，其中主語、賓語也稱為實(shí)體，謂語也稱為關(guān)系，簡言 之，RDF就是一種描述實(shí)體間關(guān)系的表示方法.而SPARQL （Simple Protocol and RDF Query Language） 則是W3C （World Wide Web Consortium）專門定義于訪問和操作RDF數(shù)據(jù)的結(jié)構(gòu)化查詢語言，以 實(shí)現(xiàn)針對大規(guī)模RDF數(shù)據(jù)的查詢與檢索.目前，針對大規(guī)模RDF數(shù)據(jù)的查詢處理主要包括基于關(guān)系 模型（如Jena[3]和RDF-3X[4]等）和基于圖模型（如gStore[5]和AMBER161等）兩類方法.
另一方面，商品知識由于具有異質(zhì)性、冗雜性、海量性等特點(diǎn)，使得原生的商品知識數(shù)據(jù)并不是 結(jié)構(gòu)化的，難以通過傳統(tǒng)的知識圖譜形式進(jìn)行組織與管理.現(xiàn)實(shí)的應(yīng)用中有一些知識圖譜具有層次化 的結(jié)構(gòu)，層次化結(jié)構(gòu)對知識數(shù)據(jù)從深度和廣度上進(jìn)行了衍生，可以從一般概念引導(dǎo)到更細(xì)粒度的知識， 因此，商品知識數(shù)據(jù)適合使用層次化的知識圖譜進(jìn)行構(gòu)建.然而現(xiàn)有的RDF知識查詢方法對具有這 種結(jié)構(gòu)的知識圖譜進(jìn)行查詢處理時不能很好地利用其層次結(jié)構(gòu)特點(diǎn)進(jìn)行存儲和查詢優(yōu)化.本文主要 是針對具有層次化組織結(jié)構(gòu)的知識圖譜進(jìn)行查詢優(yōu)化的研究，特別是對具有該結(jié)構(gòu)的商品知識數(shù)據(jù) 的檢索提出了一種查詢優(yōu)化的方法.我們所研究的商品知識，是一種具有5層結(jié)構(gòu)的知識圖譜用戶 層、用戶觀點(diǎn)層、商品屬性層、商品實(shí)例層、商品分類層），其特點(diǎn)在于每一層實(shí)體的屬性類型都是類 似的，層與層之間的實(shí)體使用同一類型的關(guān)系來聯(lián)系，商品知識的實(shí)例片段如圖1所示.例如，圖1中 包含了如下事實(shí)：用戶U1對商品P1的屬性A1持有O1的觀點(diǎn)，P1是一種S1類型的商品，S1類型商 品是C1類型商品的子類，等等.
此外，隨著商品知識規(guī)模的不斷增大，用戶對知識查詢的響應(yīng)速度要求也在不斷提高，但是現(xiàn)有 的RDF知識查詢系統(tǒng)的通用性對商品知識檢索性能提升形成了阻礙，沒有充分地考慮商品知識圖譜 結(jié)構(gòu)的特點(diǎn).基于關(guān)系模型的知識查詢系統(tǒng)查詢性能較好，但對系統(tǒng)存儲性能有較大要求;而基于圖 模型的知識查詢處理引擎則過度依賴知識數(shù)據(jù)的圖結(jié)構(gòu)，在進(jìn)行商品知識檢索時查詢性能較低.因此， 希望能針對我們的商品知識數(shù)據(jù)，或者說對具有這種層次結(jié)構(gòu)的知識圖譜檢索提出一種查詢優(yōu)化方 法.此外，隨著硬件技術(shù)的不斷發(fā)展，GPU （Graphics Processing Unit）的功能逐漸從圖形計(jì)算領(lǐng)域衍 生拓展到通用計(jì)算領(lǐng)域，利用CPU （Central Processing Unit）和GPU的協(xié)同計(jì)算進(jìn)行查詢處理也成 為提高數(shù)據(jù)檢索性能的一個突破口 .本文以大規(guī)模商品知識數(shù)據(jù)為研究對象，以提升商品知識檢索的 性能為目標(biāo)，提出一種高效可擴(kuò)展的符合商品知識層次結(jié)構(gòu)的查詢處理技術(shù)，實(shí)現(xiàn)了一種基于CPU- GPU協(xié)同計(jì)算的商品知識查詢處理方法，并在公開的標(biāo)準(zhǔn)數(shù)據(jù)集和半合成的商品數(shù)據(jù)集上驗(yàn)證了所 提出方法的有效性.總體而言，本文的主要貢獻(xiàn)如下：
（1）對于具有層次化組織結(jié)構(gòu)的知識圖譜，如本文所研究的商品知識圖譜，提出了一種基于稀疏 矩陣的存儲策略，并依據(jù)層次化的結(jié)構(gòu)特點(diǎn)進(jìn)行存儲優(yōu)化;
（2）根據(jù)稀疏矩陣的存儲結(jié)構(gòu)設(shè)計(jì)了一種查詢轉(zhuǎn)換方式，將SPARQL查詢轉(zhuǎn)換為矩陣操作，并將 連接查詢算法擴(kuò)展到GPU上進(jìn)行加速;
（3）在一個標(biāo)準(zhǔn)數(shù)據(jù)集和一個半合成數(shù)據(jù)集上驗(yàn)證了提出方法的有效性.實(shí)驗(yàn)結(jié)果表明，我們的 方法不僅在大規(guī)模的商品知識查詢上具有較明顯的優(yōu)勢，而且也對通用知識的查詢處理具有實(shí)用性.
本文的組織結(jié)構(gòu)如下：第1章簡要描述了相關(guān)的工作;第2章主要介紹所設(shè)計(jì)的查詢系統(tǒng)的總體 框架;第3章詳細(xì)介紹了基于稀疏矩陣的知識表示;第4章對基于稀疏矩陣的查詢轉(zhuǎn)換方式及其優(yōu)化 進(jìn)行了詳細(xì)的闡述;第5章對實(shí)驗(yàn)結(jié)果進(jìn)行分析和討論;第6章對本文進(jìn)行總結(jié).
1相關(guān)工作
根據(jù)RDF數(shù)據(jù)存儲和查詢方式的不同，目前RDF數(shù)據(jù)的查詢系統(tǒng)主要分為兩類：基于關(guān)系模型 的查詢系統(tǒng)以及基于圖模型的查詢系統(tǒng).
基于關(guān)系模型的查詢系統(tǒng)通過關(guān)系型數(shù)據(jù)庫對數(shù)據(jù)進(jìn)行管理.Jena[3]使用一張巨大的表來分別存 儲S、P、O值，并將SPARQL查詢轉(zhuǎn)換為SQL查詢，但由于在執(zhí)行連接查詢時需要大量執(zhí)行自連接 操作，所以查詢代價(jià)很大.RDF-3X[4]則是通過將S、P、O的全排列都進(jìn)行了存儲，用于加速連接查詢， 但也導(dǎo)致存儲空間顯著增加.S2RDF[8]將RDF數(shù)據(jù)劃分成若干個關(guān)系表，借助Spark對RDF數(shù)據(jù)進(jìn) 行存儲和查詢.BitMat[9]通過對RDF每個元素進(jìn)行編號，并建立位圖索引來收集候選查詢，不過也面 臨著大量空間浪費(fèi)的問題.這類查詢系統(tǒng)在存儲具有層次化結(jié)構(gòu)的知識數(shù)據(jù)時，不能有效利用其結(jié)構(gòu) 特點(diǎn)進(jìn)行優(yōu)化.我們的方法針對這類數(shù)據(jù)的稀疏性，以及知識數(shù)據(jù)層與層之間只有一類謂語這一特點(diǎn)， 降低了索引矩陣的存儲維度.
基于圖模型的查詢系統(tǒng)則是將SPARQL查詢處理轉(zhuǎn)換為子圖匹配問題，能夠?qū)DF數(shù)據(jù)中的語 義信息進(jìn)行保留和查詢.gStore[5]通過將謂語編碼成二進(jìn)制串并構(gòu)建VS*-tree來輔助查詢，查詢處理 性能較關(guān)系型查詢系統(tǒng)要高效.Kim等[10]在RDF數(shù)據(jù)圖上結(jié)合深度優(yōu)先和廣度優(yōu)先算法得到SPARQL 查詢點(diǎn)的候選區(qū)域，并按照一定的匹配順序找到查詢的最終解.AMBER[6]則是將RDF數(shù)據(jù)和 SPARQL查詢表示成多圖，雖然復(fù)雜查詢中的表現(xiàn)優(yōu)于基于關(guān)系的系統(tǒng)，但幾乎不可擴(kuò)展.Zouaghi等 提出了一種基于圖的RDF管理系統(tǒng)的優(yōu)化策略，利用關(guān)系數(shù)據(jù)庫的優(yōu)勢來描述圖查詢的邏輯結(jié)構(gòu)[11]. Manolescu提出了一種結(jié)構(gòu)化的遍歷策略，通過尋找相似結(jié)構(gòu)的節(jié)點(diǎn)組來搜索RDF圖[12].這類基于圖 模型的方法主要采用子圖同構(gòu)算法來完成查詢，避免了連接操作.但由于缺乏并行性，這類查詢系統(tǒng) 計(jì)算量都比較大，頻繁的遍歷操作造成了大量耗時.而我們針對存儲結(jié)構(gòu)設(shè)計(jì)了可以并行執(zhí)行連接操 作的方法，可有效降低查詢耗時.
近幾年，利用新型硬件（特別是GPU）來加速RDF數(shù)據(jù)的查詢是一個研究的熱點(diǎn).MapSQ[13]是一 個基于MapReduce的SPARQL查詢處理框架，它首先通過CPU完成SPARQL子查詢，然后利用 GPU執(zhí)行子查詢結(jié)果的連接操作.Tran等人將查詢計(jì)劃轉(zhuǎn)化為一系列有利于GPU計(jì)算的原語操作 （如排序、歸并等）|14]. TripleID-Q叫將編碼后的RDF三元組裝載到GPU的全局內(nèi)存中，通過大量 GPU線程并行搜索需要的主體、謂詞和客體.然而，RDF數(shù)據(jù)圖的規(guī)模不斷增大導(dǎo)致查詢性能逐漸 降低，并且可拓展性變差.gSMat|16]則使用基于謂語的索引矩陣來存儲數(shù)據(jù)，但是在連接查詢的過程 中需要借助輔助數(shù)組來完成查詢，而且無法用于缺失謂語的SPARQL查詢.Wukong+G[1M吏用GPU 的高并行性和大內(nèi)存帶寬來加速處理具有大量中間結(jié)果的SPARQL查詢.MAGiQ |18]則是使用矩陣 來處理異構(gòu)環(huán)境下的SPARQL查詢，但是由于該方法是構(gòu)建了一個由所有實(shí)體組成的二維矩陣，在 面對稀疏性比較大且具有層次化結(jié)構(gòu)的知識圖譜時，這種存儲方式會造成大量的空間浪費(fèi)，而我們的 方法則是依據(jù)謂語來劃分RDF數(shù)據(jù)，從而減少單個矩陣的大小，并且構(gòu)建每個謂語索引矩陣的實(shí)體 只與對應(yīng)的謂語相關(guān).
2系統(tǒng)的整體架構(gòu)
本文所設(shè)計(jì)的面向大規(guī)模商品知識的查詢系統(tǒng)的整體架構(gòu)如圖2所示，該系統(tǒng)主要分為3個層 次，其核心功能主要在系統(tǒng)層.其中對于商品知識數(shù)據(jù)構(gòu)建過程的主要模塊是：RDF解析器、矩陣構(gòu) 建器，而商品知識數(shù)據(jù)檢索過程的主要模塊是：SPARQL解析器、查詢處理器.此外，還有一個提供數(shù) 據(jù)持久性的RDF矩陣和映射字典模塊.
（1）RDF解析器：負(fù)責(zé)處理商品知識RDF數(shù)據(jù)文件，并對其中的主語、賓語及謂語構(gòu)建與ID值 的雙向映射.原生三元組和ID形式的三元組集合都將保存于映射字典中;
（2）矩陣構(gòu)建器：主要將RDF解析器中得到的ID形式的三元組集合構(gòu)建稀疏矩陣.依據(jù)謂語索 引來構(gòu)建0/1矩陣，行列標(biāo)簽分別為三元組的主語和賓語.實(shí)現(xiàn)細(xì)節(jié)可見第3章;
（3）SPARQL解析器：該模塊解析輸入的SPARQL查詢語句，并對查詢語句進(jìn)行預(yù)處理，以便查 詢處理器執(zhí)行查詢;
⑷查詢處理器：負(fù)責(zé)處理SPARQL查詢?nèi)蝿?wù)，主要分為CPU計(jì)算與CPU-GPU計(jì)算兩種查詢模 式.具體實(shí)現(xiàn)細(xì)節(jié)見第4章;
（5） RDF矩陣及映射字典：當(dāng)商品知識圖譜數(shù)據(jù)有所更新時，如增加、刪除等操作，將更新后的三 重映射關(guān)系以及稀疏矩陣進(jìn)行同步更新和迭代，以保證全部RDF數(shù)據(jù)的完整性.
在接下來的章節(jié)中，我們將主要介紹矩陣構(gòu)建器模塊和查詢處理器模塊的實(shí)現(xiàn)細(xì)節(jié)，即基于稀疏 矩陣的知識表示方法以及基于稀疏矩陣的查詢轉(zhuǎn)換與處理.
3基于稀疏矩陣的商品知識表示
由于互聯(lián)網(wǎng)上的商品知識數(shù)據(jù)大多以非結(jié)構(gòu)化的形式存在，且這些數(shù)據(jù)具有一定的數(shù)據(jù)異質(zhì)性 與冗雜性，這使得統(tǒng)一管理難度較大.因此，本文是在文獻(xiàn)[7]所設(shè)計(jì)的商品知識組織結(jié)構(gòu)的基礎(chǔ)上， 對商品數(shù)據(jù)集的存儲策略以及查詢優(yōu)化進(jìn)行研究，通過分層的方式聚集同類型的數(shù)據(jù)，這有利于商品 知識數(shù)據(jù)的維護(hù)、檢索以及推薦等.如圖1所示，商品知識的實(shí)例片段大體上可以分為這幾層結(jié)構(gòu)：商 品分類層、商品實(shí)例層、商品屬性層、用戶觀點(diǎn)層、用戶層等，并根據(jù)不同層與層之間的關(guān)系，使用相 對應(yīng)的謂語進(jìn)行聯(lián)系.
基于商品知識這類具有層次化組織結(jié)構(gòu)的知識圖譜，我們考慮使用稀疏矩陣進(jìn)行知識表示.在讀 取完RDF數(shù)據(jù)后，我們?yōu)槿M中的實(shí)體（主語、賓語）與關(guān)系（謂語）構(gòu)建了與數(shù)字ID的雙向映射， 從而將操作從字符串三元組轉(zhuǎn)換為數(shù)字三元組，減少存儲空間的同時也降低了數(shù)據(jù)I/O的耗時.商品 知識表示的轉(zhuǎn)換過程如圖3所示.
用S、P、O分別表示主語、謂語、賓語，將經(jīng)過數(shù)字編碼后的三元組按照S、P、O三個維度構(gòu)建 一個知識數(shù)據(jù)立方體，如圖3（a）所示.整個數(shù)據(jù)立方體的數(shù)值用0/1表示，假設(shè)存在編碼后的三元組 （?巧，Ofc），則該三元組在數(shù)據(jù)立方體中的值為1;否則對應(yīng)位置的值為0.
假設(shè)有一個查詢?nèi)M，通過索引Pi和巧即可以在數(shù)據(jù)立方體中定位到查詢變量？^的 值.但是由于RDF數(shù)據(jù)集稀疏性較大，而且實(shí)體的數(shù)量會遠(yuǎn)多于關(guān)系的數(shù)量，這將導(dǎo)致存儲數(shù)據(jù)立方 體的空間過大，因此需要將數(shù)據(jù)立方體進(jìn)一步切分來優(yōu)化存儲效率.在優(yōu)化的過程中，還需要考慮如 何使得存儲的結(jié)構(gòu)有利于連接查詢操作.基于圖模型的查詢處理主要利用基本圖模式匹配（Basic Graph Pattern）的思想，也就是基于子圖匹配來完成查詢處理，其特點(diǎn)主要是對每條查詢?nèi)M的實(shí) 體進(jìn)行連接，形成一個查詢圖，從而在整個RDF數(shù)據(jù)形成的數(shù)據(jù)圖中找到匹配的查詢子圖.這說明在 進(jìn)行連接查詢時其本質(zhì)是對查詢實(shí)體的連接，因此數(shù)據(jù)立方體的切分應(yīng)當(dāng)按照謂語（即維度P）進(jìn)行 切分，從而保留主語和賓語的維度以便進(jìn)行實(shí)體的連接，如圖3（b）所示.數(shù)據(jù)降維后形成謂語索引的 S-O矩陣，對于RDF三元組（?巧，O&）的查詢，可以通過索引謂語巧對應(yīng)的S-O矩陣并定位到（?ofc） 來確定該三元組是否存在，從而保證降維后的三元組查詢?nèi)匀痪哂懈咝?，如圖3（c）所示.
此外，在本文的存儲方案中，以0/1的矩陣值來表示實(shí)體之間是否存在某一關(guān)系，如圖3（d）所示. 主語和賓語同為查詢實(shí)體，具有相似的屬性，因此在進(jìn)行數(shù)字編碼時將兩者歸在一塊進(jìn)行處理，這也 是常見存儲方法的處理思路.假設(shè)整個數(shù)據(jù)集的實(shí)體數(shù)量為Mo，謂語數(shù)量為飾，則數(shù)據(jù)降維后的空 間復(fù)雜度為O（飾· ^1。）.這相比于原始的數(shù)據(jù)立方體的存儲效率雖然有提高，但是存儲空間并沒有降 低.一種比較直接的優(yōu)化思路是將主語和賓語進(jìn)行拆分，考慮商品知識具有層次化的組織結(jié)構(gòu)特點(diǎn)， 這類知識圖譜的特點(diǎn)是層與層之間的實(shí)體通過同一類型的有向邊進(jìn)行連接.因此，與一個謂語相關(guān)性 比較強(qiáng)的應(yīng)當(dāng)是相鄰層的實(shí)體.對于謂語索引的S-O矩陣，可以利用這一特點(diǎn)進(jìn)行降維.單個S-O矩 陣的維度由原來的W|O更改為M · Wo，即維度大小由與這一謂語相關(guān)性更強(qiáng)的主語和賓語決定，而不 是全部實(shí)體.
舉例來說，根據(jù)圖1中的謂語hasAttribute和謂語hasOpinion構(gòu)建對應(yīng)的謂語索引矩陣如圖4所 示.圖4（a）將所有商品和屬性實(shí)體用關(guān)系hasAttribute進(jìn)行匯總和索弓丨，比如商品P1具有A1和A2 屬性，商品P2具有A3和A4屬性;圖4（b）則是將屬性和用戶觀點(diǎn)實(shí)體用關(guān)系hasOpinion進(jìn)行匯總和 索引，描述的是對于某一屬性有哪些用戶的觀點(diǎn).矩陣的橫軸將由該關(guān)系所有的主語表示，縱軸由該 關(guān)系所有的賓語表示，并可以通過矩陣轉(zhuǎn)置調(diào)換主語與賓語的位置關(guān)系.這種表示方式能夠很好地利 用商品知識圖譜的層次化結(jié)構(gòu)特點(diǎn)，從而有效地降低存儲空間.
4基于稀疏矩陣的查詢轉(zhuǎn)換
本章主要介紹基于稀疏矩陣的知識表示方法的查詢處理，將按照3個部分進(jìn)行介紹：查詢處理、 查詢預(yù)處理、基于GPU的查詢優(yōu)化.
4.1 查詢處理
對于簡單查詢、不涉及連接查詢的情況，可以直接通過查詢?nèi)M已知的元素來匹配查詢變量. 對于有謂語的查詢，則可以直接通過謂語索引到對應(yīng)的S-O矩陣，從而直接匹配到需要查詢的變量. 例如，假設(shè) SPARQL 查詢語句為 “SELECT ？x WHERE {P1 < hasAttribute > ？x.}”，即查詢商品 P1 的所有屬性，則可以直接對謂語hasAttribute矩陣進(jìn)行操作，通過定位到P1所在的列向量，所有標(biāo)識 為1的屬性都為商品P1的屬性.簡單查詢的轉(zhuǎn)換過程如圖5所示，最終商品P1具有的屬性有A1和A2.而對于未給定的謂語的查詢，可以遍歷謂語索引矩陣，通過判斷是否含有符合要求的主語/賓語來 確定最終要查詢的謂語是什么，遍歷謂語索引矩陣的時間復(fù)雜度為O（飾），其中飾為謂語的數(shù)量.
然而在真實(shí)的查詢處理過程中，連接是復(fù)雜查詢的核心操作.由于謂語索引矩陣的行和列分別由 主語和賓語構(gòu)成且值為0或1，其中1表示某個主語與賓語所對應(yīng)的實(shí)體存在謂語所對應(yīng)的關(guān)系，0則 表示不存在.通常，矩陣相乘類似于一種連接過程，但矩陣相乘與連接查詢有一個本質(zhì)的不同，即查詢 過程存在語義的轉(zhuǎn)換，不同的語義查詢結(jié)果不能進(jìn)行合并，而矩陣相乘則會將行和列的值相乘后直接 相加，因此無法保存謂語索引矩陣中的語義關(guān)系.但可以從這種連接過程中得到啟發(fā)，具有相同連接 變量的查詢?nèi)M，或者說具有相同連接實(shí)體的索引矩陣，可以按照對應(yīng)實(shí)體的維度進(jìn)行對齊，并對 相應(yīng)行/列的元素進(jìn)行位與操作.
為此，我們定義一種矩陣操作?，該運(yùn)算的含義為：在進(jìn)行矩陣維度的對齊后，進(jìn)行行列掃描的過 程中將對應(yīng)位置的每個元素進(jìn)行位與操作;即當(dāng)兩個謂語索引矩陣需要進(jìn)行連接運(yùn)算時，當(dāng)且僅當(dāng)兩 個矩陣需要連接的三元組的對應(yīng)位置為i時，兩個三元組的存在關(guān)系才能進(jìn)行傳遞，表現(xiàn)為結(jié)果矩陣 中的值也為1.例如，對于存在連接操作的SPARQL查詢“ SELECT ？yWHERE{？x
4.2查詢預(yù)處理
由4.1節(jié)對復(fù)雜查詢運(yùn)算的介紹可知，查詢?nèi)M的排列順序?qū)Σ樵冋Z句能否按順序執(zhí)行構(gòu)成直 接影響.因此，在執(zhí)行查詢之前還需要對查詢進(jìn)行預(yù)處理，即構(gòu)思一種查詢?nèi)M的重排列方案，使得 在連續(xù)執(zhí)行連接查詢時，盡可能保證查詢?nèi)M之間存在可以連接的實(shí)體.
對于本文所研究的商品知識圖譜，或者說這類具有層次化組織結(jié)構(gòu)的知識圖譜，根據(jù)圖1所示的商品知識表示實(shí)例可知，在讀取原始三元組數(shù)據(jù)時，可以依照謂語關(guān)系按照層與層之間分布的這一特 點(diǎn)，在構(gòu)建謂語與數(shù)字ID的雙向映射的過程中，保留謂語ID按順序排列的規(guī)則，即按照謂語出現(xiàn)的 層次順序從上往下（或者從下往上）去存儲.根據(jù)這種謂語的排列規(guī)則，兩兩相鄰的謂語索引矩陣一定 存在相連接的實(shí)體.
根據(jù)這一謂語存儲規(guī)則，在進(jìn)行查詢預(yù)處理時，依據(jù)謂語映射過來的數(shù)字ID的順序可以對查詢 三元組進(jìn)行重排列，從而保證在進(jìn)行實(shí)際的查詢過程中連接查詢執(zhí)行的連貫性，即連續(xù)執(zhí)行連接查詢 不會出現(xiàn)中斷的情況.如果重排后發(fā)現(xiàn)查詢?nèi)M的實(shí)體存在不連續(xù)的情況，則說明該查詢語句不存 在連接查詢，從而可以判斷該查詢?yōu)楹唵尾樵?，為之后的查詢?yōu)化做準(zhǔn)備.
4.3基于GPU的查詢優(yōu)化
通常而言，矩陣運(yùn)算這種數(shù)據(jù)密集型的運(yùn)算十分適合使用并行的方式進(jìn)行處理，因此對于矩陣的 索引以及基于矩陣的連接查詢也自然適合使用GPU進(jìn)行加速運(yùn)算.經(jīng)過查詢?nèi)M重排后，可以保 證對于需要連續(xù)執(zhí)行的連接查詢存在可以進(jìn)行相連接的實(shí)體.SPARQL查詢由多個子查詢?nèi)M構(gòu) 成，因此對于每條查詢?nèi)M，在對應(yīng)的謂語索引矩陣中的查詢也可以使用并行的方式加速計(jì)算.而 對基于矩陣的連接查詢，使用并行計(jì)算的方式也可以大大降低整個查詢的計(jì)算耗時.對基于GPU的 查詢優(yōu)化采用如下幾個步驟：
1.將每條查詢?nèi)M要查詢的索引矩陣傳輸?shù)紾PU中，使用并行方式計(jì)算各查詢的結(jié)果，并將 每條查詢?nèi)M的查詢結(jié)果放入全局內(nèi)存中，盡可能降低數(shù)據(jù)傳輸耗時;
2.在執(zhí)行連接查詢時，依據(jù)重排后的查詢?nèi)M順序，依次對每條查詢?nèi)M的查詢結(jié)果執(zhí)行連 接運(yùn)算，直到所有查詢被執(zhí)行完并得到最終的查詢結(jié)果.每次連接查詢后得到的結(jié)果矩陣大小由輸入 矩陣的行/列決定.由于連接查詢的中間結(jié)果會被頻繁讀寫，所以每次得到的中間結(jié)果也會放入全局 內(nèi)存中，但是上一次的查詢中間結(jié)果會在下一次查詢計(jì)算完成后被覆蓋，這是為了盡量減少GPU 內(nèi)存的占用.此外，在執(zhí)行連接查詢的過程中，隨著查詢條件的增多，本質(zhì)上是對查詢變量限制條件的 增加，因此中間結(jié)果的大小不會隨著查詢的增多而導(dǎo)致維度的增加;
3.將最終的計(jì)算結(jié)果傳輸回CPU中，并將查詢變量對應(yīng)的值作為最終的查詢結(jié)果進(jìn)行輸出. 根據(jù)以上的查詢步驟，我們期望在整個查詢過程中充分利用GPU的并行性能，并盡量減少數(shù)據(jù)傳輸耗時.
5實(shí) 驗(yàn)
本章主要是評估我們的查詢系統(tǒng)在標(biāo)準(zhǔn)數(shù)據(jù)集和商品知識數(shù)據(jù)集上的查詢性能.我們的方法主 要是針對具有層次化結(jié)構(gòu)的知識圖譜進(jìn)行了優(yōu)化，但與此同時，也驗(yàn)證了我們的方法對于通用的知識 數(shù)據(jù)具有適用性.
5.1實(shí)驗(yàn)環(huán)境
實(shí)驗(yàn)的硬件環(huán)境為單臺Intel（R） Core（TM） i7-8700 @ 3.20GHz的計(jì)算機(jī)，擁有16 GB DDR3內(nèi)存 和 1 TB 普通硬盤，其中 CPU 型號為 3.20 GHz， GPU 型號為 NVIDIA GeForce GTX 1060 （1280SIMD， 6 GB顯存），操作系統(tǒng)為Ubuntu 18.04 （64位），CUDA版本為9.0，使用C++11作為開發(fā)環(huán)境.此外， 為了增強(qiáng)實(shí)驗(yàn)結(jié)果的可靠性，對每輪的查詢實(shí)驗(yàn)執(zhí)行10次并將查詢耗時取平均作為實(shí)驗(yàn)結(jié)果.
5.2標(biāo)準(zhǔn)數(shù)據(jù)集LUBM上的實(shí)驗(yàn)對比和討論
為了驗(yàn)證基于稀疏矩陣的查詢轉(zhuǎn)換方式的有效性，實(shí)驗(yàn)對比采用了 6種不同數(shù)據(jù)量的LUBM數(shù) 據(jù)集（http：//swat.cse.lehigh.edu/projects/lubm/），并使用該數(shù)據(jù)集自帶的標(biāo)準(zhǔn)SPARQL查詢語句進(jìn)
行驗(yàn)證.這6個數(shù)據(jù)集的一些統(tǒng)計(jì)信息如表1所示.
LUBM數(shù)據(jù)集自帶的6個標(biāo)準(zhǔn)SPARQL查詢語句為Q1到Q6，對于我們的方法分別記錄了 CPU 下和CPU-GPU協(xié)同下的查詢響應(yīng)時間，主要是為了驗(yàn)證我們的查詢方法在標(biāo)準(zhǔn)數(shù)據(jù)集上的適用性. 實(shí)驗(yàn)結(jié)果如表2所示.
其中 Q1 為一個簡單的查詢（SELECT ？x WHERE {？x
5.3商品知識數(shù)據(jù)集上的實(shí)驗(yàn)對比和討論
根據(jù)目前大多數(shù)電子商務(wù)網(wǎng)站中商品的組織，從Amazon上獲取了商品的分類信息構(gòu)建成商品知 識圖譜中的商品分類層次，并將人工合成用戶的觀點(diǎn)信息整合到商品知識圖譜中.每個用戶遵從正態(tài) 分布隨機(jī)挑選商品并發(fā)表評論，而用戶評論中隨機(jī)數(shù)量的觀點(diǎn)知識也同樣符合正態(tài)概率分布，該數(shù)據(jù) 集的一些統(tǒng)計(jì)信息如表3所示.
針對商品數(shù)據(jù)集，設(shè)計(jì)了 3個SPARQL查詢語句，如表4所示，其中Q7為遍歷式查詢，Q8為鏈 式查詢，Q9為環(huán)式查詢.
在具有層次化結(jié)構(gòu)的商品知識圖譜上與常用的知識圖譜查詢系統(tǒng)RDF-3X和gStore進(jìn)行對比， 其中設(shè)計(jì)的各查詢語句在數(shù)據(jù)集AmazonDataset1、AmazonDataset2、AmazonDataset3上的運(yùn)行時間 結(jié)果如表5所示.
實(shí)驗(yàn)結(jié)果顯示，在三類商品知識數(shù)據(jù)的查詢中，得益于CPU-GPU異構(gòu)環(huán)境下的計(jì)算優(yōu)勢，我們 方法的平均查詢時間比RDF-3X和gStore的平均查詢時間短.即使是簡單查詢語句Q7，由于數(shù)據(jù)量 足夠大，所以查詢性能的優(yōu)越性也得以體現(xiàn);而且隨著數(shù)據(jù)量和查詢復(fù)雜度的進(jìn)一步提升，我們提出 方法的查詢效率提升也更加明顯.
6總結(jié)
知識圖譜已經(jīng)成為眾多智能應(yīng)用的基礎(chǔ)支持設(shè)施，面向大規(guī)模的知識數(shù)據(jù)提供高效的查詢處理 是一個重要的問題.商品知識具有層次化結(jié)構(gòu)的特點(diǎn)，現(xiàn)有的RDF知識查詢系統(tǒng)在查詢處理過程中 并沒有充分考慮這種特點(diǎn).本文針對大規(guī)模的商品知識圖譜，提出了一種基于矩陣的存儲方式，并依據(jù)層次化的組織結(jié)構(gòu)特點(diǎn)進(jìn)行了存儲優(yōu)化.同時，基于矩陣的存儲方式有利于使用并行方式加速查詢 的計(jì)算過程，本文設(shè)計(jì)了一種基于稀疏矩陣的查詢轉(zhuǎn)換方式，并將連接查詢算法擴(kuò)展到GPU上進(jìn)行 加速.我們與常用的RDF查詢引擎RDF-3X和gStore在標(biāo)準(zhǔn)數(shù)據(jù)集和商品知識數(shù)據(jù)集上進(jìn)行了查詢 性能對比.實(shí)驗(yàn)表明，文中提出的查詢處理方法在大規(guī)模商品知識圖譜上相對于對比方法具有較明顯 的優(yōu)勢，同時在標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)表明，提出的查詢處理方法也適用于通用知識數(shù)據(jù)的處理，并驗(yàn) 證了通過GPU提升大規(guī)模知識查詢處理效率的可行性.
然而，GPU內(nèi)存的大小仍然是制約其并行計(jì)算性能的主要因素.因此，在未來的工作中我們將針 對這一問題進(jìn)一步優(yōu)化存儲結(jié)構(gòu)，并且針對更大數(shù)據(jù)量的商品知識查詢需求，還將研究在分布式環(huán)境 中CPU-GPU協(xié)同的知識查詢處理.
[參考文獻(xiàn)]
[1]陳強(qiáng)，代仕婭.基于金融知識圖譜的會計(jì)欺詐風(fēng)險(xiǎn)識別[J].大數(shù)據(jù)，2021， 7（3）： 116-129.
[2]TAKEDA A， ITO Y. A review of FinTech research [J]. International Journal of Technology Management， 2021， 86（1）： 67-88.
[3 ] LEE K， LIU L. Scaling queries over big RDF graphs with semantic hash partitioning [J]. Proceedings of the VLDB Endowment， 2013， 6（1（4）： 1894-1905.
[4]NEUMANN T， WEIKUM G. The RDF-3X engine for scalable management of RDF data [J]. The VLDB Journal， 2010， 19（1）： 91-113.
[5]ZOU L， OZSU M T， CHEN L， et al. gStore： A graph-based SPARQL query engine [J]. The VLDB Journal， 2014， 23（4）： 565-590.
[6]INGALALLI V， IENCO D， PONCELET P， et al. Querying RDF data using a multigraph-based approach [C]// International Conference on Extending Database Technology （EDBT 2016）. 2016： 245-256.
[7]黃濤貽，李優(yōu)，未浩，等.大規(guī)模商品知識的組織和查詢優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用，2020， 56（2（1）： 154-163.
[8 ] SCHTZLE A， PRZYJACIEL-ZABLOCKI M， SKILEVIC S， et al. S2RDF： RDF querying with SPARQL on Spark [J]. Proceedings of the VLDB Endowment， 2016， 9（10）： 804-815.
[9]ATRE M， CHAOJI V， ZAKI M J， et al. Matrix Bit loaded： A scalable lightweight join query processor for RDF data [C]// Proceedings of the 19th International Conference on World Wide Web （WWW 2010）. 2010： 41-50.
[10]KIM J， SHIN H， HAN W S， et al. Taming subgraph isomorphism for RDF query processing [J]. Proceedings of the VLDB Endowment， 2015， 8（1（1）： 1238-1249.
[11]ZOUAGHI I， MESMOUDI A， GALICIA J， et al. Query optimization for large scale clustered RDF data [C]// Proceedings of the 22nd International Workshop on Design， Optimization， Languages and Analytical Processing of Big Data. 2020： 56-65.
[12]MANOLESCU I. Exploring RDF graphs through summarization and analytic query discovery [C] // Proceedings of the 22nd International Workshop On Design， Optimization， Languages and Analytical Processing of Big Data. 2020： 1-5.
[13]SONG J， PENG P， FENG Z， et al. MapSQ： A plugin-based MapReduce framework for SPARQL queries on GPU [C]// WWW18 Companion. 2018： 81-82.
[14]TRAN H N， CAMBRIA E， DO H G. Efficient semantic search over structured web data： A GPU approach [C]// International Conference on Computational Linguistics and Intelligent Text Processing （CICLing 2017）. 2017： 549-562.
[15]CHANTRAPORNCHAI C， CHOKSUCHAT C. TripleID-Q： RDF query processing framework using GPU [J]. IEEE Transactions on Parallel and Distributed Systems， 2018， 29（9）： 2121-2135.
[16]ZHANG X， ZHANG M， PENG P， et al. A scalable sparse matrix-based join for SPARQL query processing [C] // International Conference on Database Systems for Advanced Applications （DASFAA 2019）. 2019： 510-514.
[17]WANG S， LOU C， CHEN R， et al. Fast and concurrent RDF queries using RDMA-assisted GPU graph exploration [C]// Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference （USENIX ATC18）. 2018： 651-664.
[18]JAMOUR F， ABDELAZIZ I， CHEN Y， et al. Matrix algebra framework for portable， scalable and efficient query engines for RDF graphs [C]// Proceedings of the Fourteenth EuroSys Conference. 2019： 1-15.
（責(zé)任編輯：林晶）
