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.

REFERENCES

• 1: Stephen Alstrup , Thore Husfeldt , Theis Rauhe, Marked Ancestor Problems, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.534, November 08-11, 1998
• 2: A. Andersson, Sublogarithmic searching without multiplications, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.655, October 23-25, 1995
• 3: A. Andersson, Faster deterministic sorting and searching in linear space, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.135, October 14-16, 1996
• 4: Arne A. Andersson , Mikkel Thorup, Tight(er) worst-case bounds on dynamic searching and priority queues, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.335-342, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335344]
• 5: A. Andersson and M. Thorup. Dynamic ordered sets with exponential search trees. Technical Report cs.DS/0210006, The Computing Research Repository (CoRR), 2002. http://arXiv.org/abs/cs.DS/0210006. Combined journal version of {3,4}.
• 6: Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem and related problems, Journal of Computer and System Sciences, v.65 n.1, p.38-72, August 2002 [doi>10.1006/jcss.2002.1822]
• 7: J. L. Bentley. Algorithms for Klee's rectangle problem. Technical report, Carnegie-Mellon University, 1977.
• 8: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 9: S. Deering and R. Hinden. Internet protocol, version 6 (IPv6), specification. Network Working Group, Request for Comments, http://search.ietf.org/rfc/rfc1883.txt, December 1995.
• 10: H. Edelsbrunner. Dynamic data structures for orthogonal intersection queries. Technical Report F59, Inst. Informationsverarb., Tech. Univ. Graz, 1980.
• 11: A. Feldmann and S. Muthukrishnan. Tradeoffs for packet classification. In Proc. IEEE INFOCOM, pages 1193--1202, 2000.
• 12: Paolo Ferragina , S. Muthukrishnan, Efficient Dynamic Method-Lookup for Object Oriented Languages (Extended Abstract), Proceedings of the Fourth Annual European Symposium on Algorithms, p.107-120, September 25-27, 1996
• 13: Paolo Ferragina , S. Muthukrishnan , Mark de Berg, Multi-method dispatching: a geometric approach with applications to string matching problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.483-491, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301378]
• 14: Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
• 15: Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
• 16: Torben Hagerup , Peter Bro Miltersen , Rasmus Pagh, Deterministic dictionaries, Journal of Algorithms, v.41 n.1, p.69-85, October 2001 [doi>10.1006/jagm.2001.1171]
• 17: IEEE. IEEE standard for binary floating-point arithmetic. ACM Sigplan Notices, 22:9--25, 1985.
• 18: E. M. McCreight. Efficient algorithms for enumerating intersecting intervals and rectangles. Technical Report CSL-80-9, Xerox Corp., 1980.
• 19: E. M. McCreight. Priority search trees. SIAM J. Comp., 14(2):257--276, 1985.
• 20: K. Mehlhorn , S. Näher, Bounded ordered dictionaries in O(loglogN) time and O(n) space, Information Processing Letters, v.35 n.4, p.183-189, Aug. 1990 [doi>10.1016/0020-0190(90)90022-P]
• 21: M. H. Overmars. Computational geometry on a grid: an overview. NATO ASI Series, F40:167--184, 1988.
• 22: P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80--82, 1977.
• 23: P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Math. Syst. Theory, 10:99--127, 1977.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Classes and objects

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Inheritance

  E. Data
  E.1 DATA STRUCTURES

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout; Geometrical problems and computations; Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
IP packet classification, dynamic stabbing, object oriented method look-up