Benchmark: jsNetworkX big graph vs 2 smaller ones - lookup time --2

HTML Preparation code:

<script src='https://cdn.rawgit.com/fkling/JSNetworkX/master/jsnetworkx.js'></script>

Script Preparation code:

const graph_size = 100000;
var G_Both = new jsnx.DiGraph();
for (let i=0; i<graph_size-1; i++) {
  	// add regular graph data
    G_Both.addNode(i, {name: `${i}`})
	G_Both.addEdge(i, i+1); 
  	// add reverse index
    G_Both.addEdge(`${i}`, i)
}


// separate graphs for data and reverse lookup
var G_regularData = new jsnx.DiGraph();
for (let i=0; i<graph_size-1; i++) {
  	G_regularData.addNode(i, {name: `${i}`})
	G_regularData.addEdge(i, i+1);
}
var G_reverseLookup = new jsnx.Graph();
for (let i=0; i<graph_size-1; i++) {
    G_reverseLookup.addEdge(`${i}`, i)
}

Tests:

graph with local reverse index
G_Both.node.get(G_Both.successors('90000')[0]);
graph with separate reverse index
G_regularData.node.get(G_reverseLookup.neighbors('90000')[0]);
reverse lookup only - both
G_Both.successors('90000')
reverse lookup only - index
G_reverseLookup.neighbors('90000')

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
graph with local reverse index
graph with separate reverse index
reverse lookup only - both
reverse lookup only - index

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 28 days ago):

LLMs can make mistakes. Check important info.

Measuring the performance of different approaches for finding neighbors in graphs is an interesting benchmark.

**Benchmark Overview**

The provided JSON represents a microbenchmarking test case that compares the performance of three different approaches:

1.  **Local Reverse Index**: Using a local reverse index, which stores the reverse edges of each node separately.
2.  **Separate Reverse Index**: Storing both forward and reverse edges in separate graphs.
3.  **Both (Combined)**: Combining both approaches by storing both forward and reverse edges in a single graph.

**Approach Comparison**

### Local Reverse Index

This approach uses a single graph with a local reverse index, where each node stores its reverse edges separately. To find the neighbors of a node, the algorithm iterates over all nodes and checks if there is an edge from that node to the target node. This approach has a good cache locality and can be efficient for small to medium-sized graphs.

**Pros:**

*   Good cache locality
*   Efficient for small to medium-sized graphs

**Cons:**

*   May not scale well for large graphs due to increased memory usage
*   More complex implementation compared to other approaches

### Separate Reverse Index

This approach stores both forward and reverse edges in separate graphs. To find the neighbors of a node, the algorithm first retrieves the forward edges from the corresponding graph and then looks up the reverse edge in the reverse index graph.

**Pros:**

*   Scalable for large graphs
*   Simple implementation

**Cons:**

*   Lower cache locality due to frequent graph switching
*   May incur additional overhead when looking up reverse edges

### Both (Combined)

This approach combines both local and separate reverse indices. The algorithm first checks the combined index, which contains both forward and reverse edges of all nodes. If the target node is not found in the combined index, it falls back to using a local reverse index.

**Pros:**

*   Good balance between locality and scalability
*   Simple implementation

**Cons:**

*   May have higher memory usage compared to separate reverse index approach

**Library Usage (JSNetworkX)**

JSNetworkX is a JavaScript library for working with graphs. It provides a simple and efficient way to create, manipulate, and query graphs.

The provided benchmark uses the `jsnx.DiGraph` class to represent directed graphs and the `Graph` class to represent undirected graphs. The `successors`, `neighbors`, and `node.get()` methods are used to find neighbors of nodes and retrieve node data, respectively.

**Special JavaScript Features/Syntax**

This benchmark does not explicitly use any special JavaScript features or syntax.

**Alternatives**

Other approaches for finding neighbors in graphs include:

*   **Hash Tables**: Using hash tables to store graph edges can provide fast lookups.
*   **Tree Data Structures**: Utilizing tree data structures, such as binary search trees, to organize graph edges can improve lookup efficiency.
*   **Parallel Processing**: Employing parallel processing techniques to concurrently query multiple nodes or edges in a graph.

These alternatives may offer different trade-offs between performance, memory usage, and implementation complexity.

Latest run results:

Run details: (Test run date: 6 years ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/70.0.3521.0 Safari/537.36

Browser/OS: Chrome 70 on Mac OS X 10.13.6

View result in a separate tab

Test name	Executions per second
graph with local reverse index	489205.6 Ops/sec
graph with separate reverse index	488956.9 Ops/sec
reverse lookup only - both	546229.2 Ops/sec
reverse lookup only - index	534460.1 Ops/sec

Related benchmarks:

jsNetworkX big graph vs 2 smaller ones - lookup time --2 (version: 1)

Comparing performance of: graph with local reverse index vs graph with separate reverse index vs reverse lookup only - both vs reverse lookup only - index

Created: 6 years ago by: Registered User

Jump to the latest result

graph with local reverse index

graph with separate reverse index

reverse lookup only - both

reverse lookup only - index

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 28 days ago):