Cache Oblivious Distribution Sweeping

Gerth Stølting Brodal and Rolf Fagerberg

Technical Report, ALCOMFT-TR-02-52, ALCOM-FT, 22 pages, May 2002.

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.

Online version

alcomft-tr-02-52.pdf (195 Kb)

BIBTEX entry

@techreport{alcomft-tr-02-52,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg",
  institution = "ALCOM-FT",
  month = "May",
  number = "ALCOMFT-TR-02-52",
  pages = "22",
  title = "Cache Oblivious Distribution Sweeping",
  year = "2002"
}