Skip to content
K-d Tree Explorer, home
All decision records

DR-004Accepteddecided 2026-10-10

Report search cost with uncertainty, from repeated seeded query sets and paired comparisons

docs/decisions/DR-004-benchmark-evaluation-design.md

Context

The 2020 experiment compared five insertion orders on 13 query points, one file per order, with no measure of spread. The revival's /experiment page added 2,000 queries from one seed and reported means and percentiles, still without intervals. Two things were missing: how much the numbers would move with a different set of queries, and whether a difference between two orders is larger than that movement. The kit's single "random" file has the same problem: it is one draw from all the random orders it could have been.

Decision

Report every cost and shape with its uncertainty, from fixed and displayed seeds, and compare orders on the same queries. The benchmark (web/src/lib/benchmark.ts, rendered at /benchmark) is computed at build time:

  • Cost per query. Ten query sets (seeds 101 to 110) of 300 queries each, in two distributions: near a business (a random location moved up to 0.0005° in x and y) and uniform over the city's bounding box. Every query is answered by all five kit trees.
  • Uncertainty. Medians and means with 95% percentile bootstrap intervals (2,000 resamples of the 3,000 queries, seed 20003). All statistics for one distribution use the same resamples. The per-set medians are shown as the spread across query sets.
  • Comparisons. Each order against median-first on the same queries: the mean paired difference and the ratio of means, with paired bootstrap intervals; the queries each tree won and the ties; the share of untied queries where median-first is cheaper, with a Wilson interval; and an exact sign test on the untied pairs, with the side it favours. Effect sizes come first, and p-values are secondary.
  • More than one shuffle. The kit's two shuffled files are single draws, so the same 3,000 queries per distribution also run on twenty seeded shuffles of the locations (seeds 1 to 20), each built by insertion as the kit's files are, and each is compared with median-first. The intervals resample both the shuffles and the queries (a pigeonhole bootstrap), and the share of shuffles cheaper than median-first gets a Wilson interval.
  • Shape. Twenty seeded shuffles of the 4,181 locations, to place the kit's random file in the distribution it came from, next to the expected mean depth of a random binary search tree, 2(1 + 1/n)Hₙ − 4.
  • Growth. Random subsets of n = 125 to 4,181 locations (the first n of each shuffle) built three ways (shuffled, balanced by DR-003, sorted by x) and searched by one fixed set of 200 queries. Intervals resample the 20 seeds, because queries on the same tree are not independent. The mean cost is fitted against log₂ n and, for contrast, against a power of n.

Options considered

  1. Keep single-seed means. Rejected. It hides whether a difference between orders is real.
  2. Report p-values only. Rejected. With 3,000 paired queries almost any difference is "significant", so the size of the difference is what matters.
  3. Wall-clock timing. Rejected for now. Timing in a browser or on a shared build machine is noisy and depends on the machine; comparison counts are what the assignment asked about and are exactly reproducible.
  4. Let the kit's shuffled files stand for shuffled trees. Rejected. Each file is one draw, and a claim about "shuffled trees" needs the spread across shuffles.
  5. Seeded queries, bootstrap intervals, paired comparisons and seeded shuffles. Chosen.

Why

Bootstrap intervals need no distributional assumptions, and comparison counts are skewed whole numbers, so a normal approximation would be poor. Pairing removes the variation between queries from the comparison of orders, which is most of the variation. Seeds make every number reproducible by anyone who runs the tests.

What happened

  • For queries near a business, median-first is the cheapest order: median 17 comparisons (95% CI 16 to 17), mean 18.2 (18.0 to 18.4). Sorted by x needs 4.17 times as many on average (95% CI 4.09 to 4.25), and median-first is cheaper on 2,945 of the 3,000 queries, or 98.5% of the untied ones (98.0% to 98.8%).
  • Near a business, all 20 seeded shuffles cost more than median-first, by 5.5 comparisons per query on average (95% CI 5.2 to 5.9). Their means range from 22.6 to 24.9, against 18.2.
  • The weak spot, and how far it goes. For queries spread uniformly over the city, the kit's random file has the lower mean: it needs 2.5 fewer comparisons per query than median-first (95% CI 1.9 to 3.0 fewer; ratio of means 0.93, 0.92 to 0.95). The difference sits in the tail, where median-first's 90th percentile is 83 comparisons against 65. Query by query, median-first still wins more often: it is cheaper on 1,513 queries, dearer on 1,322 and tied on 165, which is 53.4% of the untied queries (51.5% to 55.2%; sign test p < 0.001 in median-first's favour). The shuffled-and-sorted file shows the same split (2.0 fewer comparisons on average, but median-first wins 1,534 queries to 1,363).
  • The kit's random file is a favourable draw. Over the 20 seeded shuffles, 12 of 20 are cheaper than median-first for uniform queries (95% CI 38.7% to 78.1%), their means range from 30.35 to 39.47 against 35.77, and the average difference is −0.8 comparisons per query (95% CI −2.0 to +0.5). The data do not show that shuffled trees are cheaper for uniform queries. The first version of this benchmark said they were, from the two kit files alone; the shuffle comparison was added after review, and the claim was withdrawn. A likely reason that median-first has a heavy tail at all, which I have not tested, is that balancing by the number of locations draws split lines through dense blocks and leaves large empty cells, and queries in parkland or on the river pay for it.
  • Medians of whole numbers give coarse intervals (for example 17, 95% CI 16 to 17), and six have zero width: the shuffled-and-sorted file near businesses (23 to 23) and five of the growth medians. Two growth rows have no sampling at all: at n = 4,181 every seed uses all the locations, the balanced and sorted-by-x builds give the same tree for every seed, and the page prints them without an interval. The means and paired differences carry more information, which is why both are shown.
  • The kit's random file has mean depth 13.16, at the 10th percentile of the 20 shuffles (13.02 to 14.87). The shuffles average 13.76 (95% CI 13.55 to 13.99), which contains the random-BST expectation of 13.84.
  • Shuffled trees deepen by 1.37 levels per doubling of n (95% CI 1.35 to 1.39), against 1.37 from the random-BST formula over the same sizes. Their cost grows by 1.89 comparisons per doubling (1.83 to 1.95), and balanced trees by 1.31 (1.28 to 1.33). Sorted-by-x trees fit a power law better than a logarithm: cost grows roughly like n^0.33 (95% CI 0.32 to 0.34).
  • Over sizes from 125 to 4,181, a logarithm and a small power (n^0.13 to n^0.15) fit the shuffled and balanced curves almost equally well (R² 0.9997 and 0.994). The data support "slow, roughly logarithmic growth", not a proof of O(log n).
  • Sign-test p-values are below 0.001 for every comparison except one (shuffled-and-sorted file against median-first, uniform queries, p = 0.002). They mostly add little beyond the intervals, except where they disagree with the mean, as in the weak spot above: there they show which tree wins more often, while the mean shows which is cheaper on average.

What I'd change

Report wins, ties and losses from the start, and never let one shuffled file stand for all shuffled trees. Draw queries from real usage (for example, where people search on the explorer) rather than from two synthetic distributions, and extend the growth curve beyond the 4,181 locations of one census with synthetic points, so the log-versus-power question has more range to work with. I would also add wall-clock timings on a dedicated machine, as a second measure next to the counts.