Cache Oblivious Distribution Sweeping

We adapt the distribution sweepingmetho d to the cache oblivious model. Distribution sweepingis 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, computingthe measure of a set of axis-parallel rectangles, computingthe visibility of a set of line segments from a point, batched orthogonal range queries, and reportingpairwise intersections of axis-parallel rectangles. Our basic buildingblo ck is a simplified version of the cache oblivious sorting algorithm Funnelsort of Frigo et al., which is of independent interest.

• Publication year

  2002

• Venue

  International Colloquium on Automata, Languages and Programming

• Publication date

  2002-04-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/3-540-45465-9_37
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A locality-preserving cache-oblivious dynamic dictionary

  2002cited by this paper
• Cache-oblivious priority queue and graph algorithm applications

  2002cited by this paper
• Exponential Structures for Efficient Cache-Oblivious Algorithms

  2002cited by this paper
• Cache oblivious search trees via binary trees of small height

  2001cited by this paper
• External memory algorithms and data structures: dealing with massive data

  2001cited by this paper
• Cache-oblivious B-trees

  2000cited by this paper
• Cache-Oblivious Algorithms

  1999cited by this paper
• Cache-oblivious algorithms

  1999influential reference
• Computational geometry: algorithms and applications

  1997cited by this paper
• Computer architecture (2nd ed.): a quantitative approach

  1996cited by this paper
• The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract)

  1995cited by this paper
• External-memory computational geometry

  1993cited by this paper
• On the parallel decomposability of geometric problems

  1989cited by this paper
• The input/output complexity of sorting and related problems

  1988influential reference
• Quasi-Valid range querying and its implications for nearest neighbor problems

  1988cited by this paper
• An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles

  1980cited by this paper
• On Finding the Maxima of a Set of Vectors

  1975cited by this paper
• An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set

  1972cited by this paper
• Organization and maintenance of large ordered indexes

  1972cited by this paper
• Computer Architecture: A Quantitative Approach

  1969cited by this paper

• External-Memory Priority Queues with Optimal Insertions

  2025cites this paper
• Deterministic Cache-Oblivious Funnelselect

  2024cites this paper
• Multi-variable Quantification of BDDs in External Memory using Nested Sweeping (Extended Paper)

  2024cites this paper
• External-Memory Sorting with Comparison Errors

  2023cites this paper
• Funnelselect: Cache-Oblivious Multiple Selection

  2023cites this paper
• When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting

  2022influential citation
• Problem Definition

  2022cites this paper
• Towards transparent combination of model management execution strategies for low-code development platforms

  2020influential citation
• Cache Oblivious Sparse Matrix Multiplication

  2018cites this paper
• Performance Evaluation of Lazy-Funnelsort Algorithm on Multicore System

  2018influential citation
• Cache-Oblivious and Data-Oblivious Sorting and Applications

  2018cites this paper
• APPENDIX : Cache-Adaptive Analysis ( Full Version )

  2017cites this paper
• Remote Memory References at Block Granularity

  2017cites this paper
• Efficient sparse polynomial factoring using the Funnel heap

  2016influential citation
• On The Implementation of Recursive Data Structures for Cache-Oblivious Algorithms

  2016cites this paper
• High Performance Self Organizing Dynamic Dictionaries

  2016cites this paper
• High-performance data structures for de novo assembly of genomes: cache oblivious generic programming

  2016cites this paper
• Cache oblivious sparse polynomial factoring using the funnel heap

  2015cites this paper
• Cache-Oblivious Sorting

  2015cites this paper
• I/O-Efficient Range Minima Queries

  2014cites this paper
• Algorithm Engineering for fundamental Sorting and Graph Problems

  2014cites this paper
• Cache-Adaptive Algorithms

  2014influential citation
• Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs

  2014cites this paper
• Cache-Oblivious VAT-Algorithms

  2014cites this paper
• Cache Oblivious B-tree and Sorting Using Sequential Accessing

  2013cites this paper
• Cache-Adaptive Analysis

  2013cites this paper
• Distributed Duplicate Removal

  2013cites this paper
• Program-Centric Cost Models for Locality and Parallelism

  2013cites this paper
• I/O-Optimal Distribution Sweeping on Private-Cache Chip Multiprocessors

  2011cites this paper
• A Fast Algorithm for Three-Dimensional Layers of Maxima Problem

  2010cites this paper
• Low depth cache-oblivious algorithms

  2010cites this paper
• Memory Hierarchies and Models of Them

  2010cites this paper
• Geometric Algorithms for Private-Cache Chip Multiprocessors - (Extended Abstract)

  2010cites this paper
• I / O-optimal Algorithms for Orthogonal Problems for Privat e-Cache Chip Multiprocessors

  2010cites this paper
• Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

  2010cites this paper
• On Improving Stochastic Simulation for Systems Biology

  2010cites this paper
• Two dimensional Range Minimum/Maximum Query revisited

  2010cites this paper
• Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions

  2010influential citation
• Discovery of Unconventional Patterns for Sequence Analysis: Theory and Algorithms

  2009cites this paper
• Design and Engineering of External Memory Traversal Algorithms for General Graphs

  2009cites this paper
• Masking patterns in sequences: A new class of motif discovery with don't cares

  2009cites this paper
• String algorithms and data structures

  2008cites this paper
• Cache-Oblivious Model

  2008cites this paper
• Cache-Oblivious Databases : Limitations and Opportunities 1

  2008cites this paper
• Cache-Oblivious Red-Blue Line Segment Intersection

  2008influential citation
• Cache-oblivious databases: Limitations and opportunities

  2008cites this paper
• Engineering a cache-oblivious sorting algorithm

  2008cites this paper
• Uniform Hashing in Constant Time and Optimal Space

  2008cites this paper
• Traversing large graphs in realistic settings

  2008cites this paper
• Computing visibility on terrains in external memory

  2007cites this paper
• Improved External Memory BFS Implementation

  2007cites this paper
• A general framework for improving query processing performance on multi-level memory hierarchies

  2007cites this paper
• 2 External-memory Model

  2007cites this paper
• An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms

  2007cites this paper
• Cache-Oblivious Query Processing

  2007cites this paper
• Optimal Cache-Oblivious Mesh Layouts

  2007cites this paper
• Cache-oblivious nested-loop joins

  2006cites this paper
• Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching

  2006cites this paper
• Cache-Oblivious Query Processing Position paper

  2006cites this paper
• Cache-oblivious string dictionaries

  2006cites this paper
• Cache-Oblivious Hash Joins

  2006cites this paper
• Breadth First Search on Massive Graphs

  2006cites this paper
• External String Sorting: Faster and Cache-Oblivious

  2006cites this paper
• Cache-Oblivious Planar Shortest Paths

  2005influential citation
• Cache-Oblivious Comparison-Based Algorithms on Multisets

  2005cites this paper
• Cache-oblivious planar orthogonal range searching and counting

  2005cites this paper
• Cache-Aware and Cache-Oblivious Adaptive Sorting

  2005influential citation
• Proximity Mergesort: optimal in-place sorting in the cache-oblivious model

  2004influential citation
• Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths

  2004cites this paper
• Cache-Oblivious Algorithms and Data Structures

  2004influential citation
• Cache-Oblivious Data Structures

  2004influential citation
• Clustering and reconstructing large data sets

  2004cites this paper
• .1 Notation 2 External-memory Sorting 3 Cache-oblivious Sorting

  2003cites this paper
• Cache-oblivious data structures for orthogonal range searching

  2003cites this paper
• Algorithms for Memory Hierarchies

  2003cites this paper
• Cache-Oblivious Searching and Sorting

  2003influential citation
• The Cost of Cache-Oblivious Searching

  2003cites this paper
• Engineering Cache-Oblivious Sorting Algorithms

  2003cites this paper
• Cache-Oblivious Algorithms and Data Structures

  2003influential citation
• On the limits of cache-obliviousness

  2003influential citation
• Deciding Framed Bisimilarity

  2003cites this paper
• Formal Tree Series

  2002cites this paper
• An Extension Theorem with an Application to Formal Tree Series

  2002cites this paper
• Funnel Heap - A Cache Oblivious Priority Queue

  2002cites this paper
• Compact representations of BL-algebras

  2002cites this paper
• A locality-preserving cache-oblivious dynamic dictionary

  2002cites this paper
• Static Analysis for Dynamic XML

  2002cites this paper
• Mann iterates of directionally nonexpansive mappings in hyperbolic spaces

  2002cites this paper
• Comparative Methods for Gene Structure Prediction in Homologous Sequences

  2002cites this paper
• I/O-Efficient Construction of Voronoi Diagrams

  2002cites this paper
• Cache-oblivious B-trees

  2000cites this paper
• Organic Mergesort and Finger Buffer-Tree Sort: Adaptive Sorting Algorithms with External-Memory or Parallel Implementations

  year unknowninfluential citation
• 38 Cache-Oblivious Data Structures

  year unknowncites this paper
• 2 External-memory Model

  year unknowncites this paper