EUVIMEDEUVIMED entdecken
Crossref

On Reporting Durable Patterns in Temporal Proximity Graphs

Pankaj K. Agarwal, Xiao Hu, Stavros Sintos, Jun Yang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →