### 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 language | English (US) |
---|---|

Title of host publication | PODS 2017 - Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |

Publisher | Association for Computing Machinery |

Pages | 337-346 |

Number of pages | 10 |

ISBN (Electronic) | 9781450341981 |

DOIs | |

State | Published - May 9 2017 |

Event | 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017 - Chicago, United States Duration: May 14 2017 → May 19 2017 |

### Publication series

Name | Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems |
---|---|

Volume | Part F127745 |

### Other

Other | 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017 |
---|---|

Country | United States |

City | Chicago |

Period | 5/14/17 → 5/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

*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