Skip to content

Run shortestPath from many sources with multi-source BFS #76

Open

Description

@prrao87

Problem

shortestPath runs one breadth-first search per source node (a source with one target searches from both ends; a source with several targets shares one forward search). A query that starts from many source nodes repeats traversals over the same parts of the graph.

Idea

Multi-source BFS runs many breadth-first searches over the CSR at once. Each search is a bit in a per-node bitset, so one pass over a neighbour list advances every search that has reached that node. DuckPGQ uses it for path-finding (CIDR 2023 paper, cited in lance-format/lance-graph#159).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions