Metadata-Version: 2.4
Name: sqsketch
Version: 0.2.0
Summary: Fixed-size, abundance-preserving sketches of count profiles over unbounded alphabets
Author: Abderrahmane Sghairi
License: MIT License
        
        Copyright (c) 2026 Abderrahmane Sghairi
        
        Permission is hereby granted, free of charge, to any person obtaining a copy
        of this software and associated documentation files (the "Software"), to deal
        in the Software without restriction, including without limitation the rights
        to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
        copies of the Software, and to permit persons to whom the Software is
        furnished to do so, subject to the following conditions:
        
        The above copyright notice and this permission notice shall be included in all
        copies or substantial portions of the Software.
        
        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
        IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
        FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
        AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
        LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
        OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
        SOFTWARE.
        
Project-URL: Homepage, https://github.com/riscoss63/sqsketch
Project-URL: Paper, https://github.com/riscoss63/sqsketch/tree/main/paper
Project-URL: DOI, https://doi.org/10.5281/zenodo.22214969
Keywords: sketching,Bhattacharyya,Hellinger,random projection,hyperdimensional computing,vector symbolic architectures
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.21
Requires-Dist: scipy>=1.7
Provides-Extra: experiments
Requires-Dist: scikit-learn>=1.0; extra == "experiments"
Requires-Dist: torch>=2.0; extra == "experiments"
Requires-Dist: transformers>=4.30; extra == "experiments"
Provides-Extra: dev
Requires-Dist: pytest>=7.0; extra == "dev"
Dynamic: license-file

# sqsketch

[![DOI](https://zenodo.org/badge/DOI/10.5281/zenodo.22214969.svg)](https://doi.org/10.5281/zenodo.22214969)
[![tests](https://github.com/riscoss63/sqsketch/actions/workflows/ci.yml/badge.svg)](https://github.com/riscoss63/sqsketch/actions/workflows/ci.yml)
[![licence: MIT](https://img.shields.io/badge/licence-MIT-blue.svg)](LICENSE)

**Compare two probability or count profiles from a fixed number of bytes, however large the
alphabet.**

```python
from sqsketch import Sketch

a = Sketch.from_dict({"apple": 12, "pear": 3, "quince": 1})
b = Sketch.from_dense(probability_vector, D=1024)

a.similarity(b)            # Bhattacharyya coefficient
a.hellinger(b)             # Hellinger distance
a.confidence_interval(b)   # computed from the two sketches alone, without the profiles
a.kl_lower_bound(b)        # certified: the KL divergence is at least this
a.merge(b)                 # a sketch of the pooled profile
```

Each sketch is `D` numbers. No vocabulary, no codebook, no inverted index; encoding is one
pass over the items. The accuracy depends on `D` alone — the number of *possible* items never
enters the error, so the same width serves an alphabet of a thousand or of 4³¹.

```bash
pip install -e .          # numpy and scipy, nothing else
pytest                    # 26 tests, one per claim in the paper, ~18 s
```

## Should you use it? One number decides

The thing you are already doing — keeping the `k` heaviest items and lumping the rest into
one bucket — is the competitor. Top-`k` logprobs, frequent-item tables, truncated term
vectors are all this. What truncation cannot represent is the mass it throws away, so
measure that:

```python
from sqsketch.baselines import tail_mass
tail_mass(your_profiles, k)      # mass outside the top k, at your byte budget
```

| tail mass at your budget | verdict |
|--------------------------|---------|
| below ≈ 0.10 | keep the top `k` — simpler, and more accurate |
| 0.15 – 0.4 | sketch wins, by 1.4× to 4× |
| above 0.7 | sketch wins, by 4× to 7× |

The *effective support* `1/Σp²` is **not** the predictor: across the sweep that produced this
table it ranged from 4 to 800 000 without changing the verdict. Measured on real data, the
criterion called 14 of 14 cases correctly:

| domain | alphabet | tail mass | outcome |
|--------|---------:|----------:|---------|
| 21-mer abundance profiles (10 NCBI genomes) | 1 432 940 | 0.992 | sketch, 6.7× |
| USDT transfer counts per address (live chain) | 27 049 | 0.589 | sketch, 10× |
| personalised PageRank, 200 000-node graph | 200 000 | 0.502 | sketch, 2.1× |
| GPT-2 output aggregated over a corpus | 50 257 | 0.412 | sketch, 6.3× |
| GPT-2 next token, one position | 50 257 | 0.105 | truncation |
| USDT transfer *value* per address | 27 049 | 0.037 | truncation |
| document term counts | 45 969 | 0.039 | tie |
| binned returns, trade sizes (Binance) | 400 / 300 | 0.000 | truncation, exactly |

Value-weighted flows are dominated by a handful of addresses; activity counts are spread
over tens of thousands. Same data, opposite verdicts — which is why the criterion is worth
measuring rather than guessing.

## What it will not do

- **Exact top-1 retrieval among near-identical neighbours.** Accuracy is governed by the gap
  between the true nearest neighbour and the runner-up, against the noise floor `√(2/D)`.
  On a real text corpus that gap is ~0.03 and recall@1 falls apart; recall@10 stays at 97 %.
  Use `Index.search` as a candidate generator and rerank the shortlist exactly.
- **Sampling-noise-dominated histograms.** If each profile is a small sample from a much
  larger alphabet, Hellinger between two empirical histograms mostly measures sample
  overlap. That is a property of the statistic, not of the sketch, but it rules the approach
  out there.
- **Upper-bounding the KL divergence.** `kl_lower_bound` is one-sided by construction: it
  certifies that two profiles are far apart, never that they are close.
- **Forecasting anything.** It measures a distance between two distributions. It has no
  notion of time, and confers no predictive edge.

## Accuracy

Unbiased at every width, with variance `σ²/D` where `σ² = 1 + BC² − 2⟨Q,P⟩ < 2` for every
pair and every alphabet size, so the standard error is at most `√(2/D)`:

| `D` | bytes (float32) | standard error at most |
|-----|-----------------|------------------------|
| 256 | 1 KB | 0.088 |
| 1024 | 4 KB | 0.044 |
| 4096 | 16 KB | 0.022 |

`confidence_interval` is asymptotic in `D` and under-covers below `D ≈ 256`; above that it is
valid and deliberately conservative, since its width is calibrated for the raw inner product
while `similarity` returns the lower-variance self-normalised cosine.

## How to audit this

Every claim is checked twice: as a unit test, and as an end-to-end reproduction.

```bash
pytest                                    # 26 tests, one per proposition
cd experiments
python reproduce.py > outputs/reproduce_output.txt        # 14 sections
python survey.py   > outputs/survey_output.txt            # the decision criterion
python verify.py                                          # 36 checks, 5 batteries
```

`verify.py` is the part worth knowing about. Beyond checking the mathematics, **battery 3
extracts every experimental number printed in the paper and requires it to appear in a
script's output.** The manuscript this work supersedes reported a correlation from one
column of a table as though it came from another; that class of error is invisible to
proofreading, so it is checked mechanically. It currently matches 142 of 142.

## Repository

```
sqsketch/        the library: core.py, hashing.py, baselines.py
                 adapters: genomics.py (k-mers, FASTA, MinHash baselines), llm.py
tests/           one test per proposition
paper/           square_root_sketch.tex, and the superseded v1 draft it retracts
experiments/     everything that produces a number in the paper, plus verify.py
data/            reference genomes, downloaded on demand (not in git)
```

## The paper

*Norm-Invariance in Vector-Symbolic Encodings of Probability Distributions* — why the square
root is the only exponent that makes the error independent of the alphabet size, what the
vector's magnitude therefore cannot encode, and how to read one bit.

It carries three explicit retractions of earlier claims, an eight-item limitations section,
and 20 references each checked against the publisher record. The variance formula it uses is
**not new** and is attributed throughout to Li, Hastie and Church (2006).

## Citing

```bibtex
@software{sghairi2026sqsketch,
  author  = {Sghairi, Abderrahmane},
  title   = {sqsketch: alphabet-independent sketches of discrete
             probability and count profiles},
  year    = {2026},
  version = {0.2.0},
  doi     = {10.5281/zenodo.22214969},
  url     = {https://github.com/riscoss63/sqsketch}
}
```

## Licence

MIT for the code. The Zenodo record is deposited under the same terms; note that the
manuscript in `paper/` is part of the same deposit.
