On Reporting Durable Patterns in Temporal Proximity Graphs
Proceedings of the ACM on Management of Data · 10.05.2024 · 2 (2) · 1-26
DOI: 10.1145/3651144 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2024. Verfasst von Pankaj K. Agarwal und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 56 Literaturangaben. Gefördert von: NSF, US-Israel grant.
Abstract (Originalsprache)
Finding patterns in graphs is a fundamental problem in databases and data mining. In many applications, graphs are temporal and evolve over time, so we are interested in finding durable patterns, such as triangles and paths, which persist over a long time. While there has been work on finding durable simple patterns, existing algorithms do not have provable guarantees and run in strictly super-linear time. The paper leverages the observation that many graphs arising in practice are naturally proximity graphs or can be approximated as such, where nodes are embedded as points in some high-dimensional space, and two nodes are connected by an edge if they are close to each other. We work with an implicit representation of the proximity graph, where nodes are additionally annotated by time intervals, and design near-linear-time algorithms for finding (approximately) durable patterns above a given durability threshold. We also consider an interactive setting where a client experiments with different durability thresholds in a sequence of queries; we show how to compute incremental changes to result patterns efficiently in time near-linear to the size of the changes.
Förderung
- NSF
- US-Israel grant
Zitieren
APA
Agarwal, P. K., Hu, X., Sintos, S., & Yang, J. (2024). On Reporting Durable Patterns in Temporal Proximity Graphs. Proceedings of the ACM on Management of Data, 2(2), 1-26. https://doi.org/10.1145/3651144
Vancouver
Agarwal PK, Hu X, Sintos S, Yang J. On Reporting Durable Patterns in Temporal Proximity Graphs. Proceedings of the ACM on Management of Data. 2024;2(2):1-26. doi:10.1145/3651144
BibTeX
@article{Agarwal2024,
author = {Agarwal, Pankaj K. and Hu, Xiao and Sintos, Stavros and Yang, Jun},
title = {On Reporting Durable Patterns in Temporal Proximity Graphs},
journal = {Proceedings of the ACM on Management of Data},
year = {2024},
volume = {2},
number = {2},
pages = {1--26},
doi = {10.1145/3651144}
}
EUVIMED