Streaming Algorithms for Measuring H-Impact

Summary: First streaming algorithms for computing users' H-index: cash‑register model yields an additive-ε approximation in space poly(1/ε, log(1/δ), log n); aggregated model algorithms use much smaller (ε‑dependent or constant) space. Also give randomized streaming heavy‑hitters methods to find users within a 1+ε factor of top H-index using poly(1/ε, log(1/δ)) space. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1729
Venue: PODS
Year: 2017
Pagerank: 5.4574671e-05
Overall Rank: 8,267 | 43.29%
DOI: 10.1145/3034786.3056118

Incoming Non-self Citations Over Time

Authors

1. Priya Govindan (Rutgers University)
2. Morteza Monemizadeh (Rutgers University)
3. S. Muthukrishnan (Rutgers University)

BibTeX Citation

@inproceedings{govindan_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{Streaming Algorithms for Measuring H-Impact}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3056118},
        doi = {10.1145/3034786.3056118},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Govindan, Priya and Monemizadeh, Morteza and Muthukrishnan, S.},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,162	On Sketching Trimmed Statistics	2026	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185
777	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001410593

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,537	Finding Heavy-Hitters with Optimal State Changes	2026	PODS
2	7,548	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD
3	8,795	Finding Seeds and Relevant Tags Jointly: For Targeted Influence Maximization in Social Networks	2018	SIGMOD
4	5,036	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB
5	2,390	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB
6	5,669	Data Streams with Bounded Deletions	2018	PODS
7	2,260	Online Topic-Aware Influence Maximization	2015	VLDB
8	7,831	Differentially Private Hierarchical Heavy Hitters	2024	PODS
9	6,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS
10	3,989	Real-Time Influence Maximization on Dynamic Social Streams	2017	VLDB