Where the data came from, what was rebuilt, and how it was checked.

The data is the City of Melbourne's Census of Land Use and Employment (CLUE) 2018, business establishments, published under CC BY 4.0. I use the copy supplied in the COMP20003 2020 test kit, kept unchanged in coursework/testing-files/: 19,117 records at 4,181 distinct locations, in five insertion orders, plus five random subsets used only for parity tests.

The site serves one derived file, /data/clue2018.json, written by scripts/build_web_data.py. Nothing is filtered or corrected; the file only re-encodes the records and the five orders so the browser can rebuild exactly the trees the C program builds. The data card lists its composition and known issues (two coordinate precisions, 3,144 vacant-space records, a 2018 snapshot).

The 2020 results shown on the site (the saved output result/test1.txt and my comparison counts in result1.csv and result2.csv) are reproduced as recorded. Nothing added in 2026 changes them.

A 2-d tree keyed on (longitude, latitude): depth 0 splits on x, depth 1 on y, alternating; strictly smaller keys go left; businesses at the same location share one node, in file order. The nearest search descends towards the query, then crosses a split line only if it is closer than the best distance so far. Distances are Euclidean in raw degrees. One comparison is one node whose key is compared with the query.

The original C source is lost. The rebuild in coursework/rebuild-2026 follows the surviving evidence, and DR-001 sorts each choice into pinned down, consistent but unproven, and unrecoverable (the 2020 counting rule). DR-002 covers ties and the output format, and DR-003 the balanced build used by the benchmark. The TypeScript port in web/src/lib/ follows the C code line by line and powers every page.

The C programs were run over all 10 files of the test kit with 4 query sets (40 runs, compiled with Apple clang version 21.0.0 (clang-2100.3.34.2)). The TypeScript port must print the same comparison count for every query and an output file with the same SHA-256. The test suite fails on any mismatch, so every deployed build has matched all of them.

The experiment recomputes the 2020 question live in the browser with one seeded set of 2,000 queries. The benchmark adds the uncertainty (DR-004):

• 10 seeded query sets of 300 queries (seeds 101 to 110), near businesses and uniform over the city, each answered by all five trees.
• Medians and means with 95% percentile bootstrap intervals (2,000 resamples, seed 20003); the per-set medians show the spread across query sets.
• Paired comparisons with median-first on the same queries: mean difference and ratio of means (paired bootstrap), the queries each tree wins and the ties, the share of untied queries median-first wins (Wilson interval), and an exact sign test with the side it favours. Effect sizes come first.
• The same queries on 20 seeded shuffles, so that no claim about shuffled trees rests on the kit's single shuffled file; these intervals resample both the shuffles and the queries.
• 20 seeded shuffles to show the distribution the kit's random file came from, next to the random-BST expectation 2(1 + 1/n)H_n − 4.
• Growth over n = 125, 250, 500, 1,000, 2,000, 4,181 for shuffled, balanced and sorted builds, with intervals that resample the seeds (queries on one tree are not independent), and fits against log₂ n and against a power of n.

The result that did not flatter the balanced tree is reported as prominently as the ones that did: for queries spread uniformly over the city, the kit's shuffled files have a lower mean than median-first, because median-first has the heavier tail, although median-first is cheaper on more individual queries. Over 20 seeded shuffles that difference disappears: the kit's file is a favourable draw.

The optional AI explanation has its own design (DR-006): 20 fixed searches (explain-eval-v2, seed 2026), four kinds of search on each insertion order, graded mechanically against the trace. The harness reports the share fully grounded with a Wilson interval, the median latency with a bootstrap interval, and compares two runs on the same cases: the paired difference with Newcombe's score interval, which does not collapse when the runs agree on every case, and an exact McNemar test. Failures that are not the model's, such as a rate limit, are kept out of every denominator, and so are calls logged with an older prompt.

AI is optional on this site. Every page, the explorer, the experiment and the benchmark work without it. One feature uses a language model: “Explain this search” in the explorer, which asks a model to walk through a finished search (DR-005, and the model card). The evaluation harness runs the same prompt over twenty fixed searches, so a model's grounding rate comes with an interval and two models can be compared case by case (DR-006).

What AI does

Writes a plain-language walkthrough of one search, citing its step numbers, from the search trace. A rule-based summary is always shown first, without AI.

What AI never does

Build or search the tree, count comparisons, produce any number in the experiment or benchmark, or change the 2020 results. All of those are deterministic code.

Data sent

Only the facts of the finished search: insertion order, tree size, the query point, the counts, up to 150 steps, and up to five public trading names at the answer, with the system prompt (explain-v1). Not the place name you searched for, and never your key. The panel shows the full payload before you send it.

Where it goes

Directly from your browser to the provider you choose, with your own key: Anthropic (Claude Haiku 4.5 by default, or Claude Sonnet 5.5) or OpenAI (gpt-5-mini by default, editable). The key stays in your browser (this tab only, unless you choose to remember it). No code on this site sends it anywhere except the provider's API, and none of this site's server routes, such as the place-search proxy, accept or log it.

Checks

The answer must fit a JSON schema, and its claimed numbers (comparisons, skipped locations, pruned subtrees, the answer's step) and every cited step are checked against the trace. The result is shown with the answer. Over the evaluation set, the share of fully grounded answers gets a Wilson interval, and two runs are compared with a Newcombe interval for the paired difference and an exact McNemar test. The site publishes no scores of its own: runs happen in your browser, with your key.

Human in the loop

Every AI output is labelled “AI-generated”. You accept, edit or reject it, and that decision is stored with the call in the AI audit log in your browser, which you can review and export as JSON or CSV.

Governance

These practices are informed by the Australian Government's policy for the responsible use of AI in government (DTA), the transparency principles of the EU AI Act and the NIST AI Risk Management Framework. They are not a claim of compliance with any of them.

• The test kit's files are the files my 2020 program read, and result/test1.txt was produced from CLUEdata2018_original.csv (its record order matches that file exactly).
• Distances in raw degrees, as the assignment worked in coordinate units. The surviving outputs cannot distinguish this from metres (DR-001).
• A shuffled 2-d tree behaves like a random binary search tree, which is what the reference curve on the benchmark assumes. Tied keys break this slightly.
• Synthetic queries stand in for real ones: near a business (within about 50 m) or uniform over the city.

• The 2020 comparison counts cannot be reproduced; the rebuild counts differently, and only one 2020 finding (sorted by x was the most expensive order) carries over.
• Stage 2 is inferred from counts alone. No Stage 2 output survived.
• Parity is with my C rebuild, not with the 2020 binary. It shows the port and the rebuild agree, not that either matches the lost code beyond the saved output.
• The cost intervals for the five kit files cover the choice of queries only; the shuffle comparison covers shuffles and queries; the shape and growth intervals cover shuffles. None cover other data or other machines, and comparison counts are not running time.
• Only the AI explanation's agreement with the trace is measured, case by case and over the twenty searches of the evaluation set. Whether the prose explains well is left to the reader's decision on each call, and I have published no evaluation results (there is no budget for API calls).

• Keep source and build outputs outside the repository from day one, so a deleted repository is not fatal.
• Print the counting rule next to every count, so saved outputs explain themselves.
• Use real query logs for the benchmark, and extend the growth curve beyond one census.
• With a budget, run the evaluation set on several models, twice each, publish the runs, and rate the prose against a rubric by two people independently.

Each record states the decision first, the options I considered, why, what happened (including the weak numbers) and what I would change. Past records are never edited; a new record supersedes an old one.

1. DR-001Accepteddecided 2026-10-09

   Rebuild the lost program from its surviving outputs, and label what is certain and what is inferred

   Rebuild the program in C99 from the evidence, test the rebuild against every surviving output that it should reproduce, and say plainly which design choices the evidence pins down and which ones I inferred. The rebuild lives in coursework/rebuild-2026/, apart from the original files, and the site calls it a rebuild everywhere.

2. DR-002Accepteddecided 2026-10-09

   Handle ties the way the evidence allows, and match the 2020 output byte for byte

   Settle each tie with the simplest rule that the saved output allows, and reproduce that output's format byte for byte.

3. DR-003Accepteddecided 2026-10-10

   Build balanced trees by recursive lower medians, through the ordinary insert

   Build a balanced tree with a deterministic recursive median, and insert the points in that order through the same KdTree.insert every other tree uses (web/src/lib/balanced.ts).

4. DR-004Accepteddecided 2026-10-10

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

   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.

5. DR-005Accepteddecided 2026-10-10

   Optional AI explanations with the visitor's own key, grounded on the search trace and checked against it

   Add an optional "Explain this search" panel to the explorer.

6. DR-006Accepteddecided 2026-10-10

   Evaluate the AI explanations on a fixed, seeded set of searches, run with the visitor's own key

   Add an evaluation harness at /ai-eval that runs the explorer's prompt over a fixed set of twenty searches with the visitor's own key, and reports what comes back with intervals.