The proliferation of online graph data - such as produced on social networks, citation networks, and online graph databases - calls for space-efficient graph indexing methods that support fast graph queries and graph analytics. Labeled property multidigraphs as a model of representing complicated graph data are widely used in practice. However, the fundamental problem of compressing and indexing labeled property multidigraphs has remained unsolved. In this paper, we focus on the static data case and propose a novel self-index, called CGraphIndex, to compress and index labeled property multidigraphs that for the first time achieves the high-order entropy space for multidigraph properties (the dominant term in practice) and the 1st-order graph entropy for multidigraph structures. A self-index actually encodes the original input and thus there is no need to store the input separately. CGraphIndex supports fundamental and navigational operations on the structures and on the properties in constant time, and supports fast property extraction on vertices and edges. Our experimental results on the large LDBC SNB benchmarks demonstrate that CGraphIndex outperforms the popular graph database systems (Community Editions), generally several times to orders of magnitude faster in query time and several times less in space usage for the compared interactive complex queries, business intelligence queries, as well as typical graph analytics BFS and PageRank.

The ranked (or top- k ) document retrieval problem is defined as follows: preprocess a collection {T 1 ,T 2 ,… ,T d } of d strings (called documents) of total length n into a data structure, such that for any given query (P,k) , where P is a string (called pattern) of length p ≥ 1 and k ∈ [1,d] is an integer, the identifiers of those k documents that are most relevant to P can be reported, ideally in the sorted order of their relevance. The seminal work by Hon et al. [FOCS 2009 and Journal of the ACM 2014] presented an O(n) -space (in words) data structure with O(p+k log k) query time. The query time was later improved to O(p+k) [SODA 2012] and further to O(p/ log σn+k ) [SIAM Journal on Computing 2017] by Navarro and Nekrich, where σ is the alphabet size. We revisit this problem in the external memory model and present three data structures. The first one takes O(n) -space and answer queries in O(p/B + log B n + k/B+ log * (n/B) ) I/Os, where B is the block size. The second one takes O(n log * (n/B) ) space and answer queries in optimal O(p/B + log B n + k/B) I/Os. In both cases, the answers are reported in the unsorted order of relevance. To handle sorted top- k document retrieval, we present an O(n log (d/B)) space data structure with optimal query cost.

Compressed self-indexes are used widely in string processing applications, such as information retrieval, genome analysis, data mining, and web searching. The index not only indexes the data, but also encodes the data, and it is in compressed form. Moreover, the index and the data it encodes can be operated upon directly, without need to uncompress the entire index, thus saving time while maintaining small storage space. In some applications, such as in genome analysis, existing methods do not exploit the full possibilities of compressed self-indexes, and thus we seek faster and more space-efficient indexes. In this paper, we propose a practical high-order entropy-compressed self-index for efficient pattern matching in a text. We give practical implementations of compressed suffix arrays using a hybrid encoding in the representation of the neighbor function . We analyze the performance in theory and practice of our recommended indexing method, called GeCSA. We can improve retrieval time further using an iterated version of the neighbor function. Experimental results on the tested data demonstrate that the proposed index GeCSA has good overall advantages in space usage and retrieval time over the state-of-the-art indexing methods, especially on the repetitive data.

MOTIVATION: Ultrahigh-throughput next-generation sequencing instruments continue to generate vast amounts of genomic data. These data are generally stored in FASTQ format. Two important simultaneous goals are space-efficient compressed storage of the genomic data and fast query performance. Toward that end, we introduce compressed indexing to store and retrieve FASTQ files. RESULTS: We propose a compressed index for FASTQ files called CIndex. CIndex uses the Burrows-Wheeler transform and the wavelet tree, combined with hybrid encoding, succinct data structures and tables REF and Rγ, to achieve minimal space usage and fast retrieval on the compressed FASTQ files. Experiments conducted over real publicly available datasets from various sequencing instruments demonstrate that our proposed index substantially outperforms existing state-of-the-art solutions. For count, locate and extract queries on reads, our method uses 2.7-41.66% points less space and provides a speedup of 70-167.16 times, 1.44-35.57 times and 1.3-55.4 times. For extracting records in FASTQ files, our method uses 2.86-14.88% points less space and provides a speedup of 3.13-20.1 times. CIndex has an additional advantage in that it can be readily adapted to work as a general-purpose text index; experiments show that it performs very well in practice. AVAILABILITY AND IMPLEMENTATION: The software is available on Github: https://github.com/Hongweihuo-Lab/CIndex. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In this paper, we focus upon the important problem of indexing and searching highly repetitive DNA sequence collections. Given a collection$\mathcal {G}$of$t$sequences$\mathcal {S}_{i}$of length$n$each, we can represent$\mathcal {G}$succinctly in$2n\mathcal {H}_{k}(\mathcal {T}) + \mathcal {O}(n^{\prime }\ {\log \log n}) + o(q n^{\prime }) + o(tn)$bits using$\mathcal {O}(t n^{2} + q n^{\prime })$time, where$\mathcal {H}_{k}(\mathcal {T})$is the$k$th-order empirical entropy of the sequence$\mathcal {T} \in \mathcal {G}$that is used as the reference sequence,$n^{\prime }$is the total number of variations between$\mathcal {T}$and the sequences in$\mathcal {G}$, and$q$is a small fixed constant. We can restore any length$ {len}$substring$\mathcal {S}[ {sp}, \dots, {sp} + {len}-1]$of$\mathcal {S} \in \mathcal {G}$in$\mathcal {O}\bigl (n_{s}^{\prime } + {len}(\log n)^{2} / {\log \log n}\bigr)$time and report all positions where$P$occurs in$\mathcal {G}$in$\mathcal {O}\bigl (m \cdot t + {occ} \cdot t \cdot (\log n)^{2}/\log \log n \bigr)$time. In addition, we propose a dynamic programming method to find the variations between$\mathcal {T}$and the sequences in$\mathcal {G}$in a space-efficient way, with which we can build succinct structures to enable efficient 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.

Graph similarity search under the graph edit distance constraint 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 tens of millions of graphs. In this article, we present a succinct index 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 percent of the previous state-of-the-art indexing size while at the same time achieving several times acceleration in query time on the tested data. We also improve the query performance by augmenting the global filter with range searching, which allows us to perform similarity search in a reduced region. In addition, we propose two effective lower bounds together with a boosting technique to obtain the smallest possible candidate set. Extensive experiments demonstrate that our proposed approach is superior both in space and 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. The source code is available online.

Chien et al. [1, 2] introduced the geometric Burrows-Wheeler transform (GBWT) as the first succinct text index for I/O-efficient pattern matching in external memory; it operates by transforming a text T into point set S in the two-dimensional plane. In this paper we introduce a practical succinct external memory text index, called mKD-GBWT. We partition S into σ2subregions by partitioning the x-axis into σ intervals using the suffix ranges of characters of T and partitioning the y-axis into σ intervals using characters of T, where σ is the alphabet size of T. In this way, we can represent a point using fewer bits and perform a query in a reduced region so as to improve the space usage and I/Os of GBWT in practice. In addition, we plug a crit-bit tree into each node of string B-trees to represent variable-length strings stored. Experimental results show that mKD-GBWT provides significant improvement in space usage compared with the state-of-the-art indexing techniques. The source code is available online [3].

Next generation sequencing technologies generate normous 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.

BACKGROUND: The planted (l, 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 (l, 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. RESULTS: 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× on the protein data, and (3) is also suitable for large data sets which contain hundreds or more sequences. CONCLUSIONS: 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.

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.

The planted (l, d) motif search (PMS) is an important yet challenging problem in computational biology. Patterndriven PMS algorithms usually use k out of t input sequences as reference sequences to generate candidate motifs, and they can find all the (l, 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× on the protein data, and (3) is also suitable for large data sets which contain hundreds or more sequences.

In the dynamic indexing problem, we must maintain a changing collection of text documents so that we can efficiently support insertions, deletions, and pattern matching queries. We are especially interested in developing efficient data structures that store and query the documents in compressed form. All previous compressed solutions to this problem rely on answering rank and select queries on a dynamic sequence of symbols. Because of the lower bound in [Fredman and Saks, 1989], answering rank queries presents a bottleneck in compressed dynamic indexing. In this paper we show how this lower bound can be circumvented using our new framework. We demonstrate that the gap between static and dynamic variants of the indexing problem can be almost closed. Our method is based on a novel framework for adding dynamism to static compressed data structures. Our framework also applies more generally to dynamizing other problems. We show, for example, how our framework can be applied to develop compressed representations of dynamic graphs and binary relations.

In recent years, there has been an increasing interest in planted (l, 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 is recently introduced to search motifs on large-alphabet inputs. A motif stem is an l-length string with some wildcards. The goal of the MSS problem is to find a set of stems that represents a superset of all (l , 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 MSS algorithms, StemFinder runs much faster and reports fewer stems which represent a smaller superset of all (l, d) motifs. StemFinder is freely available at http://sites.google.com/site/feqond/stemfinder.

The planted (l, 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 (l, 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 (l, 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 (l, d) motifs efficiently and effectively in thousands to millions of input sequences, and runs faster than the state-of-the-art (l, 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.

In this paper we develop a simple and practical text indexing scheme for compressed suffix arrays (CSA). For a text of n characters, our CSA can be constructed in linear time and needs 2nHk+ n + o(n) bits of space for any k ≤ clogσn - 1 and any constant ckdenotes the kth order entropy. We compare the performance of our method with two established compressed indexing methods, the FM-index and the Sad-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.

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.

In this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. For a constant size alphabet our data structure uses O(n.log^e(n)) bits for any e>0 and reports all occ occurrences of a wildcard string in O(m+s^g.M(n)+occ) time, where M(n)=o(log(log(log(n)))), s 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+s^g+occ).log^e(n)) query time and an O(n{log(log(n))}^2)-bit index with O((m+s^g+occ).log(log(n))) query time. These are the first non-trivial data structures for this problem that need o(n.log(n)) bits of space.

The inverted index is the backbone of modern web search engines. For each word in a collection of web documents, the index records the list of documents where this word occurs. Given a set of query words, the job of a search engine is to output a ranked list of the most relevant documents containing the query. However, if the query consists of an arbitrary string—which can be a partial word, multiword phrase, or more generally any sequence of characters—then word boundaries are no longer relevant and we need a different approach. In string retrieval settings, we are given a set D ={ d 1 , d 2 , d 3 , …, d D } of D strings with n characters in total taken from an alphabet set Σ = [σ], and the task of the search engine, for a given query pattern P of length p , is to report the “most relevant” strings in D containing P . The query may also consist of two or more patterns. The notion of relevance can be captured by a function score ( P , d r ), which indicates how relevant document d r is to the pattern P . Some example score functions are the frequency of pattern occurrences, proximity between pattern occurrences, or pattern-independent PageRank of the document. The first formal framework to study such kinds of retrieval problems was given by Muthukrishnan [SODA 2002]. He considered two metrics for relevance: frequency and proximity. He took a threshold-based approach on these metrics and gave data structures that use O ( n log n ) words of space. We study this problem in a somewhat more natural top- k framework. Here, k is a part of the query, and the top k most relevant (highest-scoring) documents are to be reported in sorted order of score. We present the first linear-space framework (i.e., using O ( n ) words of space) that is capable of handling arbitrary score functions with near-optimal O ( p + k log k ) query time. The query time can be made optimal O ( p + k ) if sorted order is not necessary. Further, we derive compact space and succinct space indexes (for some specific score functions). This space compression comes at the cost of higher query time. At last, we extend our framework to handle the case of multiple patterns. Apart from providing a robust framework, our results also improve many earlier results in index space or query time or both.

Motif stem search (MSS) is a recent motif search problem to search motifs on large-alphabet inputs. A motif stem is an l-length string with some wildcards. The goal of the MSS problem is to find a set of stems that represents a superset of all (l, d) motifs present in the input sequences. 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 new method for generating all possible motif stems. (3) We propose an efficient 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 representing a smaller superset of all (l, d) motifs.

Let D = {d1, d2,...dD} be a given collection of D string documents of total length n, our task is to index D, such that whenever a pattern P (of length p) and an integer k come as a query, those k documents in which P appears the most number of times can be listed efficiently. In this paper, we propose a compressed index taking 2|CSA| + D logn/D + O(D) + o(n) bits of space, which answers a query with O(tsalog k logϵn) per document report time. This improves the O(tsalog k log1+ϵn) per document report time of the previously best-known index with (asymptotically) the same space requirements [Belazzougui and Navarro, SPIRE 2011]. Here, |CSA| represents the size (in bits) of the compressed suffix array (CSA) of the text obtained by concatenating all documents in V, and tsais the time for decoding a suffix array value using the CSA.

We describe recent breakthroughs in the field of compressed data structures, in which the data structure is stored in a compressed representation that still allows fast answers to queries. We focus in particular on compressed data structures to support the important application of pattern matching on massive document collections. Given an arbitrary query pattern in textual form, the job of the data structure is to report all the locations where the pattern appears. Another variant is to report all the documents that contain at least one instance of the pattern. We are particularly interested in reporting only the most relevant documents, using a variety of notions of relevance. We discuss recently developed techniques that support fast search in these contexts as well as under additional positional and temporal constraints.

This study explores an alternative way of storing text files to answer exact match queries faster. We decompose the original file into two parts as filter and payload. The filter part contains the most informative k bits of each byte, and the remaining bits of the bytes are concatenated in the order of appearance to generate the payload. We refer to this structure as k-bit filtered format. When an input pattern is to be searched on the k-bit filtered structure, the same decomposition is performed on the pattern. The k bits from each byte of the pattern form the pattern filter bit sequence, and the rest is the payload. The pattern filter is first scanned on the filter part of the file. At each match position detected in the filter part, the pattern payload is verified against the corresponding location in the payload part of the text. Thus, instead of searching an m-byte pattern on an n-byte text, first k·m bits are scanned on k·n bits, followed by a verification of (8 − k)·m bits on the respective locations of the matching positions. Experiments conducted on natural language texts, plain ASCII DNA sequences and random byte sequences showed that the search performance with the proposed scheme is on average two times faster than the tested best exact pattern-matching algorithms. The highest gain is obtained on plain ASCII DNA sequences. We also developed an effective bitwise pattern-matching algorithm of possible independent interest within this study.

Finding repetitive structures in genomes and proteins is important to understand their biological functions. Many data compressors for modern genomic sequences rely heavily on finding repeats in the sequences. Small-scale and local repetitive structures are better understood than large and complex interspersed ones. The notion of maximal repeats captures all the repeats in the data in a space-efficient way. Prior work on maximal repeat finding used either a suffix tree or a suffix array along with other auxiliary data structures. Their space usage is 19-50 times the text size with the best engineering efforts, prohibiting their usability on massive data such as the whole human genome. We focus on finding all the maximal repeats from massive texts in a time- and space-efficient manner. Our technique uses the Burrows-Wheeler Transform and wavelet trees. For data sets consisting of natural language texts and protein data, the space usage of our method is no more than three times the text size. For genomic sequences stored using one byte per base, the space usage of our method is less than double the sequence size. Our space-efficient method keeps the timing performance fast. In fact, our method is orders of magnitude faster than the prior methods for processing massive texts such as the whole human genome, since the prior methods must use external memory. For the first time, our method enables a desktop computer with 8 GB internal memory (actual internal memory usage is less than 6 GB) to find all the maximal repeats in the whole human genome in less than 17 hours. We have implemented our method as general-purpose open-source software for public use.

Given a set D of d patterns of total length n, the dictionary matching problem is to index D such that for any query text T, we can locate the occurrences of any pattern within T efficiently. This problem can be solved in optimal O(|T|+occ) time by the classical AC automaton (Aho and Corasick, 1975) where occ denotes the number of occurrences. The space requirement is O(n) words. In the {approximate} dictionary matching problem with one error, we consider a substring of T[i..j] an occurrence of P whenever the edit distance between T[i..j] and P is at most one. For this problem, the best known indexes are by Cole et al. (2004), which requires O(n+ d\log{d}) words of space and reports all occurrences in O(|T|\log{d}\log{\log{d}}+occ) time, and by Ferragina et al. (1999), which requires O(n^{1+\epsilon}) words of space and reports all occurrences in O(|T|\log\log n + occ) time. Recently, there have been successes in compressing the dictionary matching index while keeping the query time optimal (Belazzougui, 2010, Hon et al., 2010). However, a compressed index for approximate dictionary matching problem is still open. In this paper, we propose the first such index which requires an optimal nH_k+O(n)+o(n\log\sigma)-bit index space, where H_k denotes the kth-order empirical entropy of \D, and \sigma is the size of alphabet set from which all the characters in \D and T are drawn. The query time of our index is O(σ|T|log3n log \ log n + occ).

Inverted indexes are the most fundamental and widely used data structures in information retrieval. For each unique word occurring in a document collection, the inverted index stores a list of the documents in which this word occurs. Compression techniques are often applied to further reduce the space requirement of these lists. However, the index has a shortcoming, in that only predefined pattern queries can be supported efficiently. In terms of string documents where word boundaries are undefined, if we have to index all the substrings of a given document, then the storage quickly becomes quadratic in the data size. Also, if we want to apply the same type of indexes for querying phrases or sequence of words, then the inverted index will end up storing redundant information. In this paper, we show the first set of inverted indexes which work naturally for strings as well as phrase searching. The central idea is to exclude document d in the inverted list of a string P if every occurrence of P in d is subsumed by another string of which P is a prefix. With this we show that our space utilization is close to the optimal. Techniques from succinct data structures are deployed to achieve compression while allowing fast access in terms of frequency and document id based retrieval. Compression and speed trade-offs are evaluated for different variants of the proposed index. For phrase searching, we show that our indexes compare favorably against a typical inverted index deploying position-wise intersections. We also show efficient top-k based retrieval under relevance metrics like frequency and tf-idf.

Finding repetitive structures in genomes is important to understand their biological functions. Many modern genomic sequence data compressors also highly rely on finding the repeats over the sequences. The notion of maximal repeats captures all the repeats in a space-efficient way. Prior works on maximal repeat finding used either a suffix tree or a suffix array along with other auxiliary data structures. Their space usage is 19-50 times as large as the text size with the best engineering efforts, prohibiting their usability on massive data such as the whole human genome. Our technique is based on the Burrows-Wheeler Transform and wavelet trees. For genomic sequences stored using one byte per base, the space usage of our method is less than double of the sequence size. Our space-efficient method keeps the timing performance fast. In fact, our method is orders of magnitude faster than the prior methods for processing massive texts such as the whole human genome, since the prior methods must use external memory. For the first time, our method enables a normal computer with 8GB internal memory (actual internal memory usage is less than 6GB) to find all the maximal repeats in the whole human genome in less than 17 hours.

We concentrate on indexing DNA sequences via sparse suffix arrays (SSAs) and propose a new short read aligner named PSI-RA (parallel sparse index read aligner). The motivation in using SSAs is the ability to trade memory against time. It is possible to 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 on exact matching of short reads, an elegant way of approximate matching capability was missing. We provide this by defining the right-most mismatch criteria that prioritizes the errors towards the end of the reads since it is known that the errors are more probable at that area. 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 genome with SSA is a good alternative to Burrows-Wheeler transform or seed based solutions.

Pattern matching on text data has been a fundamental field of Computer Science for nearly 40 years. Databases supporting full-text indexing functionality on text data are now widely used by biologists. In the theoretical literature, the most popular internal-memory index structures are the suffix trees and the suffix arrays, and the most popular external-memory index structure is the string B-tree. However, the practical applicability of these indexes has been limited mainly because of their space consumption and I/O issues. These structures use a lot more space (almost 20 to 50 times more) than the original text data and are often disk-resident. Ferragina and Manzini (2005) and Grossi and Vitter (2005) gave the first compressed text indexes with efficient query times in the internal-memory model. Recently, Chien et al (2008) presented a compact text index in the external memory based on the concept of Geometric Burrows-Wheeler Transform. They also presented lower bounds which suggested that it may be hard to obtain a good index structure in the external memory. In this paper, we investigate this issue from a practical point of view. On the positive side we show an external-memory text indexing structure (based on R-trees and KD-trees) that saves space by about an order of magnitude as compared to the standard String B-tree. While saving space, these structures also maintain a comparable I/O efficiency to that of String B-tree. We also show various space vs I/O efficiency trade-offs for our structures.

Given a set D={d1, d2,..., dD} 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 in while maintaining optimal query performance. We also develop compressed variants of these data structures for several specific relevance metrics.

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 [16]? We also introduce a reverse transform, called Points2Text; which converts a set of points into text. This transform allows us to derive the first 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.

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 |T| Hk(T) + o (|T| log sigma) bits, where Hk(T) denotes the kth-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 existingO(n)-word index to an (n Hk(D) + o(n log sigma))-bit index with only a small sacrifice in search time.

Run-Length-Encoding (RLE) is a data compression technique that is used in various applications, e.g., time series, biological sequences, and multimedia databases. One of the main challenges is how to operate on (e.g., index, search, and retrieve) compressed data without decompressing it. In this paper, we introduce 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 [7]. The SBC-tree supports pattern matching queries such as substring matching, 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. Substring matching, prefix matching, and range search execute in an optimal O(logB N + |p|+T/B) I/O operations, where |p| is the length of the compressed query pattern and T is the query output size. The SBC-tree is also dynamic and supports insert and delete operations efficiently. The insertion and deletion of all suffixes of a compressed sequence of length m take O(m logB(N + m)) amortized I/O operations. The SBC-tree index is realized inside PostgreSQL. Performance results illustrate that using the SBC-tree to index RLE-compressed sequences achieves up to an order of magnitude reduction in storage, while retains the optimal search performance achieved by the String B-tree over the uncompressed sequences.

Current data structures for searching large string collections either fail to achieve minimum space or 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 compressed. We provide new insights on front coding [24], introduce 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. Our second contribution is a novel dictionary encoding scheme that builds upon such linearizations and 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 [2, 5] and obtain a succinct variant whose space is close to the information-theoretic minimum.

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 Σ =(b1,b2,...,bn) where each block bi 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 [18, 12, 13, 26]. Note that this problem is non-trivial even if all requests in Σ are unique. This restricted version is called read-once. Despite the progress in the offline version [13, 15] and read-once version [12], 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.

In many applications data values are inherently uncertain. This includes moving-objects, sensors and biological databases. There has been recent interest in the development of database management systems that can handle uncertain data. Some proposals for such systems include attribute values that are uncertain. In particular, an attribute value can be modeled as a range of possible values, associated with a probability density function. Previous efforts for this type of data have only addressed 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 join queries over uncertain data. We propose a semantics for the join operation, define probabilistic operators over uncertain data, and propose join algorithms that provide efficient execution of probabilistic joins. The paper focuses on an important class of joins termed probabilistic threshold joins that avoid some of the semantic complexities of dealing with uncertain data. For this class of joins we develop three sets of optimization techniques: item-level, page-level, and index-level pruning. 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.

We propose measures for compressed data structures, in which space usage is measured in a data-aware manner. In particular, we consider the fundamental dictionary problem on set data, where the task is to construct a data structure to represent a set S of n items out of a universe U = {0,..., u $1} and support various queries on S. We use a well-known data-aware measure for set data called gap to bound the space of our data structures. We describe a novel dictionary structure taking gap+O(n log(u/n)/ log n)+O(n log log(u/n)) bits. Under the RAM model, our dictionary supports membership, rank, select, and predecessor queries in nearly optimal time, matching the time bound of Andersson and Thorup's predecessor structure (2000), while simultaneously improving upon their space usage. Our dictionary structure uses exactly gap bits in the leading term (i.e., the constant factor is 1) and answers queries in near-optimal time. When seen from the worst case perspective, we present the first O(n log(u/n))-bit dictionary structure which supports these queries in near-optimal time under RAM model. We also build a dictionary which requires the same space and supports membership, select, and partial rank queries even more quickly in O(loglogn) time. To the best of our knowledge, this is the first of a kind result which achieves data-aware space usage and retains near-optimal time.

Parallel independent disks can enhance the performance of external memory (EM) algorithms, but the programming task is often difficult. Each disk can service only one read or write request at a time; the challenge is to keep the disks as busy as possible. In this article, we develop a randomized allocation discipline for parallel independent disks, called randomized cycling . We show how it can be used as the basis for an efficient distribution sort algorithm, which we call randomized cycling distribution sort (RCD). We prove that the expected I/O complexity of RCD is optimal. The analysis uses a novel reduction to a scenario with significantly fewer probabilistic interdependencies. We demonstrate RCD's practicality by experimental simulations. Using the randomized cycling discipline, algorithms developed for the unrealistic multihead disk model can be simulated on the realistic parallel disk model for the class of multipass algorithms, which make a complete pass through their data before accessing any element a second time. In particular, algorithms based upon the well-known distribution and merge paradigms of EM computation can be optimally extended from a single disk to parallel disks.

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, which 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.

We report on a new experimental analysis of high-order entropy-compressed suffix arrays, which retains the theoretical performance of previous work and represents an improvement in practice. Our experiments indicate that the resulting text index offers state-of-the-art compression. In particular, we require roughly 20% of the original text size---without requiring a separate instance of the text. We can additionally use a simple notion to encode and decode block-sorting transforms (such as the Burrows--Wheeler transform), achieving a compression ratio comparable to that of bzip2. We also provide a compressed representation of suffix trees (and their associated text) in a total space that is comparable to that of the text alone compressed with gzip.

Rank-aware query processing has emerged as a key requirement in modern applications. In these applications, efficient and adaptive evaluation of top-kqueries 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-kqueries 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-kquery 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.

We consider the natural extension of the single disk caching problem to parallel disk I/O model. We close the existing gap between lower and upper bounds and achieve optimal competitive ratio of O(√D) when lookahead is more than the memory size M. When lookahead is smaller, we derive various upper bounds and lower bounds on the competitive ratio under various adversarial models.

The proliferation of online text, such as found on the World Wide Web and in online databases, motivates the need for space-efficient text indexing methods that support fast string searching. We model this scenario as follows: Consider a text T consisting of n symbols drawn from a fixed alphabet $\Sigma$. The text T can be represented in $n \lg |\Sigma|$ bits by encoding each symbol with $\lg |\Sigma|$ bits. The goal is to support fast online queries for searching any string pattern P of m symbols, with T being fully scanned only once, namely, when the index is created at preprocessing time. The text indexing schemes published in the literature are greedy in terms of space usage: they require $\Omega(n \lg n)$ additional bits of space in the worst case. For example, in the standard unit cost RAM, suffix trees and suffix arrays need $\Omega(n)$ memory words, each of $\Omega(\lg n)$ bits. These indexes are larger than the text itself by a multiplicative factor of $\Omega(\smash{\lg_{|\Sigma|} n})$, which is significant when $\Sigma$ is of constant size, such as in \textsc{ascii} or \textsc{unicode}. On the other hand, these indexes support fast searching, either in $O(m \lg |\Sigma|)$ time or in $O(m +\lg n)$ time, plus an output-sensitive cost $O(\mathit{occ})$ for listing the $\mathit{occ}$ pattern occurrences. We present a new text index that is based upon compressed representations of suffix arrays and suffix trees. It achieves a fast $\smash{O(m /\lg_{|\Sigma|} n + \lg_{|\Sigma|}^\epsilon n)}$ search time in the worst case, for any constant $0 < \epsilon \leq 1$, using at most $\smash{\bigl(\epsilon^{-1} + O(1)\bigr) \, n \lg |\Sigma|}$ bits of storage. Our result thus presents for the first time an efficient index whose size is provably linear in the size of the text in the worst case, and for many scenarios, the space is actually sublinear in practice. As a concrete example, the compressed suffix array for a typical 100 MB \textsc{ascii} file can require 30--40 MB or less, while the raw suffix array requires 500 MB. Our theoretical bounds improve \emph{both} time and space of previous indexing schemes. Listing the pattern occurrences introduces a sublogarithmic slowdown factor in the output-sensitive cost, giving $O(\mathit{occ} \, \smash{\lg_{|\Sigma|}^\epsilon n})$ time as a result. When the patterns are sufficiently long, we can use auxiliary data structures in $O(n \lg |\Sigma|)$ bits to obtain a total search bound of $O(m /\lg_{|\Sigma|} n + \mathit{occ})$ time, which is optimal.

We investigate the problem of smoothing multiplexed network traffic when either a streaming server transmits data to multiple clients or a storage server accesses data from multiple storage devices or other servers. We introduce efficient algorithms for lexicographically optimally smoothing the aggregate bandwidth requirements over a shared network link. Possible applications include improvement in the bandwidth utilization of network links and reduction in the energy consumption of server hosts. In the data transmission problem, we consider the case in which the clients have different buffer capacities and unlimited bandwidth constraints or unlimited buffer capacities and different bandwidth constraints. For the data access problem, we handle the general case of a shared buffer capacity and individual network bandwidth constraints. Previous approaches for the data access problem handled either the case of only a single stream or did not compute the lexicographically optimal schedule. By provably minimizing the variance of the required aggregate bandwidth, lexicographically optimal smoothing makes the maximum resource requirements within the network more predictable and increases the useful resource utilization. It also improves fairness in sharing a network link among multiple users and makes new requests from future clients more likely to be successfully admitted without the need for rescheduling previously accepted traffic. With appropriate hardware and system support, data traffic smoothing can also reduce the energy consumption of the host processor and the communication links. Overall, we expect that efficient resource management at the network edges will better meet quality of service requirements without restricting the scalability of the system.

We report on a simple encoding format called wzip for decompressing block-sorting transforms, such as the Burrows-Wheeler transform (BWT). Our compressor uses the simple notions of gamma encoding and RLE, organized with a wavelet tree, to achieve a slightly better compression ratio than bzip2 in less time. In fact, our compression/decompression time is dependent on H/sub h/, the hth order empirical entropy. This relationship of performance to the compressibility of data is a key new idea among compression algorithms. Another key contribution of our compressor is its simplicity. Our compressor can also operate as a full-text index with a small amount of data, while still preserving backward compatibility with just the compressor.

The emergence of extensible index structures, e.g., GiST (generalized search tree) [J.M. Hellerstein et al. (1995)] and SP-GiST (space-partitioning generalized search tree) [W. G Aref et al., (2001)], 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.

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.

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(√(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 Ω(≾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 Θ(≾MD/L) can be achieved. This problem generalizes the well-known paging problem on a single disk to the parallel disk model.

Recent work on incremental crawling has enabled the indexed document collection of a search engine to be more synchronized with the changing World Wide Web. However, this synchronized collection is not immediately searchable, because the keyword index is rebuilt from scratch less frequently than the collection can be refreshed. An inverted index is usually used to index documents crawled from the web. Complete index rebuild at high frequency is expensive. Previous work on incremental inverted index updates have been restricted to adding and removing documents. Updating the inverted index for previously indexed documents that have changed has not been addressed.In this paper, we propose an efficient method to update the inverted index for previously indexed documents whose contents have changed. Our method uses the idea of landmarks together with the diff algorithm to significantly reduce the number of postings in the inverted index that need to be updated. Our experiments verify that our landmark-diff method results in significant savings in the number of update operations on the inverted index.

In this paper we present the external interval tree, an optimal external memory data structure for answering stabbing queries on a set of dynamically maintained intervals. The external interval tree can be used in an optimal solution to the dynamic interval management problem, which is a central problem for object-oriented and temporal databases and for constraint logic programming. Part of the structure uses a weight-balancing technique for efficient worst-case manipulation of balanced trees, which is of independent interest. The external interval tree, as well as our new balancing technique, have recently been used to develop several efficient external data structures.

One approach to high-performance processing of massive data sets is to incorporate computation into storage systems. Previous work has shown that this active storage model is effective for a variety of problems. This paper explores opportunities to use active storage as a basis for exploiting asymmetric parallelism in applications using a streaming computation model on collections of fixed-size records. This model is the basis for much of the research in I/O-efficient algorithms, which deals with an important class of massive data problems not studied in previous work on active storage. We present an extension of a streaming computation model for an external memory toolkit to support a flexible mapping of computations to storage-based processors. Our approach enables load-managed active storage: it exposes parallelism, ordering constraints, and primitive computation units to the system, which can configure the application to balance load and make the best use of available processing power Emulation results from a sorting application demonstrate the potential of dynamic adaptation in load-managed active storage.

We investigate the problem of smoothing multiplexed network traffic, when either a streaming server transmits data to multiple clients, or a server accesses data from multiple storage devices or other servers. We introduce efficient algorithms for lexicographically optimally smoothing the aggregate bandwidth requirements over a shared network link. In the data transmission problem, we consider the case in which the clients have different buffer capacities but no bandwidth constraints, or no buffer capacities but different bandwidth constraints. For the data access problem, we handle the general case of a shared buffer capacity and individual network bandwidth constraints. Previous approaches in the literature for the data access problem handled either the case of only a single stream or did not compute the lexicographically optimal schedule.Lexicographically optimal smoothing (lexopt smoothing) has several advantages. By provably minimizing the variance of the required aggregate bandwidth, maximum resource requirements within the network become more predictable, and useful resource utilization increases. Fairness in sharing a network link by multiple users can be improved, and new requests from future clients are more likely to be successfully admitted without the need for frequently rescheduling previously accepted traffic. Efficient resource management at the network edges can better meet quality of service requirements without restricting the scalability of the system.

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 prefetching plus caching, where 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 mergesort, addressing a question that had been open for some time.

No abstract available.

The proliferation of online text, such as on the World Wide Web and in databases, motivates the need for space-efficient index methods that support fast search. Consider a text T of n binary symbols to index. Given any query pattern P of m binary symbols, the goal is to search for P in T quickly, with T being fully scanned only once, namely, when the index is created. All indexing schemes published in the last thirty years support searching in \\Theta(m) worst-case time and require \\Theta(n) memory words (or \\Theta(n log n) bits), which is significantly larger than the text itself. In this paper we provide a breakthrough both in searching time and index space under the same model of computation as the one adopted in previous work. Based upon new compressed representations of suffix arrays and suffix trees, we construct an index structure that occupies only O(n) bits and compares favorably with inverted lists in space. We can search any binary pattern P , stored in O(m= log n) words, in only o(m) time. Specifically, searching takes O(1) time for m = o(log n), and O(m= log n + log ffl n) = o(m) time for m =\\Omega\\Gamma239 n) and any fixed 0 ! ffl ! 1. That is, we achieve optimal O(m= log n) search time for sufficiently large m =\\Omega\\Gamma206 1+ffl n). We can list all the occ pattern occurrences in optimal O(occ) additional time when m = \\Omega\\Gamma1 olylog(n)) or when occ = \\Omega\\Gamma n ffl ); otherwise, listing takes O(occ log ffl n) additional time.

We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in ${\Bbb R}^3$ such that the aspect ratio of each rectangle in S is at most $\alpha$, for some constant $\alpha \geq 1$. We present an $n2^{O(\sqrt{\log n})}$-time algorithm to build a binary space partition of size $n2^{O(\sqrt{\log n})}$ for S. We also show that if m of the n rectangles in S have aspect ratios greater than $\alpha$, we can construct a BSP of size $n\sqrt{m}2^{O(\sqrt{\log n})}$ for S in $n\sqrt{m}2^{O(\sqrt{\log n})}$ time. The constants of proportionality in the big-oh terms are linear in $\log \alpha$. We extend these results to cases in which the input contains nonorthogonal or intersecting objects.

We propose a provably efficient application-controlled global strategy for organizing a cache of size k shared among P application processes. Each application has access to information about its own future page requests, and by using that local information along with randomization in the context of a global caching algorithm, we are able to break through the conventional $H_k \sim \ln k$ lower bound on the competitive ratio for the caching problem. If the P application processes always make good cache replacement decisions, our online application-controlled caching algorithm attains a competitive ratio of $2H_{P-1}+2 \sim 2 \ln P$. Typically, P is much smaller than k, perhaps by several orders of magnitude. Our competitive ratio improves upon the 2P+2 competitive ratio achieved by the deterministic application-controlled strategy of Cao, Felten, and Li. We show that no online application-controlled algorithm can have a competitive ratio better than min{H P-1 ,H k }, even if each application process has perfect knowledge of its individual page request sequence. Our results are with respect to a worst-case interleaving of the individual page request sequences of the P application processes. We introduce a notion of fairness in the more realistic situation when application processes do not always make good cache replacement decisions. We show that our algorithm ensures that no application process needs to evict one of its cached pages to service some page fault caused by a mistake of some other application. Our algorithm not only is fair but remains efficient; the global paging performance can be bounded in terms of the number of mistakes that application processes make.

External Memory algorithms play a key role in database management systems and large scale processing systems. External memory algorithms are typically tuned for efficient performance given a fixed, statically allocated amount of internal memory. However, with the advent of real-time database system and database systems based upon administratively defined goals, algorithms must increasingly be able to adapt in an online manner when the amount of internal memory allocated to them changes dynamically and unpredictably. In this paper, we present a theoretical and applicable framework for memoryadaptive algorithms (or simply MA algorithms). We define the competitive worst-case notion of what it means for an MA algorithm to be dynamically optimal and prove fundamental lower bounds on the performance of MA algorithms for problems such as sorting, standard matrix multiplication, and several related problems. Our main tool for proving dynamic optimality is the notion of resource consumption, wh...

In this paper we settle several longstanding open problems in theory of indexability and external orthogonal range searching. In the rst part of the paper, we apply the theory of indexability to the problem of two-dimensional range searching. We show that the special case of 3-sided querying can be solved with constant redundancy and access overhead. From this, we derive indexing schemes for general 4-sided range queries that exhibit an optimal tradeo between redundancy and access overhead. In the second part of the paper, we develop dynamic external memory data structures for the two query types. Our structure for 3-sided queries occupies O(N=B) disk blocks, and it supports insertions and deletions in O(log B N) I/Os and queries in O(log B N + T=B) I/Os, where B is the disk block size, N is the number of points, and T is the query output size. These bounds are optimal. Our structure for general (4-sided) range searching occupies O (N=B)(log(N=B))= log log B N disk blocks and answers queries in O(log B N + T=B) I/Os, which are optimal. It also supports updates in O (log B N)(log(N=B))= log log B N I/Os. Center for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC 27708{0129. Supported in part by the U.S. Army Research O ce through MURI grant DAAH04{96{1{0013 and by the National Science Foundation through ESS grant EIA{9870734. Part of this work was done while visiting BRICS, Department of Computer Science, University of Aarhus, Denmark. Email: [email protected]. yDepartment of Computer Sciences, University of Texas at Austin, Austin, TX 78712-1188. Email [email protected] zCenter for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC 27708{0129. Supported in part by the U.S. Army Research O ce through MURI grant DAAH04{96{1{0013 and by the National Science Foundation through grants CCR{9522047 and EIA{9870734. Part of this work was done while visiting BRICS, Department of Computer Science, University of Aarhus, Denmark and I.N.R.I.A., Sophia Antipolis, France. Email: [email protected].

In modern I/O architectures, multiple disk drives are attached to each I/O controller.A study of the performance of such architectures under I/O-intensive workloads has revealed a performance impairment that results from a previously unknown form of convoy behavior in disk I/O.In this paper, we describe measurements of the read performance of multiple disks that share a SCSI bus under a heavy workload, and develop and validate formulas that accurately characterize the observed performance (to within 12% on several platforms for I/O sizes in the range 16-128 KB).Two terms in the formula clearly characterize the lost performance seen in our experiments.We describe techniques to deal with the performance impairment, via user-level workarounds that achieve greater overlap of bus transfers with disk seeks, and that increase the percentage of transfers that occur at the full bus bandwidth rather than at the lower bandwidth of a disk head.Experiments show bandwidth improvements of lo-20% when using these user-level techniques, but only in the case of large I/OS.

Computing multidimensional aggregates in high dimensions is a performance bottleneck for many OLAP applications. Obtaining the exact answer to an aggregation query can be prohibitively expensive in terms of time and/or storage space in a data warehouse environment. It is advantageous to have fast, approximate answers to OLAP aggregation queries.

External sorting—the process of sorting a file that is too large to fit into the computer's internal memory and must be stored externally on disks—is a fundamental subroutine in database systems[G], [IBM]. Of prime importance are techniques that use multiple disks in parallel in order to speed up the performance of external sorting. The simple randomized merging (SRM ) mergesort algorithm proposed by Barve et al. [BGV] is the first parallel disk sorting algorithm that requires a provably optimal number of passes and that is fast in practice. Knuth [K,Section 5.4.9] recently identified SRM (which he calls ``randomized striping'') as the method of choice for sorting with parallel disks.

Article Free Access Share on Data cube approximation and histograms via wavelets Authors: Jeffrey Scott Vitter Center for Geometric Computing and Department of Computer Science, Duke University, Durham, NC Center for Geometric Computing and Department of Computer Science, Duke University, Durham, NCView Profile , Min Wang Center for Geometric Computing and Department of Computer Science, Duke University, Durham, NC Center for Geometric Computing and Department of Computer Science, Duke University, Durham, NCView Profile , Bala Iyer Database Technology Institute, IBM Santa Teresa Laboratory, P.O. Box 49023, San Jose, CA Database Technology Institute, IBM Santa Teresa Laboratory, P.O. Box 49023, San Jose, CAView Profile Authors Info & Claims CIKM '98: Proceedings of the seventh international conference on Information and knowledge managementNovember 1998 Pages 96–104https://doi.org/10.1145/288627.288645Online:01 November 1998Publication History 169citation593DownloadsMetricsTotal Citations169Total Downloads593Last 12 Months34Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Classification is a key function of many business intelligence toolkits and a fundamental building block in data mining. Immense data may be needed to train a classifier for good accuracy. The state-of-art classifiers need an in-memory data structure of size O(N), where N is the size of the training data, to achieve efficiency. For large data sets, such a data structure will not fit in the internal memory. The best previously known classifier does a quadratic number of I/Os for large N. We propose a novel classification algorithm (classifier) called MIND (MINing in Databases). MIND can be phrased in such a way that its implementation is very easy using the extended relational calculus SQL, and this in turn allows the classifier to be built into a relational database system directly. MIND is truly scalable with respect to I/O efficiency, which is important since scalability is a key requirement for any data mining algorithm. We built a prototype of MIND in the relational database manager DB2 and benchmarked its performance. We describe the working prototype and report the measured performance with respect to the previous method of choice. MIND scales not only with the size of the datasets but also with the number of processors on an IBM SP2 computer system. Even on uniprocessors, MIND scales well beyond the dataset sizes previously published for classifiers. We also give some insights that may have an impact on the evolution of the extended relational calculus SQL.

We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint x d a 0 + P d 1 i=1 a i x i ; the data structure must report all the points of S that satisfy the constraint. Our goal is to minimize the number of disk blocks required to store the data structure and the number of disk accesses (I/Os) required to answer a query. For d = 2 and d = 3, we present the first near-linear size data structures that can answer linear-constraint queries using an optimal number of I/Os. We also present a linear-size data structures that can answer queries efficiently in the worst case. For the d = 2 case, we also show how to combine these two approaches to obtain tradeoffs between space and query time. Finally, we show that some of our techniques extend to higher dimensions.

Data sets in large applications are often too massive to fit completely inside the computer's internal memory.The re sulting 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 tutorial, we survey the state of the art in the design and analysis of external memory algorithms (also known as out-of-core algorithms or I/O algorithms).External memory algorithms are often designed using the parallel diik model (PDM).The three machine-independent measures of an algorithm's performance in PDM are the number of I/O operations performed, tho CPU time, and the amount of disk space used.PDM allows for multiple disks (or disk arrays) and parallel CPUs, and it can be generalized to handle cache hierarchies, hierarchical memory, and tertiary storage.We discuss a variety of problems and identify paradigms for solving them efficiently in external memory.Programming tools and environments are available for simplifying the programming task.Experiments on some newly developed algorithms for spatial databases incorporating these paradigms, implemented using TPIE (Transparent Parallel I/O programming Environment), show a speedup over currently used methods.

For a wide variety of computational tasks, disk I/O continues to be a serious obstacle to high performance. The focus of the present paper is on systems that use multiple disks per SCSI bus. We measured the performance of concurrent random I/Os, and observed bus-related phenomena that impair performance. We describe these phenomena, and present a new I/O performance model that accurately predicts the average bandwidth achieved by a heavy workload of random reads from disks on a SCSI bus. This model, although relatively simple, predicts performance on several platforms to within 12% for I/O sizes in the range 16-128 KB. We describe a technique to improve the I/O bandwidth by 10-20% for random-access workloads that have large I/Os and high concurrency. This technique increases the percentage of disk head positioning time that is overlapped with data transfers, and increases the percentage of transfers that occur at bus bandwidth, rather than at disk-head bandwidth.

Query optimization is an integral part of relational database management systems. One important task in query optimization is selectivity estimation. Given a query P, we need to estimate the fraction of records in the database that satisfy P. Many commercial database systems maintain histograms to approximate the frequency distribution of values in the attributes of relations. In this paper, we present a technique based upon a multiresolution wavelet decomposition for building histograms on the underlying data distributions. Histograms built on the cumulative data distributions give very good approximations with limited space usage. We give fast algorithms for constructing histograms and using them in an on-line fashion for selectivity estimation. Our histograms can also be used to provide quick approximate answers to OLAP queries when the exact answers are not required. Our method captures the joint distribution of multiple attributes effectively, especially when the attributes are correlated. Experiments confirm that our histograms offer substantial improvements in accuracy over random sampling and other previous approaches.

Response time delays caused by I/O are a major problem in many systems and database applications. Prefetching and cache replacement methods are attracting renewed attention because of their success in avoiding costly I/Os. Prefetching can be looked upon as a type of online sequential prediction, where the predictions must be accurate as well as made in a computationally efficient way. Unlike other online problems, prefetching cannot admit a competitive analysis, since the optimal offline prefetcher incurs no cost when it knows the future page requests. Previous analytical work on prefetching [. Vitter Krishnan 1991.] [J. Assoc. Comput. Mach., 143 (1996), pp. 771--793] consisted of modeling the user as a probabilistic Markov source. In this paper, we look at the much stronger form of worst-case analysis and derive a randomized algorithm for pure prefetching. We compare our algorithm for every page request sequence with the important class of finite state prefetchers, making no assumptions as to how the sequence of page requests is generated. We prove analytically that the fault rate of our online prefetching algorithm converges almost surely for every page request sequence to the fault rate of the optimal finite state prefetcher for the sequence. This analysis model can be looked upon as a generalization of the competitive framework, in that it compares an online algorithm in a worst-case manner over all sequences with a powerful yet nonclairvoyant opponent. We simultaneously achieve the computational goal of implementing our prefetcher in optimal constant expected time per prefetched page using the optimal dynamic discrete random variate generator of [. Matias Matias, Vitter, and Ni [Proc. 4th Annual SIAM/ACM Symposium on Discrete Algorithms, Austin, TX, January 1993].

We present and compare methods for choosing motion vectors for block-based motion-compensated video coding. The primary focus is on videophone and videoconferencing applications, where low bit rates are necessary, where motion is usually limited, and where the amount of computation is also limited. In a typical block-based motion-compensated video coding system, motion vectors are transmitted along with a lossy encoding of the residuals. As the bit rate decreases, the proportion required to transmit the motion vectors increases. We provide experimental evidence that choosing motion vectors explicitly to minimize rate (including motion vector coding), subject to implicit constraints on distortion, yields better rate-distortion tradeoffs than minimizing some measure of prediction error. Minimizing a combination of rate and distortion yields further improvements. Although these explicit-minimization schemes are computationally intensive, they provide invaluable insight which we use to develop practical algorithms. We show that minimizing a simple heuristic function of the prediction error and the motion vector code length results in rate-distortion performance comparable to explicit-minimization schemes while being computationally feasible. Experimental results are provided for coders that operate within the H.261 standard.

We describe the rst known algorithm for efficiently maintaining a Binary Space Partition (BSP) for n continuously moving segments in the plane. Under reasonable assumptions on the motion, we show that the total number of times the BSP changes is O(n²), and that we can update the BSP in O(log n) expected time per change. We also consider the problem of constructing a BSP for n triangles in R³. We present a randomized algorithm that constructs a BSP of expected size O(n²) in O(n² log² n) expected time. We also describe a deterministic algorithm that constructs a BSP of size O((n + k) log n) and height O(log n) in O((n + k) log² n) time, where k is the number of intersection points between the edges of the projections of the triangles onto the xy-plane.

We present the first systematic comparison of the performance of algorithms that construct Binary Space Partitions for orthogonal rectangles in R³. We compare known algorithms with our implementation of a recent algorithm of Agarwal et al. [1]. We show via an empirical study that their algorithm constructs BSPs of near-linear size in practice and performs better than

We consider the problem of allocating bits among pictures in an MPEG video coder to equalize the visual quality of the coded pictures, while meeting buffer and channel constraints imposed by the MPEG video buffering verifier. We address this problem within a framework that consists of three components: (1) a bit production model for the input pictures, (2) a set of bit-rate constraints imposed by the video buffering verifier, and (3) a novel lexicographic criterion for optimality. Under this framework, we derive simple necessary and sufficient conditions for optimality that lead to efficient algorithms.

We consider re-representing the alphabet so that a representation of a character reflects its properties as a predictor of future text. This enables us to use an estimator from a restricted class to map contexts to predictions of upcoming characters. We describe an algorithm that uses this idea in conjunction with neural networks. The performance of this implementation is compared to other compression methods, such as UNIX compress, gzip, PPMC, and an alternative neural network approach.

Query optimization is an integral part of relational database management systems. One important task in query optimization is selectivity estimation, that is, given a query P, one needs to estimate the fraction of records in the database that satisfy P. Almost all previous work dealt with the estimation of numeric selectivity, i.e., the query contains only numeric variables. The general problem of estimating alphanumeric selectivity is much more difficult and has attracted attention only very recently, and the focus has been on the special case when only one column is involved. The authors consider the more general case when there are two correlated alphanumeric columns. They develop efficient algorithms to build storage structures that can fit in a database catalog. Results from extensive experiments to test the algorithms, on the basis of error analysis and space requirements, are given to guide DBMS implementors.

We apply a novel lexicographic framework for bit allocation to the multiplexing of multiple VBR video streams onto a single CBR channel. In the lexicographic framework, the maximum distortion is minimized, then the second highest distortion, and so on, resulting in nearly constant quality. With a suitably constructed multiplexing model, we show that the multiplexing problem reduces to a single-stream CBR bit allocation problem, to which we apply the lexicographic framework. This method has applications for video servers.

We consider the problem of allocating bits among pictures in an MPEG video coder to equalize the visual quality of the coded pictures, while meeting buffer and channel constraints imposed by the MPEG video buffering verifier We address this problem within a framework that consists of three components: (1) a bit production model for the input pictures, (2) a set of bit-rate constraints imposed by the video buffering verifier and (3) a novel lexicographic criterion for optimality. Under this framework, we derive simple necessary and sufficient conditions for optimality that lead to efficient algorithms.

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 strings of total ¥ length ¦¨§©¤���������¤��¨¥� � is. By analogy, in the external memory (or I/O) model, where the internal memory has � size and the block transfer size � is, it would be natural to guess that the I/O complexity of sorting strings ¦¨§������������ � � �������� � is, 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

We make a case that, even with severe efficiency constraints, taking the number of bits to code each motion vector into account when estimating motion for video compression results in significantly better performance at low bit rates, using simulation studies on established benchmark image sequences. In particular, we examine an algorithm that differs from a "vanilla" implementation of the H.261 standard by choosing motion vectors to minimize a cost function of prediction error and the number of bits to code a particular motion vector, where the coefficients of the cost function are adapted on-line using the Widrow-Hoff (1960) rule. We show that this algorithm performs comparably to a variety of more idealized, computationally intensive methods we examined in earlier papers and substantially better than the original "vanila" method, which ignores the number of bits to code the motion vector when choosing it.

The authors consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in R/sup 3/ such that the aspect ratio of each rectangle in S is at most /spl alpha/, for some constant a /spl alpha//spl ges/1. They present an n2/sup O(/spl radic/logn)/-time algorithm to build a binary space partition of size n2/sup O(/spl radic/logn)/ for S. They also show that if m of the n rectangles in S have aspect ratios greater than /spl alpha/, they can contact a BSP of size n/spl radic/m2/sup O(/spl radic/logn)/ for S in n/spl radic/2/sup O(/spl radic/logn)/ time. The constants of proportionality in the big-oh terms are linear in log /spl alpha/. They extend these results to cases in which the input contains non-orthogonal or intersecting objects.

The authors present a space- and I/O-optimal external-memory data structure for answering stabbing queries on a set of dynamically maintained intervals. The data structure settles an open problem in databases and I/O algorithms by providing the first optimal external-memory solution to the dynamic interval management problem, which is a special case of 2-dimensional range searching and a central problem for object-oriented and temporal databases and for constraint logic programming. The data structure simultaneously uses optimal linear space (that is, O(N/B) blocks of disk space) and achieves the optimal O(log/sub B/ N+T/B) I/O query bound and O(log/sub B/ N) I/O update bound, where B is the I/O block size and T the number of elements in the answer to a query. The structure is also the first optimal external data structure for a 2-dimensional range searching problem that has worst-case as opposed to amortized update bounds. Part of the data structure uses a novel balancing technique for efficient worst-case manipulation of balanced trees, which is of independent interest.

Success of commercial query optimizers and database management systems (object-oriented or relational) depend on accurate cost estimation of various query reordering [BGI]. Estimating predicate selectivity, or the fraction of rows in a database that satisfy a selection predicate, is key to determining the optimal join order. Previous work has concentrated on estimating selectivity for numeric fields [ASW, HaSa, IoP, LNS, SAC, WVT]. With the popularity of textual data being stored in databases, it has become important to estimate selectivity accurately for alphanumeric fields. A particularly problematic predicate used against alphanumeric fields is the SQL like predicate [Dat]. Techniques used for estimating numeric selectivity are not suited for estimating alphanumeric selectivity.In this paper, we study for the first time the problem of estimating alphanumeric selectivity in the presence of wildcards. Based on the intuition that the model built by a data compressor on an input text encapsulates information about common substrings in the text, we develop a technique based on the suffix tree data structure to estimate alphanumeric selectivity. In a statistics generation pass over the database, we construct a compact suffix tree-based structure from the columns of the database. We then look at three families of methods that utilize this structure to estimate selectivity during query plan costing, when a query with predicates on alphanumeric attributes contains wildcards in the predicate.We evaluate our methods empirically in the context of the TPC-D benchmark. We study our methods experimentally against a variety of query patterns and identify five techniques that hold promise.

We consider the problem of sorting a file of N records on the D-disk model of parallel I/0 [VS94] in which there are two sources of parallehsm. Records are transferred to and from disk concurrently in blocks of B con-tiguous 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, eficient, 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 forecasting technique of [Knu73], 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/0 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. Our analysis technique involves a novel reduction to various maximum occupancy problems. We prove that the expected I/O performance of SRM is efficient under varying sizes of memory and that it compares favorably in practice to disk-striped mergesort (DSM). Our studies indicate that SRM outperforms DSM even when the number D of parallel disks is fairly small.

We present a new approach to designing data structures for the important problem of externalmemory range searching in two and three dimensions. We construct data structures for answering range queries in O((log log log B N) log B N + K=B) I/O operations, where N is the number of points in the data structure, B is the I/O block size, and K is the number of points in the answer to the query. Our data structures answer a longstanding open problem by providing three dimensional results comparable to those provided by [8, 10] for the two dimensional case, though completely new techniques are used. Ours is the first 3-D range search data structure that simultaneously achieves both a base-B logarithmic search overhead (namely, (log log log B N) log B N) and a fully blocked output component (namely, K=B). This gives us an overall I/O complexity extremely close to the well-known lower bound of \\Omega\\Gamma/89 B N +K=B). We base our data structures on the novel concept of B-approximate boundarie...

Caching and prefetching are important mechanisms for speeding up access time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new algorithms for caching. In this paper, we apply a form of the competitive philosophy for the first time to the problem of prefetching to develop an optimal universal prefetcher in terms of fault rate, with particular applications to large-scale databases and hypertext systems. Our prediction algorithms with particular applications to large-scale databases and hypertext systems. Our prediction algorithms for prefetching are novel in that they are based on data compression techniques that are both theoretically optimal and good in practice. Intuitively, in order to compress data effectively, you have to be able to predict future data well, and thus good data compressors should be able to predict well for purposes of prefetching. We show for powerful models such as Markov sources and m the order Markov sources that the page fault rate incurred by our prefetching algorithms are optimal in the limit for almost all sequences of page requests.

Motivated by the desire to find text compressors that compress better than existing dictionary methods, but run faster than PPM implementations, we describe methods for text compression using multiple dictionaries, one for each context of preceding characters, where the contexts have varying lengths. The context to be used is determined using an escape mechanism similar to that of PPM methods. We describe modifications of three popular dictionary coders along these lines and experiments evaluating their efficacy using the text files in the Calgary corpus. Our results suggest that modifying LZ77 along these lines yields an improvement in compression of about 4%, that modifying LZFG yields a compression improvement of about 8%, and that modifying LZW in this manner yields an average improvement on the order of 12%.

In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion. Traditionally, the assignment of jobs to servers is measured by the L/sub /spl infin// norm; in other words, an assignment of jobs to servers is quantified by the maximum load assigned to any server. In this measure the performance of the greedy load balancing algorithm may be a logarithmic factor higher than the offline optimal. In many applications, the L/sub /spl infin// norm is not a suitable way to measure how well the jobs are balanced, If each job sees a delay that is proportional to the number of jobs on its server, then the average delay among all jobs is proportional to the sum of the squares of the numbers of jobs assigned to the servers. Minimizing the average delay is equivalent to minimizing the Euclidean (or L/sub 2/) norm. For any fixed p, 1/spl les/p</spl infin/, we show that the greedy algorithm performs within a constant factor of the offline optimal with respect to the L/sub p/ norm. The constant grows linearly with p, which is best possible, but does not depend on the number of servers and jobs.

We consider a cache shared by several concurrently running application processes and propose a provably efficient application-controlled global strategy for the shared cache. Using future information implicitly in the form of good decisions by application processes, we are able to break through the H/sub k/ lower bound on competitive ratio proved for classical paging for a k-sized cache in [FKL/sup +/91]. For a size-k cache shared by P application processes that always make good cache replacement decisions, we develop an online application-controlled paging algorithm with and competitive ratio of 2H/sub P-1/+2 Typically, P is much smaller than k, perhaps by several orders of magnitude. Our competitive ratio improves upon the 2P+2 competitive ratio achieved by [CFL94a]. We show for this problem that no on-line algorithm A can have a competitive ratio better than H/sub P-1/ even if the application processes aiding A have perfect knowledge of individual request sequences. Our results are with respect to a worst-case interleaving of the individual request sequences of the P applications. We introduce a notion of fairness in the more realistic situation when application processes do not always make good cache replacement decisions. We show that our algorithm ensures that no application process needs to evict one of its cached pages to service some page fault caused by a mistake of some other application. Our algorithm is not only fair, but remains efficient; the global paging performance can be bounded in terms of the number of mistakes that application processes make.

We present an algorithm for sorting efficiently with parallel two-level memories. Our main result is an elegant, easy-to-implement, optimal, deterministic 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/O) 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 θ(( N/BD ) log( N/B )/ log( M/B )) deterministically, and thus 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.

Compares methods for choosing motion vectors for motion-compensated video compression. The primary focus is on videophone and videoconferencing applications, where very low bit rates are necessary, where the motion is usually limited, and where the frames must be coded in the order they are generated. the authors provide evidence, using established benchmark videos of this type, that choosing motion vectors to minimize codelength subject to (implicit) constraints on quality yields substantially better rate-distortion tradeoffs than minimizing notions of prediction error. They illustrate this point using an algorithm within the p/spl times/64 standard. They show that using quadtrees to code the motion vectors in conjunction with explicit codelength minimization yields further improvement. They describe a dynamic-programming algorithm for choosing a quadtree to minimize the codelength.>

Arithmetic coding provides an effective mechanism for removing redundancy in the encoding of data. We show how arithmetic coding works and describe an efficient implementation that uses table lookup as a first alternative to arithmetic operations. The reduced-precision arithmetic has a provably negligible effect on the amount of compression achieved. We can speed up the implementation further by use of parallel processing. We discuss the role of probability models and how they provide probability information to the arithmetic coder. We conclude with perspectives on the comparative advantages and disadvantages of arithmetic coding.>

We examine the complexity of testing different program constructs by defining a measure called VCP-dimension and applying it to classes of programs, where all programs in a class share the same syntactic structure. VCP-dimension gives bounds on the number of test points needed to determine approximate correctness, so it gives insight into the difficulty of testing a program construct represented by a program class. We investigate the VCP-dimension of straight line code, if-then-else statements and for loops, and we compare the VCP-dimension of different combinations of constructs.>

A detailed algorithm for fast text compression, related to the PPM method, simplifies the modeling phase by eliminating the escape mechanism, and speeds up coding by using a combination of quasi-arithmetic coding and Rice coding. The authors provide details of the use of quasi-arithmetic code tables, and analyze their compression performance. The Fast PPM method is shown experimentally to be almost twice as fast as the PPMC method, while giving comparable compression.>

A new method gives compression comparable with the JPEG lossless mode, with about five times the speed. FELICS is based on a novel use of two neighboring pixels for both prediction and error modeling. For coding, the authors use single bits, adjusted binary codes, and Golomb or Rice codes. For the latter they present and analyze a provably good method for estimating the single coding parameter.>

In this paper we give new techniques for designing efficient algorithms for computational geometry problems that are too large to be solved in internal memory. We use these techniques to develop optimal and practical algorithms for a number of important large-scale problems. We discuss our algorithms primarily in the context of single processor/single disk machines, a domain in which they are not only the first known optimal results but also of tremendous practical value. Our methods also produce the first known optimal algorithms for a wide range of two-level and hierarchical multilevel memory models, including parallel models. The algorithms are optimal both in terms of I/O cost and internal computation.>

We examine I/O-efficient data structures that provide indexing support for new data models. The database languages of these models include concepts from constraint programming (e.g., relational tuples are generalized to conjunctions of constraints) and from object-oriented programming (e.g., objects are organized in class hierarchies). Let n be the size of the database, c the number of classes, B the secondary storage page size, and t the size of the output of a query. Indexing by one attribute in the constraint data model (for a fairly general type of constraints) is equivalent to external dynamic interval management, which is a special case of external dynamic 2-dimensional range searching. We present a semi-dynamic data structure for this problem which has optimal worst-case space O(n/B) pages and optimal query I/O time O(logBn+t/B) and has O(logBn+(log2Bn)/B) amortized insert I/O time. If the order of the insertions is random then the expected number of I/O operations needed to perform insertions is reduced to O(logBn). Indexing by one attribute and by class name in an object-oriented model, where objects are organized as a forest hierarchy of classes, is also a special case of external dynamic 2-dimensional range searching. Based on this observation we first identify a simple algorithm with good worst-case performance for the class indexing problem. Using the forest structure of the class hierarchy and techniques from the constraint indexing problem, we improve its query I/O time from O(log2c logBn + t/B) to O(logB + log2B).

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. We also show that for the special case of grid graphs blocked with isothetic hypercubes, there is a provably better speed-up if even a small amount of redundancy is permitted.

An important issue that affects response time performance in current OODB and hypertext systems is the I/O involved in moving objects from slow memory to cache. A promising way to tackle this problem is to use prefetching, in which we predict the user's next page requests and get those pages into cache in the background. Current databases perform limited prefetching using techniques derived from older virtual memory systems. A novel idea of using data compression techniques for prefetching was recently advocated in [KrV, ViK], in which prefetchers based on the Lempel-Ziv data compressor (the UNIX compress command) were shown theoretically to be optimal in the limit. In this paper we analyze the practical aspects of using data compression techniques for prefetching. We adapt three well-known data compressors to get three simple, deterministic, and universal prefetchers. We simulate our prefetchers on sequences of page accesses derived from the OO1 and OO7 benchmarks and from CAD applications, and demonstrate significant reductions in fault-rate. We examine the important issues of cache replacement, size of the data structure used by the prefetcher, and problems arising from bursts of “fast” page requests (that leave virtually no time between adjacent requests for prefetching and book keeping). We conclude that prediction for prefetching based on data compression techniques holds great promise.

We present an elegant deterministic load balancing strategy for distribution sort that is applicable to a wide variety of parallel diska and parallel memory hierarchies with both single and parallel processors.The simplest application

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— ε-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 [LiVb] to PAC-learn in polynomial time using only polynomial storage in typical situations.

The authors present a new method for error modeling applicable to the multi-level progressive (MLP) algorithm for hierarchical lossless image compression. This method, based on a concept called the variability index, provides accurate models for pixel prediction errors without requiring explicit transmission of the models. They also use the variability index to show that prediction errors do not always follow the Laplace distribution, as is commonly assumed; replacing the Laplace distribution with a more general distribution further improves compression. They describe a new compression measurement called compression gain, and give experimental results showing that the using variability index gives significantly better compression than other methods in the literature.>

The authors show that high-resolution images can be encoded and decoded efficiently in parallel. They present an algorithm based on the hierarchical multi-level progressive (MLP) method, used either with Huffman coding or with a new variant of arithmetic coding called quasi-arithmetic coding. The coding step can be parallelized, even though the codes for different pixels are of different lengths; parallelization of the prediction and error modeling components is straightforward.>

The authors present new vector quantization algorithms. The new approach is to formulate a vector quantization problem as a 0-1 integer linear program. They first solve its relaxed linear program by linear programming techniques. Then they 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. They also introduce the notion of pseudorandom pruned tree-structured vector quantizers. Initial experimental results on image compression are very encouraging.>

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 NP-hard discrete optimization problem. Without any constraint violation, the ε-approximation problem for many problems of this type is itself NP-hard. Our methods provide polynomial-time ε-approximations while attempting to minimize the packing constraint violation.

The authors analyze the amount of compression possible when arithmetic coding is used for text compression in conjunction with various input models. Arithmetic coding, a technique for statistical lossless encoding, can be thought of as a generalization of Huffman coding in which probabilities are not constrained to be integral powers of 2 and code lengths need not be integers. Adaptive codes are proven to be as good as decrementing semi-adaptive codes. The tradeoff between scaling overheads and savings from exploitation of locality of reference is characterised exactly by means of weighted entropy.>

Lossless text compression methods involve some form of moderately high-order exact string matching. However, this work cannot easily be carried over to lossless image compression, because images are two-dimensional and (more important) essentially quantized analog data. A better plan is to find and encode as much of the image structure of the data as possible, and then to encode efficiently the unstructured, noisy residual. In three steps the authors predict the value of each pixel, model the error of the prediction, and encode the error of the prediction. Having a probabilistic model for the errors, they can use arithmetic coding to encode the errors efficiently with respect to the model.>

A form of the competitive philosophy is applied to the problem of prefetching to develop an optimal universal prefetcher in terms of fault ratio, with particular applications to large-scale databases and hypertext systems. The algorithms are novel in that they are based on data compression techniques that are both theoretically optimal and good in practice. Intuitively, in order to compress data effectively, one has to be able to predict feature data well, and thus good data compressors should be able to predict well for purposes of prefetching. It is shown for powerful models such as Markov sources and mth order Markov sources that the page fault rates incurred by the prefetching algorithms presented are optimal in the limit for almost all sequences of page accesses.>

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.

Parallel algorithms for several graph and geometric problems are presented, including transitive closure and topological sorting in planar $st$-graphs, preprocessing planar subdivisions for point location queries, and construction of visibility representations and drawings of planar graphs. Most of these algorithms achieve optimal $O(\log n)$ running time using $n / \log n$ processors in the EREW PRAM model, n being the number of vertices.

The authors introduce input/output (I/O) overhead psi as a complexity measure for VLSI implementations of two-dimensional lattice computations of the type arising in the simulation of physical systems. It is shown by pebbling arguments that psi = Omega (n/sup -1/) when there are n/sup 2/ processing elements available. If the results must be observed at every generation and if no on-chip storage is allowed, the lower bound is the constant 2. The authors then examine four VLSI architectures and show that one of them, the multigeneration sweep architecture also has I/O overhead proportional to n/sup -1/. A closed-form for the discrete minimization equation giving the optimal number of generations to compute for the multigeneration sweep architecture is proved.>

Fractional cascading is a technique designed to allow efficient sequential search in a graph with catalogs of total sizen. The search consists of locating a key in the catalogs along a path. In this paper we show how to preprocess a variety of fractional cascaded data structures whose underlying graph is a tree so that searching can be done efficiently in parallel. The preprocessing takesO(logn) time withn/logn processors on an EREW PRAM. For a balanced binary tree, cooperative search along root-to-leaf paths can be done inO((logn)/logp) time usingp processors on a CREW PRAM. Both of these time/processor constraints are optimal. The searching in the fractional cascaded data structure can be either explicit, in which the search path is specified before the search starts, or implicit, in which the branching is determined at each node. We apply this technique to a variety of geometric problems, including point location, range search, and segment intersection search.

We provide optimal algorithms for sorting, FFT, matrix transposition, standard matrix multiplication, and related problems in terms of the number of input/outputs (I/Os) required between internal memory and secondary storage.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 (disks) can simultaneously transfer a contiguous block of B records.We also introduce parallel variants of the hierarchical memory models of [1,2] and give optimal algorithms.In our models there are P hierarchies, which operate in parallel.Communication among the hierarchies takes place at a base memory level.The difficulty in developing optimal algorithms in our two-level and hierarchical models is to cope with the partitioning of memory into P separate physical devices.Our sorting algorithms are randomized, but practical; the probability of using more than an optimal number of I/Os falls off exponentially.

We present a new technique to display a scene of three-dimensional isothetic parallelepipeds (3D-rectangles), viewed from infinity along one of the coordinate axes (axial view). In this situation, there always exists a topological sorting of the 3D-rectangles based on the relation of occlusion (a dominance relation). The arising total order is used to generate the axial view, where the two-dimensional view of each 3D-rectangle is incrementally added, starting from the closest 3D-rectangle. The proposedscene-sensitivealgorithm runs in timeO(Nlog2N+dlogN), whereNis the number of 3D-rectangles anddis the number of edges of the display. This improves over the previously best known technique based on the same approach.

We present parallel algorithms for several graph and geometric problems, including transitive closure and topological sorting in planar $st$-graphs, preprocessing planar subdivisions for point location queries, and construction of visibility representations and drawings of planar graphs. Most of these algorithms achieve optimal $O( log n)$ running time with $n / log n$ processors in the EREW PRAM model.

We present a Pascal implementation of the one-pass algorithm for constructing dynamic Huffman codes that is described and analyzed in a companion paper. The program runs in real time; that is, the processing time for each letter of the message is proportional to the length of its codeword. The number of bits used to encode a message of t letters is less than t bits more than that used by the well-known two-pass algorithm. This is best possible for any one-pass Huffman scheme. In practice, it uses fewer bits than all other Huffman schemes. The algorithm has applications in file compression and network transmission.

A new one-pass algorithm for constructing dynamic Huffman codes is introduced and analyzed. We also analyze the one-pass algorithm due to Faller, Gallager, and Knuth. In each algorithm, both the sender and the receiver maintain equivalent dynamically varying Huffman trees, and the coding is done in real time. We show that the number of bits used by the new algorithm to encode a message containing t letters is < t bits more than that used by the conventional two-pass Huffman scheme, independent of the alphabet size. This is best possible in the worst case, for any one-pass Huffman method. Tight upper and lower bounds are derived. Empirical tests show that the encodings produced by the new algorithm are shorter than those of the other one-pass algorithm and, except for long messages, are shorter than those of the two-pass method. The new algorithm is well suited for on-line encoding/decoding in data networks and for tile compression.

We examine several methods for drawing a sequential random sample of n records from a file containing N records. Method D is recommended for general use. The algorithm is on-line (so that CPU time can be overlapped with I/O), has a small constant memory requirement, and is easy to program. An improved implementation is detailed in the Appendix.

We present efficient deletion algorithms for three variants of coalesced chaining – late insertion (LICH), early insertion (EICH), and varied insertion (VICH). Our approach is uniform in the sense that each deletion algorithm works simultaneously for all three variants, though the implementation details are of course different. Deletion algorithms for coalesced hashing when there is a cellar have not been studied previously in the literature; these algorithms are useful because coalesced hashing is most efficient when a cellar is utilised. First we present and analyse a deletion algorithm that preserves randomness – in that deleting a record is in some sense like never having inserted it. In particular, the formulas for the average search times after N random insertions intermixed with d random deletions are the same as the formulas for the average search times after N-d random insertions. This answers an open question in the literature. We then present two deletion algorithms that require fewer pointer fields per table slot; the latter one does not relocate records once inserted. These two algorithms do not preserve randomness, but simulations suggest that search times remain good after repeated deletions and insertions.

Previous theoretical work in computational complexity has suggested that any problem which is log-space complete for P is not likely in NC, and thus not parallelizable. In practice, this is not the case. To resolve this paradox, we introduce new complexity classes PC and PC* that capture the practical notion of parallelizability we discuss in this paper. We show that foqur complete problems for P (nonsparse versions of unification, path system accessibility, monotone circuit value, and ordered depth-first search) are parallelizable. That is, their running times are O(E + V) on a sequential RAM and O(E/P + V log P) on an EXCLUSIVE-READ EXCLUSIVE-WRITE Parallel RAM with P processors where V and E are the numbers of vertices and edges in the inputed instance of the problem. These problems are in PC and PC*, since an appropriate choice of P can speed up their sequential running times by a factor of μ(P). Several interesting open questions are raised regarding these new parallel complexity classes PC and PC*. Unification is particularly important because it is a basic operation in theorem proving, in type inference algorithms, and in logic programming languages such as Prolog. A fast parallel implementation of Prolog is needed for software development in the Fifth Generation project.

We introduce an efficient new algorithm for dynamic Huffman coding, called Algorithm V. It performs one-pass coding and transmission in real-time, and uses at most one more bit per letter than does the standard two-pass Huffman algorithm; this is optimum in the worst case among all one-pass schemes. We also analyze the dynamic Huffman algorithm due to Faller, Gallager, and Knuth. In each algorithm, both the sender and the receiver maintain equivalent dynamically varying Huffman trees. The processing time required to encode and decode a letter whose node in the dynamic Huffman tree is currently on the lth level is O(l); hence, the processing can be done in real time. Empirical tests show that Algorithm V performs quite well in practice, often better than the two-pass method. The proposed algorithm is well-suited for file compression and online encoding/decoding in data networks.

Direct chaining is a popular and efficient class of hashing algorithms. In this paper we study optimum algorithms among direct chaining methods, under the restrictions that the records in the hash table are not moved after they are inserted, that for each chain the relative ordering of the records in the chain does not change after more insertions, and that only one link field is used per table slot. The varied-insertion coalesced hashing method (VICH), which is proposed and analyzed in [CV84], is conjectured to be optimum among all direct chaining algorithms in this class. We give strong evidence in favor of the conjecture by showing that VICH is optimum under fairly general conditions.

BucketSort is a new external sorting algorithm for very large files that is a substantial improvement over merge sorting with disks. BucketSort requires an associative secondary storage device, which can be realized by large disk drives with logic-per-track capabilities or by magnetic bubble memory (MBM). This paper describes and analyzes a hypothetical Bucket-Sort implementation that uses bubble memory. A new software marking technique is introduced that reduces the effective time for an associative search.

We introduce the notion of an I/O interface for optical digital (write-once) disks, which is quite different from earlier research. The purpose of an I/O interface is to allow existing operating systems and application programs that use magnetic disks to use optical disks instead, with minimal change. We define what it means for an I/O interface to be disk-efficient. We demonstrate a practical disk- efficient I/O interface and show that its I/O performance in many cases is optimum, up to a constant factor, among all disk-efficient interfaces. The interface is most effective for applications that are not update-intensive. An additional capability is a built-in history mechanism that provides software support for accessing previous versions of records. Even if not implemented, the I/O interface can be used as a programming tool to develop efficient special purpose applications for use with optical disks.

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.

We analyze a simple method for finding shortest paths in Euclidean graphs (where vertices are points in a Euclidean space and edge weights are distances between points). For many graph models, the running time of the algorithm to find the shortest path between a specified pair of vertices in a graph with V vertices and E edges is shown to be O(V) as compared with O (V log V + E) required by the classical (Dijkstra) algorithm.

The coalesced hashing method has been shown to be very fast for dynamic information storage and retrieval. This paper analyzes in a uniform way the performance of coalesced hashing and its variants, thus settling some open questions in the literature. In all the variants, the range of the hash function is called the address region , and extra space reserved for storing colliders is called the cellar . We refer to the unmodified method, which was analyzed previously, as late-insertion coalesced hashing. In this paper we analyze late insertion and two new variations called early insertion and varied insertion . When there is no cellar, the early-insertion method is better than late insertion; however, past experience has indicated that it might be worse when there is a cellar. Our analysis confirms that it is worse. The varied-insertion method was introduced as a means of combining the advantages of late insertion and early insertion. This paper shows that varied insertion requires fewer probes per search, on the average, than do the other variants. Each of these three coalesced hashing methods has a parameter that relates the sizes of the address region and the cellar. Techniques in this paper are designed for tuning the parameter in order to achieve optimum search times. We conclude with a list of open problems.

Several fast new algorithms are presented for sampling n records at random from a file containing N records. The first problem we solve deals with sampling when N is known, and the the second problem considers the case when N is unknown. The two main results in this paper are Algorithms D and Z. Algorithm D solves the first problem by doing the sampling with a small constant amount of space and in O(n) time, on the average; roughly n uniform random variates are generated, and approximately n exponentiation operations are performed during the sampling The sample is selected sequentially and online; it answers an open problem in [Knuth 81]. Algorithm Z solves the second problem by doing the sampling using O(n) space, roughly n ln(N/n) uniform random variates and O(n(1 + log(N/n))) time, on the average. Both algorithms are time- and space-optimum and are short and easy to implement.

An analysis is presented of the coalesced hashing method, m which a portion of memory (called the address region) serves as the range of the hash function while the rest of memory (called the cellar) Is devoted solely to storing records that collide when inserted.If the cellar should get full, subsequent colliders must be stored in empty slots in the address region and thus may cause later collisions.Varying the relative size of the cellar affects search performance.The main result of this paper expresses the average search tunes as a function of the number of records and the cellar size, solving a long-standing open problem.These formulas are used to pick the cellar size that leads to optimum search performance, and tt is shown that this "tuned" method outperforms several well-known hashing schemes A discussion of past work on coalesced hashing and a generalization of the method to nonuniform hash functions conclude the paper Categories and SubJect Descriptors E 2 [Data]. Data Storage Representations--hash-table representations; F 2 2 [Analysis of Algorithms and Problem Complexity]-Nonnumencal Algorithms and Problems--sorting and searching; G 2 1 [Discrete Mathematics] Combinatoncs--generating functions', permutations and combinations, recurrences and difference equauons; G.3 [Mathematics of Computing]: Probability and Statistlcs--i andom number generat:on, H 3 3 [Information Storage and Retrieval].

This paper analyzes the early-insertion standard coalesced hashing method (EISCH), which is a variant of the standard coalesced hashing algorithm (SCH) described in [Knu73], [Vit80] and [Vit82b]. The analysis answers the open problem posed in [Vit80]. The number of probes per successful search in full tables is 5% better with EISCH than with SCH.

This paper studies the problem of finding efficient deletion algorithms for the coalesced hashing method, in which a portion of memory (called the address region) serves as the range of the hash function while the rest of memory (called the cellar) is devoted solely to storing records that collide when inserted. We present a deletion algorithm, which solves the open problem described in [Knu73, §6.4-23]. The main result of this paper, Theorem 3, shows that the deletion algorithm preserves randomness for the special case of standard coalesced hashing, in that deleting a record is in some sense like never having inserted it. This means that the formulas for the search times (which are analyzed in [Vit80a] and [Vit80b]) are still valid after deletions. There is as yet no known deletion algorithm that preserves randomness for the general case (when there is a cellar). We give some reasons why and then discuss some heuristics that seem to make deletions practical anyway.

This paper analyzes the coalesced hashing method, in which a portion of memory (called the address region) serves as the range of the hash function while the rest of memory (called the cellar) is devoted solely to storing records that collide when inserted. If the cellar should get full, subsequent colliders must be stored in empty slots in the address region and, thus, may cause later collisions. Varying the relative size of the cellar affects search performance. The main result of this paper expresses the average search times as a function of the number of records and the cellar size, solving the long-standing open problem described in [Knu73, §6.4-43]. We use these formulas to pick the cellar size that leads to optimum search performance and then show that this "tuned" method is competitive with several well-known hashing schemes.