Update-efficient data structures for dynamic IP router tables Thomas Ottmann, Institute for Computer Science University of Freiburg Germany     March 24th, 2006 at 11:00 am, Seminar Room 1.24 Abstract:   We propose two data structures, min-augmented range trees and priority search pennants, which efficiently support all the required operations for updatable IP router tables, and argue that both structures are better suited for the one-dimensional IP lookup problem than priority search trees (PST) used in a previous solution. It is possible to maintain both structures in time O(1) after a rotation, while PST with n elements may require Ω(log n) steps for a single rotation. Therefore, the proposed structures can be balanced using a larger class of rebalancing schemes than for PST. Both structures are also of interest independent of the IP lookup problem and may be used as attractive implementations of priority search queues in other contexts as well. Dr. Lyndon While