Motivation
Evaluate a succinct grid index (wavelet matrix / k2-tree) for the triple store to cut the index memory and enable persistence, while still supporting the range/rank/select operations LTJ needs.
Current state (feasibility)
TripleIndex (src/runtime/ltj/triple_index.rs) holds six plain sorted Vec<IndexEntry> orderings, ~172 MiB in RAM at SF0.1 (measured), currently memory-only (rebuilt every open, ~670 ms). Persisting it would add ~12% to the .gdb.- A wavelet matrix over the triples represents them compactly (succinct) and answers the
leapfrog intersection primitives (seek/next on sorted candidate lists) via rank/select, potentially replacing all six arrays with one compact structure.
Scope (evaluation first)
- Prototype a wavelet-matrix index for
(src, label, tgt) triples.
- Compare RAM and query latency vs the six-array version on LDBC + micro-benchmarks.
- Assess persistence feasibility (succinct structures serialize well).
Overlaps #compact-CLTJ (the paper's CLTJ is built on wavelet trees). Research/prototype; large if adopted.
Motivation
Evaluate a succinct grid index (wavelet matrix / k2-tree) for the triple store to cut the index memory and enable persistence, while still supporting the range/rank/select operations LTJ needs.
Current state (feasibility)
TripleIndex(src/runtime/ltj/triple_index.rs) holds six plain sortedVec<IndexEntry>orderings, ~172 MiB in RAM at SF0.1 (measured), currently memory-only (rebuilt every open, ~670 ms). Persisting it would add ~12% to the.gdb.leapfrogintersection primitives (seek/next on sorted candidate lists) via rank/select, potentially replacing all six arrays with one compact structure.Scope (evaluation first)
(src, label, tgt)triples.Overlaps #compact-CLTJ (the paper's CLTJ is built on wavelet trees). Research/prototype; large if adopted.