Probabilistic counting algorithms for data base applications
From MaRDI portal
Publication:1069325
DOI10.1016/0022-0000(85)90041-8zbMath0583.68059OpenAlexW2025051251WikidataQ59831137 ScholiaQ59831137MaRDI QIDQ1069325
G. Nigel Martin, Philippe Flajolet
Publication date: 1985
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/inria-00076244/file/RR-0313.pdf
Related Items (72)
On finding common neighborhoods in massive graphs. ⋮ Binary vectors for fast distance and similarity estimation ⋮ The Online Space Complexity of Probabilistic Languages ⋮ Mellin transforms and asymptotics. The mergesort recurrence ⋮ Counting distinct items over update streams ⋮ Unnamed Item ⋮ On the distribution for the duration of a randomized leader election algorithm ⋮ A Statistical Analysis of Probabilistic Counting Algorithms ⋮ The number of distinct values in a geometrically distributed sample ⋮ The Cost of Fault Tolerance in Multi-Party Communication Complexity ⋮ Prefixes of infinite words and ambiguous context-free languages ⋮ The Largest Missing Value in a Sample of Geometric Random Variables ⋮ Occupancy schemes associated to Yule processes ⋮ Streaming algorithms for multitasking scheduling with shared processing ⋮ Combinatorics of geometrically distributed random variables: Left-to-right maxima ⋮ Summary Data Structures for Massive Data ⋮ Spatially-decaying aggregation over a network ⋮ Analytical depoissonization and its applications ⋮ A variation of the Newton-Pepys problem and its connections to size-estimation problems ⋮ Thue, combinatorics on words, and conjectures inspired by the Thue-Morse sequence ⋮ Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity ⋮ The visibility parameter for words and permutations ⋮ When distributed computation is communication expensive ⋮ More infinite products: Thue-Morse and the gamma function ⋮ Philippe Flajolet's early work in combinatorics ⋮ Combinatorics of geometrically distributed random variables: Run statistics ⋮ Accurate and precise aggregation counting ⋮ Simplified Planar Coresets for Data Streams ⋮ Estimating hybrid frequency moments of data streams ⋮ An analytic approach to the asymptotic variance of trie statistics and related structures ⋮ FURL: fixed-memory and uncertainty reducing local triangle counting for multigraph streams ⋮ Streaming techniques and data aggregation in networks of tiny artefacts ⋮ Secure and highly-available aggregation queries in large-scale sensor networks via set sampling ⋮ A flexible way of counting large numbers approximately in small registers ⋮ A unified scheme for generalizing cardinality estimators to sum aggregation ⋮ Distributed data clustering in sensor networks ⋮ Paperfolding infinite products and the gamma function ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ Mellin transforms and asymptotics: Harmonic sums ⋮ Measuring the impact of MVC attack in large complex networks ⋮ Accuracy vs. Lifetime: Linear sketches for aggregate queries in sensor networks ⋮ Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. ⋮ Efficient sampling strategies for relational database operations ⋮ On gaps and unoccupied urns in sequences of geometrically distributed random variables ⋮ Aggregate query processing in the presence of duplicates in wireless sensor networks ⋮ Statistical estimation with bounded memory ⋮ LiMoSense: live monitoring in dynamic sensor networks ⋮ Distinctness of compositions of an integer: A probabilistic analysis ⋮ The zeta-regularized product of odious numbers ⋮ Give me some slack: efficient network measurements ⋮ Incremental delay enumeration: space and time ⋮ A note on compressed sensing and the complexity of matrix multiplication ⋮ Gap-free compositions and gap-free samples of geometric random variables ⋮ Secure and efficient multiparty private set intersection cardinality ⋮ On adaptive sampling ⋮ Transcendental Infinite Products Associated with the $\pm 1$ Thue-Morse Sequence ⋮ Probabilistic analysis of adaptative sampling ⋮ Analytic analysis of algorithms ⋮ How to count quickly and accurately: A unified analysis of probabilistic counting and other related problems ⋮ Approximate set union via approximate randomization ⋮ Approximate set union via approximate randomization ⋮ Fast size approximation of a radio network in beeping model ⋮ Two improved range-efficient algorithms for \(F_0\) estimation ⋮ A general method for estimating correlated aggregates over a data stream ⋮ Space‐efficient tracking of persistent items in a massive data stream ⋮ Hierarchical sampling from sketches: Estimating functions over data streams ⋮ A Note on Estimating Hybrid Frequency Moment of Data Streams ⋮ Depth First Search in the Semi-streaming Model ⋮ Accelerate the classification statistics in RFID systems ⋮ Approximating the Size of a Radio Network in Beeping Model ⋮ On Approximating Matrix Norms in Data Streams ⋮ A result in order statistics related to probabilistic counting
Cites Work
This page was built for publication: Probabilistic counting algorithms for data base applications
