NDLI: An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

Please wait, while we are loading the content...

A Theory of Regular Queries

2016 ACM PODS Alberto O. Mendelzon Test-of-Time Award

Optimal Score Aggregation Algorithms

Incremental View Maintenance For Collection Programming

Data Management for Social Networking

Verification of Hierarchical Artifact Systems

Schema Validation via Streaming Circuits

Logical Aspects of Massively Parallel and Distributed Systems

Counting Answers to Existential Positive Queries: A Complexity Classification

Towards Tight Bounds for the Streaming Set Cover Problem

Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures

FAQ: Questions Asked Frequently

Hypertree Decompositions: Questions and Answers

AJAR: Aggregations and Joins over Annotated Relations

Recency-Bounded Verification of Dynamic Database-Driven Systems

Variability in Data Streams

Computing Join Queries with Functional Dependencies

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

Space Lower Bounds for Itemset Frequency Sketches

Shortest Paths and Distances with Differential Privacy

Bounded Query Rewriting Using Views

Making SQL Queries Correct on Incomplete Databases: A Feasibility Study

Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors

Semantic Acyclicity Under Constraints

Better Algorithms for Counting Triangles in Data Streams

Are Few Bins Enough: Testing Histogram Distributions

Minimization of Tree Pattern Queries

Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable

Designing a Query Language for RDF: Marrying Open and Closed Worlds

Efficient Top-k Indexing via General Reductions

Tractable Lineages on Treelike Instances: Limits and Extensions

Locating a Small Cluster Privately

Range-Max Queries on Uncertain Data

Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins

Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries

Fast Algorithms for Parsing Sequences of Parentheses with Few Errors

On the Complexity of Inner Product Similarity Join

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

Content Provider	ACM Digital Library
Author	Dey, Palash Bhattacharyya, Arnab Woodruff, David P.
Abstract	We give the first optimal bounds for returning the $l_{1}-heavy$ hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of m items in {1, 2, ., n} and parameters 0 < ε < φ ≤ 1, let $f_{i}$ denote the frequency of item i, i.e., the number of times item i occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items i for which $f_{i}$ ≥ φ m, returns no items j for which $f_{j}$ ≤ (φ -ε)m, and returns approximations $~f_{i}$ with $\|~f_{i}$ - $f_{i}\|$ ≤ ε m for each item i that it returns. Our algorithm uses $O(ε^{-1}$ $logφ^{-1}$ + $φ^{-1}$ log n + log log m) bits of space, processes each stream update in O(1) worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive ε m error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on Algorithms for Data Streams for the case of $l_{1}-heavy$ hitters. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by rank aggregation and voting schemes, and show how our techniques can be applied in such settings. Unlike the traditional heavy hitters problem, some of these variants look at comparisons between items rather than numerical values to determine the frequency of an item.
Starting Page	385
Ending Page	400
Page Count	16
File Format	PDF
ISBN	9781450341912
DOI	10.1145/2902251.2902284
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-06-15
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Heavy hitters Algorithms Data streams Frequent items
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

BPTree: An $ℓ_{2}$ Heavy Hitters Algorithm Using Constant Memory

Beating CountSketch for heavy hitters in insertion streams

Plan of attack Frequent Items / Heavy Hitters Counting Distinct Elements Clustering items in Streams What are we going to do today? Frequent items – Classical algorithms

An Exact and O(1) Time Heaviest and Lightest Hitters Algorithm for Sliding-Window Data Streams

Beating CountSketch for Heavy Hitters in Insertion Streams

Finding frequent items in probabilistic data

Adaptive shared-state sampling

New Algorithms for Heavy Hitters in Data Streams

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

Similar Documents

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

BPTree: An $ℓ_{2}$ Heavy Hitters Algorithm Using Constant Memory

Beating CountSketch for heavy hitters in insertion streams

Plan of attack Frequent Items / Heavy Hitters Counting Distinct Elements Clustering items in Streams What are we going to do today? Frequent items – Classical algorithms

An Exact and O(1) Time Heaviest and Lightest Hitters Algorithm for Sliding-Window Data Streams

Beating CountSketch for Heavy Hitters in Insertion Streams

Finding frequent items in probabilistic data

Adaptive shared-state sampling

New Algorithms for Heavy Hitters in Data Streams

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems