Speaker: Mikkel Thorup
<br>
<br>
Title: Space Efficient Dynamic Stabbing with Fast Queries
<br>
<br>
In dynamic stabbing, we operate on a dynamic set of intervals. A
stabbing query asks for an interval containing a given point. This
basic problem encodes problems such as method look-up in object
oriented programming languages and classification in IP firewalls. For
such application, very fast, say constant, query time is extremely
important, small space is very important, and fast updates are good
but the least important. Previous solutions traded space and update
time for fast queries.  We show here that space needs not be
sacrificed. We get the same trade-off between update time and query
time but using only the space necessary for locating a query point
among the interval end-points.  All our bounds are optimal or
near-optimal.