An optimal dynamic interval stabbing-max data structure?

ABSTRACT

In this paper we consider the dynamic stabbing-max problem, that is, the problem of dynamically maintaining a set S of n axis-parallel hyper-rectangles in R^d, where each rectangle s ∈ S has a weight w(s) ∈ R, so that the rectangle with the maximum weight containing a query point can be determined efficiently. We develop a linear-size structure for the one-dimensional version of the problem, the interval stabbing-max problem, that answers queries in worst-case O(log n) time and supports updates in amortized O(log n) time. Our structure works in the pointer-machine model of computation and utilizes many ingredients from recently developed external memory structures. Using standard techniques, our one-dimensional structure can be extended to higher dimensions, while paying a logarithmic factor in space, update time, and query time per dimension. Furthermore, our structure can easily be adapted to external memory, where we obtain a linear-size structure that answers queries and supports updates in O(logB n) I/Os, where B is the disk block size.

REFERENCES

• 1: P. K. Agarwal, L. Arge, J. Yang, and K. Yi, I/O-efficient structures for orthogonal range max and stabbing max queries, Proc. European Symposium on Algorithms, Lecture Notes in Computer Science, 2832, 2003, Springer Verlag, pp. 7--18.
• 2: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 3: Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.346-357, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304010]
• 4: Lars Arge , Jan Vahrenhold, I/O-efficient dynamic planar point location, Computational Geometry: Theory and Applications, v.29 n.2, p.147-162, October 2004 [doi>10.1016/j.comgeo.2003.04.001]
• 5: Lars Arge , Jeffrey Scott Vitter, Optimal External Memory Interval Management, SIAM Journal on Computing, v.32 n.6, p.1488-1508, 2003 [doi>10.1137/S009753970240481X]
• 6: Gerth Stølting Brodal , Shiva Chaudhuri , Jaikumar Radhakrishnan, The randomized complexity of maintaining the minimum, Nordic Journal of Computing, v.3 n.4, p.337-351, Winter 1996
• 7: Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
• 8: H. Edelsbrunner, A new approach to rectangle intersections, part I, Int. J. Computer Mathematics, 13 (1983), 209--219.
• 9: Haim Kaplan , Eyal Molad , Robert E. Tarjan, Dynamic rectangular intersection with priorities, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780635]
• 10: K. Mehlhorn and S. Näher, Dynamic fractional cascading, Algorithmica, 5 (1990), 215--241.
• 11: Christian Worm Mortensen, Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 12: Data Structures For One-Dimensional Packet Classification Using Most-Specific-Rule Matching, Proceedings of the 2002 International Symposium on Parallel Architectures, Algorithms and Networks, p.3, May 22-24, 2002
• 13: R. E. Tarjan, A class of algorithms that require nonlinear time to maintain disjoint sets, Journal of Computer and System Sciences, 18 (1979), 110--127.
• 14: Jun Yang , Jennifer Widom, Incremental Computation and Maintenance of Temporal Aggregates, Proceedings of the 17th International Conference on Data Engineering, p.51-60, April 02-06, 2001