Benchmark · with uncertainty
How much does a query cost, and how sure can we be?
The experiment answers the 2020 question with one set of queries. Here the same trees answer ten seeded query sets, every number comes with a 95% interval, every order is compared with the balanced tree on the same queries, and the growth of the cost is checked against log₂ n.
Design (fixed seeds, computed at build time)
- Query sets
- 10 sets of 300 queries (seeds 101 to 110) in two distributions, answered by all five trees
- Intervals
- 95% percentile bootstrap, 2,000 resamples (seed 20003); Wilson for proportions
- Shuffles
- 20 seeded shuffles of the 4,181 locations (seeds 1 to 20)
- Growth
- n = 125, 250, 500, 1,000, 2,000, 4,181; 200 fixed queries (seed 4181); intervals resample the 20 seeds
- Counting
- One comparison per node whose key is compared with the query (the rebuild's rule)
Why it is designed this way, and what came out weak, is in DR-004. Every number on this page is computed from the seeded benchmark at build time, and the numbers quoted in DR-004 and the README are checked against it by a unit test.
Cost per query
3,000 queries per tree and distribution. Near businesses, median-first is cheapest (median 17, mean 18.2) and sorted by x dearest. Spread uniformly over the city, the kit's two shuffled files have lower means than median-first, but they are favourable draws: over 20 seeded shuffles there is no clear difference (below). Sorted by x has a long tail (one query needed 2,338 comparisons).
Near a business
A random business location moved up to 0.0005° (about 50 m) in x and y: where people ask.
- Original
median 27.0 (27.0 to 28.0)mean 29.5 (29.1 to 29.9)
- Sorted by x
median 67.5 (66.0 to 69.0)mean 75.9 (74.4 to 77.4)
- Median first
median 17.0 (16.0 to 17.0)mean 18.2 (18.0 to 18.4)
- Random
median 21.0 (21.0 to 22.0)mean 22.5 (22.2 to 22.7)
- Random, sorted
median 23.0 (23.0 to 23.0)mean 24.8 (24.5 to 25.1)
Anywhere in the city
Uniform over the data's bounding box, including parkland, rail yards and the river.
- Original
median 35.0 (34.0 to 36.0)mean 53.8 (51.7 to 56.0)
- Sorted by x
median 53.0 (50.0 to 56.0)mean 150.6 (139.1 to 162.3)
- Median first
median 24.0 (23.0 to 24.0)mean 35.8 (34.6 to 37.0)
- Random
median 25.0 (24.0 to 25.0)mean 33.3 (32.4 to 34.2)
- Random, sorted
median 26.0 (25.0 to 26.0)mean 33.8 (32.9 to 34.7)
Each order against median-first, query by query
Every query is answered by both trees, so the comparison is paired: the extra comparisons per query, the ratio of the means, and how many queries each tree won. Near businesses, sorted by x costs 4.17 times as much (4.09 to 4.25).
For queries anywhere in the city the two measures disagree, and the highlighted rows show both. The kit's random file needs 2.5 fewer comparisons per query on average (ratio 0.93), because median-first has the heavier tail (90th percentile 83 against 65). Yet median-first is cheaper on more queries: 1,513 against 1,322, with 165 ties, or 53.4% of the untied pairs (51.5% to 55.2%; sign test p < 0.001).
OriginalNear a business
- Extra per query
- +11.3 (+10.9 to +11.7)
- Ratio of means
- 1.62 (1.60 to 1.65)
- Median-first cheaper · tied · dearer
- 2,576 · 69 · 355
- Median-first cheaper, untied
- 87.9% (86.7% to 89.0%)
- Sign test
- p < 0.001, favours median-first
Sorted by xNear a business
- Extra per query
- +57.7 (+56.3 to +59.1)
- Ratio of means
- 4.17 (4.09 to 4.25)
- Median-first cheaper · tied · dearer
- 2,945 · 9 · 46
- Median-first cheaper, untied
- 98.5% (98.0% to 98.8%)
- Sign test
- p < 0.001, favours median-first
RandomNear a business
- Extra per query
- +4.3 (+4.0 to +4.5)
- Ratio of means
- 1.24 (1.22 to 1.25)
- Median-first cheaper · tied · dearer
- 2,142 · 164 · 694
- Median-first cheaper, untied
- 75.5% (73.9% to 77.1%)
- Sign test
- p < 0.001, favours median-first
Random, sortedNear a business
- Extra per query
- +6.6 (+6.3 to +6.9)
- Ratio of means
- 1.36 (1.34 to 1.38)
- Median-first cheaper · tied · dearer
- 2,334 · 89 · 577
- Median-first cheaper, untied
- 80.2% (78.7% to 81.6%)
- Sign test
- p < 0.001, favours median-first
OriginalAnywhere in the city
- Extra per query
- +18.0 (+16.5 to +19.7)
- Ratio of means
- 1.50 (1.46 to 1.55)
- Median-first cheaper · tied · dearer
- 2,156 · 59 · 785
- Median-first cheaper, untied
- 73.3% (71.7% to 74.9%)
- Sign test
- p < 0.001, favours median-first
Sorted by xAnywhere in the city
- Extra per query
- +114.8 (+103.4 to +126.4)
- Ratio of means
- 4.21 (3.88 to 4.54)
- Median-first cheaper · tied · dearer
- 2,314 · 26 · 660
- Median-first cheaper, untied
- 77.8% (76.3% to 79.3%)
- Sign test
- p < 0.001, favours median-first
RandomAnywhere in the citylower mean than median-first
- Extra per query
- −2.5 (−3.0 to −1.9)
- Ratio of means
- 0.93 (0.92 to 0.95)
- Median-first cheaper · tied · dearer
- 1,513 · 165 · 1,322
- Median-first cheaper, untied
- 53.4% (51.5% to 55.2%)
- Sign test
- p < 0.001, favours median-first
Random, sortedAnywhere in the citylower mean than median-first
- Extra per query
- −2.0 (−2.7 to −1.3)
- Ratio of means
- 0.94 (0.93 to 0.96)
- Median-first cheaper · tied · dearer
- 1,534 · 103 · 1,363
- Median-first cheaper, untied
- 53.0% (51.1% to 54.8%)
- Sign test
- p 0.002, favours median-first
| Order | Queries | Extra comparisons per query (95% CI) | Ratio of means (95% CI) | Median-first cheaper · tied · dearer | Median-first cheaper, untied (95% CI) | Sign test p (favours) |
|---|---|---|---|---|---|---|
| Original | Near a business | +11.3 (+10.9 to +11.7) | 1.62 (1.60 to 1.65) | 2,576 · 69 · 355 | 87.9% (86.7% to 89.0%) | < 0.001favours median-first |
| Sorted by x | Near a business | +57.7 (+56.3 to +59.1) | 4.17 (4.09 to 4.25) | 2,945 · 9 · 46 | 98.5% (98.0% to 98.8%) | < 0.001favours median-first |
| Random | Near a business | +4.3 (+4.0 to +4.5) | 1.24 (1.22 to 1.25) | 2,142 · 164 · 694 | 75.5% (73.9% to 77.1%) | < 0.001favours median-first |
| Random, sorted | Near a business | +6.6 (+6.3 to +6.9) | 1.36 (1.34 to 1.38) | 2,334 · 89 · 577 | 80.2% (78.7% to 81.6%) | < 0.001favours median-first |
| Original | Anywhere in the city | +18.0 (+16.5 to +19.7) | 1.50 (1.46 to 1.55) | 2,156 · 59 · 785 | 73.3% (71.7% to 74.9%) | < 0.001favours median-first |
| Sorted by x | Anywhere in the city | +114.8 (+103.4 to +126.4) | 4.21 (3.88 to 4.54) | 2,314 · 26 · 660 | 77.8% (76.3% to 79.3%) | < 0.001favours median-first |
| Random | Anywhere in the citylower mean | −2.5 (−3.0 to −1.9) | 0.93 (0.92 to 0.95) | 1,513 · 165 · 1,322 | 53.4% (51.5% to 55.2%) | < 0.001favours median-first |
| Random, sorted | Anywhere in the citylower mean | −2.0 (−2.7 to −1.3) | 0.94 (0.93 to 0.96) | 1,534 · 103 · 1,363 | 53.0% (51.1% to 54.8%) | 0.002favours median-first |
Positive differences and ratios above 1 mean the order costs more than median-first. The untied share and the sign test leave out tied queries and ask which tree is cheaper more often; the mean difference asks by how much on average. They can point different ways when one tree has the heavier tail, as in the highlighted rows. With 3,000 pairs almost every sign test is far below 0.001, so the size of the difference matters more than the p-value.
Twenty shuffles, not one file
The comparison above uses the kit's two shuffled files, which are single draws. Here the same 3,000 queries run on 20 seeded shuffles of the locations (seeds 1 to 20), each built by insertion as the kit's file was. Near businesses, every shuffle costs more than median-first, by 5.5 comparisons per query on average (95% CI 5.2 to 5.9). Anywhere in the city, 12 of 20 shuffles are cheaper and 8 dearer, and the average difference, −0.8 (−2.0 to +0.5), is not clearly different from zero. The kit's random file sits among the cheaper shuffles.
Near a business
Mean comparisons per query on each shuffle, against median-first on the same queries
- Shuffles cheaper than median-first
- 0 of 20 (0% to 16.1%)
- Difference from median-first
- +5.53 (+5.17 to +5.90)
- Shuffle means
- 22.58 to 24.93, against 18.19
Anywhere in the city
Mean comparisons per query on each shuffle, against median-first on the same queries
- Shuffles cheaper than median-first
- 12 of 20 (38.7% to 78.1%)
- Difference from median-first
- −0.77 (−1.99 to +0.45)
- Shuffle means
- 30.35 to 39.47, against 35.77
Intervals for the mean and the difference resample both the shuffles and the queries (a pigeonhole bootstrap, slightly conservative). Holding the queries fixed and resampling only the shuffles gives −1.9 to +0.4 for queries anywhere in the city, so most of the uncertainty comes from the shuffle. The share of shuffles cheaper has a Wilson interval.
Tree shape: the kit's random file is one draw
Shuffling the same 4,181 locations with 20 seeds shows where the kit's two shuffled files sit. Their mean depth (13.16 and 14.09) falls inside the range of the shuffles (13.02 to 14.87); the random file is at the 10th percentile. The shuffles average 13.76 (95% CI 13.55 to 13.99), which contains the random-BST expectation 2(1 + 1/n)Hn − 4 = 13.84.
Mean node depth
Levels (height)
| Tree | Levels | Mean depth | |
|---|---|---|---|
| Original | 52 | 17.49 | One file, one tree: no sampling, so no interval |
| Sorted by x | 66 | 36.23 | One file, one tree: no sampling, so no interval |
| Median first | 13 | 10.04 | One file, one tree: no sampling, so no interval |
| Random | 25 | 13.16 | One file, one tree: no sampling, so no interval |
| Random, sorted | 27 | 14.09 | One file, one tree: no sampling, so no interval |
| Balanced build (DR-003) | 13 | 10.04 | Same depth profile as the kit's median file; 2,382 of 4,181 locations have the same parent |
Empirical growth against log2 n
Random subsets of n locations (the first n of each seeded shuffle), built three ways and searched by the same 200 queries. Shuffled trees deepen by 1.37 levels per doubling of n (95% CI 1.35 to 1.39), as the random-BST formula predicts (1.37). Sorted-by-x trees grow like a power of n instead (exponent 0.33, 0.32 to 0.34).
Fits to the mean comparisons per query at each n (averaged over seeds). Intervals resample the 20 seeds.
Shuffled order
- Comparisons per doubling
- 1.89 (1.83 to 1.95), R² 0.9997
- Exponent k (cost ∝ nᵏ)
- 0.148 (0.142 to 0.154), R² 0.9941
- Depth per doubling
- 1.37 (1.35 to 1.39)
Balanced (median build)
- Comparisons per doubling
- 1.31 (1.28 to 1.33), R² 0.9997
- Exponent k (cost ∝ nᵏ)
- 0.126 (0.123 to 0.129), R² 0.9940
- Depth per doubling
- 0.99 (0.99 to 0.99)
Sorted by x
- Comparisons per doubling
- 9.92 (9.74 to 10.12), R² 0.9620
- Exponent k (cost ∝ nᵏ)
- 0.332 (0.322 to 0.341), R² 0.9990
- Depth per doubling
- 4.12 (3.97 to 4.27)
Random-BST formula
Expected mean depth 2(1 + 1/n)Hn − 4, fitted over the same sizes: depth per doubling 1.37
| Build | Comparisons per doubling (log₂ fit) | R², log₂ fit | Exponent k (cost ∝ nᵏ) | R², power fit | Depth per doubling |
|---|---|---|---|---|---|
| Shuffled order | 1.89 (1.83 to 1.95) | 0.9997 | 0.148 (0.142 to 0.154) | 0.9941 | 1.37 (1.35 to 1.39) |
| Balanced (median build) | 1.31 (1.28 to 1.33) | 0.9997 | 0.126 (0.123 to 0.129) | 0.9940 | 0.99 (0.99 to 0.99) |
| Sorted by x | 9.92 (9.74 to 10.12) | 0.9620 | 0.332 (0.322 to 0.341) | 0.9990 | 4.12 (3.97 to 4.27) |
| Random-BST formula | Expected mean depth 2(1 + 1/n)Hn − 4, fitted over the same sizes | 1.37 | |||
Median comparisons per query at every n (with 95% intervals)
| n | Shuffled order | Balanced (median build) | Sorted by x |
|---|---|---|---|
| 125 | 13.0 (13.0 to 13.0)* | 11.0 (11.0 to 11.0)* | 22.0 (21.0 to 23.0) |
| 250 | 15.0 (14.0 to 15.0) | 12.0 (12.0 to 12.0)* | 27.0 (26.0 to 29.0) |
| 500 | 17.0 (16.0 to 17.0) | 13.0 (13.0 to 13.0)* | 34.0 (32.0 to 35.0) |
| 1,000 | 18.0 (18.0 to 19.0) | 14.0 (14.0 to 14.0)* | 42.0 (41.0 to 43.0) |
| 2,000 | 20.0 (20.0 to 21.0) | 15.0 (15.0 to 16.0) | 51.0 (50.0 to 53.0) |
| 4,181 | 22.0 (22.0 to 22.5) | 17.0 (same for every seed) | 66.5 (same for every seed) |
At n = 4,181 every seed uses all the locations, and the balanced and sorted-by-x builds do not depend on the order they arrive in, so all 20 seeds give the same tree and the same costs: there is no sampling to put an interval on. * A zero-width interval: every resample of the seeds gave the same whole-number median. It shows that the median is coarse, not that there is no uncertainty.
Read with care
What this does not show
- The queries are synthetic. Real questions about Melbourne would cluster in the CBD, which would favour the balanced tree more than the uniform queries do.
- Over n = 125 to 4,181, a logarithm and a small power of n fit the shuffled and balanced curves almost equally well. The data support slow, roughly logarithmic growth; they do not prove O(log n).
- The cost intervals for the five kit files cover the choice of queries only; the twenty-shuffle comparison covers shuffles and queries; the shape and growth intervals cover shuffles. None cover other cities, other data or the 2020 counting rule, which is lost.
- Counts are not time. A comparison in a deep, cache-unfriendly tree costs more than one in a shallow one.
More on the method and its assumptions on Methods.