Cache Oblivious Distribution Sweeping

Authors

  • Gerth Stølting Brodal
  • Rolf Fagerberg

DOI:

https://doi.org/10.7146/brics.v9i18.21964

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.

 

Full text: http://dx.doi.org/10.1007/3-540-45465-9_37

Published

2002-04-13

How to Cite

Brodal, G. S., & Fagerberg, R. (2002). Cache Oblivious Distribution Sweeping. BRICS Report Series, 9(18). https://doi.org/10.7146/brics.v9i18.21964