A LINEAR-TIME PROBABILISTIC COUNTING ALGORITHM FOR DATABASE APPLICATIONS
A LINEAR-TIME PROBABILISTIC COUNTING ALGORITHM FOR DATABASE APPLICATIONS
复制标题
DOI：
10.1145/78922.78925
复制
发表时间：
1990-06-01
影响因子：
1.8
通讯作者：
TAYLOR, HM
中科院分区：
文献类型：
--
作者：
WHANG, KY;VANDERZANDEN, BT;TAYLOR, HM
我们提出了一个概率算法，用于计算存在重复的唯一值的数量。该算法具有O（q）的时间复杂度，其中q是包含重复值的值的数量，并且仅使用少量的空间就可以产生具有用户预先指定的任意精度的估计。传统上，唯一值的精确计数是通过排序获得的，排序的时间复杂度为O（qlogq）。我们的技术，称为线性计数，是基于哈希。我们提出了一个全面的理论和实验分析的线性计数。分析揭示了一个有趣的结果：负载因子（唯一值的数量/哈希表大小）远大于1.0（例如，12)可用于精确估计（例如，1%的误差）。我们提出了这种技术与两个重要的应用数据库问题：即（1）获得列基数（在一个关系的列中的唯一值的数量）和（2）获得连接选择性（在连接列中的唯一值的数量从一个无条件连接除以唯一连接列值的数量在关系到他加入）。这两个参数是关系查询优化和物理数据库设计中使用的重要统计信息。
We present a probabilistic algorithm for counting the number of unique values in the presence of duplicates. This algorithm hasO(q) time complexity, whereqis 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 hasO(qlogq) time complexity. Our technique, calledlinear 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.