Project: audit spatial counts, bounded successors, rebuilds, and filter membership

Acceptance trace

The five depot points include two at x 47. A rectangle [15,60) by [45,65) counts four; a narrow x [47,48) by y [60,65) counts one. Alert IDs 19, 29, 47, 61, 83, 103 live in universe 256. After removing 61, the successor of 47 is 83. Ascending case insertions trigger at least one scapegoat rebuild while preserving sorted membership. The XOR filter contains every alert ID from its build snapshot; nonmember positives are only candidates. Publish a new exact-index version and filter version together after an alert change.

Failure and cost review

Compare randomized rectangle counts with a direct scan, successors with a sorted set, scapegoat membership and subtree sizes with a Python set, and inserted filter keys with exact membership. Force a rectangle boundary point, remove a cluster's final vEB key, insert an out-of-universe ID, and exceed the filter's peel retry budget in a controlled construction test. Make the exact alert index advance while the old filter remains available; do not use a stale negative answer to exclude a newly added alert. Show rebuild cost and temporary allocation alongside query latency before adopting any of these static snapshots.

Common Mistakes

• Do not count a point on an excluded rectangle edge.
• Do not leave empty vEB clusters in the summary.
• Do not claim every scapegoat insertion is logarithmic worst-case.
• Do not treat a filter positive as exact or a stale filter negative as current.

Connected lessons

• Two-dimensional range trees: count a static rectangle
• Van Emde Boas trees: successor in a bounded integer universe
• Scapegoat trees: rebuild a deep insertion subtree
• Static XOR filters: peel a fingerprint membership index
• Projects
• Quizzes
• Data Structures