In multimedia, text or bioinformatics databases, applicat ions query sequences of n consecutive symbols called n-grams. Estimating the number of distinct n-grams is a view-size estimation problem. While view sizes can be estimated by sampling under statistical assumptions, we desire an unassuming algorithm with universally valid accuracy bounds. Most related work has focused on repeatedly hashing the data, which is prohibitive for large data sources. We prove that a one-pass one-hash algorithm is suffi cient for accurate estimates if the hashing is sufficiently independent. T o reduce costs further, we investigate recursive random hashing algorithms and show that they are sufficiently independent in practice. We compare our run ning times with exact counts using suffix arrays and show that, while we use ha rdly any storage, we are an order of magnitude faster. The approach further is extended to a one-pass one-hash computation of n-gram entropy and iceberg counts. The experiments use a large collection of English text from the Gutenberg Project as well as synthetic data.
@cite_30: On-line Analytical Processing (OLAP) has become one of the most powerful and prominent technologies for knowledge discovery in VLDB (Very Large Database) environments. Central to the OLAP paradigm is the data cube, a multi-dimensional hierarchy of aggregate values that provides a rich analytical model for decision support. Various sequential algorithms for the efficient generation of the data cube have appeared in the literature. However, given the size of contemporary data warehousing repositories, multi-processor solutions are crucial for the massive computational demands of current and future OLAP systems. In this paper we discuss the cgmCUBE Project, a multi-year effort to design and implement a multi-processor platform for data cube generation that targets the relational database model (ROLAP). More specifically, we discuss new algorithmic and system optimizations relating to (1) a thorough optimization of the underlying sequential cube construction method and (2) a detailed and carefully engineered cost model for improved parallel load balancing and faster sequential cube construction. These optimizations were key in allowing us to build a prototype that is able to produce data cube output at a rate of over one TeraByte per hour.
@cite_35: Preface.- Part I: Internet and the World Wide Web.- Part II: Massive Graphs.- Part III: String Processing and Data Compression.- Part IV: External Memory Algorithms and Data Structures.- Part V: Optimization.- Part VI: Data Management.- Part VII: Architecture Issues.- Part VIII: Applications.- Index.
@cite_38: 
@cite_26: To speed up multidimensional data analysis, database systems frequently precompute aggregates on some subsets of dimensions and their corresponding hierarchies. This improves query response time. However, the decision of what and how much to precompute is a difficult one. It is further complicated by the fact that precomputation in the presence of hierarchies can result in an unintuitively large increase in the amount of storage required by the database. Hence, it is interesting and useful to estimate the storage blowup that will result from a proposed set of precomputations without actually computing them. We propose three strategies for this problem: one based on sampling, one based on mathematical approximation, and one based on probabilistic counting. We investigate the accuracy of these algorithms in estimating the blowup for different data distributions and database schemas. The algorithm based upon probabilistic counting is particularly attractive, since it estimates the storage blowup to within provable error bounds while performing only a single scan of the data. *Work supported by an IBM CAS Fellowship, NSF grant IRI9157357, and a grant from IBM under the University Partnership Program. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying 1:s by permission of the Very Large Data Base Endowm.ent. To copy otherwise, 01‘ to republish, requires a fee and or special permission j orn the En.do?ument. Proceedings of the 22nd VLDB Conference Mumbai(Bombay), India, 1996
@cite_41: We present three algorithms to count the number of distinct elements in a data stream to within a factor of 1 ± ?. Our algorithms improve upon known algorithms for this problem, and offer a spectrum of time space tradeoffs.
@cite_40: Using an auxiliary memory smaller than the size of this abstract, the LogLog algorithm makes it possible to estimate in a single pass and within a few percents the number of different words in the whole of Shakespeare’s works. In general the LogLog algorithm makes use of m “small bytes” of auxiliary memory in order to estimate in a single pass the number of distinct elements (the “cardinality”) in a file, and it does so with an accuracy that is of the order of 1 sqrtm. The “small bytes” to be used in order to count cardinalities till N max comprise about loglog N max bits, so that cardinalities well in the range of billions can be determined using one or two kilobytes of memory only. The basic version of the LogLog algorithm is validated by a complete analysis. An optimized version, super–LogLog, is also engineered and tested on real-life data. The algorithm parallelizes optimally.
@cite_83: This paper introduces a class of probabilistic counting algorithms with which one can estimate the number of distinct elements in a large collection of data (typically a large file stored on disk) in a single pass using only a small additional storage (typically less than a hundred binary words) and only a few operations per element scanned. The algorithms are based on statistical observations made on bits of hashed values of records. They are by construction totally insensitive to the replicative structure of elements in the file; they can be used in the context of distributed systems without any degradation of performances and prove especially useful in the context of data bases query optimisation.
@cite_51: We present a probabilistic algorithm for counting the number of unique values in the presence of duplicates. This algorithm has O ( q ) time complexity, where q is the number of values including duplicates, and produces an estimation with an arbitrary accuracy prespecified by the user using only a small amount of space. Traditionally, accurate counts of unique values were obtained by sorting, which has O ( q log q ) time complexity. Our technique, called linear counting , is based on hashing. We present a comprehensive theoretical and experimental analysis of linear counting. The analysis reveals an interesting result: A load factor (number of unique values hash table size) much larger than 1.0 (e.g., 12) can be used for accurate estimation (e.g., 1 of error). We present this technique with two important applications to database problems: namely, (1) obtaining the column cardinality (the number of unique values in a column of a relation) and (2) obtaining the join selectivity (the number of unique values in the join column resulting from an unconditional join divided by the number of unique join column values in the relation to he joined). These two parameters are important statistics that are used in relational query optimization and physical database design.
A more sophisticated view-size estimation algorithm used in the context of data warehousing and OLAP @cite_26 @cite_35 is logarithmic probabilistic counting @cite_83 . This approach requires a single pass and almost no memory, but it assumes independent hashing for which no algorithm using limited storage is known @cite_41 . Practical results are sometimes disappointing @cite_30 , possibly because many random hash values need to be computed for each data point. Other variants of this approach include linear probabilistic counting @cite_51 @cite_38 and loglog counting @cite_40 .