Counting at Large: Efficient Cardinality Estimation in Internet-Scale Data Networks

@inproceedings{citeulike:890226, abstract = {Counting in general, and estimating the cardinality of (multi-) sets in particular, is highly desirable for a large variety of applications, representing a foundational block for the efficient deployment and access of emerging internetscale information systems. Examples of such applications range from optimizing query access plans in internet-scale databases, to evaluating the significance (rank/score) of various data items in information retrieval applications. The key constraints that any acceptable solution must satisfy are: (i) efficiency: the number of nodes that need be contacted for counting purposes must be small in order to enjoy small latency and bandwidth requirements; (ii) scalability, seemingly contradicting the efficiency goal: arbitrarily large numbers of nodes nay need to add elements to a (multi-) set, which dictates the need for a highly distributed solution, avoiding server-based scalability, bottleneck, and availability problems; (iii) access and storage load balancing: counting and related overhead chores should be distributed fairly to the nodes of the network; (iv) accuracy: tunable, robust (in the presence of dynamics and failures) and highly accurate cardinality estimation; (v) simplicity and ease of integration: special, solution-specific indexing structures should be avoided. In this paper, first we contribute a highly-distributed, scalable, efficient, and accurate (multi-) set cardinality estimator. Subsequently, we show how to use our solution to build and maintain histograms, which have been a basic building block for query optimization for centralized databases, facilitating their porting into the realm of internet-scale data networks.}, author = {Ntarmos, N. and Triantafillou, P. and Weikum, G. }, citeulike-article-id = {890226}, comment = {Algorithm for estimating number of distinct elements.}, journal = {Data Engineering, 2006. ICDE '06. Proceedings of the 22nd International Conference on}, keywords = {math}, pages = {40}, posted-at = {2006-10-09 16:36:55}, priority = {1}, title = {Counting at Large: Efficient Cardinality Estimation in Internet-Scale Data Networks}, url = {http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=1617408}, year = {2006} }

TY - CONF ID - citeulike:890226 L3 - citeulike-article-id:890226 TI - Counting at Large: Efficient Cardinality Estimation in Internet-Scale Data Networks JF - Data Engineering, 2006. ICDE '06. Proceedings of the 22nd International Conference on SP - 40 EP - 40 N2 - Counting in general, and estimating the cardinality of (multi-) sets in particular, is highly desirable for a large variety of applications, representing a foundational block for the efficient deployment and access of emerging internetscale information systems. Examples of such applications range from optimizing query access plans in internet-scale databases, to evaluating the significance (rank/score) of various data items in information retrieval applications. The key constraints that any acceptable solution must satisfy are: (i) efficiency: the number of nodes that need be contacted for counting purposes must be small in order to enjoy small latency and bandwidth requirements; (ii) scalability, seemingly contradicting the efficiency goal: arbitrarily large numbers of nodes nay need to add elements to a (multi-) set, which dictates the need for a highly distributed solution, avoiding server-based scalability, bottleneck, and availability problems; (iii) access and storage load balancing: counting and related overhead chores should be distributed fairly to the nodes of the network; (iv) accuracy: tunable, robust (in the presence of dynamics and failures) and highly accurate cardinality estimation; (v) simplicity and ease of integration: special, solution-specific indexing structures should be avoided. In this paper, first we contribute a highly-distributed, scalable, efficient, and accurate (multi-) set cardinality estimator. Subsequently, we show how to use our solution to build and maintain histograms, which have been a basic building block for query optimization for centralized databases, facilitating their porting into the realm of internet-scale data networks. KW - math N1 - Algorithm for estimating number of distinct elements. AU - Ntarmos, N AU - Triantafillou, P AU - Weikum, G PY - 2006/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1617408 ER -