Mining graphs, upon query, for k shortest paths between vertex pairs is a prominent primitive to support several analytics tasks on complex networked datasets. The state-of-the-art method to implement this primitive is kPll, a framework that provides very fast query answering, even for large inputs and volumes of queries, by pre-computing and exploiting an appropriate index of the graph. However, if the graph's topology undergoes changes over time, such index might become obsolete and thus yield incorrect query results. Re-building the index from scratch, upon every modification, induces unsustainable time overheads, incompatible with applications using k shortest paths for analytics purposes. Motivated by this limitation, in this paper, we introduce decKpll, the first dynamic algorithm to maintain a kPll index under decremental modifications. We assess the effectiveness and scalability of our algorithm through extensive experimentation and show it updates kPll indices orders of magnitude faster than the re-computation from scratch, while preserving its compactness and query performance. We also combine decKpll with incKpll, the only known dynamic algorithm to maintain a kPll index under incremental modifications, and hence showcase, on real-world datasets, the first method to support fast extraction of k shortest paths from graphs that evolve by arbitrary topological changes.

On Mining Dynamic Graphs for k Shortest Paths

D'Ascenzo Andrea
;
D'Emidio Mattia
2025-01-01

Abstract

Mining graphs, upon query, for k shortest paths between vertex pairs is a prominent primitive to support several analytics tasks on complex networked datasets. The state-of-the-art method to implement this primitive is kPll, a framework that provides very fast query answering, even for large inputs and volumes of queries, by pre-computing and exploiting an appropriate index of the graph. However, if the graph's topology undergoes changes over time, such index might become obsolete and thus yield incorrect query results. Re-building the index from scratch, upon every modification, induces unsustainable time overheads, incompatible with applications using k shortest paths for analytics purposes. Motivated by this limitation, in this paper, we introduce decKpll, the first dynamic algorithm to maintain a kPll index under decremental modifications. We assess the effectiveness and scalability of our algorithm through extensive experimentation and show it updates kPll indices orders of magnitude faster than the re-computation from scratch, while preserving its compactness and query performance. We also combine decKpll with incKpll, the only known dynamic algorithm to maintain a kPll index under incremental modifications, and hence showcase, on real-world datasets, the first method to support fast extraction of k shortest paths from graphs that evolve by arbitrary topological changes.
2025
978-3-031-78541-2
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/256159
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact