# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 5 Conclusions and Future Work  
In this paper, we have introduced a new dynamic algorithm, named queue-2 hc, to update 2-hop-cover labelings, as a consequence of decremental updates, in time-evolving graphs. We have shown its correctness and analyzed its computational complexity in the worst case. Not surprisingly, the worst-case analysis does not capture well the true performance of the new algorithm. In fact, extensive experimentation we conducted, to assess the performance of queue-2 hc, shows queue-2 hc is very effective in practice, and outperforms by far the only other known solutions for the problem, i.e., the recomputation from scratch [7] and algorithm bidir-2 hc[26]. Therefore, we provide strong evidence that queue-2 hc can considered the reference solution to allow distance mining when decremental graph operations can occur in time-evolving scenarios.  
To achieve a complete framework for handling efficiently distance queries in massive time-evolving graphs, future works following this study should concentrate on removing the main limitation of the only known algorithm able to handle incremental operations that is resume-2 hc[8]. In fact, this algorithm ignores outdated entries that are induced by incremental modifications: this does not affect correctness but leads to degradation in query performance and to the need for periodic reprocessing (see [8; 29] for more details).  
Another interesting direction should be to extend the experimental evaluation to: (i) consider the greedy ordering of [3]; (ii) include larger inputs or real-world sequences of graph modifications; (iii) investigate the existence of relationships of correlation between graph features (e.g., density, planarity or regularity) and the performance of both 2-hop-cover labelings and the corresponding algorithms, namely fs-2 hc, resume-2 hc and queue-2 hc. This could lead to a more refined analysis explaining why dynamic approaches are so effective in practice, despite bad worst-case bounds (as done in the past for other algorithmic frameworks, such as speed-up techniques for [PERSON]'s algorithm in road networks).  
Finally, it would be remarkable to develop an algorithm even faster than queue-2 hc, in practice. An idea in this sense could be that of adopting a sort of memorization approach, by precomputing and maintaining, during the evolution of the graph, some additional (compact) data structure storing information about central vertices or critical arcs, to faster identify or update outdated label entries. The benefits of this strategy, however, could be limited due to overhead that would be required to also update the additional data structure itself. An attractive alternative could be to find a lower bound on the computational effort that is necessary to update a 2-hop-cover labeling under decremental operations.  
This work has been partially supported by the Italian National Group for Scientific Computation GNCS-INdAM--Program \"Finanziamento Giovani Ricercatori 2019-2020\"--Project: \"Toward Efficient Mining of Massive Dynamic Graphs: Theory and Applications\" and by Project \"ASSIOMI--Algorithms, Systems and Devices for Machine Monitoring and Diagnosing in Smart Factories (Algorithm Sistemi e diSpositivI per mOnitoraggio e diagnostic di Macchine per le fabbriche Intelligenti)\".  
**Conflicts of Interest:** The authors declare no conflict of interest.