Tesseract
Laurent Bindschaedler, Jasmina Malicevic, Baptiste Lepers et al. · 2021
Tesseract is the first distributed system for executing general graph mining algorithms on evolving graphs. Tesseract scales out by decomposing a stream of graph updates into per-update mining tasks and dynamically assigning these tasks to a set of distributed workers. We present a novel approach to change detection that efficiently determines the exact modifications to the algorithm's output for each update to the input graph. We use a disaggregated, multiversioned graph store to allow workers to process updates independently, without producing duplicates. Moreover, Tesseract provides interactive mining insights for complex applications using an incremental aggregation API. Finally, we implement and evaluate Tesseract and demonstrate that it achieves orders-of-magnitude improvements over state-of-the-art systems.
Cited by 23 works. doi:10.1145/3447786.3456253 Open-access PDF
Authors
References
- The PageRank Citation Ranking : Bringing Order to the Web
- Network Motifs: Simple Building Blocks of Complex Networks
- Spark: cluster computing with working sets
- Algorithm 457: finding all cliques of an undirected graph
- Self-organization and identification of Web communities
- Distributed GraphLab
- 2017 USENIX Annual Technical Conference (USENIX ATC'17)
- An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
- Efficiently updating materialized views
- The webgraph framework I