The Buffer Tree: A New Technique for Optimal I/O Algorithms
BRICS Report SeriesPublished 28 January 1996Open access
Lars Arge
Citations23
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
In this paper we develop a technique for transforming an internal-memory tree data structure into an external-memory structure. We show how the technique can be used to develop a search tree like structure, a priority queue, a (one-dimensional) range tree and a segment tree, and give examples of how these structures can be used to develop efficient I/O algorithms. All our algorithms are either extremely simple or straightforward generalizations of known internal-memory algorithms - given the developed external data structures. We believe that algorithms relying on the developed structure will be of practical interest due to relatively small constants in the asymptotic bounds.
Keywords
Computer Science
Mathematics of ComputationComputational Geometry--An Introduction.
4,264 Citations1986Mikhail J. Atallah, Franco P. Preparata +1 more
Communications of the ACMThe input/output complexity of sorting and related problems
1,240 Citations1988Alok Aggarwal, Jeffrey,S. Vitter
Tight upper and lower bounds are provided for the number of inputs and outputs (I/OS) between internal memory and secondary storage required for five sorting-related problems: sorting, the fast Fourier transform (FFT), permutation networks, permuting, and matrix transposition.
ComputerAn introduction to disk drive modeling
829 Citations1994Chris Ruemmler, John Wilkes
A calibrated, high-quality disk drive model is demonstrated in which the overall error factor is 14 times smaller than that of a simple first-order model, which enables an informed trade-off between effort and accuracy.
AlgorithmicaAlgorithms for parallel memory, I: Two-level memories
358 Citations1994Jeffrey Scott Vitter, Elizabeth Shriver
This work provides the first optimal algorithms in terms of the number of input/outputs required between internal memory and multiple secondary storage devices for the problems of sorting, FFT, matrix transposition, standard matrix multiplication, and related problems.
IEEE Transactions on ComputersAn Optimal Worst Case Algorithm for Reporting Intersections of Rectangles
246 Citations1980Bentley, ⁄ Wood
This paper investigates the problem of reporting all intersecting pairs in a set of n rectilinearly oriented rectangles in the plane and describes an algorithm that solves this problem in worst case time proportional to n lg n + k, where k is the number of interesecting pairs found.
External-memory computational geometry
195 Citations2002Michael T. Goodrich, Jyh-Jong Tsay +2 more
New techniques for designing efficient algorithms for computational geometry problems that are too large to be solved in internal memory are given and these algorithms are the first known optimal algorithms for a wide range of two-level and hierarchical multilevel memory models, including parallel models.
Acta InformaticaA new data structure for representing sorted lists
187 Citations1982Scott Huddleston, Kurt Mehlhorn
A new data structure is proposed (level-linked weak B-trees) for representing sorted lists when the access pattern exhibits a (time-varying) locality of reference and can treat arbitrary sequences of insertions and deletions whilst theirs can only treat non-interacting insertion and deletion.
Optimal dynamic interval management in external memory
139 Citations2002Lars Arge, Jeffrey Scott Vitter
The data structure is the first optimal external-memory solution to the dynamic interval management problem, which is a special case of 2-dimensional range searching and a central problem for object-oriented and temporal databases and for constraint logic programming.
Deterministic distribution sort in shared and distributed memory multiprocessors
95 Citations1993Mark H. Nodine, Jeffrey Scott Vitter
An elegant deterministic load balancing strategy for distribution sort that is applicable to a wide variety of parallel diska and parallel memory hierarchies with both single and parallel processors and shows how to sort determiniatically in parallelMemory hierarchies.
Journal of Computer and System SciencesIndexing for Data Models with Constraints and Classes
78 Citations1996Paris C. Kanellakis, Sridhar Ramaswamy +2 more
This work identifies a simple algorithm with good worst-case performance for the class indexing problem and improves its query I/O time from $O(\log_2 c \log_B n +t/B)$ to $O(log_b n + t/B + \log-2 B)$.
Journal of AlgorithmsBatched dynamic solutions to decomposable searching problems
64 Citations1985Herbert Edelsbrunner, Mark H. Overmars
Methods for solving batched static and batched dynamic versions of searching problems which are in particular applicable to decomposable searching problems are developed and show that batchedstatic (dynamic) versions of searched problems can often be solved more efficiently than by using known static (d dynamic) data structures.
Symposium on Principles of Database SystemsPath Caching: A Technique for Optimal External Searching
57 Citations1994Sridhar Ramaswamy, Sairam Subramanian
The definitions of common and privileged ground are analyzed and a conceptual extension that may facilitate a theoretical account of agents that coordinate via linguistic communication is proposed that is applied to one of the recurrent issues in psycholinguistic research, namely the problem of perspective-taking in dialog, and to the broader problem of audience design.
Lecture notes in computer scienceA general lower bound on the I/O-complexity of comparison-based algorithms
54 Citations1993Lars Arge, Mikael Bergholz Knudsen +1 more
The result is used to show lower bounds on the I/O-complexity on a number of problems where known techniques only give trivial bounds, and develops algorithms for these problems in order to show that the lower bounds are tight.
Efficient 3-D range searching in external memory
54 Citations1996Darren Erik Vengroff, Jeffrey Scott Vitter
The authors' is the first 3-D range search data structure that simultaneously achieves both a base-B logarithmic search overhead and a fully blocked output component (namely, K/B), and provides three dimensional results comparable to those provided by [8, 10] for the two dimensional case.
IEEE Conference on Mass Storage Systems and TechnologiesI/O Efficient Scientific Computation Using TPIE
48 Citations1995Erik D Vengroff, Jeffrey Scott Vitter
This paper discusses algorithmic issues underlying the design and implementation of the relevant components of TPIE and presents performance results of programs written to solve a series of benchmark problems using the current TPIE prototype.
Lecture notes in computer scienceExternal-memory algorithms for processing line segments in geographic information systems
47 Citations1995Lars Arge, Darren Erik Vengroff +1 more
Efficient External-Memory Data Structures and Applications
46 Citations1996Lars Arge
This thesis develops a technique for transforming an internal memory tree data structure into an external data structure which can be used in a batched dynamic setting, and proves that the new ordered binary-decision diagram manipulation algorithms are asymptotically optimal among a class of algorithms that include all know manipulation algorithms.
Lecture notes in computer scienceThe I/O-complexity of Ordered Binary-Decision Diagram manipulation
35 Citations1995Lars Arge
This work analyzes the I/O-complexity of existing Ordered Binary-Decision Diagram manipulation algorithms and develops new efficient algorithms that are optimal in all realistic I/ O-systems.
Lecture notes in computer scienceExperiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep
32 Citations1995Yi‐Jen Chiang
This is the first experimental work comparing the practical performance between external-memory algorithms and conventional algorithms with large-scale test data and three variations of plane sweep, which is optimal in terms of internal computation.
Dynamic and i/o-efficient algorithms for computational geometry and graph problems: theoretical and experimental results
18 Citations1996Yi‐Jen Chiang
An extensive experimental study comparing the practical I/Oiency of four algorithms for the orthogonal segment intersection problem with large-scale test data is presented, and the observed behavior of the algorithms is consistent with their theoretical properties.