SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS

DOI10.1142/S0218195908002520zbMath1147.68461OpenAlexW2143606444MaRDI QIDQ3521590

Christian Sohler, Gereon Frahling, Piotr Indyk

Publication date: 26 August 2008

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195908002520

zbMATH Keywords

random samplingminimum spanning tree

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (6)

Dynamic coresets ⋮ Streaming Embeddings with Slack ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ Improved Time and Space Bounds for Dynamic Range Mode ⋮ Perfect $L_p$ Sampling in a Data Stream ⋮ Efficient sampling of non-strict turnstile data streams

Cites Work

• A guided tour of Chernoff bounds
• \(\epsilon\)-nets and simplex range queries
• Universal classes of hash functions
• The space complexity of approximating the frequency moments
• Approximating extent measures of points
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time

This page was built for publication: SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS