hide
Free keywords:
-
Abstract:
Counting items in a distributed system, and estimating the cardinality of
multisets in particular, is important for a large variety of applications and a
fundamental building block for emerging Internet-scale information systems.
Examples of such applications range from optimizing query access plans in
peer-to-peer data sharing, to computing the significance (rank/score) of data
items in distributed information retrieval. The general formal problem
addressed in this article is computing the network-wide distinct number of
items with some property (e.g., distinct files with file name containing
“spiderman”) where each node in the network holds an arbitrary subset, possibly
overlapping the subsets of other nodes. The key requirements that a viable
approach must satisfy are: (1) scalability towards very large network size, (2)
efficiency regarding messaging overhead, (3) load balance of storage and
access, (4) accuracy of the cardinality estimation, and (5) simplicity and easy
integration in applications. This article contributes the DHS (Distributed Hash
Sketches) method for this problem setting: a distributed, scalable, efficient,
and accurate multiset cardinality estimator. DHS is based on hash sketches for
probabilistic counting, but distributes the bits of each counter across network
nodes in a judicious manner based on principles of Distributed Hash Tables,
paying careful attention to fast access and aggregation as well as update
costs. The article discusses various design choices, exhibiting tunable
trade-offs between estimation accuracy, hop-count efficiency, and load
distribution fairness. We further contribute a full-fledged, publicly
available, open-source implementation of all our methods, and a comprehensive
experimental evaluation for various settings.
