How does path indexing in B+ tree looks like?

Suppose, we want to search for (1)-[edgeA]-(2)-[edgeB]-(3) efficiently where (1), (2) and (3) are nodes and we have two edges connecting between them [edgeA], [edgeB].

I came across this work: Path indexing for efficient path query processing in graph databases — Eindhoven University of Technology research portal

This is extremely clear and detailed work but, I feel confused regarding an indexing in B+ tree. It feels like for k-path indexing where k=2, we have to index 5 (k+k+1) dimension data in B+tree where the sequences of the entities has to be also taken into consideration. How does the b+ tree work in such indexing? What is the key and value of each node in the b+ tree?

Thank you Neo4j community for being extremely supportive.

Keep in mind, even though the paper does cite and query against Neo4j, Neo4j does not currently implement path indexing, and as such the contents and design described in the paper are unfamiliar to Neo4j users and employees.

The questions you're asking seem specific to the implementation as presented in the paper, and as such reaching out to the paper authors or looking for some place where the paper has been discussed is more likely to yield answers.

While we are looking at ways to improve pathfinding, including by supplementary indexes, I don't believe we are looking at that particular paper for reference.

That is an interesting paper. And it does feel like we should have a subcategory here for discussion of graph theory and graph/index implementation, even if tangential or unrelated to Neo4j.

1 Like