Pith Number

pith:RXPXUD66

pith:2025:RXPXUD666STXIJ4W2GQPQLV5IW

not attested not anchored not stored refs pending

Bonsai: Compiling Queries to Pruned Tree Traversals

Alexander J Root, Andrew Adams, Christophe Gyurgyik, Fredrik Kjolstad, Jonathan Ragan-Kelley, Kayvon Fatahalian, Purvi Goel

A compiler derives pruning conditions for tree queries via symbolic interval analysis to generate traversals matching expert code and outperforming linear scans for complex predicates.

arxiv:2511.15000 v3 · 2025-11-19 · cs.PL · cs.DB

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{RXPXUD666STXIJ4W2GQPQLV5IW}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

The generated traversals match the behavior of expert-written code that implements query-specific traversals, and can asymptotically outperform the linear scans and nested-loop joins that existing systems fall back to when hand-written cases do not apply.

C2weakest assumption

That symbolic interval analysis extended with new rules for geometric predicates (intersection, containment) can derive correct and complete pruning conditions for the supported class of queries without missing cases or introducing unsound simplifications.

C3one line summary

Bonsai compiles queries to pruned tree traversals by deriving pruning conditions with extended symbolic interval analysis and fusing compound queries into single traversals.

Formal links

1 machine-checked theorem link

Cited by

1 paper in Pith

Decoupling Data Layouts from Bounding Volume Hierarchies

Receipt and verification

First computed	2026-06-05T01:14:30.958691Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

8ddf7a0fdef4a7742796d1a0f82ebd4597c6f577e53fcdbbcc5716af6c4db1df

Aliases

arxiv: 2511.15000 · arxiv_version: 2511.15000v3 · doi: 10.48550/arxiv.2511.15000 · pith_short_12: RXPXUD666STX · pith_short_16: RXPXUD666STXIJ4W · pith_short_8: RXPXUD66

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/RXPXUD666STXIJ4W2GQPQLV5IW \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 8ddf7a0fdef4a7742796d1a0f82ebd4597c6f577e53fcdbbcc5716af6c4db1df

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "47123306a9446d2a3505f76ca04bdab3a48404165b1e4a6e50dae02207787ca1",
    "cross_cats_sorted": [
      "cs.DB"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.PL",
    "submitted_at": "2025-11-19T00:50:20Z",
    "title_canon_sha256": "a952657ba002d8af8aceba8f01a66ec6a8000a6035daa834d0dd4a7de2452a20"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2511.15000",
    "kind": "arxiv",
    "version": 3
  }
}