Streaming algorithms for measuring H-impact

Priya Govindan, Morteza Monemizadeh, S. Muthukrishnan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We consider publication settings with positive user feedback, such as, users publishing tweets and other users retweeting them, friends posting photos and others liking them or even authors publishing research papers and others citing these publications. A well-accepted notion of "impact" for users in these settings is the H-Index, which is the largest k such that at least k publications have k or more (positive) feedback. We study how to calculate H-index on large streams of user publications and feedback. If all the items can be stored, H-index of a user can be computed by sorting. We focus on the streaming setting where as is typical, we do not have space to store all the items. We present the first known streaming algorithm for computing the H-index of a user in the cash register streaming model using space poly(1/e,log(1/δ), logn); this algorithm provides an additive e approximation. For the aggregated model where feedback for a publication is collated, we present streaming algorithms that use much less space, either only dependent on e and even a small constant. We also address the problem of finding "heavy hitters" users in H-index without estimating everyones' H-index. We present randomized streaming algorithms for finding 1 + e approximation to heavy hitters that uses space poly (1/e, log (1/δ), log n) and succeeds with probability at least 1 - δ. Again, this is the first sub-linear space algorithm for this problem, despite extensive research on heavy hitters in general. Our work initiates study of streaming algorithms for problems that estimate impact or identify impactful users.

Original languageEnglish (US)
Title of host publicationPODS 2017 - Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PublisherAssociation for Computing Machinery
Pages337-346
Number of pages10
ISBN (Electronic)9781450341981
DOIs
StatePublished - May 9 2017
Event36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017 - Chicago, United States
Duration: May 14 2017May 19 2017

Publication series

NameProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
VolumePart F127745

Other

Other36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017
CountryUnited States
CityChicago
Period5/14/175/19/17

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Streaming algorithms for measuring H-impact'. Together they form a unique fingerprint.

Cite this