Skip to content
ZhangYangyi03Public

About

SWPL (Skew-Phase Law) for Zipf-distributed keys: a phase transition at alpha=1 and the zeta-Trie dictionary

Topics

Resources

Contributing

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

9 Commits

Folders and files

Repository files navigation

SWPL — Skew-Phase Law (working hypothesis)

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

ci license: MIT

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.md before citing anything here. python scripts/check_claims.py reproduces every number in that note and fails CI if the overclaims come back.


The idea (as a conjecture, not a law)

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.

The ζ-Trie

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

What is not established

  • 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 to 1.7693, larger than the measured 0.8820.
  • No optimality, no sharp phase transition, no proof. See paper/CLAIM_STATUS.md for all six issues, including the two different ζ-Trie definitions across the manuscripts and the M_90 formula 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.


Install

pip install swpl

The 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].

Quick start

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']}")

CLI

swpl analyze access.log
swpl recommend --alpha 1.5 --ordered
swpl plot

Release status

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.

Tests and CI

python -m pytest -q              # 14 tests, standard library + pytest only
python scripts/check_claims.py   # recompute the claim-status numbers and guard wording

CI 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.

Repository structure

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

Citation

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}}
}

About

SWPL (Skew-Phase Law) for Zipf-distributed keys: a phase transition at alpha=1 and the zeta-Trie dictionary

Topics

Resources

Contributing

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages