Scalable temporal clique enumeration

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Downloads (Pure)

Abstract

We study the problem of enumeration of all k-sized subsets of temporal events that mutually overlap at some point in a query time window. This problem arises in many application domains, e.g., in social networks, life sciences, smart cities, telecommunications, and others. We propose a start time index (STI) approach that overcomes the efficiency bottlenecks of current methods which are based on 2-way join algorithms to enumerate temporal k-cliques. Additionally, we investigate how precomputed checkpoints can be used to further improve the efficiency of STI. Our experimental results demonstrate that STI outperforms the state of the art by a wide margin and that our checkpointing strategies are effective.

Original languageEnglish
Title of host publicationProceedings of the 16th International Symposium on Spatial and Temporal Databases, SSTD 2019
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages120-129
Number of pages10
ISBN (Electronic)978-1-4503-6280-1
DOIs
Publication statusPublished - 19 Aug 2019
Event16th International Symposium on Spatial and Temporal Databases, SSTD 2019 - Vienna, Austria
Duration: 19 Aug 201921 Aug 2019

Conference

Conference16th International Symposium on Spatial and Temporal Databases, SSTD 2019
CountryAustria
CityVienna
Period19/08/1921/08/19

Keywords

  • Checkpoints
  • Query processing
  • Temporal clique
  • Temporal join

Fingerprint Dive into the research topics of 'Scalable temporal clique enumeration'. Together they form a unique fingerprint.

  • Cite this

    Zhu, K., Fletcher, G., Yakovets, N., Papapetrou, O., & Wu, Y. (2019). Scalable temporal clique enumeration. In Proceedings of the 16th International Symposium on Spatial and Temporal Databases, SSTD 2019 (pp. 120-129). Association for Computing Machinery, Inc. https://doi.org/10.1145/3340964.3340987