Graph Traversal

We’ll start with the most basic syntax and slowly build up more complexity. The most basic syntax for gatherNodes is:

Let’s break down this simple expression.

The first parameter, emails, is the collection being traversed. The second parameter, walk, maps a hard-coded node ID ("johndoe@apache.org") to a field in the index (from). This will return all the edges in the index that have johndoe@apache.org in the from field.

The gather parameter tells the function to gather the values in the `to `field. The values that are gathered are the node IDs emitted by the function.

In the example above the nodes emitted will be all of the people that "johndoe@apache.org" has emailed.

The walk parameter also accepts a list of root node IDs:

The gatherNodes function above finds all the edges with "johndoe@apache.org" or "janesmith@apache.org" in the from field and gathers the to field.

Like all Streaming Expressions, you can execute a gatherNodes expression by sending it to the /stream handler. For example:

The output of this expression would look like this:

All of the tuples returned have the node field. The node field contains the node IDs gathered by the function. The collection, field, and level of the traversal are also included in the output.

Notice that the level is "1" for each tuple in the example. The root nodes are level 0 (in the example above, the root nodes are "johndoe@apache.org, janesmith@apache.org") By default the gatherNodes function emits only the *leaf nodes* of the traversal, which is the outer-most node set. To emit the root nodes you can specify the scatter parameter:

The scatter parameter controls whether to emit the branches with the leaves. The root nodes are considered "branches" because they are not the outer-most level of the traversal.

When scattering both branches and leaves the output would like this:

Now the level 0 root node is included in the output.

gatherNodes also supports aggregations. For example:

The expression above finds the edges with "johndoe@apache.org" or "janesmith@apache.org" in the from field and gathers the values from the to field. It also aggregates the count for each node ID gathered.

A gathered node could have a count of 2 if both "johndoe@apache.org" and "janesmith@apache.org" have emailed the same person. Node sets contain a unique set of nodes, so the same person won’t appear twice in the node set, but the count will reflect that it appeared twice during the traversal.

Edges are uniqued as part of the traversal so the count will not reflect the number of times "johndoe@apache.org" emailed the same person. For example, personA might have emailed personB 100 times. These edges would get uniqued and only be counted once. But if person personC also emailed personB this would increment the count for personB.

The aggregation functions supported are count(*), sum(field), min(field), max(field), and avg(field). The fields being aggregated should be present in the edges collected during the traversal. Later examples (below) will show aggregations can be a powerful tool for providing recommendations and limiting the scope of traversals.

The gatherNodes function can be nested to traverse deeper into the graph. For example:

In the example above the outer gatherNodes function operates on the node set collected from the inner gatherNodes function.

Notice that the inner gatherNodes function behaves exactly as the examples already discussed. But the walk parameter of the outer gatherNodes function behaves differently.

In the outer gatherNodes function the walk parameter works with tuples coming from an internal streaming expression. In this scenario the walk parameter maps the node field to the from field. Remember that the node IDs collected from the inner gatherNodes expression are placed in the node field.

Put more simply, the inner expression gathers all the people that "johndoe@apache.org" has emailed. We can call this group the "friends of johndoe@apache.org". The outer expression gathers all the people that the "friends of johndoe@apache.org" have emailed. This is a basic friends-of-friends traversal.

This construct of nesting gatherNodes functions is the basic technique for doing a controlled traversal through the graph.

The gatherNodes function performs cycle detection across the entire traversal. This ensures that nodes that have already been visited are not traversed again. Cycle detection is important for both limiting the size of traversals and gathering accurate aggregations. Without cycle detection the size of the traversal could grow exponentially with each hop in the traversal. With cycle detection only new nodes encountered are traversed.

Cycle detection does not cross collection boundaries. This is because internally the collection name is part of the node ID. For example the node ID "johndoe@apache.org", is really emails/johndoe@apache.org. When traversing to another collection "johndoe@apache.org" will be traversed.

Each level in the traversal can be filtered with a filter query. For example:

In the example above only emails that match the filter query will be included in the traversal. Any Solr query can be included here. So you can do fun things like geospatial queries, apply any of the available query parsers, or even write custom query parsers to limit the traversal.

Any streaming expression can be used to provide the root nodes for a traversal. For example:

The example above provides the root nodes through a search expression. You can also provide arbitrarily complex, nested streaming expressions with joins, etc., to specify the root nodes.

Notice that the walk parameter maps a field from the tuples generated by the inner stream. In this case it maps the to field from the inner stream to the from field.

It’s often desirable to skip traversing high frequency nodes in the graph. This is similar in nature to a search term stop list. The best way to describe this is through an example use case.

Let’s say that you want to recommend content for a user based on a collaborative filter. Below is one approach for a simple collaborative filter:

Look closely at step 2. In large graphs, step 2 can lead to a very large traversal. This is because userA may have viewed content that has been viewed by millions of other people. We may want to skip these high frequency nodes for two reasons:

The gatherNodes function has the maxDocFreq param to allow for filtering out high frequency nodes. The sample code below shows steps 1 and 2 of the recommendation:

In the example above, the inner search expression searches the logs collection and returning all the articles viewed by "user1". The outer gatherNodes expression takes all the articles emitted from the inner search expression and finds all the records in the logs collection for those articles. It then gathers and aggregates the users that have read the articles. The maxDocFreq parameter limits the articles returned to those that appear in no more then 10,000 log records (per shard). This guards against returning articles that have been viewed by millions of users.

By default the gatherNodes function only tracks enough information to do cycle detection. This provides enough information to output the nodes and aggregations in the graph.

For some use cases, such as graph visualization, we also need to output the edges. Setting trackTraversal="true" tells gatherNodes to track the connections between nodes, so the edges can be constructed. When trackTraversal is enabled a new ancestors property will appear with each node. The ancestors property contains a list of node IDs that pointed to the node.

Below is a sample gatherNodes expression with trackTraversal set to true:

Nested gatherNodes functions can operate on different SolrCloud collections. This allow traversals to "walk" from one collection to another to gather nodes. Cycle detection does not cross collection boundaries, so nodes collected in one collection will be traversed in a different collection. This was done deliberately to support cross-collection traversals. Note that the output from a cross-collection traversal will likely contain duplicate nodes with different collection attributes.

Below is a sample gatherNodes expression that traverses from the "emails" collection to the "logs" collection:

The example above finds all people who sent emails with a body that contains "solr rocks". It then finds all the people these people have emailed. Then it traverses to the logs collection and gathers all the content IDs that these people have edited.

The gatherNodes function can act as both a stream source and a stream decorator. The connection with the wider stream expression library provides tremendous power and flexibility when performing graph traversals. Here is an example of using the streaming expression library to intersect two friend networks:

The example above gathers two separate friend networks, one rooted with "johndoe@apache.org" and another rooted with "janedoe@apache.org". The friend networks are then sorted by the node field, and intersected. The resulting node set will be the intersection of the two friend networks.

In the examples above, the gatherNodes expression was sent to Solr’s /stream handler like any other streaming expression. This approach outputs the nodes in the same JSON tuple format as other streaming expressions so that it can be treated like any other streaming expression. You can use the /stream handler when you need to operate directly on the tuples, such as in the recommendation use cases above.

There are other graph traversal use cases that involve graph visualization. Solr supports these use cases with the introduction of the /graph request handler, which takes a gatherNodes expression and outputs the results in GraphML.

GraphML is an XML format supported by graph visualization tools such as Gephi, which is a sophisticated open source tool for statistically analyzing and visualizing graphs. Using a gatherNodes expression, parts of a larger graph can be exported in GraphML and then imported into tools like Gephi.

There are a few things to keep mind when exporting a graph in GraphML: