Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 5872
- Type
- E - Conference contribution
- DOI
-
10.1145/2746539.2746592
- Title of conference / published proceedings
- Forty-seventh annual ACM symposium on Theory of computing
- First page
- 173
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- June
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
T - Theory and Foundations
- Citation count
- 22
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Published in one of the two top conferences in theoretical computer science, this paper considers a widely studied data mining problem motivated by community detection in social networks, and gives the first result at the intersection of dynamic algorithms and streaming algorithms. Along with three other papers, it forms the basis of a successful EPSRC grant proposal (EP/S03353X/1). McGregor et al. (UMass, Amherst) and Esfandiari, Hajiaghayi (University of Maryland), Woodruff (IBM) subsequently simplify the random sampling framework introduced here. This leads to a further improvement in STOC 2020 by Sawlani (Georgia Tech) and Wang (Carnegie Mellon University).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -