###### tags: `整理paper`
# Comparative Survey of Query Processing on Graph Databases

## 一. 前言

索引編制是優化查詢處理時間的最流行方法。在本文中，我們比較了一些有關子圖查詢處理的現有工作，包括**cIndex、gIndex**和**FG-Index**。

在圖數據庫上遇到的查詢可以大致分為subgraph，supergraph和similarity查詢。根據定義，圖數據庫是提供index-free adjacency的任何存儲系統。

這意味著每個元素都包含一個指向其相鄰元素的直接指針，並且不需要索引查找。 但是，沒有索引的查詢處理將需要大量的子圖同構檢查，這使其成為最無效的方法。 一個好的索引對於使圖形查詢與關係數據庫查詢保持一致是必不可少的，即使對於中等大小的圖形數據集也是如此。

首先第一項工作集中在過濾和候選驗證上。 第一個過程根據一些查詢參數過濾數據集。 此過濾後的圖形集比原始數據集小得多。

第二步，候選者驗證，是一個子圖同構問題。 即使大大減少了圖形的數量，每次查詢數據庫時執行此操作也證明是昂貴的。 一旦人們接受了過濾驗證方法不能產生預期的結果，特別是考慮到數據集擴展的方式，便提出了不同的索引方法。

我們提出了“Similarity Hash Index”或“ SHIndex”，這是一個兩步索引過程。在這裡，第一步是將圖形映射到平面上，然後基於相似性將它們分組到存儲桶中。當查詢進入時，我們在查詢圖上執行相同的map和hash函數。這將嚴重限制候選集中圖形的數量，從而確保在子圖形同構上花費的時間更少。

## 二. Exact Subgraph Queries
圖資料庫上最常見的查詢類型是精確子圖查詢。
給定一個圖數據庫D = {g1，g2 .... gN}，並使用較小的圖q，我們檢索D中所有作為q的超圖的圖。與近似匹配的情況相比，這裡的結果集受到更多的限制，但是缺點是定位精確匹配時需要進行額外的計算。再次證明，單純的過濾和驗證方法無效。在該領域中使用的常用方法包括快速增長的基於路徑或基於頻繁結構的機制。

這裡的一個範例是gIndex，其中涉及過多的候選驗證。這種方法的瓶頸是候選驗證，並且在遵循Amdahl原則之後，我們必須嘗試並最小化（如果不是徹底的話）消除這一昂貴的步驟。

FG-Index使用“頻繁子圖挖掘”的數據挖掘技術來收集在數據集中非常頻繁出現的一組子圖，因此也可能會非常頻繁地對其進行查詢。這組圖稱為頻繁圖集。該頻繁圖形集的大小可以通過用戶定義的閾值σ來確定。 FG是D中至少（σ。| D |）個圖的子圖。本文還使用δ容差的概念來減少索引中這組圖的總基數。該集合稱為δ容差閉合子圖集合。A graph g is a δ-TCFG ⇔ g ∈ F and there is no g’ ∈ F such that g’⊃ g and freq(g’)≥((1–δ)freq(g)), where (0 ≤ δ ≤ 1). Figure 1 shows an example of a δ-TCFG.


FG索引由核心FG索引和Edge索引組成。核心FGIndex由兩部分組成。首先，在δ-TCFG的集合τ上構造駐留內存的倒置索引。這些由數據庫中最常見的頻率圖形組成。

這些圖集中可能包含許多較小的子圖，它們在磁盤駐留反向索引中的單獨索引。 built on the FGs in the closure of each δ-TCFG.

這種索引結構將使我們能夠查詢最頻繁的子圖而無需執行候選驗證。為了允許對已遺漏的圖進行查詢，在D中很少出現的不同邊的集合上建立了另一個索引，稱為Edge-index。該索引使我們可以存儲頻繁圖和不頻繁圖之間的差異。圖2顯示了FG-Index的示例。

給定一個查詢圖q，我們首先在核心FG索引中搜索它。如果q是δ-TCFG，則從內存駐留索引中檢索q和Dq。

否則，我們需要找到qs最接近的δ-TCFG上圖g的磁盤駐留索引並檢索Dq。 但是，如果q恰好是一個不頻繁的子圖，因此在前面的兩個步驟中都找不到，則我們從核心索引中獲得一組q的子圖得分，而從邊緣索引中獲得不頻繁的邊緣的Sedge； 併計算交點以獲得候選集Cq。 現在在Cq上執行候選驗證，以消除誤報。

因此，FG索引是一種最小化精確子圖搜索所需的候選驗證次數的有效方法。 但是，該方法的效率取決於σ和δ的選擇。

### Study of Supergraph Indices

可以在圖形數據庫上執行兩種類型的查詢。第一個，子圖查詢返回給定查詢q的數據庫D子圖集的結果。另一方面，給定查詢q，超圖查詢從圖形數據庫D的超圖返回結果。在本節中，我們研究一些超圖索引編制實踐，旨在將其一些基本思想應用於子圖中。儘管查詢本質上是不同的，但是在圖形中執行搜索的方式從根本上是相似的，我們也許可以從這一領域中獲得一些啟發。
超圖查詢很難處理，並且通常的過濾和驗證方法效率很低。過濾和驗證技術是一種用於快速處理子圖的方法，因為處理子圖是NP完全問題。

通常，通過從圖形數據庫中提取子圖並使用cIndex算法對其進行處理來處理超圖。 cIndex算法基於查詢日誌中的歷史數據構造特徵索引。儘管cIndex是有效的，但是cIndex的一大缺點是查詢日誌是變量，導致特徵索引會過時。

針對圖數據庫的存儲問題，提出了一種新的GPTree方法。 GPTree通過將所有圖形數據庫作為子圖形並將它們放入一個圖形數據庫結構中來工作。首先通過編碼算法對數據庫中的所有圖形進行編碼，然後創建名為GVCodes的實體。然後，通常出現的子圖僅在新的GPTree結構中存儲一次。遞歸執行GPTree算法，直到創建最終的壓縮GPTree。壓縮完成後，我們繼續進行特徵生成的概念。

特徵生成是通過兩種不同的方法完成的。一個選擇所有重要的頻繁子圖，而另一個選擇重要的頻繁子圖的子集。據說頻繁的子圖暴露了圖數據庫的內在特徵。使用上述技術提取所有特徵後，將其過濾以節省不必要的子圖同構測試的成本，這減少了查詢處理的總成本。獲得了功能集之後，我們構建了一個優化的GP樹，稱為FGPTree，其中包含通用GVCode和功能集的有序集合。

#### 此處使用三種方法進行查詢處理

第一個是子圖同構測試（從一個到多個）。此處，子圖同構性由一組匹配的頂點的有序對表示，這些對用於創建圖數據庫g的增長的誘導子圖。與從根到GPTree中任何節點的路徑相對應的圖是從根到後代節點的圖的子圖。

冗餘特徵消除的第二種方法用於從sub-iso testing中濾除特徵。這用於從subgraph iso testing算法中去除特徵集。

第三種方法，集成查詢處理方法將上述兩種方法集成在一起，並在GPTree測試後生成結果集。本文最後指出，提出的創建GPTree和GPTreeTest的方法通過減少要在過濾器和驗證方法中執行的子圖同構測試的次數來提高效率。

## 三. Technical Details

在相關工作的調查中已經描述了我們作為比較研究的一部分實施的三種算法。的
使用Neo4j圖形數據庫的Neo4j Java API實現了三種算法：Cindex，Gindex和FGIndex。 Neo4j還具有用於Lucene索引引擎的API，這使我們的工作更加輕鬆。

Neo4j Lucene索引的源代碼可在線獲得，我們對Lucene jar文件中的IndexImplementation類進行了修改，以更改Lucene構建索引的方式。完成此修改後，Lucene引擎將負責索引的構造和維護。

因此，只有3種不同的方式實現了索引構建算法。完成此操作後，然後將3種索引方法彼此相對，並與“無索引”狀態進行比較。我們觀察到FG-Index表現最好，而g-Index緊隨其後。與預期相反，C-index的表現要差於G-index，但這可能與該特定數據集有關。

下一步是SHIndex算法的開發。 這是一個多階段的過程。 我們必須首先找出合適的映射函數，才能將圖形繪製到二維空間上。 然後，我們必須基於一些支持和閾值來確定數據集中的頻繁圖。 這些值可以由數據庫管理員固定。

下一步是使用適當的相似性哈希函數，根據與頻繁圖的相似性將圖分類為存儲桶。

這是索引構建階段的最後一步。 當查詢發送到系統時，查詢圖也會被映射和散列。 現在它將落入一個（或多個）存儲桶中。 僅所選存儲桶中的圖形需要進行候選驗證。 我們相信，儘管花費很長時間來構建索引，這仍將加快查詢速度。

## 四. Evaluation
Neo4j數據庫是一個高度健壯的開源屬性圖數據庫，完全符合ACID。它具有擴展到十億個節點的能力，並且對於存儲高度連接的實體非常有效。

選擇Neo4j的基本原因是它是開源的，並帶有Java API來更改其內部算法。
Neo4j帶有一個Web界面，該界面在系統localhost apache服務器上運行，並提供各種查詢和數據表示工具。下載了名為Campaign 2012 Election Data的數據集，並將其用作初始研究的示例數據集。該數據集包含525,769個節點，4614311個屬性，527,767個關係和6個關係類型。

也試用了不同的Cypher查詢，並記錄並繪製了每個查詢的計算時間。為了進行評估，我們開發了5個標準查詢。
查詢1.通過屬性查找特定的節點。
查詢2.查找按屬性排序的前100個結果。
查詢3.基於匹配關係，在關係上做聯接。
查詢4.匹配2個關係中的一組屬性。
查詢5.是基於2個匹配項的匯總查詢。

當我們運行查詢時，我們得到的運行時變化很大。 因此，對於每個索引結構，每個查詢都運行了50次，然後將運行時間平均化。 下圖以無索引方式繪製了3種索引算法的性能比較圖。 如我們所見，FG-Index表現最佳，其次是G-Index。

## 補充:
### Amdahl's Law 阿姆達爾定律
定義 : 針對電腦系統裡面某一個特定的元件予以最佳化，對於整體系統有多少的效能改變。

例子:[改變後與原本的效率，改變特定的因素後，加了8倍的速度，對總體而言可能只有2.5倍的效率(裡面是詳細連結)](https://chi_gitbook.gitbooks.io/personal-note/content/amdahls_law.html)

### 反向(倒排)索引(Inverted Index)

是文件檢索系統中最常用的資料結構。
是當代(21世紀初葉)搜尋引擎在製作索引的主流，兼具效率和彈性。
一個搜索引擎執行的目標就是優化查詢的速度：
找到某個單字在文件檔中出現的地方。
用來儲存在全文搜索下單字(word)與單字本身在文件中所在位置之間的映射。
反向索引通常利用關聯陣列呈現。它有兩種呈現形式：
inverted file index，其呈現形式為 {單字，單字所在文件的位置}
full inverted index，其呈現形式為 {單字，（單字所在文件的位置，單字在該文件本身的位置）}

### Lucene中最基礎的概念是索引（index），文檔（document．，域（field）和項（term）。

索引包含了一個文檔的序列。

· 文檔是一些域的序列。

· 域是一些項的序列。

· 項就是一個字串。

存在於不同域中的同一個字串被認為是不同的項。因此項實際是用一對字串表示的，第一個字串是域名，第二個是域中的字串。

倒排索引

為了使得基於項的搜索更有效率，索引中項是靜態存儲的。Lucene的索引屬於索引方式中的倒排索引，因為對於一個項這種索引可以列出包含它的文檔。這剛好是文檔與項自然聯繫的倒置。

域的類型

Lucene中，域的文本可能以逐字的非倒排的方式存儲在索引中。而倒排過的域稱為被索引過了。域也可能同時被存儲和被索引。

域的文本可能被分解許多項目而被索引，或者就被用作一個項目而被索引。大多數的域是被分解過的，但是有些時候某些標識符域被當做一個項目索引是很有用的。

段（Segment）

Lucene索引可能由多個子索引組成，這些子索引成為段。每一段都是完整獨立的索引，能被搜索。索引是這樣作成的：

1. 為新加入的文檔創建新段。

2. 合併已經存在的段。

搜索時需要涉及到多個段和/或者多個索引，每一個索引又可能由一些段組成。

文檔號（document．nbspNumber）

內部的來說，Lucene用一個整形（interger）的文檔號來指示文檔。第一個被加入到索引中的文檔就是0號，順序加入的文檔將得到一個由前一個號碼遞增而來的號碼。

注意文檔號是可能改變的，所以在Lucene外部存儲這些號碼時必須小心。特別的，號碼的改變的情況如下：

· 只有段內的號碼是相同的，不同段之間不同，因而在一個比段廣泛的上下文環境中使用這些號碼時，就必須改變它們。標準的技術是根據每一段號碼多少為每一段分配一個段號。將段內文檔號轉換到段外時，加上段號。將某段外的文檔號轉換到段內時，根據每段中可能的轉換後號碼範圍來判斷文檔屬於那一段，並減調這一段的段號。例如有兩個含5個文檔的段合併，那麼第一段的段號就是0，第二段段號5。第二段中的第三個文檔，在段外的號碼就是8。

·文檔刪除後，連續的號碼就出現了間斷。這可以通過合併索引來解決，段合併時刪除的文檔相應也刪掉了，新合併而成的段並沒有號碼間斷。

### FG-Index: Towards Verification-Free Query Processing on Graph Databases

圖同構常見的步驟都是生成候選集合（candidate set）將不可能入選結果集的結果過濾掉，第二部就是對候選集合進行驗證。

假設現在存在一組頻繁子圖FG（Frequent subGraph），如果查詢圖是FG當中的一個元素，那麼FG-index就可以直接把對應的結果返回給用戶。如果查詢不存在FG當中，那麼FG-index會給出一個跟正確結果很相近的候選集合，那麼這樣的驗證也相應的可以減少很多。

為了可以讓索引載入到內存當中，文章中提出了δ-Tolerance Closed Frequent Graphs。可以調整索引的大小。

#### 背景
圖同構兩大步驟：過濾=>驗證
頻繁出現的圖意味著過濾以後的候選集合會非常大，那麼就需要驗證很多的候選結果。
較少出現的圖意味著利用FG-index可以返回基本和結果一樣的候選集合。
需要解決的一個問題是，如果選定的閾值太小δ，那麼index將會太大。這也是文章想解決的一個問題。
每個δ-TCFG都可以看作是FGs的代表超圖。 這樣，FG-index在駐留在主記憶中的δTCFGs集合上建立外部反向索引。 然後，在每個δ-TCFG的FGs上建立一個內部反向索引，該聚集駐留在disk中。
核心FG索引的第一級IGI，δTCFG和Edge索引位於主記憶體中。
FG-index的所有其他部分都駐留在disk中。
每個索引圖g的Dg存儲在disk中。

#### 基本定義
圖頻率給定一個圖數據庫D，給定一個圖g，所有g'滿足g是g'的子圖，g'是D中的一個元素，這樣g'的數量表示g的頻率。直觀來講就是g是D中多少個圖的子圖。計作freq(g).
頻繁子圖用戶給定σ，當一個圖g的freq(g)大於σ時，那麼就稱g是一個頻繁子圖。
最大頻繁子圖MFG對於一個頻繁子圖的集合F，對於F中的一個元素g，不存在其他的元素g'是g的超圖，那麼g是F當中的一個MFG。
閉頻繁子圖CFG對於一個頻繁子圖的集合F，對於F中的一個元素g，不存在g'是g的超圖，並且freq(g')=freq(g)，那麼我們稱g是F的一個CFG。

### Cindex
cIndex首先在要素上構造索引，這些要素是從圖數據庫中提取的子圖，並且很少出現在歷史查詢圖中。在查詢處理期間，cIndex通過使用過濾和驗證方法避免了大量的子圖同構測試。另外，由cIndex構造的特徵索引的大小非常小，因為索引中的特徵是從圖形數據庫中提取時，由查詢日誌中的歷史查詢過濾的。

cIndex具有以下缺點。功能索引的有效性和效率取決於查詢日誌中的歷史查詢。但是，查詢日誌可能會隨時間頻繁更改，因此功能索引可能會過時。

監視和更新特徵索引的機制涉及大量的子圖同構測試。因此，cIndex的整體性能大大降低。
### GPTree

在提出的新方法中，圖數據庫以扁平方式緊湊地存儲，即，圖數據庫中的圖被一一排列，以提高查詢處理（驗證）的效率。為了加快特徵索引的構建，提出了一種不考慮查詢日誌的從圖數據庫中提取特徵的快速算法。

為了進一步提高查詢處理（過濾）的效率，將特徵集上的最佳順序添加到特徵索引中。為了大大提高超圖查詢處理關鍵部分的性能，提出了一種從多圖到一個圖的子圖同構測試新算法。
#### 查詢處理方法概述
1. 組織資料庫，建造GTPtree。
2. 創建index，首先，從圖形數據庫中提取特徵。 然後，基於所提取特徵的支持集之間的包含關係來確定特徵集上的順序。 最後，基於用於GPTree構造的算法，在給定的圖形數據庫上創建了兩個特徵索引，分別為FGPTree和CRGraph。
3. 查詢處理。 首先，使用FGPTree和CRGraph生成帶有查詢圖q的給定查詢的候選答案集。 然後，通過使用GPTree和GPTreeTest算法測試所有候選者到q的子圖同構性，即從多個圖測試一個圖的子圖同構性的算法，最終驗證候選答案集中的所有候選者（或圖），最後獲得查詢答案。
#### GPTree of a Graph Database
**值觀想法:**

A，B，C表示三個不同的頂點標籤，圖2說明了圖1中圖數據庫的緊湊組織。在該組織中，粗實線三角形是g1和g2的公共子圖，而實線五邊形子圖是g3和g4的公共子圖。

要構建圖形數據庫的GPTree，數據庫中的所有圖形都需要通過編碼方法進行編碼。 這種圖形編碼，稱為GVCode。

以a3為例:第三點的label是A，相鄰點1與點2，<1,A,->代表相鄰V1值是A，而邊的label為-(作者在這裡先忽略了邊上的label)
建構GPTree步驟:
Step 1. Select optimal induced subgraph for each graph in D .
Step 2. Generate GVcodes for all the graphs in D using the induced subgraphs obtained in Step 1.
Step 3. Construct the GPTree of D using the GVcodes generated in Step 2.
#### Indices on Graph Databases

Feature Generation:

對於超級圖查詢，下面將分析每個頻繁子圖的過濾能力。 將會看到，與所有特徵子集相比，所有被選作特徵的頻繁子圖的子集能夠實現相同的過濾能力。

從數據庫生成特徵集的**精確算法**包括以下兩個步驟。
Step 1, mine closed frequent subgraphs.
Step 2, refine subgraphs obtained in Step 1，即根據用戶指定的δmin消除不重要的頻繁子圖，該值以水平方式逐級從大到小進行。

因此，所有最大頻繁子圖都被選擇為特徵。 根據挖掘算法中的深度優先搜索順序，可以得到步驟1中某些封閉頻繁子圖之間的包含關係，在步驟2中無需再次檢查； 因此，在用於特徵生成的精確算法中，減少了子iso測試的次數。

用於生成特徵集的**近似算法**直接挖掘特徵，而不是在挖掘後進行細化。

CRGraph。 CRGraph索引結構是有向無環圖（DAG）。


支持功能集之間的這種直接包含關係定義了偏序關係。然後，將特徵的支持集從概念上組織成一個格，格點由代表相應特徵的DAG表示，邊表示直接包含關係。

FGPTree。 在獲得有序的特徵集之後，我們使用與GPTree類似的策略來組織所有特徵，以獲得稱為“ GPGPTree”的準“ GPTree”結構。

在FGPTree中，結合了不同特徵的GVCode的一些但不是全部通用前綴，並保留了特徵集上的順序。
#### Discussions on Graph Database Organizing and Index Creating

我們的方法中的預處理包括將圖形數據庫組織到GPTree中，以及創建CRGraph和FGPTree的索引。

將用於GPTree構造的數據庫上指定的頻繁誘發子圖挖掘的過程與指定的封閉頻繁子圖挖掘進行合併，以進行特徵生成，方法如下。在集成挖掘的過程中，如果可以根據一種挖掘算法的條件對搜索分支進行修剪，則僅沿分支進行另一種挖掘算法；否則，這兩種挖掘方案的檢查均以原始方式進行。

總而言之，我們方法中的預處理包括兩個步驟。首先構造給定圖形數據庫的GPTree。同時，將生成初始特徵集。

然後，如果採用精確的特徵生成算法，則從初始特徵集中進行特徵選擇；如果使用近似的特徵生成方法，則初始特徵集不會改變；對特徵進行排序，並創建CRGraph和FGPTree。
#### Query Processing

Subgraph Isomorphism Testing from Many to One
gs= small graph,gl= large graph
從編碼為GVCode（gs）的gs到gL的sub-iso測試涉及帶有回溯的樹搜索過程。按照按照與GVCode（gs）一致的順序檢查Vs的頂點的方式構造狀態空間，並以頂點增長的方式將gL與gs逐個頂點進行比較。

搜索空間中的每個狀態t與部分子圖同構(partial subgraph isomorphism)psi（t）相互關聯，這是一組匹配的有序頂點pair，它們對應於從root到搜索樹中狀態t的路徑。這兩個狀態對應於一對新的匹配頂點的添加。

在搜索空間上採用深度優先搜索。對於每個狀態t，我們計算一個候選對集合(candidate pair set)CPS（t），該對集合由潛在的後續匹配頂點對組成。對於CPS（t）中的所有對，第一個分量相同，並且等於gVCode（gs）中設置的頂點順序中gs中的下一個頂點，第二個分量對應於gL中不涉及的每個頂點psi（t）。

在搜索過程中的每個狀態下，通過刪除隨後無法擴展為子圖同構的頂點對來優化CPS （t）。用於CPS（t）的條件稱為修剪條件。 顯然，Vs中的一個頂點不能與VL中的一個頂點與其他標籤匹配。

修剪條件2確保部分子圖同構psi（t'）本身是從Vs（t'）到gL的頂點所引起的gs子圖的子圖同構。 修剪條件2表示為PruCondig。
例如，在通過修剪條件1細化之後，示例2中的CPS（t）等於{（v4，u4），（v5，u5）} ，在通過修剪條件2細化之後，CPS（t）等於{（v4，u4）}。

當我們從GPTree中的多個圖形執行子iso測試時，將一起檢查它們在一條路徑中的常見感應子圖形。

因此，將q中的每個嵌入（子圖同構的圖像）與多個圖的共同誘導子圖同時進行比較。 這樣，可以節省許多子iso測試。
每個狀態都與一個頂點對（最後添加的對以psi為單位）相關聯。 對於與（n6，u4）相關的狀態t，psi（t）= {（n1，u1），（n2，u2），（n3，u3），（n6，u4）}。

請注意，每對的第一個分量psi（t）是GPTree中的一個節點，因為與從GPTree中的根開始的任何路徑相對應的子圖與該路徑所代表的任何子圖都是同構的。 狀態t中的矩形表示在t中找到了對q2的一些答案。 特別地，在（n6，u4）的狀態下，找到g2； 在（n5，u4）的狀態下，找到g1。 因此，當完成搜索空間時，獲得答案集，即{g1，g2}。

#### On-line Redundant Features Shedding
根據CRGraph的索引，嵌入到過濾階段的q的在線冗餘特徵將按以下方式工作。 以最佳順序≺*檢查特徵。 在此過程中，如果q中不包含特徵f，則將與CRGraph中f對應的頂點的所有後代添加到名為散射特徵集的集合SF中。 之後，無需測試SF中的所有功能是否具有q的子等式。 在下一次迭代中，我們以≺*的順序檢查下一個特徵，這不在SF中。

重複此過程，直到檢查或去除所有特徵為止。 因此，最終散射特徵集SF記錄了從子圖同構測試中避免的所有特徵。
#### The Integrated Query Processing Method
FGPTree上的查詢處理將在線冗餘功能釋放和FGPTree上的GPTreeTest集成在一起，而GPTree上的查詢處理直接遵循GPTreeTest，並參考在過濾步驟之後獲得的候選集。

也就是說，整個查詢處理是一種集成方法，其技術包括在線冗餘特徵消除和從GPTree中的多個圖形到查詢的子iso測試。 它可以很容易地集成，因此我們沒有明確闡述。

總之，查詢處理包括兩個步驟。 給定一個查詢，首先使用CRGraph來檢查FGPTree，即在線冗餘特徵脫落，並生成候選集。

然後，將GPTreeTest用於將GPTree中的圖形投影到候選集上，並返回答案集。
#### support for external storage as follows

外部存儲的支持，如下所示。基於磁盤的策略是，圖形數據庫的GPTree的樹狀結構並未物理實現，而是僅記錄了每個圖形的頂點集在GVCode中的順序。在處理查詢時，僅檢索候選圖，並且即時構建這些候選的GPTree的樹。

如果所有候選者的GPTree不能容納在內存中，則接連加載一個候選者的一部分，並多次調用GPTreeTest以完成驗證步驟。

我們將重點放在該方法的內存方面，並且探索詳細的支持外部存儲的策略被認為是未來的工作。

接下來，在插入和刪除的兩種情況下討論組織和索引的維護。為了插入，將新圖g插入D時，

步驟1，對於GPTree，將以隨機順序生成其中的代碼的GVCode（g），然後將生成的GVCode（g）插入GPTree。

步驟2，執行FGPTree上的GPTreeTest來更新g包含的所有功能的支持集；

第3步，對於CRGraph，如果每個有向邊的原點對應於g中不包含的特徵，而其目的地端點對應於g中包含的特徵，則將其移除。步驟2和步驟3一起進行。對於刪除，當要通過其圖形ID從D刪除圖形g時，僅與g相關的路徑將從GPTree中直接刪除。

### 三種子圖解釋