EdgeSketch: Efficient Analysis of Massive Graph Streams
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910029139935232 |
|---|---|
| author | Lemiesz, Jakub Yang, Dingqi Cudré-Mauroux, Philippe |
| author_facet | Lemiesz, Jakub Yang, Dingqi Cudré-Mauroux, Philippe |
| contents | We introduce EdgeSketch, a compact graph representation for efficient analysis of massive graph streams. EdgeSketch provides unbiased estimators for key graph properties with controllable variance and supports implementing graph algorithms on the stored summary directly. It is constructed in a fully streaming manner, requiring a single pass over the edge stream, while offline analysis relies solely on the sketch. We evaluate the proposed approach on two representative applications: community detection via the Louvain method and graph reconstruction through node similarity estimation. Experiments demonstrate substantial memory savings and runtime improvements over both lossless representations and prior sketching approaches, while maintaining reliable accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18957 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | EdgeSketch: Efficient Analysis of Massive Graph Streams Lemiesz, Jakub Yang, Dingqi Cudré-Mauroux, Philippe Data Structures and Algorithms Networking and Internet Architecture We introduce EdgeSketch, a compact graph representation for efficient analysis of massive graph streams. EdgeSketch provides unbiased estimators for key graph properties with controllable variance and supports implementing graph algorithms on the stored summary directly. It is constructed in a fully streaming manner, requiring a single pass over the edge stream, while offline analysis relies solely on the sketch. We evaluate the proposed approach on two representative applications: community detection via the Louvain method and graph reconstruction through node similarity estimation. Experiments demonstrate substantial memory savings and runtime improvements over both lossless representations and prior sketching approaches, while maintaining reliable accuracy. |
| title | EdgeSketch: Efficient Analysis of Massive Graph Streams |
| topic | Data Structures and Algorithms Networking and Internet Architecture |
| url | https://arxiv.org/abs/2602.18957 |