Space efficient dynamic stabbing with fast queries

DOI10.1145/780542.780636MaRDI QIDQ3581262zbMATH OpenOpenAlexFDO

Authors Mikkel Thorup

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/780542.780636

Mathematics Subject Classification ID

Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Interval Stabbing Problems in Small Integer Ranges
• An optimal dynamic interval stabbing-MAX data structure?
• Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals
• An optimal dynamic data structure for stabbing-semigroup queries
• A dynamic stabbing-max data structure with sub-logarithmic query time

Cited in

(8)

• Two-dimensional packet classification and filter conflict resolution in the internet
• Fast and compact regular expression matching
• Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals
• An optimal dynamic data structure for stabbing-semigroup queries
• An optimal dynamic interval stabbing-MAX data structure?
• A dynamic stabbing-max data structure with sub-logarithmic query time
• On the dynamic one-dimensional interval management problem in external memory
• Substring range reporting

This page was built for publication: Space efficient dynamic stabbing with fast queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581262)