Fully Retroactive Approximate Range and Nearest Neighbor Searching.

link: http://arxiv.org/abs/1109.0312
Abstract

We describe fully retroactive dynamic data structures for approximate range
reporting and approximate nearest neighbor reporting. We show how to maintain,
for any positive constant $d$, a set of $n$ points in $\R^d$ indexed by time
such that we can perform insertions or deletions at any point in the timeline
in $O(\log n)$ amortized time. We support, for any small constant $\epsilon>0$,
$(1+\epsilon)$-approximate range reporting queries at any point in the timeline
in $O(\log n + k)$ time, where $k$ is the output size. We also show how to
answer $(1+\epsilon)$-approximate nearest neighbor queries for any point in the
past or present in $O(\log n)$ time.