Metraipolis › archive › dc_5d66fa69776e

Dual-Number Associative Arrays for One-Pass Provenance and Sensitivity — arXiv:2611.09589

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.09589
License (as archived)
CC0-1.0
Archived
2026-11-09T22:47:13.565Z
SHA-256 of the archived text
fc2832913c01cc92480f687c4a180cf72883f62f679662d4131fad82895fef09
Stable URL of this page
https://metraipolis.com/documento/dc_5d66fa69776e

How to cite

Dual-Number Associative Arrays for One-Pass Provenance and Sensitivity — arXiv:2611.09589 — arXiv (en), https://arxiv.org/abs/2611.09589 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5d66fa69776e (Metraipolis archive dc_5d66fa69776e, sha256 fc2832913c01cc92480f687c4a180cf72883f62f679662d4131fad82895fef09)
BibTeX
@misc{dc5d66fa69776e,
  title = {Dual-Number Associative Arrays for One-Pass Provenance and Sensitivity — arXiv:2611.09589},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.09589},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5d66fa69776e; sha256 fc2832913c01cc92480f687c4a180cf72883f62f679662d4131fad82895fef09},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09589. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Associative arrays and GraphBLAS express sparse computations as matrix operations over a chosen semiring, but the result normally contains only the ordinary value. We define a dual-number extension $D_k(S)=S\ltimes S^k$ that carries this value together with $k$ independent auxiliary channels in the same computation. We prove that the construction is a split square-zero extension of any commutative semiring. Over min-plus, the auxiliary value is the weight of the shortest walk constrained to use the corresponding edge, excluding the weight of that edge. This gives an exact shortest-path membership test for that edge, although ties return the union of the edges on all optimal paths. We implement the min-plus construction using sparse \texttt{python-graphblas} operations, with a fixpoint test that checks the value and auxiliary components together. We validate the implementation across 18,692 checks, including 2,825 tied target pairs. On random graphs with 100,000 vertices and 32 seed edges, the dual method is $3.39\times$ faster than the sequential algorithm but $1.50\times$ slower than a min-plus-specific batched method. This difference is largely explained by the dual method requiring $1.55\times$ as many sweeps. Thus, the main contribution is a general algebraic approach with competitive sparse performance, rather than information that specialized min-plus algorithms cannot already compute.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.09589 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-09T22:40:29.877Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).