大規(guī)模RDF圖數據的子圖匹配查詢研究.pdf

1、子圖匹配(Basic Subgraph Pattern Matching)是RDF圖數據管理中的一種基本查詢類型，又稱子圖同構(Subgraph Isomorphism)，是一個NP-Complete問題。隨著語義網的發(fā)展和開放鏈接數據運動的發(fā)展，越來越多的數據通過RDF格式發(fā)布出來。高時間復雜度和巨大的數據規(guī)模給RDF圖數據的管理帶來了巨大挑戰(zhàn)。目前的單機查詢算法由于受限與子圖匹配問題的特性，往往會引入大量的連接操作，效率較低;基于M

2、apReduce的分布式查詢方案受限于MapReduce的迭代機制，查詢效率很難提升。因此，如何高效地在大規(guī)模的RDF圖數據上解決子圖匹配問題，成為一個具有挑戰(zhàn)性的工作。
　　本文提出了集中式和分布式兩種RDF圖數據查詢方案。在集中式查詢方案中，數據圖根據頂點度數的大小拆分成星狀的小規(guī)模子圖，并將這每個子圖編碼成一個二進制串。將子圖匹配的部分操作轉換成二進制位的“與”和“或”操作。使用該二進制串來過濾出可能的子結果。然后將子結果拼

3、接成完整的查詢結果。該方案避免了大多數的連接操作，使得每次訪問索引獲得一條三元組信息優(yōu)化到每次訪問索引獲得一組三元組信息。這種查詢方案提高了每次查詢獲得的信息量，大大減少了連接操作數量。在分布式查詢方案中，將RDF圖中的每個頂點都視為可執(zhí)行計算的單元，將整個圖映射成可互相傳遞消息的頂點集。這種模型基于BSP計算模型設計，充分利用了圖的特點，使用消息傳遞的方式逐步完善查詢圖，逐一減少變量數量，最終得到查詢結果，避免了迭代的MapReduc

4、e計算模型在解決圖計算問題時存在的很多限制，查詢效率明顯提高。本文設計的實驗從索引的空間代價和查詢響應時間等方面對上述兩種方法做了評價，集中式查詢方案在查詢響應時間上優(yōu)于目前性能最好的通用RDF集中式查詢引擎RDF-3X和gStore，分布式查詢方案也較MapReduce框架下實現(xiàn)的查詢方案有較大的性能提升。
　　綜上所述，本文針對RDF圖數據上的子圖匹配問題提出了單機集中式查詢和集群分布式查詢兩種查詢方案，在索引結構、數據編碼、