Space efficient dynamic stabbing with fast queries

Abstract

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.