A Data Structure Supporting Exclusion Persistence Range Search

We present a new type of query on spatiotemporal data, termed ”exclusion persistence”. When bulk updates are made to stored spatial data, all previous versions remain accessible. A query returns the most recently observed data intersecting the query region, while permitting the exclusion of any subset of previous versions in areas where data overlaps. We propose several solutions to this new problem defined on a set of N points. For an axis-aligned rectangular exclusion persistence query, we give a 2-dimensional linear-space data structure that, af-ter m updates, answers the query in O( m