Graph sketches: sparsification, spanners, and subgraphs

By Kook Jin Ahn, Sudipto Guha, Andrew McGregor. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2012

334 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/984b5464f58e3d6270b385c96e96d788e7fbd232

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Adam Bates
2. Andrew McGregor
3. Margo I. Seltzer
4. Thomas Pasquier
5. Xueyuan Han
6. James W. Mickens
7. Cynthia Rudin

In Computational Mechanics

1. Andrew McGregor

Citations in the corpus

• UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats (2020, methodology): “UNICORN employs a similaritypreserving hashing technique [132] to transform the histogram to a graph sketch [7].”
• Graph stream algorithms: a survey (2014, methodology): “(2t− 1)-Spanners O(n) space [11, 23] Only multiple pass results known [6] O( √ wn(1+1/t)) space [22]”