8 COMBINATORIAL ALGORITHMS AND COMBINATORIAL OPTIMIZATION

• C. J. Van Wyk and J. S. Vitter. “The Complexity of Hashing with Lazy Deletion,” Algorithmica 1(1), 1986, 17-29.

  We examine a version of the dynamic dictionary problem in which stored items have expiration times and can be removed from the dictionary once they have expired. We show that under several reasonable assumptions about the distribution of the items, hashing with lazy deletion uses little more space than methods that use eager deletion. The simple algorithm suggested by this observation was used in a program for analyzing integrated circuit artwork.

• J. S. Vitter. “Faster Methods for Random Sampling,” Communications of the ACM, 27(7), July 1984, 703-718.

  Several new methods are presented for selecting $n$ records at random without replacement from a file containing $N$ records. Each algorithm selects the records for the sample in a sequential manner -- in the same order the records appear in the file. The algorithms are online in that the records for the sample are selected iteratively with no preprocessing. The algorithms require a constant amount of space and are short and easy to implement. The main result of this paper is the design and analysis of Algorithm D, which does the sampling in $O(n)$ time, on the average; roughly $n$ uniform random variates are generated, and approximately $n$ exponentiation operations (of the form $a^ b$, for real numbers $a$ and $b$) are performed during the sampling. This solves an open problem in the literature. CPU timings on a large mainframe computer indicate that Algorithm D is significantly faster than the sampling algorithms in use today.

  For an improved and optimized version of the random sampling method, see a related paper. For reservoir methods, where $n$ is not known in advance, see a related paper.

• J. S. Vitter. “Random Sampling with a Reservoir,” ACM Transactions on Mathematical Software, 11(1), March 1985, 37-57.

  We introduce fast algorithms for selecting a random sample of $n$ records without replacement from a pool of $N$ records, where the value of $N$ is unknown beforehand. The main result of the paper is the design and analysis of Algorithm Z; it does the sampling in one pass using constant space and in $O(n(1 + \log(N/n)))$ expected time, which is optimum, up to a constant factor. Several optimizations are studied that collectively improve the speed of the naive version of the algorithm by an order of magnitude. We give an efficient Pascal-like implementation that incorporates these modifications and that is suitable for general use. Theoretical and empirical results indicate that Algorithm Z outperforms current methods by a significant margin.

  For sampling methods where $n$ is known in advance, see a related paper.

• J. S. Vitter and Ph. Flajolet. “Average-Case Analysis of Algorithms and Data Structures,” Chapter 9 in Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (edited by J. van Leeuwen), Elsevier and M.I.T. Press, 1990, 431-524.

  The aim of this chapter to describe the main mathematical methods and applications in the average-case analysis of algorithms and data structures. It comprises two parts: First, we present basic combinatorial enumerations based on symbolic methods and asymptotic methods with emphasis on complex analysis techniques (such as singularity analysis, saddle point, Mellin transforms). Next, we show how to apply these general methods to the analysis of sorting, searching, tree data structures, hashing, and dynamic algorithms. The emphasis is on algorithms for which exact “analytic models” can be derived.

• A. Aggarwal and J. S. Vitter. “The Input/Output Complexity of Sorting and Related Problems,” Communications of the ACM, 31(9), September 1988, 1116-1127. A shorter version appears in “The I/O Complexity of Sorting and Related Problems,” Proceedings of the 14th Annual International Colloquium on Automata, Languages, and Programming (ICALP '87), Karlsruhe, West Germany, July 1987, published in Lecture Notes in Computer Science, 267, Springer-Verlag, Berlin.

  We provide tight upper and lower bounds, up to a constant factor, 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. The bounds hold both in the worst case and in the average case, and in several situations the constant factors match.

  Secondary storage is modeled as a magnetic disk capable of transferring $P$ blocks each containing $B$ records in a single time unit; the records in each block must be input from or output to $B$ contiguous locations on the disk. We give two optimal algorithms for the problems, which are variants of merge sorting and distribution sorting. In particular we show for $P=1$ that the standard merge sorting algorithm is an optimal external sorting method, up to a constant factor in the number of I/Os. Our sorting algorithms use the same number of I/Os as does the permutation phase of key sorting, except when the internal memory size is extremely small, thus affirming the popular adage that key sorting is not faster. We also give a simpler and more direct derivation of Hong and Kung's lower bound for the FFT for the special case $B = P = O(1)$.

• J. S. Vitter. “An Efficient Algorithm for Sequential Random Sampling,” ACM Transactions on Mathematical Software, 13(1), March 1987, 58-67.

  This paper presents an improved and optimized version of the random sampling method from J. S. Vitter, “Faster Methods for Random Sampling,” Communications of the ACM, 27(7), July 1984, 703-718. The object is to choose in sequential online fashion a random sample of size $n$ from a universe of size $N$. For reservoir methods, where $n$ is not known in advance, see a related paper.

• C. M. Kenyon and J. S. Vitter. “Maximum Queue Size and Hashing with Lazy Deletion,” Algorithmica, 6(4), 1991, 597-619. An extended abstract appears in Proceedings of the 20th Annual Symposium on the Interface of Computing Science and Statistics, Reston, VA, April 1988, 743-748.

  We answer questions about the distribution of the maximum size of queues and data structures as a function of time. The concept of "maximum" occurs in many issues of resource allocation. We consider several models of growth, including general birth-and-death processes, the M/G/$\infty$ model, and a non-Markovian process (data structure) for processing plane-sweep information in computational geometry, called "hashing with lazy deletion" (HwLD). It has been shown that HwLD is optimal in terms of expected time and dynamic space; our results show that it is also optimal in terms of expected preallocated space, up to a constant factor.

  We take two independent and complementary approaches: first, in Section 2, we use a variety of algebraic and analytical techniques to derive exact formulas for the distribution of the maximum queue size in stationary birth-and-death processes and in a nonstationary model related to file histories. The formulas allow numerical evaluation and some asymptotics. In our second approach, in Section 3, we consider the M/G/$\infty$ model (which includes M/M/$\infty$ as a special case) and use techniques from the analysis of algorithms to get optimal big-oh bounds on the expected maximum queue size and on the expected maximum amount of storage used by HwLD in excess of the optimal amount. The techniques appear extendible to other models, such as M/M/1.

• C. M. Kenyon-Mathieu and J. S. Vitter. “The Maximum Size of Dynamic Data Structures,” SIAM Journal on Computing, 20(5), October 1991, 807-823. An extended abstract appears in “General Methods for the Analysis of the Maximum Size of Dynamic Data Structures,” Proceedings of the 16th Annual International Colloquium on Automata, Languages, and Programming (ICALP '89), Stresa, Italy, July 1989, published in Lecture Notes in Computer Science, 372, Springer, Berlin, Germany, 473-487.

  This paper develops two probabilistic methods that allow the analysis of the maximum data structure size encountered during a sequence of insertions and deletions in data structures such as priority queues, dictionaries, linear lists, and symbol tables, and in sweepline structures for geometry and Very-Large- Scale-Integration (VLSI) applications. The notion of the "maximum" is basic to issues of resource preallocation. The methods here are applied to combinatorial models of file histories and probabilistic models, as well as to a non-Markovian process (algorithm) for processing sweepline information in an efficient way, called "hashing with lazy deletion" (HwLD). Expressions are derived for the expected maximum data structure size that are asymptotically exact, that is, correct up to lower-order terms; in several cases of interest the expected value of the maximum size is asymptotically equal to the maximum expected size. This solves several open problems, including longstanding questions in queueing theory. Both of these approaches are robust and rely upon novel applications of techniques from the analysis of algorithms. At a high level, the first method isolates the primary contribution to the maximum and bounds the lesser effects. In the second technique the continuous-time probabilistic model is related to its discrete analog-the maximum slot occupancy in hashing.

• J.-H. Lin and J. S. Vitter. “$\epsilon$-Approximations with Small Packing Constraint Violation,” Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC '92), Victoria, Canada, May 1992, 771-782.

  We present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding $\cal NP$-hard discrete optimization problem. Without any constraint violation, the $\epsilon$-approximation problem for many problems of this type is itself $\cal NP$-hard. Our methods provide polynomial-time $\epsilon$-approximations while attempting to minimize the packing constraint violation.

  Our methods lead to the first known approximation algorithms with provable performance guarantees for the $s$-median problem, the tree pruning problem, and the generalized assignment problem. These important problems have numerous applications to data compression, vector quantization, memory-based learning, computer graphics, image processing, clustering, regression, network location, scheduling, and communication. We provide evidence via reductions that our approximation algorithms are nearly optimal in terms of the packing constraint violation. We also discuss some recent applications of our techniques to scheduling problems.

• J.-H. Lin and J. S. Vitter. “Approximation Algorithms for Geometric Median Problems,” Information Processing Letters, 44, 1992, 245-249.

  In this paper we present approximation algorithms for median problems in metric spaces and fixed-dimensional Euclidean space. Our algorithms use a new method for transforming an optimal solution of the linear program relaxation of the $s$-median problem into a provably good integral solution. This transformation technique is fundamentally different from the methods of randomized and deterministic rounding by Raghavan and the methods proposed the authors' earlier work in the following way: Previous techniques never set variables with zero values in the fractional solution to the value of 1. This departure from previous methods is crucial for the success of our algorithms.

• J.-H. Lin and J. S. Vitter. “Nearly Optimal Vector Quantization via Linear Programming,” Proceedings of the 1992 IEEE Data Compression Conference (DCC '92), Snowbird, UT, March 1992, 22-31.

  We present new vector quantization algorithms based on the theory developed by the authors. The new approach is to formulate a vector quantization problem as a 0-1 integer linear program. We first solve its relaxed linear program by linear programming techniques. Then we transform the linear program solution into a provably good solution for the vector quantization problem. These methods lead to the first known polynomial-time full-search vector quantization codebook design algorithm and tree pruning algorithm with provable worst-case performance guarantees. We also introduce the notion of pseudo-random pruned tree-structured vector quantizers. Initial experimental results on image compression are very encouraging.

• J.-H. Lin and J. S. Vitter. “A Theory for Memory-Based Learning,” special issue of Machine Learning, 17(2/3), November/December 1994, 143-167. A shorter version appears in Proceedings of the 5th Annual ACM Conference on Computational Learning Theory (COLT '92), Pittsburgh, PA, July 1992, 103-115.

  A memory-based learning system is an extended memory management system that decomposes the input space either statically or dynamically into subregions for the purpose of storing and retrieving functional information. The main generalization techniques employed by memory-based learning systems are the nearest-neighbor search, space decomposition techniques, and clustering. Research on memory-based learning is still in its early stage. In particular, there are very few rigorous theoretical results regarding memory requirement, sample size, expected performance, and computational complexity. In this paper, we propose a model for memory-based learning and use it to analyze several methods -- $\epsilon$-covering, hashing, clustering, tree-structured clustering, and receptive-fields -- for learning smooth functions. The sample size and system complexity are derived for each method. Our model is built upon the generalized PAC learning model of Haussler and is closely related to the method of vector quantization in data compression. Our main result is that we can build memory-based learning systems using new clustering algorithms of Lin and Vitter to PAC-learn in polynomial time using only polynomial storage in typical situations.

• J. S. Vitter and E. A. M. Shriver. “Algorithms for Parallel Memory I: Two-Level Memories,” double special issue on large-scale memories in Algorithmica, 12(2-3), 1994, 110-147. A shorter version appears in “Optimal Disk I/O with Parallel Block Transfer,” Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC '90), Baltimore, MD, May 1990, 159-169.

  We provide the first optimal algorithms in terms of the number of input/outputs (I/Os) required between internal memory and multiple secondary storage devices for the problems of sorting, FFT, matrix transposition, standard matrix multiplication, and related problems. Our two-level memory model is new and gives a realistic treatment of parallel block transfer, in which during a single I/O each of the $P$ secondary storage devices can simultaneously transfer a contiguous block of $B$ records. The model pertains to a large-scale uniprocessor system or parallel multiprocessor system with $P$ disks. In addition, the sorting, FFT, permutation network, and standard matrix multiplication algorithms are typically optimal in terms of the amount of internal processing time. The difficulty in developing optimal algorithms is to cope with the partitioning of memory into $P$ separate physical devices. Our algorithms' performance can be significantly better than those obtained by the well-known but nonoptimal technique of disk striping. Our optimal sorting algorithm is randomized, but practical; the probability of using more than $\ell$ times the optimal number of I/Os is exponentially small in $\ell (\log \ell) \log (M/B)$, where $M$ is the internal memory size.

• J. S. Vitter and E. A. M. Shriver. “Algorithms for Parallel Memory II: Hierarchical Multilevel Memories,” double special issue on large-scale memories in Algorithmica, 12(2-3), 1994, 148-169. A shorter version appears in “Optimal Disk I/O with Parallel Block Transfer,” Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC '90), Baltimore, MD, May 1990, 159-169.

  In this paper we introduce parallel versions of two hierarchical memory models and give optimal algorithms in these models for sorting, FFT, and matrix multiplication. In our parallel models, there are $P$ memory hierarchies operating simultaneously; communication among the hierarchies takes place at a base memory level. Our 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 probability of using $\ell$ times the optimal running time is exponentially small in  $\ell (\log \ell) \log P$.

• M. H. Nodine and J. S. Vitter. “Greed Sort: An Optimal Sorting Algorithm on Parallel Disks,” Journal of the ACM, 42(4), July 1995, 919-933. An extended abstract appears in “Large-Scale Sorting in Parallel Memories,” Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '91), Hilton Head, SC, July 1991, 29-39.

  We present an algorithm for sorting efficiently with parallel two-level memories. Our main result is an elegant, easy-to-implement, optimal, detemzinistic algorithm for external sorting with $D$ disk drives. This result answers in the affirmative the open problem posed by Vitter and Shriver of whether an optimal algorithm exists that is deterministic. Our measure of performance is the number of parallel input/output (I/0) operations, in which each of the $D$ disks can simultaneously transfer a block of $B$ contiguous records. We assume that internal memory can hold $M$ records. Our algorithm sorts $N$ records in the optimal bound of $O(( N/BD) log (N/B)/ log (M/B))$ deterministically, and thus it improves upon Vitter and Shriver’s optimal randomized algorithm as well as the well-known deterministic but nonoptimal technique of disk striping. It is also practical to implement.

• J. S. Vitter and M. H. Nodine. “Large-Scale Sorting in Uniform Memory Hierarchies,” special issue on parallel I/O systems in Journal of Parallel and Distributed Computing, 17, January 1993, 107-114. A shorter version appears in “Large-Scale Sorting in Parallel Memories,” Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '91), Hilton Head, SC, July 1991, 29-39.

  We present several efficient algorithms for sorting on the uniform memory hierarchy (UMH), introduced by Alpern, Carter, and Feig, and its parallelization P-UMH. We give optimal and nearly-optimal algorithms for a wide range of bandwidth degradations, including a parsimonious algorithm for constant bandwidth. We also develop optimal sorting algorithms for all bandwidths for other versions of UMH and P-UMH, including natural restrictions we introduce called RUMH and P-RUMH, which more closely correspond to current programming languages.

• M. H. Nodine and J. S. Vitter. “Optimal Deterministic Sorting on Parallel Disks.” manuscript. A shorter version appears in Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '93), Velen, Germany, June-July 1993, 120-129.

  We present a load balancing technique that leads to an optimal deterministic algorithm called Balance Sort for external sorting on multiple disks. Our measure of performance is the number of input/output (I/O) operations. In each I/O, each of the $D$ disks can simultaneously transfer a block of data. Our algorithm improves upon the randomized optimal algorithm of Vitter and Shriver as well as the (non-optimal) commonly-used technique of disk striping. It also improves upon our earlier merge-based sorting algorithm in that it has smaller constants hidden in the big-oh notation, and it is possible to implement using only striped writes (but independent reads). In a companion paper, we show how to modify the algorithm to achieve optimal CPU time, even on parallel processors and parallel memory hierarchies.

• M. H. Nodine and J. S. Vitter. “Optimal Deterministic Sorting on Parallel Processors and Parallel Memory Hierarchies,” manuscript. A shorter version appears in Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '93), Velen, Germany, June-July 1993, 120-129.

  We present a practical deterministic load balancing strategy for distribution sort that is applicable to parallel disks and parallel memory hierarchies with both single and parallel processors. The simplest application of the strategy is an optimal deterministic algorithm called Balance Sort for external sorting on multiple disks with a single CPU, as described in the companion paper. However, the internal processing of Balance Sort does not seem parallelizable. In this paper, we develop an elegant variation that achieves full parallel speedup. The algorithms so derived are optimal for all parallel memory hierarchies with any type of a PRAM base-level interconnection and are either optimal or best-known for a hypercube interconnection. We show how to achieve optimal internal processing time as well as optimal number of I/Os in parallel two-level memories.

• Y. Matias, J. S. Vitter, and N. Young. “Approximate Data Structures with Applications,” Proceedings of the 5th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '94), Alexandria, VA, January 1994. The work is the basis of a patent by the authors, “Implementation of Approximate Data Structures,” United States Patent No. 5,519,840, Bell Laboratories, May 21, 1996.

  In this paper we introduce the notion of approximate data structures, in which a small amount of error is tolerated in the output. Approximate data structures trade error of approximation for faster operation, leading to theoretical and practical speedups for a wide variety of algorithms. We give approximate variants of the van Emde Boas data structure, which support the same dynamic operations as the standard van Emde Boas data structure, except that answers to queries are approximate. The variants support all operations in constant time provided the error of approximation is $1/{\mathop{\rm polylog}}(n)$, and in $O(\log\log n)$ time provided the error is $1/{\mathop{\rm polynomial}}(n)$, for $n$ elements in the data structure.

  We consider the tolerance of prototypical algorithms to approximate data structures. We study in particular Prim's minimum spanning tree algorithm, Dijkstra's single-source shortest paths algorithm, and an on-line variant of Graham's convex hull algorithm. To obtain output which approximates the desired output with the error of approximation tending to zero, Prim's algorithm requires only linear time, Dijkstra's algorithm requires $O(m\log\log n)$ time, and the on-line variant of Graham's algorithm requires constant amortized time per operation.

• M. H. Nodine, M. T. Goodrich, and J. S. Vitter. “Blocking for External Graph Searching,” Algorithmica, 16(2), August 1996, 181-214. A shorter version appears in Proceedings of the 12th Annual ACM Symposium on Principles of Database Systems (PODS '93), Washington, D. C, May 1993.

  In this paper, we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for complete $d$-ary trees and $d$-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.

• Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. “External-Memory Graph Algorithms,” Proceedings of the 6th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '95), San Francisco, CA, January 1995.

  We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of specific problems. Our results include:

  • Proximate-neighboring. We present a simple method for deriving external-memory lower bounds via reductions from a problem we call the “proximate neighbors” problem. We use this technique to derive non-trivial lower bounds for such problems as list ranking, expression tree evaluation, and connected components.
  • PRAM simulation. We give methods for efficiently simulating PRAM computations in external memory, even for some cases in which the PRAM algorithm is not work-optimal. We apply this to derive a number of optimal (and simple) external-memory graph algorithms.
  • Time-forward processing. We present a general technique for evaluating circuits (or “circuit-like” computations) in external memory. We also use this in a deterministic list ranking algorithm.
  • Deterministic 3-coloring of a cycle. We give several optimal methods for 3-coloring a cycle, which can be used as a subroutine for finding large independent sets for list ranking. Our ideas go beyond a straightforward PRAM simulation, and may be of independent interest.
  • External depth-first search. We discuss a method for performing depth first search and solving related problems efficiently in external memory. Our technique can be used in conjunction with ideas due to Ullman and Yannakakis in order to solve graph problems involving closed semi-ring computations even when their assumption that vertices fit in main memory does not hold.

  Our techniques apply to a number of problems, including list ranking, which we discuss in detail, finding Euler tours, expression-tree evaluation, centroid decomposition of a tree, least-common ancestors, minimum spanning tree verification, connected and biconnected components, minimum spanning forest, ear decomposition, topological sorting, reachability, graph drawing, and visibility representation.

• L. Arge, D. E. Vengroff, and J. S. Vitter. “External-Memory Algorithms for Processing Line Segments in Geographic Information Systems,” Algorithmica, 47(1), January 2007, 1-25. A shorter version appears in Proceedings of the 3rd Annual European Symposium on Algorithms (ESA '95), September 1995, published in Lecture Notes in Computer Science, 979, Springer-Verlag, Berlin, 295-310.

  In the design of algorithms for large-scale applications it is essential to consider the problem of minimizing I/O communication. Geographical information systems (GIS) are good examples of such large-scale applications as they frequently handle huge amounts of spatial data. In this paper we develop efficient new external-memory algorithms for a number of important problems involving line segments in the plane, including trapezoid decomposition, batched planar point location, triangulation, red-blue line segment intersection reporting, and general line segment intersection reporting. In GIS systems, the first three problems are useful for rendering and modeling, and the latter two are frequently used for overlaying maps and extracting information from them.

  To solve these problems, we combine and modify in novel ways several of the previously known techniques for designing efficient algorithms for external memory. We also develop a powerful new technique that can be regarded as a practical external memory version of fractional cascading. Except for the batched planar point location problem, no algorithms specifically designed for external memory were previously known for these problems. Our algorithms for triangulation and line segment intersection partially answer previously posed open problems, while the batched planar point location algorithm improves on the previously known solution, which applied only to monotone decompositions. Our algorithm for the red-blue line segment intersection problem is provably optimal.

• R. D. Barve, E. F. Grove and J. S. Vitter. “Simple Randomized Mergesort on Parallel Disks,” special issue on parallel I/O in Parallel Computing, 23(4), 1997. A shorter version appears in Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '96), Padua, Italy, June 1996, 109-118.

  We consider the problem of sorting a file of $N$ records on the $D$-disk model of parallel I/O in which there are two sources of parallelism. Records are transferred to and from disk concurrently in blocks of $B$ contiguous records. In each I/O operation, up to one block can be transferred to or from each of the $D$ disks in parallel. We propose a simple, efficient, randomized mergesort algorithm called SRM that uses a forecast-and-flush approach to overcome the inherent difficulties of simple merging on parallel disks. SRM exhibits a limited use of randomization and also has a useful deterministic version. Generalizing the technique of forecasting, our algorithm is able to read in, at any time, the “right” block from any disk, and using the technique of flushing, our algorithm evicts, without any I/O overhead, just the “right” blocks from memory to make space for new ones to be read in. The disk layout of SRM is such that it enjoys perfect write parallelism, avoiding fundamental inefficiencies of previous mergesort algorithms. By analysis of generalized maximum occupancy problems we are able to derive an analytical upper bound on SRM's expected overhead valid for arbitrary inputs.

  The upper bound derived on expected I/O performance of SRM indicates that SRM is provably better than disk-striped mergesort (DSM) for realistic parameter values $D$, $M$, and $B$. Average-case simulations show further improvement on the analytical upper bound. Unlike previously proposed optimal sorting algorithms, SRM outperforms DSM even when the number $D$ of parallel disks is small.

• L. Arge, P. Ferragina, R. Grossi, and J. S. Vitter. “On Sorting Strings in External Memory,” Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC '97), El Paso, TX, May 1997, 540-548, and in “Sequence Sorting in Secondary Storage," Proceedings of the 1997 International Conference on Compression and Complexity of Sequences (SEQUENCES '97), Positano, Italy, June 1997.

  In this paper we address for the first time the I/O complexity of the problem of sorting strings in external memory, which is a fundamental component of many large-scale text applications. In the standard unit-cost RAM comparison model, the complexity of sorting $K$ strings of total length $N$ is $\Theta(K\log_2 K+N)$. By analogy, in the external memory (or I/O) model, where the internal memory has size $M$ and the block transfer size is $B$, it would be natural to guess that the I/O complexity of sorting strings is $\Theta(\frac{K}{B}\log_{M/B} \frac{K}{B}+\frac{N}{B})$, but the known algorithms do not come even close to achieving this bound. Our results show, somewhat counterintuitively, that the I/O complexity of string sorting depends upon the length of the strings relative to the block size. We first consider a simple comparison I/O model, where one is not allowed to break the strings into their characters, and we show that the I/O complexity of string sorting in this model is $\Theta(\frac{N_1}{B}\log_{M/B} \frac{N_1}{B} + K_2\log_{M/B} K_2+\frac{N}{B})$, where $N_1$ is the total length of all strings shorter than $B$ and $K_2$ is the number of strings longer than $B$. We then consider two more general I/O comparison models in which string breaking is allowed. We obtain improved algorithms and in several cases lower bounds that match their I/O bounds. Finally, we develop more practical algorithms without assuming the comparison model.

• R. D. Barve and J. S. Vitter. “A Simple and Efficient Parallel Disk Mergesort,” Theory of Computing Systems, 35(2), March/April 2002, 189-215. A shorter version appears in Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '99), St. Malo, France, June 1999.

  Slides for talk plus extra foils on dynamic memory allocation (gzip-compressed postscript)

  External sorting is a fundamental operation in many large scale data processing systems not only for producing sorted output but also as a core subroutine in many operations. Technology trends indicate that developing techniques that effectively use multiple disks in parallel in order to speed up the performance of external sorting is of prime importance. The simple randomized merging (SRM) mergesort algorithm proposed in our earlier work is the first parallel disk sorting algorithm that requires a provably optimal number of passes and that is fast in practice. Knuth (in the new edition of The Art of Computer Programming, Vol. 3: Sorting and Searching) recently identified SRM (which he calls “randomized striping”) as the method of choice for sorting with parallel disks.

  In this paper, we present an efficient implementation of SRM, based upon novel data structures. We give a new implementation for SRM's lookahead forecasting technique for parallel prefetching and its forecast and flush technique for buffer management. Our techniques amount to a significant improvement in the way SRM carries out the parallel, independent disk accesses necessary to efficiently read blocks of input runs during external merging.

  We present the performance of SRM over a wide range of input sizes and compare its performance with that of disk-striped mergesort (DSM), the commonly used technique to implement external mergesort on $D$ parallel disks. DSM consists of using a standard mergesort algorithm in conjunction with striped I/O for parallel disk access. SRM merges together significantly more runs at a time compared with DSM, and thus it requires fewer merge passes. We demonstrate in practical scenarios that even though the streaming speeds for merging with DSM are a little higher than those for SRM (since DSM merges fewer runs at a time), sorting using SRM is significantly faster than with DSM, since SRM requires fewer passes.

  The techniques in this paper can be generalized to meet the load-balancing requirements of other applications using parallel disks, including distribution sort, multiway partitioning of a file into several other files. and some potential multimedia streaming applications.

• J. S. Vitter. “Online Data Structures in External Memory,” invited keynote paper in Proceedings of the 26th Annual International Colloquium on Automata, Languages, and Programming (ICALP '99), Prague, Czech Republic, July 1999, published in Lecture Notes in Computer Science, 1644, Springer-Verlag, Berlin, 119-133.

  This survey article is superseded by a more comprehensive book. The book is available online and is recommended as the preferable reference.

  Slides for ICALP '99 talk (gzip-compressed postscript)

  The data sets for many of today's computer applications are too large to fit within the computer's internal memory and must instead be stored on external storage devices such as disks. A major performance bottleneck can be the input/output communication (or I/O) between the external and internal memories. In this paper we discuss a variety of online data structures for external memory, some very old and some very new, such as hashing (for dictionaries), B-trees (for dictionaries and 1-D range search), buffer trees (for batched dynamic problems), interval trees with weight-balanced B-trees (for stabbing queries), priority search trees (for 3-sided 2-D range search), and R-trees and other spatial structures. We also discuss several open problems along the way.

• R. D. Barve and J. S. Vitter. “External Memory Algorithms with Dynamically Changing Memory Allocations,” Report CS-1998-09, June 1998. A shorter version of the paper appeared as “A Theoretical Framework for Memory-Adaptive Algorithms,” Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS '99), New York, NY, October 1999, 273-284.

  We consider the problem of devising external memory algorithms whose memory allocations can change dynamically and unpredictably at run-time. The investigation of “memory-adaptive” algorithms, which are designed to adapt to dynamically changing memory allocations, can be considered a natural extension of the investigation of traditional, non-adaptive external memory algorithms. Our study is motivated by high performance database systems and operating systems in which applications are prioritized and internal memory is dynamically allocated in accordance with the priorities. In such situations, external memory applications are expected to perform as well as possible for the current memory allocation. The computation must be reorganized to adapt to the sequence of memory allocations in an online manner.

  In this paper we present a simple and natural dynamic memory allocation model. We define memory-adaptive external memory algorithms and specify what is needed for them to be dynamically optimal. Using novel techniques, we design and analyze dynamically optimal memory-adaptive algorithms for the problems of sorting, permuting, FFT, permutation networks, (standard) matrix multiplication and LU decomposition. We also present a dynamically optimal (in an amortized sense) memory-adaptive version of the buffer tree, a generic external memory data structure for a large number of batched dynamic applications. We show that a previously devised approach to memory-adaptive external mergesort is provably nonoptimal because of fundamental drawbacks. The lower bound proof techniques for sorting and matrix multiplication are fundamentally distinct techniques, and they are invoked by most other external memory lower bounds; hence we anticipate that the techniques presented here will apply to many external memory problems.

• Y. Matias, E. Segal, and J. S. Vitter. “Efficient Bundle Sorting,” SIAM Journal on Computing, 36(2), 2006, 394-410. A shorter version appeared in Proceedings of the 11th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '00), San Francisco, CA, January 2000, 839-848.

  Many data sets to be sorted consist of a limited number of distinct keys. Sorting such data sets can be thought of as bundling together identical keys and having the bundles placed in order; we therefore denote this as bundle sorting. We describe an efficient algorithm for bundle sorting in external memory that requires at most $c (N/B) \log_{M/B} k$ disk accesses, where $N$ is the number of keys, $M$ is the size of internal memory, $k$ is the number of distinct keys, $B$ is the transfer block size, and $2<c<4$. For moderately sized $k$, this bound circumvents the $\Theta((N/B)\log_{M/B}(N/B))$ I/O lower bound known for general sorting. We show that our algorithm is optimal by proving a matching lower bound for bundle sorting. The improved running time of bundle sorting over general sorting can be significant in practice, as demonstrated by experimentation. An important feature of the new algorithm is that it is executed “in-place”, requiring no additional disk space.

• J. S. Vitter. “External Memory Algorithms and Data Structures: Dealing with Massive Data,” ACM Computing Surveys, 33(2), June 2001, 209-271. Shorter versions appear in “External Memory Algorithms,” invited keynote paper in Proceedings of the 6th Annual European Symposium on Algorithms (ESA '98), Venice, August 1998, published in Lecture Notes in Computer Science, 1461, Springer, Berlin, Germany, 1-25, and in an invited tutorial in Proceedings of the 17th Annual ACM Symposium on Principles of Database Systems (PODS '98), Seattle, WA, June 1998, 119-128.

  Slides for a talk (Adobe pdf format)

  This survey article is superseded by a more comprehensive book. The book is available online and is recommended as the preferable reference.

• J. S. Vitter and D. A. Hutchinson. “Distribution Sort with Randomized Cycling,” Journal of the ACM, 53(7), July 2006, 656-680. A shorter version appeared in Proceedings of the 12th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '01), Washington, DC, January 2001.

  Parallel independent disks can enhance the performance of external memory (EM) algorithms, but the programming task is often difficult. In this paper we develop randomized variants of distribution sort for use with parallel independent disks. We propose a simple variant called randomized cycling distribution sort (RCD) and prove that it has optimal expected I/O complexity. The analysis uses a novel reduction to a model with significantly fewer probabilistic interdependencies. Experimental evidence is provided to support its practicality. Other simple variants are also examined experimentally and appear to offer similar advantages to RCD. Based upon ideas in RCD we propose general techniques that transparently simulate algorithms developed for the unrealistic multihead disk model so that they can be run on the realistic parallel disk model. The simulation is optimal for two important classes of algorithms: the class of multipass algorithms, which make a complete pass through their data before accessing any element a second time, and the algorithms based upon the well-known distribution paradigm of EM computation.

• L. Arge, J. S. Chase, and J. S. Vitter. “Efficient Sorting using Registers and Caches,” invited paper in special issue of ACM Journal of Experimental Algorithmics, 7(9), 2002. A shorter version appears in L. Arge, R. Barve, J. S. Chase, J. S. Vitter, and R. Wickremesinghe. “Efficient Sorting using Registers and Caches,” Proceedings of the 4rd Workshop on Algorithm Engineering (WAE '00), Saarbrücken, Germany, September 2000, published in Lecture Notes in Computer Science, 1982 Springer-Verlag, Berlin, Germany, 51-62.

  Modern computer systems have increasingly complex memory systems. Common machine models for algorithm analysis do not reflect many of the features of these systems, e.g., large register sets, lockup-free caches, cache hierarchies, associativity, cache line fetching, and streaming behavior. Inadequate models lead to poor algorithmic choices and an incomplete understanding of algorithm behavior on real machines.

  A key step toward developing better models is to quantify the performance effects of features not reflected in the models. This paper explores the effect of memory system features on sorting performance. We introduce a new cache-conscious sorting algorithm, R-MERGE, which achieves better performance in practice over algorithms that are superior in the theoretical models. R-MERGE is designed to minimize memory stall cycles rather than cache misses by considering features common to many system designs.

• D. A. Hutchinson, P. Sanders, and J. S. Vitter. “Duality Between Prefetching and Queued Writing with Parallel Disks,” SIAM Journal on Computing, 34(6), 1443-1463, June 2005. An extended abstract appears in Proceedings of the 9th Annual European Symposium on Algorithms (ESA '01), Århus, Denmark, August 2001, published in Lecture Notes in Computer Science, 2161, Springer-Verlag, Berlin, Germany.

  Parallel disks promise to be a cost effective means for achieving high bandwidth in applications involving massive data sets, but algorithms for parallel disks can be difficult to devise. To combat this problem, we define a useful and natural duality between writing to parallel disks and the seemingly more difficult problem of prefetching. We first explore this duality for applications involving read-once accesses using parallel disks. We get a simple linear time algorithm for computing optimal prefetch schedules and analyze the efficiency of the resulting schedules for randomly placed data and for arbitrary interleaved accesses to striped sequences. Duality also provides an optimal schedule for the integrated caching and prefetching problem, in which blocks can be accessed multiple times. Another application of this duality gives us the first parallel disk sorting algorithms that are provably optimal up to lower order terms. One of these algorithms is a simple and practical variant of multiway merge sort, addressing a question that has been open for some time.

• A. Natsev, J. R. Smith, Y. C. Chang, C.-S. Li, and J. S. Vitter. “Constrained Querying of Multimedia Databases: Issues and Approaches,” Proceedings of SPIE Electronic Imaging 2001: Storage and Retrieval for Image and Video Databases, San Jose, CA, January 2001.

  This paper investigates the problem of high-level querying of multimedia data by imposing arbitrary domain-specific constraints among multimedia objects. We argue that the current structured query model, and the query-by-content model, are insufficient for many important applications, and we propose an alternative query framework that unifies and extends the previous two models. The proposed framework is based on the querying-by-concept paradigm, where the query is expressed simply in terms of concepts, regardless of the complexity of the underlying multimedia search engines. The query-by-concept paradigm was previously illustrated by the CAMEL system. The present paper builds upon and extends that work by adding arbitrary constraints and multiple levels of hierarchy in the concept representation model.

  We consider queries simply as descriptions of virtual data sets, and that allows us to use the same unifying concept representation for query specification, as well as for data annotation purposes. We also identify some key issues and challenges presented by the new framework, and we outline possible approaches for overcoming them. In particular, we study the problems of concept representation, extraction, refinement, storage, and matching.

• A. Natsev, Y. C. Chang, J. R. Smith, C.-S. Li, and J. S. Vitter, “Supporting Incremental Join Queries on Ranked Inputs,” Proceedings of the 27th International Conference on Very Large Databases (VLDB '01), Rome, Italy, September 2001.

  This paper investigates the problem of incremental joins of multiple ranked data sets when the join condition is a list of arbitrary user-defined predicates on the input tuples. This problem arises in many important applications dealing with ordered inputs and multiple ranked data sets, and requiring the top $k$ solutions. We use multimedia applications as the motivating examples but the problem is equally applicable to traditional database applications involving optimal resource allocation, scheduling, decision making, ranking, etc.

  We propose an algorithm $J^{\ast}$ that enables querying of ordered data sets by imposing arbitrary user-defined join predicates. The basic version of the algorithm does not use any random access but a $J^{\ast}_{PA}$ variation can exploit available indexes for efficient random access based on the join predicates. A special case includes the join scenario considered by Fagin for joins based on identical keys, and in that case, our algorithms perform as efficiently as Fagin's. Our main contribution, however, is the generalization to join scenarios that were previously unsupported, including cases where random access in the algorithm is not possible due to lack of unique keys. In addition, $J^{\ast}$ can support multiple join levels, or nested join hierarchies, which are the norm for modeling multimedia data. We also give $\epsilon$-approximation versions of both of the above algorithms. Finally, we give strong optimality results for some of the proposed algorithms, and we study their performance empirically.

• A. Natsev, G. Fuh, W. Chen, C.-H. Chiu, and J. S. Vitter. “Aggregate Predicate Support in DBMS,” Proceedings of the 13th Australasian Database Conference (ADC '02), Melbourne, Australia, January 2002, published in Conferences in Research and Practice in Information Technology, Vol. 5, Xiaofang Zhou, Ed.

  In this paper we consider aggregate predicates and their support in database systems. Aggregate predicates are the predicate equivalent to aggregate functions in that they can be used to search for tuples that satisfy some aggregate property over a set of tuples (as opposed to simply computing an aggregate property over a set of tuples). The importance of aggregate predicates is exemplified by many modern applications that require ranked search, or top-$k$ queries. Such queries are the norm in multimedia and spatial databases.

  In order to support the concept of aggregate predicates in DBMS, we introduce several extensions in the query language and the database engine. Specifically, we extend the SQL syntax to handle aggregate predicates and work out the semantics of such extensions so that they behave correctly in the existing database model. We also propose a a new rk_SORT operator into the database engine, and study relevant indexing and query optimization issues.

  Our approach provides several advantages, including enhanced usability and improved performance. By supporting aggregate predicates natively in the database engine, we are able to reuse existing indexing and query optimization techniques, without sacrificing generality or incurring the runtime overhead of database-external approaches. To the best of our knowledge, the proposed framework is the first to support user-defined indexing with aggregate predicates and search based upon user-defined ranking. We also provide empirical results from a simulation study that validates the effectiveness of our approach.

• R. Shah, P. J. Varman, and J. S. Vitter. “Online Algorithms for Prefetching and Caching in Parallel Disks,” Proceedings of the 16th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '04), Barcelona, Spain, June 2004.

  Parallel disks provide a cost effective way of speeding up I/Os in applications that work with large amounts of data. The main challenge is to achieve as much parallelism as possible, using prefetching to avoid bottlenecks in disk access. Efficient algorithms have been developed for some particular patterns of accessing the disk blocks. In this paper, we consider general request sequences. When the request sequence consists of unique block requests, the problem is called prefetching and is a well-solved problem for arbitrary request sequences. When the reference sequence can have repeated references to the same block, we need to devise an effective caching policy as well. While optimum offline algorithms have been recently designed for the problem, in the online case, no effective algorithm was previously known. Our main contribution is a deterministic online algorithm threshold-LRU which achieves $O((MD/L)^{2/3})$ competitive ratio and a randomized online algorithm threshold-MARK which achieves $O(\sqrt((MD/L) \log(MD/L)))$ competitive ratio for the caching/prefetching problem on the parallel disk model (PDM), where $D$ is the number of disks, $M$ is the size of fast memory buffer, and $M + L$ is the amount of lookahead available in the request sequence. The best-known lower bound on the competitive ratio is $O(\sqrt(MD/L))$ for lookahead $L >= M$ in both models. We also show that if the deterministic online algorithm is allowed to have twice the memory of the offline then a tight competitive ratio of $O(\sqrt(MD/L))$ can be achieved. This problem generalizes the well-known paging problem on a single disk to the parallel disk model.

• T. M. Ghanem, R. Shah, M. F. Mokbel, W. G. Aref, and J. S. Vitter. “Bulk Operations for Space-Partitioning Trees,” Proceedings of the 20th Annual IEEE International Conference on Data Engineering (ICDE '04), Boston, March-April 2004.

  The emergence of extensible index structures, e.g., GiST (Generalized Search Tree) and SP-GiST (Space-Partitioning Generalized Search Tree), calls for a set of extensible algorithms to support different operations (e.g., insertion, deletion, and search). Extensible bulk operations (e.g., bulk loading and bulk insertion) are of the same importance and need to be supported in these index engines. In this paper, we propose two extensible buffer-based algorithms for bulk operations in the class of space-partitioning trees; a class of hierarchical data structures that recursively decompose the space into disjoint partitions. The main idea of these algorithms is to build an in-memory tree of the target space-partitioning index. Then, data items are recursively partitioned into disk-based buffers using the in-memory tree. Although the second algorithm is designed for bulk insertion, it can be used in bulk loading as well. The proposed extensible algorithms are implemented inside SP-GiST; a framework for supporting the class of space-partitioning trees. Both algorithms have I/O bound $O(NH/B)$, where $N$ is the number of data items to be bulk loaded/inserted, $B$ is the number of tree nodes that can fit in one disk page, $H$ is the tree height in terms of pages after applying a clustering algorithm. Experimental results are provided to show the scalability and applicability of the proposed algorithms for the class of space-partitioning trees. A comparison of the two proposed algorithms shows that the first algorithm performs better in case of bulk loading. However the second algorithm is more general and can be used for efficient bulk insertion.

• S. Muthukrishnan, R. Shah, and J. S. Vitter. “Mining Deviants in Time Series Data Streams,” Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM '04), Santorini Island, Greece, June 2004.

  One of the central tasks in managing, monitoring and mining data streams is that of identifying outliers. There is a long history of study of various outliers in statistics and databases, and a recent focus on mining outliers in data streams. Here, we adopt the notion of deviants from Jagadish et al as outliers. Deviants are based on one of the most fundamental statistical concept of standard deviation (or variance). Formally, deviants are defined based on a representation sparsity metric, i.e., deviants are values whose removal from the dataset leads to an improved compressed representation of the remaining items. Thus, deviants are not global maxima/minima, but rather these are appropriate local aberrations. Deviants are known to be of great mining value in time series databases. We present first-known algorithms for identifying deviants on massive data streams. Our algorithms monitor streams using very small space (polylogarithmic in data size) and are able to quickly find deviants at any instant, as the data stream evolves over time. For all versions of this problem--univariate vs multivariate time series, optimal vs nearoptimal vs heuristic solutions, offline vs streaming--our algorithms have the same framework of maintaining a hierarchical set of candidate deviants that are updated as the time series data gets progressively revealed. We show experimentally using real network traffic data (SNMP aggregate time series) as well as synthetic data that our algorithm is remarkably accurate in determining the deviants.

• I. Ilyas, R. Shah, W. G. Aref, J. S. Vitter, and A. Elmagarmid. “Rank-aware Query Optimization,” Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data (SIGMOD '04), Paris, France, June 2004.

  Ranking is an important property that needs to be fully supported by current relational query engines. Recently, several rank-join query operators have been proposed based on rank aggregation algorithms. Rank-join operators progressively rank the join results while performing the join operation. The new operators have a direct impact on traditional query processing and optimization. We introduce a rank-aware query optimization framework that fully integrates rank-join operators into relational query engines. The framework is based on extending the System R dynamic programming algorithm in both enumeration and pruning. We define ranking as an interesting property that triggers the generation of rank-aware query plans. Unlike traditional join operators, optimizing for rank-join operators depends on estimating the input cardinality of these operators. We introduce a probabilistic model for estimating the input cardinality, and hence the cost of a rank-join operator. To our knowledge, this paper is the first effort in estimating the needed input size for optimal rank aggregation algorithms. Costing ranking plans, although challenging, is key to the full integration of rank-join operators in real-world query processing engines. We experimentally evaluate our framework by modifying the query optimizer of an open-source database management system. The experiments show the validity of our framework and the accuracy of the proposed estimation model.

• R. Cheng, Y. Xia, S. Prabhakar, R. Shah, and J. S. Vitter. “Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data,” Proceedings of the 30th International Conference on Very Large Databases (VLDB '04), Toronto, CA, August 2004.

  It is infeasible for a sensor database to contain the exact value of each sensor at all points in time. This uncertainty is inherent in these systems due to measurement and sampling errors, and resource limitations. In order to avoid drawing erroneous conclusions based upon stale data, the use of uncertainty intervals that model each data item as a range and associated probability density function (pdf) rather than a single value has recently been proposed. Querying these uncertain data introduces imprecision into answers, in the form of probability values that specify the likeliness the answer satisfies the query. These queries are more expensive to evaluate than their traditional counterparts but are guaranteed to be correct and more informative due to the probabilities accompanying the answers. Although the answer probabilities are useful, for many applications, it is only necessary to know whether the probability exceeds a given threshold; we term these Probabilistic Threshold Queries (PTQ). In this paper we address the efficient computation of these types of queries.

  In particular, we develop two index structures and associated algorithms to efficiently answer PTQs. The first index scheme is based on the idea of augmenting uncertainty information to an R-tree. We establish the difficulty of this problem by mapping one-dimensional intervals to a two-dimensional space, and show that the problem of interval indexing with probabilities is significantly harder than interval indexing which is considered a well-studied problem. To overcome the limitations of this R-tree based structure, we apply a technique we call variance-based clustering, where data points with similar degrees of uncertainty are clustered together. Our extensive index structure can answer the queries for various kinds of uncertainty pdfs, in an almost optimal sense. We conduct experiments to validate the superior performance of both indexing schemes.

• I. Ilyas, W. G. Aref, A. K. Elmagarmid, H. G. Elmongui, R. Shah, and J. S. Vitter. “Adaptive Rank-aware Query Optimization in Relational Databases,” ACM Transactions on Database Systems, 31(4), December 2006, 1257-1304.

  Rank-aware query processing has emerged as a key requirement in modern applications. In these applications, efficient and adaptive evaluation of top-k queries is an integral part of the application semantics. In this article, we introduce a rank-aware query optimization framework that fully integrates rank-join operators into relational query engines. The framework is based on extending the System R dynamic programming algorithm in both enumeration and pruning. We define ranking as an interesting physical property that triggers the generation of rank-aware query plans. Unlike traditional join operators, optimizing for rank-join operators depends on estimating the input cardinality of these operators.We introduce a probabilistic model for estimating the input cardinality, and hence the cost of a rank-join operator. To our knowledge, this is the first effort in estimating the needed input size for optimal rank aggregation algorithms. Costing ranking plans is key to the full integration of rank-join operators in real-world query processing engines.

  Since optimal execution strategies picked by static query optimizers lose their optimality due to estimation errors and unexpected changes in the computing environment, we introduce several adaptive execution strategies for top-k queries that respond to these unexpected changes and costing errors. Our reactive reoptimization techniques change the execution plan at runtime to significantly enhance the performance of running queries. Since top-k query plans are usually pipelined and maintain a complex ranking state, altering the execution strategy of a running ranking query is an important and challenging task.

  We conduct an extensive experimental study to evaluate the performance of the proposed framework. The experimental results are twofold: (1) we show the effectiveness of our cost-based approach of integrating ranking plans in dynamic programming cost-based optimizers; and (2) we show a significant speedup (up to 300%) when using our adaptive execution of ranking plans over the state-of-the-art mid-query reoptimization strategies.

• R. Cheng, Y. Xia, S. Prabhakar, R. Shah, and J. S. Vitter. “Efficient Join Processing over Uncertain-Valued Attributes,” Proceedings of the 2006 ACM Conference on Information and Knowledge Management (CIKM '06), Arlington, VA, November 2006.

  In an uncertain database, each data item is modeled as a range associated with a probability density function. Previous works for this kind of data have focused on simple queries such as range and nearest-neighbor queries. Queries that join multiple relations have not been addressed in earlier work despite the significance of joins in databases. In this paper, we address probabilistic join over uncertain data, essentially a query that augments the results with probability guarantees to indicate the likelihood of each join tuple being part of the result. We extend the notion of join operators, such as equality and inequality, for uncertain data. We also study the performance of probabilistic join. We observe that a user may only need to know whether the probability of the results exceeds a given threshold, instead of the precise probability value. By incorporating this constraint, it is possible to achieve much better performance. In particular, we develop three sets of optimization techniques, namely item-level, page-level and index-level pruning, for different join operators. These techniques facilitate pruning with little space and time overhead, and are easily adapted to most join algorithms. We verify the performance of these techniques experimentally.

• A. Gupta, W.-K. Hon, R. Shah, and J. S. Vitter. “A Framework for Dynamizing Succinct Data Structures,” Proceedings of the 34th Annual International Colloquium on Automata, Languages, and Programming (ICALP '07), Wrocaw, Poland, July 2007, published in Lecture Notes in Computer Science, 4596 Springer-Verlag, Berlin, Germany, 521-532.

  We present a framework to dynamize succinct data structures, to encourage their use over non-succinct versions in a wide variety of important application areas. Our framework can dynamize most state-of-the-art succinct data structures for dictionaries, ordinal trees, labeled trees, and text collections. Of particular note is its direct application to XML indexing structures that answer $\mathit{subpath}$ queries. Our framework focuses on achieving information-theoretically optimal space along with near-optimal update/query bounds.

  As the main part of our work, we consider the following problem central to text indexing: Given a text $T$ over an alphabet $\Sigma$, construct a compressed data structure answering the queries $\mathop{access}(i)$, $\mathop{ranks}(i)$, and $\mathop{selects}(i)$ for a symbol $s \in \Sigma$. Many data structures consider these queries for static text $T$. We build on these results and give the best known query bounds for the dynamic version of this problem, supporting arbitrary insertions and deletions of symbols in $T$.

  Specifically, with an amortized update time of $O(n^\epsilon)$, any static succinct data structure $D$ for $T$, taking $t(n)$ time for queries, can be converted by our framework into a dynamic succinct data structure that supports $\mathop{ranks}(i)$, $\mathop{selects}(i)$, and $\mathop{access}(i)$ queries in $O(t(n) + \log\log n)$ time, for any constant $\epsilon > 0$. When $\vert\Sigma\vert = \mathop{\rm polylog}(n)$, we achieve $O(1)$ query times. Our update/query bounds are near-optimal with respect to the lower bounds.

• Y.-F. Chien, W.-K. Hon, R. Shah, and J. S. Vitter. “Geometric Burrows-Wheeler Transform: Linking Range Searching and Text Indexing,” Proceedings of the 2008 IEEE Data Compression Conference (DCC '08), Snowbird, UT, March 2008.

  We introduce a new variant of the popular Burrows-Wheeler transform (BWT) called Geometric Burrows-Wheeler Transform (GBWT). Unlike BWT, which merely permutes the text, GBWT converts the text into a set of points in 2-dimensional geometry. Using this transform, we can answer to many open questions in compressed text indexing: (1) Can compressed data structures be designed in external memory with similar performance as the uncompressed counterparts? (2) Can compressed data structures be designed for position restricted pattern matching? We also introduce a reverse transform, called Points2Text, which converts a set of points into text. This transform allows us to derive the best known lower bounds in compressed text indexing. We show strong equivalence between data structural problems in geometric range searching and text pattern matching. This provides a way to derive new results in compressed text indexing by translating the results from range searching.

• M. Y. Eltabakh, W.-K. Hon, R. Shah, W. Aref, and J. S. Vitter. “The SBC-tree: An Index for Run-Length Compressed Sequences,” Proceedings of the 11th International Conference on Extending Database Technology (EDBT '08), Nantes, France, March 2008, 523-534.

  Run-Length-Encoding (RLE) is a data compression technique that is used in various applications, e.g., biological se- quence databases, multimedia, and facsimile transmission. One of the main challenges is how to operate, e.g., indexing, searching, and retrieval, on the compressed data without decompressing it. In this paper, we present the String B-tree for Compressed sequences, termed the SBC-tree, for indexing and searching RLE-compressed sequences of arbitrary length. The SBC-tree is a two-level index structure based on the well-known String B-tree and a 3-sided range query structure. The SBC-tree supports substring as well as prefix matching, and range search operations over RLE-compressed sequences. The SBC-tree has an optimal external-memory space complexity of $O(N/B)$ pages, where $N$ is the total length of the compressed sequences, and $B$ is the disk page size. The insertion and deletion of all suffixes of a compressed sequence of length m takes $O(m \log_B (N+m))$ I/O operations. Substring matching, prefix matching, and range search execute in an optimal $O(\log_B N + (\vert p\vert+T)/B)$ I/O operations, where $\vert p\vert$ is the length of the compressed query pattern and $T$ is the query output size. We present also two variants of the SBC-tree: the SBC-tree that is based on an R-tree instead of the 3-sided structure, and the one-level SBC-tree that does not use a two-dimensional index. These variants do not have provable worst-case theoretical bounds for search operations, but perform well in practice. The SBC-tree index is realized inside PostgreSQL in the context of a biological protein database application. Performance results illustrate that using the SBC-tree to index RLE-compressed sequences achieves up to an order of magnitude reduction in storage, up to 30% reduction in I/Os for the insertion operations, and retains the optimal search performance achieved by the String B-tree over the uncompressed sequences.

• W.-K. Hon, R. Shah, P. J. Varman, and J. S. Vitter. “Tight Competitive Ratios for Parallel Disk Prefetching,” Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '08), Munich, Germany, June 2008, 352-361.

  We consider the natural extension of the well-known single disk caching problem to the parallel disk I/O model (PDM) [17]. The main challenge is to achieve as much parallelism as possible and avoid I/O bottlenecks. We are given a fast memory (cache) of size $M$ memory blocks along with a request sequence $\Sigma = (b_1, b_2, \dots, b_n)$ where each block $b_i$ resides on one of $D$ disks. In each parallel I/O step, at most one block from each disk can be fetched. The task is to serve in the minimum number of parallel I/Os. Thus, each I/O is analogous to a page fault. The difference here is that during each page fault, up to $D$ blocks can be brought into memory, as long as all of the new blocks entering the memory reside on different disks. The problem has a long history. Note that this problem is non-trivial even if all requests in $\Sigma$ are unique. This restricted version is called read-once. Despite the progress in the online ver- sion and read-once version, the general online problem still remained open. Here, we provide comprehensive results with a full general solution for the problem with asymptotically tight competitive ratios.

  To exploit parallelism, any parallel disk algorithm needs a certain amount of lookahead into future requests. To provide effective caching, an online algorithm must achieve $o(D)$ competitive ratio. We show a lower bound that states, for lookahead $L \leq M$, that any online algorithm must be $\Omega(D)$-competitive. For lookahead $L$ greater than $M(1 + 1/\epsilon)$, where $\epsilon$ is a constant, the tight upper bound of $O(\sqrt{MD/L})$ on competitive ratio is achieved by our algorithm SKEW. The previous algorithm tLRU was $O((MD/L)^{2/3})$ competitive and this was also shown to be tight for an LRU-based strategy. We achieve the tight ratio using a fairly different strategy than LRU. We also show tight results for randomized algorithms against oblivious adversary and give an algorithm achieving better bounds in the resource augmentation model.

• J. S. Vitter. Algorithms and Data Structures for External Memory -- main reference! Series on Foundations and Trends in Series on Foundations and Trends in Theoretical Computer Science, now Publishers, Hanover, MA, 2008. Also published as Volume 2, Issue 4 of Foundations and Trends in Theoretical Computer Science. This reference book gives a good general introduction to algorithms and data structures for use in external memory, when I/O can be a bottleneck.

  Slides for a talk (Adobe pdf format)

  Data sets in large applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. In this book we discuss the state of the art in the design and analysis of external memory (or EM) algorithms and data structures, where the goal is to exploit locality in order to reduce the I/O costs. We consider a variety of EM paradigms for solving batched and online problems efficiently in external memory.

  For the batched problem of sorting and related problems like permuting and fast Fourier transform, the key paradigms include distribution and merging. The paradigm of disk striping offers an elegant way to use multiple disks in parallel. For sorting, however, disk striping can be nonoptimal with respect to I/O, so to gain further improvements we discuss prefetching, distribution, and merging techniques for using the disks independently. We also consider useful techniques for batched EM problems involving matrices (such as matrix multiplication and transposition), geometric data (such as finding intersections and constructing convex hulls) and graphs (such as list ranking, connected components, topological sorting, and shortest paths). In the online domain, canonical EM applications include dictionary lookup and range searching. The two important classes of indexed data structures are based upon extendible hashing and B-trees. The paradigms of filtering and bootstrapping provide a convenient means in online data structures to make effective use of the data accessed from disk. We also reexamine some of the above EM problems in slightly different settings, such as when the data items are moving, when the data items are variable-length (e.g., text strings), when the internal data representations are compressed, or when the allocated amount of internal memory can change dynamically.

  Programming tools and environments are available for simplifying the EM programming task. During the course of the book, we report on some experiments in the domain of spatial databases using the TPIE system (Transparent Parallel I/O programming Environment). The newly developed EM algorithms and data structures that incorporate the paradigms we discuss are significantly faster than methods currently used in practice.

  This book is an expanded version of an earlier survey article.

• W.-K. Hon, T.-W. Lam, R. Shah, S.-L. Tam, and J. S. Vitter. “A Cache-Oblivious Index for Approximate String Matching,” Theoretical Computer Science 412(29), 2011, 3579-3588. A shorter version appears in Proceedings of the 16th Annual Conference on Combinatorial Pattern Matching (CPM '07), London, Ontario, Canada, July 2007, published in Lecture Notes in Computer Science, 4580 Springer-Verlag, Berlin, Germany, 40-51.

  This paper revisits the problem of indexing a text for approximate string matching. Specifically, given a text $T$ of length $n$ and a positive integer $k$, we want to construct an index of $T$ such that for any input pattern $P$, we can find all its $k$-error matches in $T$ efficiently. This problem is well-studied in the internal-memory setting. Here, we extend some of these recent results to external-memory solutions, which are also cache-oblivious. Our first index occupies $O((n\log k n)/B)$ disk pages and finds all $k$-error matches with I/Os, where $B$ denotes the number of words in a disk page. To the best of our knowledge, this index is the first external-memory data structure that does not require $\Omega (\vert P\vert + \mathit{occ} + \mathrm{polylog}(n))$ I/Os. The second index reduces the space to $O((nlogn)/B)$ disk pages, and the I/O complexity is $O((\vert P\vert+\mathit{occ})/B+\log^{k(k+1)} n \log\log n)$.

• W.-K. Hon, T.-W. Lam, R. Shah, S.-L. Tam, and J. S. Vitter. “Compressed Index for Dictionary Matching,” Proceedings of the 2008 IEEE Data Compression Conference (DCC '08), Snowbird, UT, March 2008.

  The past few years have witnessed several exciting results on compressed representation of a string $T$ that supports efficient pattern matching, and the space complexity has been reduced to $\vert T\vert H_k(T)+o(\vert T\vert \log \sigma)$ bits, where $H_k(T)$ denotes the $k$th-order empirical entropy of $T$, and $\sigma$ is the size of the alphabet. In this paper we study compressed representation for another classical problem of string indexing, which is called dictionary matching in the literature. Precisely, a collection $D$ of strings (called patterns) of total length $n$ is to be indexed so that given a text $T$, the occurrences of the patterns in $T$ can be found efficiently. In this paper we show how to exploit a sampling technique to compress the existing O(n)-word index to an $(nH_k(D) + o(n log \sigma))$-bit index with only a small sacrifice in search time.

• P. Ferragina, R. Grossi, A. Gupta, R. Shah, and J. S. Vitter. “On Searching Compressed String Collections Cache-Obliviously,” Proceedings of the 27th Annual ACM Symposium on Principles of Database Systems (PODS '08), Vancouver, Canada, June 2008.

  Current data structures for searching large string collections are limited in that they either fail to achieve minimum space or they cause too many cache misses. In this paper, we discuss some edge linearizations of the classic trie data structure that are simultaneously cache-friendly and storable in compressed space. The widely known frontcoding scheme is one example of linearization; it is at the core of Prefix B-trees and many other disk-conscious compressed indexes for string collections. However, it is largely thought of as a space-effective heuristic without efficient search support.

  In this paper, we introduce new insights on front-coding and other novel linearizations, and study how close their space occupancy is to the information-theoretic minimum. The moral is that they are not just heuristics. The second contribution of this paper engineers these linearizations to design a novel dictionary encoding scheme that achieves nearly optimal space, offers competitive I/O-search time, and is also conscious of the query distribution. Finally, we combine those data structures with cache-oblivious tries and obtain a succinct variant, whose space is close to the information-theoretic minimum.

• Y.-F. Chien, W.-K. Hon, R. Shah, S. V. Thankachan, and J. S. Vitter, “Geometric BWT: Compressed Text Indexing via Sparse Suffixes and Range Searching,” Algorithmica, 71, 2015, published online May 2013, 258-178. A shorter version of some results appeared in W.-K. Hon, R. Shah, S. V. Thankachan, and J. S. Vitter, “On Entropy-Compressed Text Indexing in External Memory,” Proceedings of the 16th International Conference on String Processing and Information Retrieval (SPIRE '09), Saariselkä, Finland, August 2009, published in Lecture Notes in Computer Science, 5721, Springer, Berlin, Germany, 75-89.

  We introduce a new variant of the popular Burrows-Wheeler transform (BWT), called Geometric Burrows-Wheeler Transform (GBWT), which converts a text into a set of points in 2-dimensional geometry.We also introduce a reverse transform, called Points2Text, which converts a set of points into text. Using these two transforms, we show strong equivalence between data structural problems in geometric range searching and text pattern matching. This allows us to apply the lower bounds known in the field of orthogonal range searching to the problems in compressed text indexing. In addition, we give the first succinct (compact) index for I/O-efficient pattern matching in external memory, and show how this index can be further improved to achieve higher-order entropy compressed space.

• W.-K. Hon, R. Shah, and J. S. Vitter. “Space-Efficient Frameworks for Top-$k$ String Retrieval,” Journal of the ACM, 61(2), April 2014, 9.1-9.36. An extended abstract appears in W.-K. Hon, R. Shah, and J. S. Vitter, “Space-Efficient Frameworks for Top-$k$ String Retrieval Problems,” Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09), Atlanta, GA, October 2009, 713-722.

  Given a set ${\cal D}=\{d_1,d_2,...,d_D\}$ of $D$ strings of total length $n$, our task is to report the “most relevant” strings for a given query pattern $P$. This involves somewhat more advanced query functionality than the usual pattern matching, as some notion of “most relevant” is involved. In information retrieval literature, this task is best achieved by using inverted indexes. However, inverted indexes work only for some predefined set of patterns. In the pattern matching community, the most popular pattern-matching data structures are suffix trees and suffix arrays. However, a typical suffix tree search involves going through all the occurrences of the pattern over the entire string collection, which might be a lot more than the required relevant documents.

  The first formal framework to study such kind of retrieval problems was given by Muthukrishnan. He considered two metrics for relevance: frequency and proximity. He took a threshold-based approach on these metrics and gave data structures taking $O(n \log n)$ words of space. We study this problem in a slightly different framework of reporting the top $k$ most relevant documents (in sorted order) under similar and more general relevance metrics. Our framework gives linear space data structure with optimal query times for arbitrary score functions. As a corollary, it improves the space utilization for the problems considered by Muthukrishnan while maintaining optimal query performance. We also develop compressed variants of these data structures for several specific relevance metrics.

• W.-K. Hon, R. Shah, S. V. Thankachan, and J. S. Vitter. “On Position Restricted Substring Searching in Succinct Space,” Journal of Discrete Algorithms, 17, 2012, 109-114. Part of the results appear in an extended abstract in Y.-F. Chien, W.-K. Hon, R. Shah, and J. S. Vitter, “Geometric Burrows-Wheeler Transform: Linking Range Searching and Text Indexing,” Proceedings of the 2008 IEEE Data Compression Conference (DCC '08), Snowbird, UT, March 2008.

• M. O. Külekci, W.-K. Hon, R. Shah, J. S. Vitter, and B. Xu. “$\Psi$-RA: a Parallel Sparse Index for Genomic Read Alignment,” invited paper from BIBM '10 in BMC Genomics, 12(Suppl. 2), 2011, S7. A shorter version appears in “PSI-RA: A Parallel Sparse Index for Read Alignment on Genomes," Proceedings of 2010 IEEE International Conference on Bioinformatics and Biomedicine (BIBM '10), Hong Kong, December 2010, 663-668.

  Background: Genomic read alignment involves mapping (exactly or approximately) short reads from a particular individual onto a pre-sequenced reference genome of the same species. Because all individuals of the same species share the majority of their genomes, short reads alignment provides an alternative and much more efficient way to sequence the genome of a particular individual than does direct sequencing. Among many strategies proposed for this alignment process, indexing the reference genome and short read searching over the index is a dominant technique. Our goal is to design a space-efficient indexing structure with fast searching capability to catch the massive short reads produced by the next generation high-throughput DNA sequencing technology.

  Results: We concentrate on indexing DNA sequences via sparse suffix arrays (SSAs) and propose a new short read aligner named $\Psi$-RA (PSI-RA: parallel sparse index read aligner). The motivation in using SSAs is the ability to trade memory against time. It is possible to fine tune the space consumption of the index based on the available memory of the machine and the minimum length of the arriving pattern queries. Although SSAs have been studied before for exact matching of short reads, an elegant way of approximate matching capability was missing. We provide this by defining the rightmost mismatch criteria that prioritize the errors towards the end of the reads, where errors are more probable. $\Psi$-RA supports any number of mismatches in aligning reads. We give comparisons with some of the well-known short read aligners, and show that indexing a genome with SSA is a good alternative to the Burrows-Wheeler transform or seed-based solutions.

  Conclusions: $\Psi$-RA is expected to serve as a valuable tool in the alignment of short reads generated by the next generation high-throughput sequencing technology. $\Psi$-RA is very fast in exact matching and also supports rightmost approximate matching. The SSA structure that $\Psi$-RA is built on naturally incorporates the modern multicore architecture and thus further speed-up can be gained. All the information, including the source code of $\Psi$-RA, can be downloaded at: http://www.busillis.com/o_kulekci/PSIRA.zip.

• Q. Yu, H. Huo, J. S. Vitter, J. Huan, and Y. Nekrich. “An Efficient Exact Algorithm for the Motif Stem Search Problem over Large Alphabets,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, 12(2), March/April 2015, 384-397, dx.doi.org/10.1109/TCBB.2014.2361668. A shorter version appears in “StemFinder: An Efficient Algorithm for Searching Motif Stems over Large Alphabets,” Proceedings of 2013 IEEE International Conference on Bioinformatics and Biomedicine (BIBM '13), Shanghai, December 2013.

  In recent years, there has been increasing interest in planted $(\ell, d)$ motif search (PMS) with applications to discovering significant segments in biological sequences. However, there has been little discussion about PMS over large alphabets. This paper focuses on motif stem search (MSS), which was recently introduced to search motifs on large-alphabet inputs. A motif stem is an $\ell$-length string with some wildcards. The goal of the MSS problem is to find a set of stems that represents a superset of all $(\ell, d)$ motifs present in the input sequences, and the superset is expected to be as small as possible. The three main contributions of this paper are as follows: (1) We build motif stem representation more precisely by using regular expressions. (2)  We give a method for generating all possible motif stems without redundant wildcards. (3) We propose an efficient exact algorithm, called StemFinder, for solving the MSS problem. Compared with the previous algorithms, StemFinder runs much faster and first solves the (17, 8), (19, 9) and (21, 10) challenging instances on protein sequences; moreover, StemFinder reports fewer stems which represent a smaller superset of all $(\ell, d)$ motifs. StemFinder is freely available at http://sites.google.com/site/feqond/stemfinder.

• M. Lewenstein, Y. Nekrich, and J. S. Vitter. “Space-Efficient String Indexing for Wildcard Pattern Matching,” Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS '14), Lyon, France, March 2014, published in Leibniz International Proceedings in Informatics, Schloss Dagstuhl, Wadern, Germany.

  In this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. We present a data structure that uses $O(n \log^\epsilon n)$ bits for any $\epsilon > 0$ and reports all occ occurrences of a wildcard string in $O(\sigma^g + \log^{(3)} n + \mathop{occ})$ time, where $\sigma$ is the alphabet size, $m$ is the number of alphabet symbols, and $g$ is the number of wildcard symbols in the query string. We also present an $O(n)$-bit index with $O((m+ \sigma^g + \mathop{occ}) \log^\epsilon n)$ query time and an $O(n(\log \log n)^2)$-bit index with $O((m + \sigma^g + \mathop{occ}) \log \log n)$ query time. These are the first data structures for this problem that need only $o(n log n)$ bits of space.

• H. Huo, L. Chen, J. S. Vitter, and Y. Nekrich. “A Practical Implementation for Compressed Suffix Arrays with Applications to Self-indexing,” in preparation. An extended abstract appears in Proceedings of the 2014 IEEE Data Compression Conference (DCC '14), Snowbird, UT, March 2014.

  In this paper, we develop a simple and practical storage scheme for compressed suffix arrays (CSA). Our CSA can be constructed in linear time and needs $2nH_k + n + o(n)$ bits of space simultaneously for any $k \leq c \log_\sigma n - 1$ and any constant $c <1$, where $H_k$ denotes the $k$-th order entropy. We compare the performance of our method with two established compressed indexing methods, viz. the FM-index and Sadakane's CSA. Experiments on the Canterbury Corpus and the Pizza&Chili Corpus show significant advantages of our algorithm over two other indexes in terms of compression and query time. Our storage scheme achieves better performance on all types of data present in these two corpora, except for evenly distributed data, such as DNA. The source code for our CSA is available online.

• Y. Nekrich, M. Patil, R. Shah, S. V. Thankachan, and J. S. Vitter. “`Categorical Range Maxima Queries,” Proceedings of the 33rd Annual ACM Symposium on Principles of Database Systems (PODS '14), Snowbird, UT, June 2014.

  Given an array A[1...n] of n distinct elements from the set 1, 2, ..., n a range maximum query RMQ(a, b) returns the highest element in A[a...b] along with its position. In this paper, we study a generalization of this classical problem called Categorical Range Maxima Query (CRMQ) problem, in which each element A[i] in the array has an associated category (color) given by C[i] ∈ [σ]. A query then asks to report each distinct color c appearing in C[a...b] along with the highest element (and its position) in A[a...b] with color c. Let pc denote the position of the highest element in A[a...b] with color c. We investigate two variants of this problem: a threshold version and a top-k version. In threshold version, we only need to output the colors with A[pc] more than the input threshold τ, whereas top-k variant asks for k colors with the highest A[pc] values. In the word RAM model, we achieve linear space structure along with O(k) query time, that can report colors in sorted order of A[•]. In external memory, we present a data structure that answers queries in optimal O(1+k/B) I/O's using almost-linear O(n log* n) space, as well as a linear space data structure with O(log* n + k/B) query I/Os. Here k represents the output size, log* n is the iterated logarithm of n and B is the block size. CRMQ has applications to document retrieval and categorical range reporting - giving a one-shot framework to obtain improved results in both these problems. Our results for CRMQ not only improve the existing best known results for three-sided categorical range reporting but also overcome the hurdle of maintaining color uniqueness in the output set.

• Q. Yu, H. Huo, X. Chen, H. Guo, J. S. Vitter, and J. Huan. “An Efficient Algorithm for Discovering Motifs in Large DNA Data Sets,” IEEE Transactions on NanoBioscience, 14(5), July 2015, epublished April 9, 2015. A shorter version appears in “An Efficient Motif Finding Algorithm for Large DNA Data Sets,” Proceedings of 2014 IEEE International Conference on Bioinformatics and Biomedicine (BIBM '14), Belfast, UK, November 2014.

  The planted $(\ell, d)$ motif discovery has been successfully used to locate transcription factor binding sites in dozens of promoter sequences over the past decade. However, there has not been enough work done in identifying $(\ell, d)$ motifs in the next-generation sequencing (ChIP-seq) data sets, which contain thousands of input sequences and thereby bring new challenge to make a good identification in reasonable time. To cater this need, we propose a new planted $(\ell, d)$ motif discovery algorithm named MCES, which identifies motifs by mining and combining emerging substrings. Specially, to handle larger data sets, we design a MapReduce-based strategy to mine emerging substrings distributedly. Experimental results on the simulated data show that i) MCES is able to identify $(\ell, d)$ motifs efficiently and effectively in thousands to millions of input sequences, and runs faster than the state-of-the-art $(\ell, d)$ motif discovery algorithms, such as F-motif and TraverStringsR; ii) MCES is able to identify motifs without known lengths, and has a better identification accuracy than the competing algorithm CisFinder. Also, the validity of MCES is tested on real data sets. MCES is freely available at http://sites.google.com/site/feqond/mces.

• Q. Yu, H. Huo, R. Zhao, D. Feng, J. S. Vitter, and J. Huan. “RefSelect: A Reference Sequence Selection Algorithm for Planted $(\ell, d)$ Motif Search," BMC Bioinformatics, 17(Suppl 9), July 19, 2016, DOI 10.1186/s12859-016-1130-6. A shorter version appears in “Reference Sequence Selection for Motif Searches,” Proceedings of 2015 IEEE International Conference on Bioinformatics and Biomedicine (BIBM '15), Bethesda, MD, November 2015, 569-574.

  The planted $(\ell, d)$ motif search (PMS) is an important yet challenging problem in computational biology. Pattern-driven PMS algorithms usually use $k$ out of $t$ input sequences as reference sequences to generate candidate motifs, and they can find all the $(\ell, d)$ motifs in the input sequences. However, most of them simply take the first $k$ sequences in the input as reference sequences without elaborate selection processes, and thus they may exhibit sharp fluctuations in running time, especially for large alphabets.

  In this paper, we build the reference sequence selection problem and propose a method named RefSelect to quickly solve it by evaluating the number of candidate motifs for the reference sequences. RefSelect can bring a practical time improvement of the state-of-the-art pattern-driven PMS algorithms. Experimental results show that RefSelect (1) makes the tested algorithms solve the PMS problem steadily in an efficient way, (2) particularly, makes them achieve a speedup of up to about 100.

  The proposed algorithm RefSelect can be used to solve the problem that many pattern-driven PMS algorithms present execution time instability. RefSelect requires a small amount of storage space and is capable of selecting reference sequences efficiently and effectively. Also, the parallel version of RefSelect is provided for handling large data sets.

• X. Chen, H. Huo, J. Huan, J. S. Vitter, W. Zheng, and L. Zou. “MSQ-Index: A Succinct Index for Fast Graph Similarity Search,” IEEE Transactions on Knowledge and Data Engineering, November 20, 2019.

  Graph similarity search has received considerable attention in many applications, such as bioinformatics, data mining, pattern recognition, and social networks. Existing methods for this problem have limited scalability because of the huge amount of memory they consume when handling very large graph databases with millions or billions of graphs.

  In this paper, we study the problem of graph similarity search under the graph edit distance constraint. We present a space-efficient index structure based upon the q-gram tree that incorporates succinct data structures and hybrid encoding to achieve improved query time performance with minimal space usage. Specifically, the space usage of our index requires only 5%-15% of the previous state-of-the-art indexing size on the tested data while at the same time achieving 2-3 times acceleration in query time with small data sets. We also boost the query performance by augmenting the global filter with range search, which allows us to perform a query in a reduced region. In addition, we propose two effective filters that combine degree structures and label structures. Extensive experiments demonstrate that our proposed approach is superior in space and competitive in filtering to the state-of-the-art approaches. To the best of our knowledge, our index is the first in-memory index for this problem that successfully scales to cope with the large dataset of 25 million chemical structure graphs from the PubChem dataset.

• H. Huo, L. Chen, H. Zhao, J. S. Vitter, Y. Nekrich, and Q. Yu, “A Data-Aware FM-index,” Proceedings of the 17th Meeting on Algorithm Engineering and Experiments (ALENEX '15), San Diego, CA, January 2015.

  In this paper we present some practical modifications of the higher-order entropy-compressed text indexing method of Foschini et al. [6] based upon the Burrows-Wheeler transform and the FM-index. Our method, called FM-Adaptive, applies a wavelet tree to the entire BWT. It partitions each bit vector of nodes in the wavelet tree into blocks and applies the hybrid encoding along with run-length Gamma code rather than the fixed-length code of [14] to each block while explores data-aware compression. FM-Adaptive retains the theoretical performance of previous work and introduces some improvements in practice. At the same time, broad experiments indicate that our index achieves superior performance, especially in terms of compression, in comparison to the state-of-the-art indexing techniques. The source code is available online.

• H. Huo, Z. Sun, S. Li, J. S. Vitter, X. Wang, Q. Yu, and J. Huan. “CS2A: A Compressed Suffix Array-Based Method for Short Read Alignment,” IEEE Access, 5, March 14, 2017, 4551-4560, dx.doi.org/10.1109/ACCESS.2017.2682107.

  Next generation sequencing technologies generate enormous amount of short reads, which poses a significant computational challenge for short read alignment. Furthermore, because of sequence polymorphisms in a population, repetitive sequences, and sequencing errors, there still exist difficulties in correctly aligning all reads. We propose a space-efficient compressed suffix array-based method for short read alignment (CS2A) whose space achieves the high-order empirical entropy of the input string. Unlike BWA that uses two bits to represent a nucleotide, suitable for constant-sized alphabets, our encoding scheme can be applied to the string with any alphabet set. In addition, we present approximate pattern matching on compressed suffix array (CSA) for short read alignment. Our CS2A supports both mismatch and gapped alignments for single-end and paired-end reads mapping, being capable of efficiently aligning short sequencing reads to genome sequences. The experimental results show that CS2A can compete with the popular aligners in memory usage and mapping accuracy. The source code is available online.

• X. Chen, H. Huo, J. Huan, and J. S. Vitter. “Efficient Graph Similarity Search in External Memory,” IEEE Access, 5, March 14, 2017, 4551-4560, dx.doi.org/10.1109/ACCESS.2017.2682107.

  Many real-world applications, such as bioinformatics, data mining, pattern recognition, and social network analysis, benefit from efficient solutions for the graph similarity search problem. Existing methods have limited scalability when they handle the large graph databases, for example, those with millions or billions of graphs that cannot fit in main memory. In this paper, we study the problem of graph similarity search under the graph edit distance constraint in external memory. We present an efficient framework for arbitrary q-gram based representations of a graph. Specifically, we propose a q-gram matrix index stored in hybrid layout in external memory to achieve efficient query processing, by converting the q-gram counting filter into a sparse matrix-vector multiplication (SpMV) problem. Furthermore, we also boost the query performance by transforming the global filter to a two-dimensional query rectangle, which allows us to perform a query in a reduced region, significantly reducing the number of query I/Os in practice. Extensive experiments on real datastes confirm that: (1) our method can compete with the state-of-the-art in-memory methods in index size and filtering ability, and outperform them on scalability of coping with the PubChem dataset including 25 million chemical structure graphs. (2) compared with the popular q-gram-based external inverted index, our external index structure needs much fewer number of query I/Os on the PubChem dataset.

• Z. Sun, H. Huo, J. Huan, and J. S. Vitter. “Feature Reduction Based on Semantic Similarity for Graph Classification,” Neurocomputing, 397, 2020, 114-126, doi.org/10.1016/j.neucom.2020.02.047

  Classification and recognition of graph data are crucial problems in many fields, such as bioinformatics, chemoinformatics, and data mining. In graph kernel-based classification methods, the similarity among substructures is not fully considered; in addition, poorly discriminative substructures will affect the graph classification accuracy. To improve the graph classification accuracy, we propose a feature reduction algorithm based on semantic similarity for graph classification in this paper. In the algorithm, we first learn vector representations of subtree patterns using neural language models and then merge semantically similar subtree patterns into a new feature. We then provide a new feature discrimination score to select highly discriminative features. Comprehensive experiments on real datasets demonstrate that the proposed algorithm achieves a significant improvement in classification accuracy over compared graph classification methods.

• X. Chen, H. Huo, J. Huan, and J. S. Vitter. “An Efficient Algorithm for Graph Edit Distance Computation,” Knowledge-Based Systems, 163, January 2019, 762-775, doi.org10.1016j.knosys.2018.10.002. An implementation is available at github.com/Hongweihuo-Lab/BSS-GED. A summary appears in “Fast Computation of Graph Edit Distance,” ScienceTrends.com, April 17, 2019, sciencetrends.com/fast-computation-of-graph-edit-distance/.

  The graph edit distance (GED) is a well-established distance measure widely used in many applications, such as bioinformatics, data mining, pattern recognition, and graph classification. However, existing solutions for computing the GED suffer from several drawbacks: large search spaces, excessive memory requirements, and many expensive backtracking calls. In this paper, we present BSS GED, a novel vertexbased mapping method that calculates the GED in a reduced search space created by identifying invalid and redundant mappings. BSS GED employs the beam-stack search paradigm, a widely utilized search algorithm in AI, combined with two specially designed heuristics to improve the GED computation, achieving a trade-off between memory utilization and expensive backtracking calls. Through extensive experiments, we demonstrate that BSS GED is highly efficient on both sparse and dense graphs and outperforms the state-of-the-art methods. Furthermore, we apply BSS GED to solve the well-investigated graph similarity search problem. The experimental results show that this method is dozens of times faster than state-of-the-art graph similarity search methods.

  Keywords: Graph Edit Distance, Reduced Search Space, Beam-stack Search, Heuristics, Graph Similarity Search

• H. Huo, X. Chen, X. Guo, and J. S. Vitter. “Efficient Compression and Indexing for Highly Repetitive DNA Sequence Collections,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, January 2020.

  The development of the next-generation, high-throughput sequencing technologies dramatically reduces the cost of the next-generation sequencing (NGS) data production, thereby leading to the explosive growth in the NGS data.

  In this paper, we focus upon the important problem of indexing and searching highly repetitive DNA sequence collections. Given a collection $\ensuremath{\mathcal{G}}$ of $t$ sequences $\ensuremath{\mathcal{S}_i}$ of length $n$ each, we can represent $\ensuremath{\mathcal{G}}$ succinctly in $2nH_{k}(\ensuremath{\mathcal{T}}) + \ensuremath{\mathcal{O}}(n' {\log\log n}) + o(q n') + o(tn)$ bits using $\ensuremath{\mathcal{O}}(t n^{2} + q n')$ time, where $H_{k}(\ensuremath{\mathcal{T}})$ is the $k$th-order empirical entropy of the sequence  $\ensuremath{\mathcal{T}} \in \ensuremath{\mathcal{G}}$ that is used as the reference sequence, $n'$ is the total number of variations between  $\ensuremath{\mathcal{T}}$ and the sequences in  $\ensuremath{\mathcal{G}}$, and $q$ is a small fixed constant. We can restore the length-$\mathit{len}$ substring $\mathcal{S}[\mathit{sp} , \dots, \mathit{sp} + \mathit{len}-1]$ of $\mathcal{S} \in \mathcal{G}$ in $\mathcal{O}\bigl(n_{s}' + \mathit{len}(\log n)^{2} / {\log\log n}\bigr)$ time and report the $\mathit{occ}$ occurrences where $P$ occurs in $\mathcal{G}$ in $\mathcal{O}\bigl(m + \mathit{occ} \cdot t \cdot (\log n)^{2}/\log\log n \bigr)$ time. In addition, we propose a method to find the variations between $\mathcal{T}$ and the sequences in $\mathcal{G}$, with which we can build succinct structures to enable fast search. For highly repetitive sequences, experimental results on the tested data demonstrate that the proposed method has significant advantages in space usage and retrieval time over the current state-of-the-art methods.

  The source code is available online.

• S. Majhi, J. S. Vitter, and C. Wenk. “Approximating Gromov-Hausdorff Distance in Euclidean Spaces,”, submitted.

  The Gromov-Hausdorff distance ($d_{GH}$) proves to be a useful distance measure between shapes. In order to approximate $d_{GH}$ for compact subsets $X,Y \in \Re^d$, we look into its relationship with $d_{H, iso}$, the infimum Hausdorff distance under Euclidean isometries. As already known for dimension $d \geq 2$, the $d_{H, iso}$ cannot be bounded above by a constant factor times $d_{GH}$. For $d=1$, however, we prove that $d_{H, iso} \leq \frac54 d_{GH}$. We also show that the bound is tight. In effect, this gives rise to an $O(n \log n)$-time algorithm to approximate $d_{GH}$ with an approximation factor of $(1+ \frac14)$.