Abstract
We adapt the distribution sweeping method to the cache oblivious model. Distribution sweeping is the name used for a general approach for divide-and-conquer algorithms where the combination of solved subproblems can be viewed as a merging process of streams. We demonstrate by a series of algorithms for specific problems the feasibility of the method in a cache oblivious setting. The problems all come from computational geometry, and are: orthogonal line segment intersection reporting, the all nearest neighbors problem, the 3D maxima problem, computing the measure of a set of axis-parallel rectangles, computing the visibility of a set of line segments from a point, batched orthogonal range queries, and reporting pairwise intersections of axis-parallel rectangles. Our basic building block is a simplified version of the cache oblivious sorting algorithm Funnelsort of Frigo et al., which is of independent interest.
Partially supported by the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM-FT).
Supported by the Carlsberg Foundation (contract number ANS-0257/20).
Basic Research in Computer Science, www.brics.dk, funded by the Danish National Research Foundation.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116–1127, Sept. 1988.
L. Arge, M. A. Bender, E. D. Demaine, B. Holland-Minkley, and J. I. Munro. Cache-oblivious priority queue and graph algorithm applications. In Proc. 34th Ann. ACM Symp. on Theory of Computing. ACM Press, 2002. To appear.
M. J. Atallah and J.-J. Tsay. On the parallel-decomposability of geometric problems. Algorithmica, 8:209–231, 1992.
R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173–189, 1972.
M. A. Bender, R. Cole, and R. Raman. Exponential structures for efficient cache-oblivious algorithms. In Proc. 29th International Colloquium on Automata, Languages, and Programming (ICALP), 2002. These proceedings.
M. A. Bender, E. Demaine, and M. Farach-Colton. Cache-oblivious B-trees. In Proc. 41st Ann. Symp. on Foundations of Computer Science, pages 399–409, 2000.
M. A. Bender, Z. Duan, J. Iacono, and J. Wu. A locality-preserving cache-oblivious dynamic dictionary. In Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 29–39, 2002.
J. L. Bentley. Algorithms for Klee’s rectangle problems. Carnegie-Mellon University, Pittsburgh, Penn., Department of Computer Science, unpublished notes, 1977.
G. S. Brodal and R. Fagerberg. Cache oblivious distribution sweeping. Technical Report RS-02-18, BRICS, Dept. of Computer Science, University of Aarhus, 2002.
G. S. Brodal, R. Fagerberg, and R. Jacob. Cache oblivious search trees via binary trees of small height. In Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 39–48, 2002.
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer Verlag, Berlin, 1997.
M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In 40th Annual Symposium on Foundations of Computer Science, pages 285–297, 1999.
M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. External-memory computational geometry. In Proc. 34th Ann. Symp. on Foundations of Computer Science, pages 714–723, 1993.
R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett., 1:132–133, 1972.
J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, second edition, 1996.
H. T. Kung, F. Luccio, and F. P. Preparata. On finding the maxima of a set of vectores. Journal of the ACM, 22(4):469–476, Oct. 1975.
H. Prokop. Cache-oblivious algorithms. Master’s thesis, Massachusetts Institute of Technology, June 1999.
J. S. Vitter. External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys, 33(2):209–271, June 2001.
D. E. Willard and Y. C. Wee. Quasi-valid range querying and its implications for nearest neighbor problems. In Proceedings of the Fourth Annual Symposium on Computational Geometry, pages 34–43. ACM Press, 1988.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brodal, G.S., Fagerberg, R. (2002). Cache Oblivious Distribution Sweeping. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds) Automata, Languages and Programming. ICALP 2002. Lecture Notes in Computer Science, vol 2380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45465-9_37
Download citation
DOI: https://doi.org/10.1007/3-540-45465-9_37
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43864-9
Online ISBN: 978-3-540-45465-6
eBook Packages: Springer Book Archive