圖形遍歷

使用串流運算式的圖形遍歷會使用 nodes 函式來執行廣度優先的圖形遍歷。

nodes 函式可以與 scoreNodes 函式結合，以提供建議。nodes 也可以與更廣泛的串流運算式程式庫結合，以對收集的節點集執行複雜的操作。

nodes 遍歷分散在 SolrCloud 集合中，並且可以跨越集合。

nodes 設計用於需要放大圖形中的鄰近區域，並執行精確遍歷以收集節點集和聚合的使用案例。在這些類型的使用案例中，nodes 通常會提供次秒級的效能。文件中稍後會提供一些範例使用案例。

本文件假設您對圖形術語和串流運算式有基本的了解。您可以從這篇維基百科文章開始探索圖形遍歷概念。有關串流運算式的更多詳細資訊，請參閱本指南中的串流運算式章節。

基本語法

我們將從最基本的語法開始，並逐步建立更複雜的語法。nodes 最基本的語法為

nodes(emails,
      walk="johndoe@apache.org->from",
      gather="to")

讓我們分解這個簡單的運算式。

第一個參數 emails 是要遍歷的集合。第二個參數 walk 會將硬式編碼的節點 ID ("johndoe@apache.org") 對應到索引中的欄位 (from)。這會傳回索引中 from 欄位包含 johndoe@apache.org 的所有**邊緣**。

gather 參數會指示函式收集 to 欄位中的值。收集的值是函式發出的節點 ID。

在上面的範例中，發出的節點會是所有曾經收到 "johndoe@apache.org" 寄出的電子郵件的人。

walk 參數也接受根節點 ID 的清單

nodes(emails,
      walk="johndoe@apache.org, janesmith@apache.org->from",
      gather="to")

上面的 nodes 函式會找到 from 欄位包含 "johndoe@apache.org" 或 "janesmith@apache.org" 的所有邊緣，並收集 to 欄位。

如同所有串流運算式，您可以將 nodes 運算式傳送至 /stream 處理程式來執行。例如

curl --data-urlencode 'expr=nodes(emails,
                                  walk="johndoe@apache.org, janesmith@apache.org->from",
                                  gather="to")' https://127.0.0.1:8983/solr/emails/stream

此運算式的輸出會像這樣

{
  "result-set": {
    "docs": [
      {
        "node": "slist@campbell.com",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "node": "catherine.pernot@enron.com",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "node": "airam.arteaga@enron.com",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "EOF": true,
        "RESPONSE_TIME": 44
      }
    ]
  }
}

傳回的所有元組都有 node 欄位。node 欄位包含函式收集的節點 ID。遍歷的 collection、field 和 level 也會包含在輸出中。

請注意，範例中每個元組的層級都是「1」。根節點的層級是 0 (在上面的範例中，根節點是 "johndoe@apache.org, janesmith@apache.org") 根據預設，nodes 函式只會發出遍歷的*葉節點*，也就是最外面的節點集。若要發出根節點，您可以指定 scatter 參數

nodes(emails,
      walk="johndoe@apache.org->from",
      gather="to",
      scatter="branches, leaves")

scatter 參數會控制是否發出分支和葉節點。根節點會被視為「分支」，因為它們不是遍歷的最外層。

當散佈分支和葉節點時，輸出會像這樣

{
  "result-set": {
    "docs": [
      {
        "node": "johndoe@apache.org",
        "collection": "emails",
        "field": "node",
        "level": 0
      },
      {
        "node": "slist@campbell.com",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "node": "catherine.pernot@enron.com",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "node": "airam.arteaga@enron.com",
        "collection": "emails",
        "field": "to",
        "level": 1
      },
      {
        "EOF": true,
        "RESPONSE_TIME": 44
      }
    ]
  }
}

現在層級 0 的根節點也會包含在輸出中。

聚合

nodes 也支援聚合。例如

nodes(emails,
      walk="johndoe@apache.org, janesmith@apache.org->from",
      gather="to",
      count(*))

上面的運算式會找到 from 欄位包含 "johndoe@apache.org" 或 "janesmith@apache.org" 的邊緣，並收集 to 欄位的值。它也會聚合每個收集的節點 ID 的計數。

如果「johndoe@apache.org」和「janesmith@apache.org」都發送電子郵件給同一個人，則聚集節點的計數可能為 2。節點集合包含一組唯一的節點，因此同一個人不會在節點集合中出現兩次，但計數會反映出它在遍歷期間出現了兩次。

邊緣會在遍歷過程中被視為唯一，因此計數不會反映「johndoe@apache.org」向同一個人發送電子郵件的次數。例如，personA 可能已向 personB 發送了 100 次電子郵件。這些邊緣將會被視為唯一，並且只會計算一次。但如果 personC 也向 personB 發送電子郵件，則 personB 的計數將會增加。

支援的聚合函數包括 count(*)、sum(field)、min(field)、max(field) 和 avg(field)。被聚合的欄位應存在於遍歷期間收集的邊緣中。後面的範例（如下所示）將說明聚合如何成為提供建議和限制遍歷範圍的強大工具。

巢狀節點函數

可以巢狀使用 nodes 函數來更深入地遍歷圖表。例如

nodes(emails,
      nodes(emails,
            walk="johndoe@apache.org->from",
            gather="to"),
      walk="node->from",
      gather="to")

在上面的範例中，外部的 nodes 函數會對從內部 nodes 函數收集的節點集合進行操作。

請注意，內部的 nodes 函數的行為與已討論的範例完全相同。但是，外部的 nodes 函數的 walk 參數的行為會有所不同。

在外部的 nodes 函數中，walk 參數會使用來自內部串流運算式的元組。在這種情況下，walk 參數會將 node 欄位對應到 from 欄位。請記住，從內部 nodes 運算式收集的節點 ID 會放置在 node 欄位中。

更簡單地說，內部運算式會收集「johndoe@apache.org」發送電子郵件的所有人。我們可以將此群組稱為「johndoe@apache.org 的朋友」。外部運算式會收集「johndoe@apache.org 的朋友」發送電子郵件的所有人。這是一個基本的朋友的朋友遍歷。

這種巢狀使用 nodes 函數的結構是透過圖表執行受控制的遍歷的基本技術。

循環偵測

nodes 函數會在整個遍歷過程中執行循環偵測。這可確保不會再次遍歷已造訪過的節點。循環偵測對於限制遍歷的大小和收集準確的聚合至關重要。如果沒有循環偵測，遍歷的大小可能會隨著遍歷中的每次躍點而呈指數級增長。使用循環偵測，只會遍歷遇到的新節點。

循環偵測不會跨越集合邊界。這是因為在內部，集合名稱是節點 ID 的一部分。例如，節點 ID「johndoe@apache.org」實際上是 emails/johndoe@apache.org。當遍歷到另一個集合時，將會遍歷「johndoe@apache.org」。

篩選遍歷

可以使用篩選查詢來篩選遍歷中的每個層級。例如

nodes(emails,
      walk="johndoe@apache.org->from",
      fq="body:(solr rocks)",
      gather="to")

在上面的範例中，只會將符合篩選查詢的電子郵件包含在遍歷中。這裡可以包含任何 Solr 查詢。因此，您可以執行有趣的動作，例如地理空間查詢，套用任何可用的查詢剖析器，甚至編寫自訂查詢剖析器來限制遍歷。

根串流

可以使用任何串流運算式來提供遍歷的根節點。例如

nodes(emails,
      search(emails, q="body:(solr rocks)", fl="to", sort="score desc", rows="20")
      walk="to->from",
      gather="to")

上面的範例透過搜尋運算式提供根節點。您也可以提供任意複雜的巢狀串流運算式，其中包含聯結等，以指定根節點。

請注意，walk 參數會將內部串流產生的元組中的欄位對應。在這種情況下，它會將內部串流中的 to 欄位對應到 from 欄位。

跳過高頻率節點

通常，我們會希望跳過圖表中高頻率的節點。這在性質上類似於搜尋字詞的停止清單。描述此功能的最佳方式是透過範例使用案例。

假設您想要根據協同篩選來為使用者推薦內容。以下是一種簡單的協同篩選方法

找出使用者 A 已讀取的所有內容。
找出讀取清單與使用者 A 最接近的使用者。這些是與使用者 A 有相似品味的使用者。
根據步驟 2 中使用者已讀取，但使用者 A 尚未讀取的內容推薦內容。

仔細查看步驟 2。在大型圖表中，步驟 2 可能會導致非常大的遍歷。這是因為使用者 A 可能已檢視過數百萬人檢視過的內容。我們可能想要基於以下兩個原因跳過這些高頻率節點

會造訪數百萬個唯一節點的大型遍歷速度緩慢，並且會佔用大量記憶體，因為循環偵測會在記憶體中追蹤。
高頻率節點在判斷品味相似的使用者方面也沒有用處。檢視人數較少的內容可以提供更精確的建議。

nodes 函數具有 maxDocFreq 參數，可允許篩選掉高頻率節點。以下範例程式碼顯示建議的步驟 1 和步驟 2

 nodes(logs,
       search(logs, q="userID:user1", fl="articleID", sort="articleID asc", fq="action:view", qt="/export"),
       walk="articleID->articleID",
       gather="userID",
       fq="action:view",
       maxDocFreq="10000",
       count(*)))

在上面的範例中，內部的搜尋運算式會搜尋 logs 集合，並傳回「user1」檢視的所有文章。外部的 nodes 運算式會取得從內部搜尋運算式發出的所有文章，並在記錄集合中尋找這些文章的所有記錄。然後，它會收集和聚合已讀取文章的使用者。maxDocFreq 參數會將傳回的文章限制為那些在不超過 10,000 筆記錄（每個分片）中出現的文章。這可以避免傳回已被數百萬使用者檢視過的文章。

追蹤遍歷

預設情況下，nodes 函數只會追蹤足夠的資訊來執行循環偵測。這提供了足夠的資訊來輸出圖表中的節點和聚合。

對於某些使用案例，例如圖表視覺化，我們也需要輸出邊緣。將 trackTraversal="true" 設為會告知 nodes 追蹤節點之間的連線，以便建構邊緣。啟用 trackTraversal 時，每個節點都會出現新的 ancestors 屬性。ancestors 屬性包含指向該節點的節點 ID 清單。

以下是 trackTraversal 設定為 true 的 nodes 運算式範例

nodes(emails,
      nodes(emails,
            walk="johndoe@apache.org->from",
            gather="to",
            trackTraversal="true"),
      walk="node->from",
      trackTraversal="true",
      gather="to")

跨集合遍歷

巢狀的 nodes 函數可以在不同的 SolrCloud 集合上操作。這允許遍歷從一個集合「遍歷」到另一個集合以收集節點。循環偵測不會跨越集合邊界，因此在一個集合中收集的節點將會在不同的集合中遍歷。這樣做的目的是為了支援跨集合遍歷。請注意，跨集合遍歷的輸出可能會包含具有不同集合屬性的重複節點。

以下是一個從「emails」集合遍歷到「logs」集合的 nodes 運算式範例

nodes(logs,
      nodes(emails,
            search(emails, q="body:(solr rocks)", fl="from", sort="score desc", rows="20")
            walk="from->from",
            gather="to",
            scatter="leaves, branches"),
      walk="node->user",
      fq="action:edit",
      gather="contentID")

上面的範例會尋找所有傳送電子郵件且內文包含「solr rocks」的人員。然後，它會尋找這些人員發送電子郵件的所有人員。接著，它會遍歷到 logs 集合，並收集這些人員編輯的所有內容 ID。

將節點與其他串流運算式結合

nodes 函數可以作為串流來源和串流裝飾器。與更廣泛的串流運算式程式庫的連線，在執行圖表遍歷時提供了巨大的力量和彈性。以下是使用串流運算式程式庫來交集兩個朋友網路的範例

            intersect(on="node",
                      sort(by="node asc",
                           nodes(emails,
                                 nodes(emails,
                                       walk="johndoe@apache.org->from",
                                       gather="to"),
                                 walk="node->from",
                                 gather="to",
                                 scatter="branches,leaves")),
                       sort(by="node asc",
                            nodes(emails,
                                  nodes(emails,
                                        walk="janedoe@apache.org->from",
                                        gather="to"),
                                  walk="node->from",
                                  gather="to",
                                  scatter="branches,leaves")))

上面的範例會收集兩個獨立的朋友網路，一個以「johndoe@apache.org」為根，另一個以「janedoe@apache.org」為根。然後，朋友網路會依 node 欄位排序，並進行交集。產生的節點集合將會是兩個朋友網路的交集。

圖表遍歷的範例使用案例

計算市場購物籃共同出現

知道哪些產品最常與特定產品一起購買通常很有用。此範例使用簡單的市場購物籃表格（在 Solr 中編製索引）來儲存過去的購物籃。表格的結構描述非常簡單，每一列都包含 basketID 和 productID。這可以視為圖表，表格中的每一列都代表一個邊緣。即使圖表包含數十億個邊緣，也可以非常快速地遍歷圖表來計算購物籃的共同出現。

以下是範例語法

top(n="5",
    sort="count(*) desc",
    nodes(baskets,
          random(baskets, q="productID:ABC", fl="basketID", rows="500"),
          walk="basketID->basketID",
          fq="-productID:ABC",
          gather="productID",
          count(*)))

讓我們仔細分析一下這個遍歷的確切作用。

評估的第一個運算式是內部的 random 運算式，它會從具有 productID「ABC」的 baskets 集合傳回 500 個隨機 basketID。random 運算式對於建議非常有用，因為它會將遍歷限制為一組固定的購物籃，並將驚喜元素加入建議中。使用 random 函數，您可以從非常大的圖表中提供快速的範例集。
外部的 nodes 運算式會在 baskets 集合中尋找步驟 1 中產生的 basketID 的所有記錄。它也會篩選掉 productID「ABC」，使其不會顯示在結果中。然後，它會收集和計算這些購物籃中的 productID。
外部的 top 運算式會依計數排名步驟 2 中發出的 productID，並選取前 5 個。

簡而言之，此運算式會尋找過去購物籃中與產品「ABC」最常同時出現的產品。

使用 scoreNodes 函數來提出建議

此使用案例以市場購物籃範例（上方）為基礎，該範例會計算哪些產品與 productID:ABC 的共同出現次數最多。排名後的共同出現計數提供了建議候選項目。scoreNodes 函數可用於對候選項目進行評分，以尋找最佳建議。

在深入了解 scoreNodes 函數的語法之前，了解為什麼原始共同出現計數可能無法產生最佳建議會很有用。原因是原始共同出現計數偏好在所有購物籃中頻繁出現的項目。更好的建議是尋找與 productID ABC 具有最顯著關係的產品。scoreNodes 函數會使用詞頻-逆向文件頻率 (TF-IDF) 演算法來尋找最重要的關係。

scoreNodes 的運作方式

scoreNodes 函數會為節點表達式發出的每個節點分配一個分數。預設情況下，scoreNodes 函數使用 count(*) 聚合，即共現次數，作為 TF 值。每個節點的 IDF 值會從該節點收集的集合中提取。然後使用 TF*IDF 公式對每個節點進行評分，該公式會提升在所有購物籃中頻率較低的節點的分數。

將共現次數與 IDF 結合使用，可提供一個分數，顯示 productID ABC 與推薦候選項目之間的關係有多重要。

scoreNodes 函數會將分數新增至 nodeScore 欄位中的每個節點。

`scoreNodes` 語法範例

top(n="1",
    sort="nodeScore desc",
    scoreNodes(top(n="50",
                   sort="count(*) desc",
                   nodes(baskets,
                         random(baskets, q="productID:ABC", fl="basketID", rows="500"),
                         walk="basketID->basketID",
                         fq="-productID:ABC",
                         gather="productID",
                         count(*)))))

此範例建立在先前的「計算購物籃共現次數」範例之上。

請注意，最內層的 top 函數會選取與 productID ABC 共現頻率最高的 50 個產品。這會提供 50 個候選推薦項目。
然後 scoreNodes 函數會根據每個節點的 TF*IDF 為候選項目分配分數。
最外層的 top 表達式會選取分數最高的節點。這是推薦項目。

在此範例中，我們將根據協同過濾為使用者推薦內容。此推薦是使用包含 userID 和 articleID 以及執行動作的記錄檔記錄來建立的。在此情境中，每個記錄檔記錄都可以視為圖形中的邊緣。userID 和 articleID 是節點，而動作是邊緣屬性，用於篩選遍歷。

以下是範例語法

top(n="5",
    sort="count(*) desc",
    nodes(logs,
          top(n="30",
              sort="count(*) desc",
              nodes(logs,
                    search(logs, q="userID:user1", fl="articleID", sort="articleID asc", fq="action:read", qt="/export"),
                    walk="articleID->articleID",
                    gather="userID",
                    fq="action:read",
                    maxDocFreq="10000",
                    count(*))),
              walk="node->userID",
              gather="articleID",
              fq="action:read",
              count(*)))

讓我們逐步分解上面的表達式。

第一個評估的表達式是最內層的 search 表達式。此表達式會在 logs 集合中搜尋符合 "user1" 的所有記錄。這是我們要為其建立推薦項目的使用者。

有一個篩選器會套用，只提取 "action:read" 的記錄。它會傳回找到的每個記錄的 articleID。換句話說，此表達式會傳回 "user1" 已閱讀的所有文章。
最內層的 nodes 表達式會對步驟 1 中傳回的 articleID 進行運算。它會取得找到的每個 articleID，並針對 articleID 欄位搜尋它們。

請注意，它會使用 maxDocFreq 參數來篩選掉在記錄檔中出現超過 10,000 次的文章，藉此跳過高頻率節點。它會收集使用者 ID 並彙總每個使用者的計數。此步驟會找到已閱讀與 "user1" 相同文章的使用者，並計算他們已閱讀的相同文章數量。
最內層的 top 表達式會對步驟 2 中發出的使用者進行排名。它將發出與 user1 的閱讀清單重疊最多的前 30 個使用者。
最外層的 nodes 表達式會收集步驟 3 中發出的使用者的閱讀清單。它會計算收集的 articleID。

步驟 1 中選取的任何文章（user1 閱讀清單）都不會因為週期偵測而在此步驟中出現。因此，此步驟會傳回與 "user1" 閱讀習慣最相似的使用者已閱讀但 "user1" 尚未閱讀的文章。它也會計算此使用者群組中每篇文章被閱讀的次數。
最外層的 top 表達式會取得步驟 4 中發出的前幾篇文章。這是推薦項目。

蛋白質途徑遍歷

近年來，科學家越來越能夠合理地設計針對變異蛋白質（稱為致癌基因）的藥物，這些蛋白質是一些癌症的成因。蛋白質通常透過多種蛋白質之間的長鏈化學相互作用（稱為途徑）發揮作用，而且雖然途徑中的致癌基因可能沒有相應的藥物，但途徑中的另一種蛋白質可能有。在記錄蛋白質相互作用和藥物的蛋白質集合上進行圖形遍歷可能會產生可能的候選項目。（感謝 NCBI 的 Lewis Geer 提供此範例）。

以下範例說明蛋白質途徑遍歷

nodes(proteins,
      nodes(proteins,
            walk="NRAS->name",
            gather="interacts"),
      walk="node->name",
      gather="drug")

讓我們仔細分析一下這個遍歷的確切作用。

最內層的 nodes 表達式會在 proteins 集合中遍歷。它會找到圖形中蛋白質名稱為 "NRAS" 的所有邊緣。然後，它會收集 interacts 欄位中的蛋白質。這會收集所有與 "NRAS" 相互作用的蛋白質。
最外層的 nodes 表達式也會與 proteins 集合搭配使用。它會收集與步驟 1 中發出的蛋白質相對應的所有藥物。
使用這種逐步方法，您可以收集從根蛋白質開始的任意數量的相互作用途徑中的藥物。

匯出 GraphML 以支援圖形視覺化

在上述範例中，nodes 表達式會像任何其他串流表達式一樣傳送至 Solr 的 /stream 處理常式。此方法會以與其他串流表達式相同的 JSON 元組格式輸出節點，以便可以將其視為任何其他串流表達式。當您需要直接在元組上操作時，可以使用 /stream 處理常式，例如在上述建議使用案例中。

還有其他涉及圖形視覺化的圖形遍歷使用案例。Solr 透過引入 /graph 要求處理常式來支援這些使用案例，該處理常式會採用 nodes 表達式並以 GraphML 輸出結果。

GraphML 是一種 XML 格式，受到圖形視覺化工具（例如 Gephi）的支援，Gephi 是一種用於統計分析和視覺化圖形的複雜開放原始碼工具。使用 nodes 表達式，可以將較大圖形的部分匯出為 GraphML，然後匯入到 Gephi 等工具中。

以 GraphML 匯出圖形時，有幾件事需要注意

/graph 處理常式可以匯出圖形中的節點和邊緣。預設情況下，它只會匯出節點。若要匯出邊緣，您必須在 nodes 表達式中設定 trackTraversal="true"。
/graph 處理常式目前接受任意複雜的串流表達式，其中包含 nodes 表達式。如果串流表達式不包含 nodes 表達式，/graph 處理常式將無法正確輸出 GraphML。
/graph 處理常式目前接受每個要求一個任意複雜、巢狀的 nodes 表達式。這表示您無法傳入聯結或交叉來自多個 nodes 表達式的節點集的串流表達式。/graph 處理常式支援單個 nodes 表達式內的任何巢狀層級。/stream 處理常式支援聯結和交叉節點集，但 /graph 處理常式目前不支援。

GraphML 要求範例

curl --data-urlencode 'expr=nodes(enron_emails,
                                  nodes(enron_emails,
                                        walk="kayne.coulter@enron.com->from",
                                        trackTraversal="true",
                                        gather="to"),
                                  walk="node->from",
                                  scatter="leaves,branches",
                                  trackTraversal="true",
                                  gather="to")' https://127.0.0.1:8983/solr/enron_emails/graph

GraphML 輸出範例

<graphml xmlns="http://graphml.graphdrawing.org/xmlns"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
<graph id="G" edgedefault="directed">
     <node id="kayne.coulter@enron.com">
           <data key="field">node</data>
           <data key="level">0</data>
           <data key="count(*)">0.0</data>
     </node>
     <node id="don.baughman@enron.com">
           <data key="field">to</data>
           <data key="level">1</data>
           <data key="count(*)">1.0</data>
     </node>
     <edge id="1"  source="kayne.coulter@enron.com"  target="don.baughman@enron.com"/>
     <node id="john.kinser@enron.com">
           <data key="field">to</data>
           <data key="level">1</data>
           <data key="count(*)">1.0</data>
    </node>
    <edge id="2"  source="kayne.coulter@enron.com"  target="john.kinser@enron.com"/>
    <node id="jay.wills@enron.com">
          <data key="field">to</data>
          <data key="level">1</data>
          <data key="count(*)">1.0</data>
    </node>
    <edge id="3"  source="kayne.coulter@enron.com"  target="jay.wills@enron.com"/>
</graph></graphml>