Using Persistence for Efficient Dynamic Orthogonal Range Reporting

maintains previous versions as update operations are performed to
it. The versions may only be queried (partial persistence) or even
updated (full persistence). In this talk I will present some applications
of persistence for internal and external memory dynamic data structures
that support different variants of orthogonal range reporting queries.

In particular, I will present dynamic data structures for internal memory that support
reporting the points that are not dominated by any other point within a
given 3-sided or 4-sided orthogonal range (orthogonal planar range maxima reporting).
The results improve upon previous work and are obtained by a novel
generic update technique that is based on partially persistent secondary
structures.

I will give an overview of how we obtain fully persistent $B$-trees
that are efficient in external memory. The result is a first attempt to
externalize efficiently the technique of Driscoll, Sarnak, Sleator, Tarjan [JCSS'89]
that obtain efficient fully persistent red-black trees for internal memory.