Skip to content

Releases

HashFrontier v0.26.0 — Siegel 2004 Lemma 6 finite tensor-product on-demand adjacency 100 cloud measurements (not full construction)

Choose a tag to compare

@github-actions github-actions released this 29 Oct 09:33

HashFrontier v0.26.0 — Siegel 2004 Lemma 6 finite tensor graph mechanism

  • Implements Siegel Lemma 6 finite product adjacency from an already k-certified base graph without storing expanded-product edges permanently. Explicit expansion comparator shares exactly the same per-product-right-side random table.
  • 4,893,162 full finite unique-neighbor subset checks and exact small 2-bit joint-law tests; ASan/UBSan and 7/7 strict CSV-audit regression tests pass.
  • Independent cloud experiment: 100/100 paired rows (50 cases, 10 groups, five seeds), all checksums equal, Ubuntu 24.04, AMD EPYC 7763, GCC 13.3.
  • Representative u=6,d=3,p=3: stored edge payload only 36 vs 11,664 bytes; common right-side random table 13,824 bytes; timed median 60.0498 vs 15.4299 ns/op (factorized vs fully expanded).
  • Not the full Siegel high-independence explicit graph generator or its asymptotic constant-time/space bounds. Seeded SplitMix64 samples are not a proof of independence. No DMPP06 or STOC 2025 completed, no HF-Score.

HashFrontier v0.25.0 — Siegel 2004 Lemma 2.6 finite k-peelable XOR graph exact certificate and 40 genuine cloud trials (partial)

Choose a tag to compare

@github-actions github-actions released this 29 Oct 09:21

HashFrontier v0.25.0 — SIAM J. Computing 2004 Siegel Lemma 2.6 finite graph mechanism

  • Exact finite k-peelable neighbor graph certification and XOR of independent random right-side table cells (Siegel 2004, Lemma 2.6; cross-checked with Thorup FOCS 2013 §I.B).
  • 4,416,204 exact nonempty subset certificates; 130 exhaustive tiny-graph joint distribution checks; 1,683 additional invariants; ASan/UBSan passed.
  • Independent cloud benchmark run 40848770409: 40/40 raw rows, eight configurations × five seeds; GitHub Actions AMD EPYC 9V74, GCC 13.3.0.
  • 64-key examples: degree 3 → 2.22687 ns/eval and minimum 384 B adjacency; degree 4 → 2.56612 ns/eval and minimum 512 B adjacency; each includes a separate 1,024 B random-word table.
  • Not the full Siegel explicit construction, no sublinear adjacency storage, no large-universe k=n^Ω(1) proof; the benchmark uses pseudorandom test table data. Not full DMPP06 or STOC 2025 Partner Hashing. No HF-Score.

See docs/SIEGEL-2004-LEMMA2.6-FINITE-v0.25.0.md.

HashFrontier v0.24.0 — LATIN 2006 DMPP06 finite Transformation 4 300-case cloud paired verification (partial)

Choose a tag to compare

@github-actions github-actions released this 29 Oct 08:58

HashFrontier v0.24.0 — DMPP06 §2.2 Transformation 4 finite grouped permutations

  • Strictly paper-defined group-shared uniform random permutation of first-order buckets, plus exact inverse. Finite 16-bit scaling; no Siegel-family implementation or theorem claims.
  • 13,893,153 full-domain and grouping checks pass, ASan/UBSan and five CSV-audit unit tests pass.
  • Independent GitHub Actions cloud run 40845661999: 300 complete raw records, 240 with b<n, 60 configurations and five paired seeds, raw CSV/SVG/provenance archived.
  • AMD EPYC 7763, GCC 13.3.0. n=8192, b=1024, shuffled inputs: over-threshold keys 373→350, median hash latency 1.92206→4.36252 ns/key, metadata 1024→1536 bytes.
  • Correct scope: finite transformation mechanism only. DMPP06 Theorem 5, Siegel high-independence row shifts, full DMPP06 space guarantees and STOC 2025 Partner Hashing remain outstanding. No HF-Score.

See docs/STOC25-DMPP06-TRANSFORMATION4-v0.24.0.md.

HashFrontier v0.23.0 — LATIN 2006 DMPP06 finite GF256 k-wise row shifts and column field-affine real 240-run cloud verification

Choose a tag to compare

@github-actions github-actions released this 29 Oct 08:25

HashFrontier v0.23.0 — finite DMPP06 §2.2 GF256 polynomial and field-affine model

  • k-wise polynomial row shifts over GF(256) for finite k = 2, 8, 16, and independently seeded field-affine 2-independent column permutations.
  • Full 65,536-element permutation/inverse verification; exhaustive two-row polynomial pair independence; CTest and bounded ASan/UBSan passed.
  • GitHub Actions 40841729087: 240/240 genuine experimental records, 48 groups (5 seeds), strict audit, CSV, SVG and SHA-256. Cloud machine AMD EPYC 9V74.
  • Representative 4,096 shuffled keys, 1,024 buckets: v0.22 2.237 ns/hash and 1,024 B metadata; polynomial k=2/8/16 24.954 / 74.945 / 143.542 ns/hash and 770 / 776 / 784 B.
  • Not Siegel hashing, not DMPP06 Theorem 5, not full Partner Hashing; no HF-Score. The finite polynomial has O(k) evaluation.

Source/limits: docs/STOC25-DMPP06-GF256-v0.23.0.md.

HashFrontier v0.22.0 — LATIN 2006 DMPP06 Section 2.2 finite row shifts and reversible per-column permutations - 160 real cloud trials

Choose a tag to compare

@github-actions github-actions released this 29 Oct 07:55

HashFrontier v0.22.0 — DMPP06 Section 2.2 finite reversible column quotient hash

  • Implemented §2.2 Transformation 2 (per-row circular shifts) and Transformation 3 (independently seeded bijective per-column permutation, finite modular-affine substitute).
  • Verified 12,583,011 full-domain permutation and inverse checks; AddressSanitizer/UBSan pass.
  • Independent GitHub Actions run 40838246871: 160/160 measured configurations, 16 summaries, raw CSV/SVG/environment/source SHA-256 all preserved; AMD EPYC 7763 cloud VM, Ubuntu 24.04, GCC 13.3.0.
  • Ten-seed median collision-participating keys for 1,024 contiguous keys: 530.5 / 255 / 134.5 at 1,024 / 2,048 / 4,096 buckets.
  • NOT the paper's Siegel high-independence row-shift hash family or its field-based 2-universal per-column permutation. Theorem 5, succinct representation, cited 1990 high-performance dictionary, full DMPP06 and STOC 2025 Partner Hashing remain unimplemented. No HF-Score.

See docs/STOC25-DMPP06-COLUMN-v0.22.0.md for exact reproduction boundary.

HashFrontier v0.21.0 — LATIN 2006 DMPP06 real cloud 96-run finite three-tier routing with stable codes

Choose a tag to compare

@github-actions github-actions released this 29 Oct 07:31

HashFrontier v0.21.0 — DMPP06 three-tier finite cloud reproduction

  • LATIN 2006 DMPP06 Section 3: route insert/query/update/delete through first/second/third tiers; preserve stable disjoint codes; explicit no-space failure.
  • Third tier uses a standard-library map with free-code recycling; not the theoretical compact high-performance dictionary.
  • GitHub Actions Ubuntu 24.04, GCC 13.3.0, Intel Xeon Platinum 8573C virtual CPU: 96 genuine measurements, 32 fully audited parameter groups.
  • 115,200 randomized operations; 676,373 checks; 255,374 stable-code checks; AddressSanitizer and UndefinedBehaviorSanitizer passed.
  • Actual CSV, summaries, provenance SHA-256, environment, tests and SVG are included in release assets.
  • NOT complete DMPP06, NOT complete STOC25 Partner Hashing, no final HF-Score.

See docs/STOC25-DMPP06-THREE-LEVEL-v0.21.0.md for exact scope.

HashFrontier v0.20.0 — LATIN 2006 DMPP06 second-level multi-filter finite mechanism real cloud reproduction

Choose a tag to compare

@github-actions github-actions released this 28 Oct 04:12

HashFrontier v0.20.0 — DMPP06 §3.2 tile-filter reproduction

Faithfully modelled §3.2's finite multi-filter placement and stable tile identifiers using invertible affine finite permutations. Preserves explicit overflow to an unimplemented third level.

Actually verified: 298,141 randomized correctness/invariant checks; ASan/UBSan; strict CSV parser tests; independent GitHub Actions runner 40630812596 completed 72 real benchmark configurations with source, raw CSV, hashes, compiler/CPU environment, summary and generated SVG.

Key finite observation: 256 bins, 8192 attempts, 4 seeds; 16/32/64 base tiles show median overflow 16.4185% / 0.1709% / 0%. Do not combine cloud timings with other hardware or score as HF-Score.

Not implemented: DMPP06 §2.2 Theorem 5 full high-probability quotient family, original packed constant-time space representation, §3.2 third-level high-performance dictionary, complete dynamic retrieval, or full STOC25 Partner Hashing.

HashFrontier v0.19.0 — DMPP06 LATIN 2006 affine quotient and first-level filter cloud reproduction only

Choose a tag to compare

@github-actions github-actions released this 28 Oct 03:31

HashFrontier v0.19.0 — DMPP06 LATIN 2006 first-level dependency reproduction

This release continues the reproduction of STOC 2025 Optimal Non-Oblivious Open Addressing by tackling its cited DMPP06 retrieval dependency at source-section level.

Implemented: LATIN 2006 §2.1 finite GF(2^16) affine quotient permutation and inverse, and §3.1 first-level per-bucket filter using stable local hashcodes, free-code lists, explicit overflow, retrieval/update/deletion, plus exhaustive finite permutation checks.

Verified: 2,763,711 C++ randomized/invariant checks, 65,535 nonzero multiplicative coefficients passing inverse verification, ASan/UBSan locally, and 72/72 independent GitHub Actions cloud observations with 4-seed 18-group summary, genuine CSV/SVG, actual environment log and SHA-256 audit.

Key limitation: The full DMPP06 Theorem 5 high-probability quotient construction, multi-level filters and succinct implementation are NOT reproduced. This code uses an explicit standard-library map inside buckets and does not satisfy the space bound. It is NOT a complete DMPP06 retrieval data structure, and it is NOT the full STOC 2025 Partner Hashing. Overflow is marked as failure of this filter and must be delegated to later levels in a full implementation. No HF-Score.

Evidence: docs/STOC25-DMPP06-DEPENDENCY-v0.19.0.md, results/v0.19.0-dmpp06/{raw.csv,summary.csv,audit.json,environment.txt,sha256.txt,tests.log}, figures/v0.19.0-dmpp06-{hit,overflow}.svg.

HashFrontier v0.18.0 — Experimental XOR retrieval encoded in PartnerRAM; non-DMPP06 control, 18 real cloud tests

Choose a tag to compare

@github-actions github-actions released this 28 Oct 03:03

HashFrontier v0.18.0 — STOC 2025 PartnerRAM retrieval-value encoding diagnostic

  • Verified a finite 3-hash XOR retrieval control whose values are physically encoded in PartnerRAM swaps, without accessing the external key-to-word index for retrieval reads.
  • Cloud run: https://github.com/ZJY-HSBL/HashFrontier/actions/runs/40624353966. 18/18 real trials complete; randomized verification 403,660 checks / 5,600 update operations; ASan/UBSan passed.
  • Original CSV, actual environment, SHA-256 provenance, strict completeness audit and SVG plots are attached.
  • Not the DMPP06 dynamic succinct retrieval algorithm used in Bender, Kuszmaul and Zhou (STOC 2025). Active keys, logical slots and masks still use external memory. Every update triggers a whole-XOR-layout rebuild; no asymptotic O(1) or metadata-free claim. This is not a complete paper reproduction and must not enter HF-Score.

HashFrontier v0.17.0 — STOC 2025 Algorithm 5 finite atomic partner-slot reuse real cloud measurements

Choose a tag to compare

@github-actions github-actions released this 25 Oct 13:46

HashFrontier v0.17.0 — STOC25 Algorithm 5 finite transactional partner reuse

  • Reproduces prestate reads, two-pass decouple/recouple and atomic reject on oversubscribed partner bins. Preserves the old restricted planner for audit.
  • Verified 3,600 full-bin cross-swap updates and correctness/sanitizer checks.
  • Real GitHub cloud run 40199001986: all 54/54 batches of 1,500 attempts, 3 seeds per configuration; actual CSV and SVG archived with SHA256 and environment.
  • Cloud runner: AMD EPYC 9V45, Ubuntu 24.04, GCC 13.3.0. Across new planner configurations, 40,500/40,500 actual mutating batches committed; the disjoint predecessor commits zero actual mutating batches. Old versus new timings are NOT equivalent-work comparison.
  • Limitations: DMPP06 dynamic succinct retrieval, metadata-free Section 4 and resizing Section 5 are not implemented. This release is a tested paper-subroutine reproduction, not full Partner Hashing or formal L3 / HF-Score.