Metraipolis › archive › dc_b3ee41524345

FenixWalk: Adaptive Sampling for Large-Scale Dynamic Graphs on Heterogeneous Architectures — arXiv:2611.04683

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04683
License (as archived)
CC0-1.0
Archived
2026-11-04T18:40:34.808Z
SHA-256 of the archived text
98dca12cc59f8238b3a0a165ad6764fbd5cc10b1b5402b6766bd099cbd290b4e
Stable URL of this page
https://metraipolis.com/documento/dc_b3ee41524345

How to cite

FenixWalk: Adaptive Sampling for Large-Scale Dynamic Graphs on Heterogeneous Architectures — arXiv:2611.04683 — arXiv (en), https://arxiv.org/abs/2611.04683 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b3ee41524345 (Metraipolis archive dc_b3ee41524345, sha256 98dca12cc59f8238b3a0a165ad6764fbd5cc10b1b5402b6766bd099cbd290b4e)
BibTeX
@misc{dcb3ee41524345,
  title = {FenixWalk: Adaptive Sampling for Large-Scale Dynamic Graphs on Heterogeneous Architectures — arXiv:2611.04683},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04683},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b3ee41524345; sha256 98dca12cc59f8238b3a0a165ad6764fbd5cc10b1b5402b6766bd099cbd290b4e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04683. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Random walks are fundamental to graph analytics, yet executing them efficiently on large, evolving graphs remains challenging. Existing approaches must balance sampling efficiency, update overhead, and memory consumption. Sampling structures optimized for throughput often incur substantial memory overhead and costly maintenance, whereas lightweight alternatives can suffer from high sampling latency on high-degree vertices or skewed weight distributions. These challenges become more pronounced on heterogeneous CPU--GPU platforms, where host memory provides capacity but GPU memory limits the amount of graph data that can benefit from parallel acceleration. We present FenixWalk, a memory-efficient random-walk system that combines unified in-place sampling with selective GPU acceleration for large-scale dynamic graphs. At its core, FenixWalk employs an in-place Fenwick representation that supports both rejection sampling and inverse-transform sampling without duplicating edge-level weight storage. This representation enables expected O(1) weight lookup for rejection sampling, together with O(log d) prefix sampling and updates. To exploit heterogeneous hardware efficiently, FenixWalk maintains the complete graph and its sampling structures in host memory while selectively placing frequently reused vertex-local samplers on the GPU. By transferring compact walker states instead of repeatedly migrating graph partitions, the system reduces cross-device communication and makes effective use of limited GPU memory. Experiments on large real-world graphs and representative random-walk workloads demonstrate that FenixWalk achieves average speedups ranging from 2.06x to 400.57x over existing random-walk systems.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2611.04683 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:33:07.113Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).