Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic

Estimating the number of distinct elements in a large multiset has several applications, and hence has attracted active research in the past two decades. Several sampling and sketching algorithms have been proposed to accurately solve this problem. The goal of the literature has always been to estimate the number of distinct elements while using minimal resources. However, in some modern applications, the accuracy of the estimate is of primal importance, and businesses are willing to trade more resources for better accuracy. Throughout our experience with building a distinct count system at a major search engine, Ask.com, we reviewed the literature of approximating distinct counts, and compared most algorithms in the literature. We deduced that Linear Counting, one of the least used algorithms, has unique and impressive advantages when the accuracy of the distinct count is critical to the business. For other estimators to attain comparable accuracy, they need more space than Linear Counting. We have supported our analytical results through comprehensive experiments. The experimental results highly favor Linear Counting when the number of distinct elements is large and the error tolerance is low.

估计大型多重集中不同元素的数量有多种应用，因此在过去二十年中吸引了积极的研究。已经提出了几种采样和草图算法来精确地解决这个问题。文献的目标一直是在使用最少资源的情况下估计不同元素的数量。然而，在一些现代应用中，估计的准确性至关重要，企业愿意为了更好的准确性而投入更多资源。在我们为大型搜索引擎Ask.com构建一个不同计数系统的过程中，我们回顾了近似不同计数的文献，并比较了文献中的大多数算法。我们推断出，线性计数（一种最少被使用的算法）在不同计数的准确性对业务至关重要时具有独特且令人印象深刻的优势。对于其他估计器要达到相当的准确性，它们需要比线性计数更多的空间。我们通过综合实验支持了我们的分析结果。当不同元素的数量很大且误差容忍度很低时，实验结果非常有利于线性计数。