Next: The Input/Output Complexity of Up: Online Library of Jeff Previous: Algorithms and Data Structures

EXTERNAL MEMORY ALGORITHMS, I/O EFFICIENCY, AND DATABASES

A good introduction is my book in the subject which is an expanded version of my survey on external memory algorithms and data structures that appeared in ACM Computing Surveys, June 2001.

The Input/Output Complexity of Sorting and Related Problems
I/O Overhead and Parallel VLSI Architectures for Lattice Computations
Algorithms for Parallel Memory I: Two-Level Memories
Algorithms for Parallel Memory II: Hierarchical Multilevel Memories
Large-Scale Sorting in Uniform Memory Hierarchies
Optimal Deterministic Sorting on Parallel Disks
Optimal Deterministic Sorting on Parallel Processors and Parallel Memory Hierarchies
Blocking for External Graph Searching
Indexing for Data Models with Constraints and Classes
External-Memory Computational Geometry
External-Memory Graph Algorithms
External-Memory Algorithms for Processing Line Segments in Geographic Information Systems
TPIE: Transparent Parallel I/O Programming Environment
I/O-Efficient Scientific Computation using TPIE
Efficient 3-D Range Searching in External Memory
Optimal Dynamic Interval Management in External Memory
Simple Randomized Mergesort on Parallel Disks
Report of the Working Group on Storage I/O for Large-Scale Computing
I/O-Efficient Algorithms and Environments
On Sorting Strings in External Memory
I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking
Theory and Practice of I/O-Efficient Algorithms for Multidimensional Batched Searching Problems
Scalable Sweep-Based Spatial Join
Competitive Analysis of Buffer Management Algorithms for Parallel I/O Systems
Modeling and Optimizing I/O Throughput of Multiple Disks on a Bus
Scalable Mining for Classification Rules in Relational Databases
Data Cube Approximation and Histograms via Wavelets
Efficient Searching with Linear Constraints
Wavelet-Based Histograms for Selectivity Estimation
Algorithms and Data Structures for External Memory--main survey!
Efficient Bulk Operations on Dynamic R-trees
I/O-Efficient Dynamic Point Location in Monotone Subdivisions
Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets
On Two-Dimensional Indexability and Optimal Range Search Indexing
A Simple and Efficient Parallel Disk Mergesort
Online Data Structures in External Memory
External Memory Algorithms with Dynamically Changing Memory Allocations
A Unified Approach for Indexed and Non-Indexed Spatial Joins
I/O-Efficient Algorithms for Problems on Grid-Based Terrains
Efficient Bundle Sorting
Flow Computation on Massive Grid Terrains
Distribution Sort with Randomized Cycling
Constrained Querying of Multimedia Databases: Issues and Approaches
CAMEL: Concept Annotated iMagE Libraries
A Framework for Index Bulk Loading and Dynamization
Duality Between Prefetching and Queued Writing with Parallel Disks
Optimal Incremental Algorithms for Top-k Joins with User-Defined Join Constraints
Aggregate Predicate support in DBMS
XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation
Efficient Update of Indexes for Dynamically Changing Web Documents
SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads
Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching
High-Order Entropy-Compressed Text Indexes
When Indexing Equals Compression: Experiments with Compressing Suffix Arrays and Applications
Fast Compression with a Static Model in High-Order Entropy
CXHist: An On-line Classification-based Histogram for XML String Selectivity Estimation
Compressed Data Structures: Dictionaries and the Data-Aware Measures
An Algorithmic Framework for Compression and Text Indexing
Online Algorithms for Prefetching and Caching in Parallel Disks
Bulk Operations for Space-Partitioning Trees
Mining Deviants in Time Series Data Streams
Rank-aware Query Optimization
Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data
Efficient Join Processing over Uncertain-Valued Attributes
A Cache-Oblivious Index for Approximate String Matching
The SBC-tree: An Index for Run-Length Compressed Sequences
Dynamic Rank/Select Dictionaries with Applications to XML Indexing
A Framework for Dynamizing Succinct Data Structures
Geometric Burrows-Wheeler Transform: Linking Range Searching and Text Indexing
On Searching Compressed String Collections Cache-Obliviously

Jeff Vitter
2008-04-02