APR-Quad
Paul T. Stanton, Randal C. Burns · 2011
We present an update-efficient authenticated dictionary towards the goal of providing public verification of outsourced dynamic geospatial data consolidated from a dynamic set of contributing sources. We introduce an on-disk authenticated bucket-based PR-quadtree for point and range queries over multiple attributes with minimal tree realignment upon updates. Our design minimizes cryptographic proof overhead using large, block-aligned tree nodes for high fanout and incremental cumulative hashing to consolidate neighboring elements required for verifying completeness. We introduce block-dependent indexing to reduce cryptographic recalculations required upon updates. Collectively, our design decisions result in an authenticated dictionary capable of efficiently incorporating individual updates or entire pre-existing data sets. We validate our approach with simulated data sets derived from experiences managing the Mississippi River floods of May 2011.