Skip to main content

Module join

Module join 

Source
Expand description

Binary ASP-Join for 2-hop traversals.

Implements the factorized join contract from spec Section 13.3.

Algorithm:

  1. Collect probe-side (src node’s direct neighbors).
  2. Build a Roaring semijoin filter from the probe keys.
  3. For build-side, scan mid-node neighbors — only those admitted by filter.
  4. Build hash state: {mid_node_slot → Vec<dst_slot>}.
  5. Re-probe: for each src neighbor, look up in hash to get fof set.
  6. Propagate multiplicity without materializing the full Cartesian product.

Structs§

AspJoin
Binary ASP-Join: 2-hop traversal over a CSR graph.
TwoHopChunk
A factorized 2-hop chunk: each group is one (mid, [fof…]) set.
TwoHopGroup
One group in a factorized 2-hop chunk.