Efficient External-Memory Data Structures and Applications
Published 1 January 1996
Lars Arge
Citations46
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.
TL;DR
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.
Abstract
In this thesis we study the Input/Output (I/O) complexity of large-scale problems arising e.g. in the areas of database systems, geographic information systems, VLSI design systems and computer graphics, and design I/O-efficient algorithms for them. A general theme in our work is to design I/O-efficient algorithms through the design of I/O-efficient data structures. One of our philosophies is to try to isolate all the I/O specific parts of an algorithm in the data structures, that is, to try to design I/O algorithms from internal memory algorithms by exchanging the data structures used in internal memory with their external memory counterparts. The results in the thesis include a technique for transforming an internal memory tree data structure into an external data structure which can be used in a batched dynamic setting, that is, a setting where we for example do not require that the result of a search operation is returned immediately. Using this technique we develop batched dynami...
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
IEEE Transactions on ComputersGraph-Based Algorithms for Boolean Function Manipulation
8,829 Citations1986Bryant
Experimental results from applying a new data structure for representing Boolean functions and an associated set of manipulation algorithms to problems in logic design verification demonstrate the practicality of this approach.
R-trees
6,543 Citations1984Antonin Guttman
A dynamic index structure called an R-tree is described which meets this need, and algorithms for searching and updating it are given and it is concluded that it is useful for current database systems in spatial applications.
Choice Reviews OnlineComputer graphics: principles and practice
4,665 Citations2013
This chapter discusses the development of Hardware and Software for Computer Graphics, and the design methodology of User-Computer Dialogues, which led to the creation of the Simple Raster Graphics Package.
Mathematics of ComputationComputational Geometry--An Introduction.
4,264 Citations1986Mikhail J. Atallah, Franco P. Preparata +1 more
Medical Entomology and ZoologyHandbook of theoretical computer science
4,202 Citations1990Jan Van Leeuwen
ACM Computing SurveysSymbolic Boolean manipulation with ordered binary-decision diagrams
2,019 Citations1992Randal E. Bryant
The OBDD data structure is described and a number of applications that have been solved by OBDd-based symbolic analysis are surveyed.
ACM Computing SurveysUbiquitous B-Tree
1,826 Citations1979Douglas E. Comer
The major variations of the B-tree are discussed, especially the B+-tree, contrasting the merits and costs of each implementation and illustrating a general purpose access method that uses a B- tree.
Acta InformaticaOrganization and maintenance of large ordered indexes
1,345 Citations1972Raymond Bayer, Edward M. McCreight
The index organization described allows retrieval, insertion, and deletion of keys in time proportional to logkI where I is the size of the index and k is a device dependent natural number such that the performance of the scheme becomes near optimal.
Journal of Computer and System SciencesTime bounds for selection
1,249 Citations1973Manuel Blum, Robert W. Floyd +3 more
The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm-PICK.
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.
ACM Transactions on Database SystemsThe Grid File
1,149 Citations1984J. Nievergelt, Hans Hinterberger +1 more
This work discusses in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.
Efficient implementation of a BDD package
1,071 Citations1990Karl S. Brace, Richard Rudell +1 more
IEEE Transactions on ComputersAlgorithms for Reporting and Counting Geometric Intersections
989 Citations1979Bentley, Ottmann
Algorithms that count the number of pairwise intersections among a set of N objects in the plane and algorithms that report all such intersections are given.
The K-D-B-tree
885 Citations1981John T. Robinson
A new data structure, the K-D-B-tree, is presented as a solution to the problem of retrieving multikey records via range queries from a large, dynamic index, and it is expected that the multidimensional search effieciency of balanced K-Ds and the I/O efficiency of B-trees should both be approximated in this structure.
International Conference on Computer Aided DesignDynamic variable ordering for ordered binary decision diagrams
836 Citations1993Richard Rudell
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.
Elsevier eBooksFundamentals of Spatial Information Systems
712 Citations1992
This book describes the construction of donnees spatiales and their role in the geomatique, as well as some of the mechanisms used to design and construct them.
Journal of Computer and System SciencesConstraint Query Languages
679 Citations1995Paris C. Kanellakis, Gabriel M. Kuper +1 more
It is shown that efficient, declarative database programming can be combined with efficient constraint solving and the key intuition is that the generalization of a ground fact is a conjunction of constraints over a small number of variables.
Communications of the ACMMultidimensional divide-and-conquer
676 Citations1980Jon Bentley
Multidimensional divide-and-conquer is discussed, an algorithmic paradigm that can be instantiated in many different ways to yield a number of algorithms and data structures for multidimensional problems.
Computational geometry : an introduction through randomized algorithms
544 Citations1994Ketan Mulmuley
A comparison of quick-sort and search problems, Voronoi diagrams of Hyperplanes, and the model of randomness: The number of faces and the expected structural and conflict change.
Lower bounds for algebraic computation trees
525 Citations1983Michael Ben-Or
All the apparently known lower bounds for linear decision trees are extended to bounded degree algebraic decision trees, thus answering the open questions raised by Steele and Yao [20].
Science of Computer ProgrammingFinding repeated elements
524 Citations1982Jayadev Misra, David Gries
It is proved that O(n \log(k)) is a lower bound on the time required for any algorithm based on comparing array elements, so that the second algorithm is optimal.
Logic verification using binary decision diagrams in a logic synthesis environment
509 Citations2003Sharad Malik, A.R. Wang +2 more
The results of a formal logic verification system implemented as part of the multilevel logic synthesis system MIS are discussed and it has been possible to carry out formal verification for a larger set of networks than with existing verification systems.
SIAM Journal on ComputingPriority Search Trees
491 Citations1985Edward M. McCreight
A new data structure that is called a priority search tree, of which two variants are introduced, operations (1), (2), and (3) can be implemented in $O(\log n)$ time, where n is the cardinality of D.
I/O complexity
446 Citations1981Jiawei Hong, H. T. Kung
Using the red-blue pebble game formulation, a number of lower bound results for the I/O requirement are proven and may provide insight into the difficult task of balancing I/o and computation in special-purpose system designs.
AlgorithmicaFractional cascading: I. A data structuring technique
442 Citations1986Bernard Chazelle, Leonidas Guibas
This paper shows that, if ordered lists can be put in a one-to-one correspondence with the nodes of a graph of degreed so that the iterative search always proceeds along edges of that graph, then this structure can be built, called afractional cascading structure, in which all original searches after the first can be carried out at only logd extra cost per search.
Information and ControlDeterministic coin tossing with applications to optimal parallel list ranking
424 Citations1986Richard Cole, Uzi Vishkin
The algorithms apply a novel “random-like” deterministic technique that provides for a fast and efficient breaking of an apparently symmetric situation in parallel and distributed computation.
ACM SIGMOD RecordSpatial query processing in an object-oriented database system
398 Citations1986Jack Orenstein
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.
Journal of the ACMAn optimal algorithm for intersecting line segments in the plane
327 Citations1992Bernard Chazelle, Herbert Edelsbrunner
The authors present the first optimal algorithm for the following problem: given n line segments in the plane, compute all k pairwise intersections in O(n log n+k) time.
Lecture notes in computer scienceThe Design of Dynamic Data Structures
320 Citations1983
A catalog of (multi-dimensional) searching problems and final comments and open problems.
ACM Transactions on Database SystemsThe hB-tree: a multiattribute indexing method with good guaranteed performance
279 Citations1990David Lomet, Betty Salzberg
This work presents results that guarantee that the hB-tree copes well with arbitrary distributions of keys, decent storage utilization, reasonable size index terms, and good search and insert performance.
Symposium on Discrete AlgorithmsExternal-memory graph algorithms
277 Citations1995Yi‐Jen Chiang, Michael T. Goodrich +4 more
A collection of new techniques for designing and analyzing external-memory algorithms for graph problems and illustrating how these techniques can be applied to a wide variety of speci c problems are presented.
SIAM Journal on ComputingBinary Search Trees of Bounded Balance
258 Citations1973J. Nievergelt, Edward M. Reingold
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.
A model for hierarchical memory
221 Citations1987Alok Aggarwal, Bowen Alpern +2 more
An algorithm that uses LRU policy at the successive “levels” of the memory hierarchy is shown to be optimal for arbitrary memory access time.
ACM Transactions on GraphicsTriangulating Simple Polygons and Equivalent Problems
202 Citations1984Alain Fournier, Delfin Y. Montuno
A number of problems, such as the decomposition of simple polygons into convex, star, monotone, spiral, and trapezoidal polygons and the determination of edgevertex visibility, are linearly equivalent to the triangulation problem and therefore share the same lower bound.
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.
Lecture notes in computer scienceThe buffer tree: A new technique for optimal I/O-algorithms
184 Citations1995Lars Arge
It is shown 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 examples of how these structures can be used to develop efficient I/O-algorithms.
Journal of the ACMAdding range restriction capability to dynamic data structures
184 Citations1985Dan E. Willard, George S. Lueker
A transformation is presented that enables range restrictions to be added to an arbitrary dynamic data structure on n elements, provided that the problem satisfies a certain decomposability condition and that one is willing to allow increases by a factor of O in the worst-case time for an operation and in the space used.
SIAM Journal on ComputingCascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
175 Citations1989Mikhail J. Atallah, Richard Cole +1 more
International Journal of Computer MathematicsA new approach to rectangle intersections part I
172 Citations1983Herbert Edelsbrunner
Rectangle intersections involving rectilinearly-oriented (hyper-) rectangles in d-dimensional real space are examined and a data structure is developed which is efficient in time and space and allows us to report all d- dimensional rectangles stored which intersect a d- dimension query rectangle.
Hierarchical memory with block transfer
170 Citations1987Alok Aggarwal, Ashok K. Chandra +1 more
A model of Hierarchical Memory with Block Transfer, like a random access machine, except that access to location x takes time f(x), and a block of consecutive locations can be copied from memory to memory, taking one unit of time per element after the initial access time is introduced.
Symposium on Discrete AlgorithmsEfficient suffix trees on secondary storage
168 Citations1996David Richard Clark, J. Ian Munro
A new representation for suffix trees, a data structure used in full text searching, is presented that uses little more storage than the log n bits per index point required to store the list of index points.
Proceedings of the IEEEDynamic algorithms in computational geometry
163 Citations1992Yi‐Jen Chiang, Roberto Tamassia
The work introduces the area to the nonspecialist and reviews the state of the art for the specialist inDynamic algorithms and data structures in the area of computational geometry are surveyed.
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.
Improved algorithms and data structures for solving graph problems in external memory
127 Citations2002V. Krishna Kumar, Eric J. Schwabe
This paper presents I/O-efficient analogues of well-known data structures that are shown to be useful for obtaining simpler and improved algorithms for several graph problems.
AlgorithmicaAlgorithms for parallel memory, II: Hierarchical multilevel memories
116 Citations1994Jeffrey Scott Vitter, Elizabeth Shriver
The optimal sorting algorithm is randomized and is based upon the probabilistic partitioning technique developed in the companion paper for optimal disk sorting in a two-level memory with parallel block transfer.
The design of the cell tree: an object-oriented index structure for geometric databases
109 Citations2003Oliver Günther
The design of the cell tree, an object-oriented dynamic index structure for geometric databases, is described, which is designed for paged secondary memory to minimize the number of disk accesses occurring during a tree search.
Triangulating a simple polygon in linear time
107 Citations2002Bernard Chazelle
A deterministic algorithm for triangulating a simple polygon in linear time is given, using the polygon-cutting theorem and the planar separator theorem, whose role is essential in the discovery of new diagonals.
AlgorithmicaAlgorithms for bichromatic line-segment problems and polyhedral terrains
102 Citations1994Bernard Chazelle, Herbert Edelsbrunner +2 more
A variety of problems on the interaction between two sets of line segments in two and three dimensions are considered, including counting the number of intersecting pairs between m blue segments andn red segments in the plane.
ComputerDisk arrays: high-performance, high-reliability storage subsystems
99 Citations1994Gregory R. Ganger, Bruce Worthington +2 more
Disk arrays are an essential tool for satisfying storage performance and reliability requirements, while proper selection of a data organization can tailor an array to a particular environment.
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.
Information Processing LettersReduction of OBDDs in linear time
90 Citations1993Detlef Sieling, Ingo Wegener
A new reduction algorithm which works in optimal linear time O(|G|) is presented, which is unique (up to isomorphisms) and can be computed from any OBDD G for f of size |G| in time O (¦G¦log¦ G¦).
Permuting Information in Idealized Two-Level Storage
88 Citations1972Robert W. Floyd
Assume a computer with a (relatively) slow and large memory consisting of pages, each with a capacity of p records, and available operations for manipulating information in slow memory are limited to selecting two pages, forming a subset, of size at most p, from the union of the two pages.
Reporting and Counting Intersections Between Two Sets of Line Segments
86 Citations1988Harry G. Mairson, Jorge Stolfi
This work considers the problem of computing all intersections between two sets S and T of line segments in the plane, where no two segments in S (similarly, T) intersect and presents an asymptotically optimal algorithm which reports all those intersections in O(n log n + k) time and O( n) space.
SIAM Journal on ComputingSorting and Searching in Multisets
79 Citations1976Ian Munro, Philip M. Spira
A lower bound on finding the mode of a multiset as a function of the actual multiplicity is given, and it is demonstrated that the bound can be achieved to within a multiplicative constant.
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 AlgorithmsRectilinear line segment intersection, layered segment trees, and dynamization
71 Citations1982Vijay K. Vaishnavi, D. Wood
This work provides an efficient solution to the following problem, given a family of n rectilinear line segments in two-space, which serves to introduce a powerful new data structure, the layered segment tree, which is of independent interest.
Theoretical Computer ScienceOn the average number of rebalancing operations in weight-balanced trees
69 Citations1980Norbert Blüm, Kurt Mehlhorn
It is shown that the average number of rebalancing operations (rotations and double rotations) in weight-balanced trees is constant.
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.
AlgorithmicaBlocking for external graph searching
60 Citations1996Marian Nodine, Michael T. Goodrich +1 more
This model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy, and gives matching upper and lower bounds for completed-ary trees andd-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex.
Annals of Mathematics and Artificial IntelligenceThe input/output complexity of transitive closure
60 Citations1991Jeffrey D. Ullman, Mihalis Yannakakis
The sparse case, it is shown that I/O equal toO(n2√e/s) is sufficient, although the algorithm proposed meets the definition of “standard” only if the underlying graph is acyclic, and the sparse/acyclic case, for standard algorithms is settled.
Uniform memory hierarchies
57 Citations2002Bowen Alpern, L. Carter +1 more
The authors introduce a model, called the uniform memory hierarchy (UMH), which reflects the hierarchical nature of computer memory more accurately than the RAM (random-access-machine) model, which assumes that any item in memory can be accessed with unit cost.
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.
Information Processing LettersA simple randomized parallel algorithm for list-ranking
55 Citations1990Richard Anderson, Gary L. Miller
The algorithm is a randomized O(log n) time, n/log n processor algorithm for an EREW PRAM that is substantially simpler than other optimal algorithms for list-ranking.
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.
Journal of AlgorithmsDynamic Point Location in General Subdivisions
54 Citations1994N. Baumgarten, Hermann Jung +1 more
A solution to the dynamic planar point location problem is presented which requires space O(n), has query and insertion time O(log, log), and deletion time O (log), and was previously only known for monotone subdivisions and horizontal segments and required non-linear space.
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.
Breadth-first manipulation of SBDD of Boolean functions for vector processing
50 Citations1991Hiroyuki Ochi, Nagisa Ishiura +1 more
A high-speed algorithm of manipulators based on Shared Binary Decision Diagrams, which can be used with a vector super- computer effectively and evaluated on the vector supercomputer HI- TAC S-820/80.
Communications of the ACMThe TWA reservation system
50 Citations1984David K. Gifford, Alfred Z. Spector
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.
BRICS Report SeriesExternal-Memory Algorithms for Processing Line Segments in Geographic Information Systems
45 Citations1996Lars Arge, Darren Erik Vengroff +1 more
Lecture notes in computer scienceExploiting extensible DBMS in integrated geographic information systems
44 Citations1991Laura M. Haas, William F. Cody
This paper shows how EDBMS technology can support GIS applications through powerful data modeling and data management functions that are analogous to, and integrated with, those employed for managing traditional data.
Efficient breadth-first manipulation of binary decision diagrams
43 Citations1994Pranav Ashar, Matthew Cheong
Symposium on Discrete AlgorithmsOptimal parallel sorting in multi-level storage
43 Citations1994Alok Aggarwal, C. Greg Plaxton
It is found that Sharesort achieves optimal time bounds for parallel sorting in multi-level storage, under a variety of models that have been defined in the literature.
Symposium on Discrete AlgorithmsFast string searching in secondary storage: theoretical developments and experimental results
40 Citations1996Paolo Ferragina, Roberto Grossi
Improved performance was obtained by a new space efficient and alphabet-independent organization of the internal nodes of the SB-tree, and a new batch insertion procedure that avoids thrashing.
Journal of Parallel and Distributed ComputingLarge-Scale Sorting in Uniform Memory Hierarchies
39 Citations1993Jeffrey Scott Vitter, Marian Nodine
This work presents several efficient algorithms for sorting on the uniform memory hierarchy (UMH), introduced by Alpern, Carter, and Fei, and its parallelization P-UMH, and develops optimal sorting algorithms for all bandwidths for other versions of UMH.
Efficient out-of-core algorithms for linear relaxation using blocking covers
39 Citations2002Charles E. Leiserson, Srinivasa Rao Satti +1 more
A general method that can save substantially on the I/O traffic for many problems in sparse linear relaxation problems in which each iteration of the algorithm updates the state of every vertex in a graph with a linear combination of the states of its neighbors.
A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections.
39 Citations1994Timothy M. Chan
A new simple algorithm for computing all intersections between two collections of disjoint line segments in O(nlogn +k) time and O(n) space is presented.
A fully-dynamic data structure for external substring search
38 Citations1995Paolo Ferragina, Roberto Grossi
The SBTree data structure for A is introduced, which is the first fully-dynamic data structure allowing the External Dynamic Substring Search problem to be solved with provably good worst-case and amortized 1/0 bounds.
Lecture notes in computer scienceFrontiers of feasible and probabilistic feasible Boolean manipulation with branching programs
37 Citations1993Jordan Gergov, Christoph Meinel
The following systematically study the question up to what extend more concise BP-representations can be successfully used in symbolic Boolean manipulation, too.
Journal of Parallel and Distributed ComputingFast Permuting on Disk Arrays
34 Citations1993Thomas H. Cormen
This paper generalizes the Vitter-Shriver matrix-transpose result, showing that other classes of permutations can be performed with fewer parallel I/Os than the general permutation bound in many cases.
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.
Virtual memory algorithms
30 Citations1988Alok Aggarwal, Ashok K. Chandra
Computer programs are usually written with the illusion that they will run on something like a random access machine (RAM) with a large memory, all locations of which are equally fast, but in practice this is far from the truth.
Lecture notes in computer sciencePriority search trees in secondary memory (extended abstract)
29 Citations1988Christian Icking, Rolf Klein +1 more
This paper investigates how priority search trees can be adapted to secondary memory by giving an optimal solution for the static case and presenting data structures derived from B-trees and from a generalized version of red-black trees.
Lecture notes in computer scienceTopology B-trees and their applications
28 Citations1995Paul B. Callahan, Michael T. Goodrich +1 more
The data structure, which is called the topology B-tree, is an external-memory analogue to the internal-memory topology tree data structure of Frederickson, which allows for dynamic expression evaluation and updates as well as various tree searching and evaluation queries.
Lecture notes in computer scienceSorting multisets and vectors in-place
27 Citations2005J. Ian Munro, Venkatesh Raman
An optimal in-place algorithm to lexicographically sort an array of multidimensional vectors is obtained, by applying the multiset sorting algorithm in each coordinate by adapting heapsort for multisets.
AIP conference proceedingsAn intelligent information fusion system for handling the archiving and querying of terabyte-sized spatial databases
24 Citations1993Robert F. Cromp, W. J. Campbell +1 more
The Intelligent Data Management group has developed an Intelligent Information Fusion System (IIFS) for testing approaches to handling the archiving and querying of terabyte‐sized spatial databases.
AlgorithmicaExternal segment trees
24 Citations1994Gabriele Blankenagel, R. H. G�ting
This paper transfers the underlying principle of the segment tree in a nontrivial way to secondary storage and arrives at the EST-an external file structure with the same functionality and the following properties: the EST is balanced and the update algorithms are efficient.
Asymptotically tight bounds for performing BMMC permutations on parallel disk systems
22 Citations1993Thomas H. Cormen, Leonard F. Wisniewski
One can determine efficiently at run time whether a permutation to be performed is BMMC and then avoid the general-permutation algorithm and save parallel I/Os by using the BMMC permutation algorithm herein.
Paradigms for optimal sorting with multiple disks
18 Citations2002Marian Nodine, Jeffrey Scott Vitter
It is shown that randomized and deterministic balancing can be extended to provide algorithms that are optimal both in terms of the number of I/Os and the internal processing time for parallel-processing machines with scalable I/O subsystems and parallel memory hierarchies.
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.
Lecture notes in computer scienceCounting and reporting red/blue segment intersections
16 Citations1993Larry Palazzi, Jack Snoeyink
This work simplifies the red/blue segment intersection algorithm by using a plane sweep to presort the segments; then it operates on a list of slabs that efficiently stores a single level of a segment tree.
XP-Trees: External Priority Search Trees
16 Citations1990Gabriele Blankenagel, Ralf Hartmut Güting
In vivo and in vitro data suggest that ceramide fulfills the criteria for an endogenous pyrogen, as shown by radiotelemetry that the early phase of the fever response to IL-1beta is mediated by ceramide.
Acta InformaticaMaintaining range trees in secondary memory
15 Citations1990Mark H. Overmars, Michiel H. M. Smid +2 more
A number of partition schemes that limit the part-sizes and the number of disk accesses necessary to perform updates and queries of two-dimensional range trees are given.
…