A Zipf-skew heuristic for choosing a data structure, plus a probability-mass-partitioned trie.
Now on PyPI: pip install swpl · pypi.org/project/swpl · GitHub
Status: working hypothesis, not peer-reviewed. Earlier versions of this README and the two manuscript drafts described SWPL as a theorem, called the ζ-Trie optimal, and reported a 0.88 figure as if it were a comparison-model lower bound. Those claims are not supported and have been withdrawn. Read
paper/CLAIM_STATUS.mdbefore citing anything here.python scripts/check_claims.pyreproduces every number in that note and fails CI if the overclaims come back.
Under Zipf(α) access, probability mass concentrates on a small hot set. The Riemann ζ series converges for α > 1 and diverges for α ≤ 1, so the size of the set needed to cover (1−δ) of accesses behaves very differently on the two sides of α = 1:
| α | ζ(α) | Hot set | Structure that tends to work well |
|---|---|---|---|
| α ≤ 1 | diverges | Θ(n) — all keys are "hot" | Static B-tree / hash |
| α > 1 | finite | Θ(δ^{-1/(α−1)}) | Skew-aware / adaptive |
| w ≥ 0.5 | — | — | LSM / write-optimised |
recommend() turns an estimated α and a write ratio into a suggested structure.
This is an empirical selection heuristic. The table is a design intuition,
not a proved phase diagram, and "dominates" is not a theorem here.
ProbZetaTrie partitions each node's key subspace into b groups of equal
cumulative probability mass (not equal rank count). Under Zipf(α > 1), hot
keys land in tiny buckets at shallow depth.
Measured on n = 8192, b = 8, α = 1.5:
| depth | keys | probability mass |
|---|---|---|
| 0 | 2 keys (0.02%) | 52.3% |
| 1 | 11 (0.1%) | 27.6% |
| 2+ | rest | 20.1% |
expected_depth() returns 0.8819778174160245. That number counts node
levels traversed in an 8-ary tree (0 = root only), not key comparisons.
Choosing one of 8 children needs up to 7 key comparisons (3 ideal binary
comparisons); the implementation uses bisect on a rank-indexed array and
assumes the access distribution is known. It is therefore not comparable to
the ~13 comparisons of a static comparison-based B-tree, and no 15× speedup
is measured or claimed.
from swpl import ProbZetaTrie
zt = ProbZetaTrie(list(range(8192)), b=8, alpha=1.5)
zt.expected_depth() # 0.882 node levels- No lower bound. The manuscript's "information-theoretic lower bound" uses an
invalid step (
min_{k∈H_δ} cost(k) ≥ log_b|H_δ|is false for unbalanced trees — this structure is itself a counterexample). At these parameters the claimed bound evaluates to1.7693, larger than the measured0.8820. - No optimality, no sharp phase transition, no proof. See
paper/CLAIM_STATUS.mdfor all six issues, including the two different ζ-Trie definitions across the manuscripts and theM_90formula bug that made the "bound is tight" claim look plausible. - No peer review and no independent reproduction.
The natural comparison-tree scale is the Shannon entropy H(p)/log₂ b
(1.485 at these parameters); a proper theorem would need an entropy lower
bound, an explicit per-level comparison cost, and a matching upper bound.
pip install swplThe analysis path (import swpl, recommend, estimate_alpha, the tries)
needs only the Python standard library. matplotlib/numpy are pulled in
only by swpl plot via the optional extra pip install swpl[plot].
from swpl import recommend, estimate_alpha, analyze_workload
rec = recommend(alpha=1.4, write_ratio=0.1, ordered=True)
print(rec["winner"]) # "Adaptive tree (splay / working-set tree)"
print(rec["reason"])
from pathlib import Path
lines = Path("access.log").read_text().splitlines()
result = analyze_workload(lines, ordered=True)
print(f"Estimated α: {result['estimated_alpha']}")
print(f"Recommended: {result['recommendation']['winner']}")swpl analyze access.log
swpl recommend --alpha 1.5 --ordered
swpl plot| Field | Value |
|---|---|
Repository version (pyproject.toml, __version__) |
0.1.1 |
| PyPI release | 0.1.0, 2026-09-04, "Development Status :: 3 - Alpha" |
| Canonical repository | https://github.com/ZhangYangyi03/swpl |
The PyPI 0.1.0 page still carries the older "optimal ζ-Trie" description and a
legacy canonical URL (github.com/yz1571/swpl). Correcting that requires a new
release published with the maintainer's PyPI credentials — an external action
that a commit cannot perform. Until then, the PyPI artefact and this repository
describe different versions.
Two numerical bugs were fixed in 0.1.1 and are pinned by tests:
zeta_partial the n>1e4 branch computed ζ(α) minus a tail, which is not
ζ_n(α) — 81% low at α=1.01. Now a direct sum plus an
Euler–Maclaurin tail: exact for n≤1e6, ~1e-8 relative at n=1e7.
estimate_alpha the score equation had the wrong sign and returned
α≈0.11 for a true α=1.3. Now bisection on the monotone
E_α[log r]; recovers 1.30±0.02 from synthetic data.
A third bug was fixed in the same series: benchmark() used log(n) where the
hot-set lemma needs ζ_n(α), disagreeing with hot_set_size() by 15× and
manufacturing a "tight bound". A regression test now pins the two together and
data/prob_zeta_benchmark.json has been regenerated.
python -m pytest -q # 14 tests, standard library + pytest only
python scripts/check_claims.py # recompute the claim-status numbers and guard wordingCI runs the tests on Ubuntu and Windows for Python 3.11 and 3.13, checks that
the analysis path imports with nothing installed, runs a CLI smoke test, and
asserts paper/claim_checks.json is byte-for-byte current.
swpl/
├── pyproject.toml # Build config
├── LICENSE # MIT
├── README.md
├── data/ # Experimental data (regenerated with the M_90 fix)
├── scripts/
│ └── check_claims.py # Reproducible claim-status numbers + wording guard
├── paper/
│ ├── CLAIM_STATUS.md # Authoritative statement of what is / is not established
│ ├── claim_checks.json # Generated evidence (CI asserts it is current)
│ ├── swpl_kbs.tex # Manuscript DRAFT — banner points to CLAIM_STATUS.md
│ ├── swpl_proof.tex # Proof DRAFT — banner points to CLAIM_STATUS.md
│ └── cover_letter.md # DRAFT, NOT SENT
└── swpl/
├── __init__.py
├── cli.py # CLI interface
├── recommend.py # Zipf-skew heuristics + MLE α estimation
├── zeta_trie.py # ProbZetaTrie + RankZetaTrie + benchmark
└── plot.py # Phase diagram / hot-set / crossover plots
If you use the code, cite the repository as a software artefact:
@misc{zhang2026swpl,
title = {SWPL: a Zipf-skew heuristic for data structure selection},
author = {Zhang, Yangyi},
year = {2026},
note = {Working hypothesis; not peer-reviewed. See paper/CLAIM_STATUS.md},
howpublished = {\url{https://github.com/ZhangYangyi03/swpl}}
}