Streaming algorithms for measuring H-impact

Priya Govindan, Morteza Monemizadeh, S. Muthukrishnan

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

    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

    ASJC Scopus subject areas

    • 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

    Govindan, P., Monemizadeh, M., & Muthukrishnan, S. (2017). Streaming algorithms for measuring H-impact. In PODS 2017 - Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (pp. 337-346). (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems; Vol. Part F127745). Association for Computing Machinery. https://doi.org/10.1145/3034786.3056118