Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3340964.3340987acmotherconferencesArticle/Chapter ViewAbstractPublication PagessstdConference Proceedingsconference-collections
research-article

Scalable temporal clique enumeration

Published: 19 August 2019 Publication History

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.

References

[1]
CAIDA UCSD anonymized internet traces dataset - {dates used}. http://www.caida.org/data/passive/passive_dataset.xml.
[2]
NYC citi-bikes. https://www.citibikenyc.com/system-data.
[3]
NYC Free Hired Vehicles. http://www.nyc.gov/html/tlc/downloads/pdf/data_dictionary_trip_records_fhv.pdf.
[4]
NYC Yellow Taxi. http://www.nyc.gov/html/tlc/downloads/pdf/data_dictionary_trip_records_yellow.pdf.
[5]
Panagiotis Bouros and Nikos Mamoulis. A forward scan based plane sweep algorithm for parallel interval joins. Proceedings of the VLDB Endowment, 10(11): 1346--1357, 2017.
[6]
Thomas Brinkhoff, Hans-Peter Kriegel, and Bernhard Seeger. Efficient processing of spatial joins using R-trees, volume 22. ACM, 1993.
[7]
Francesco Cafagna and Michael H Böhlen. Disjoint interval partitioning. The VLDB Journal, 26(3):447--466, 2017.
[8]
Lin Chen, Yong Deng, Weihua Luo, Zhen Wang, and Shaoqun Zeng. Detection of bursts in neuronal spike trains by the mean inter-spike interval method. Progress in Natural Science, 19(2):229--235, 2009.
[9]
Reynold Cheng, Sarvjeet Singh, Sunil Prabhakar, Rahul Shah, Jeffrey Scott Vitter, and Yuni Xia. Efficient join processing over uncertain data. In International Conference on Information and Knowledge Management CIKM, pages 738--747, 2006.
[10]
Anton Dignös, Michael H Böhlen, and Johann Gamper. Overlap interval partition join. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pages 1459--1470. ACM, 2014.
[11]
Jost Enderle. Joining interval data in relational databases. In ACM SIGMOD International Conference on Management of Data, pages 683--694, 2004.
[12]
Dengfeng Gao, Christian S. Jensen, Richard T. Snodgrass, and Michael D. Soo. Join operations in temporal databases. The VLDB Journal, 14(1):2--29, 2005.
[13]
K-I Goh and A-L Barabási. Burstiness and memory in complex systems. EPL (Europhysics Letters), 81(4):48002, 2008.
[14]
Martin Kaufmann, Peter M Fischer, Norman May, Chang Ge, Anil K Goel, and Donald Kossmann. Bi-temporal timeline index: A data structure for processing queries on bi-temporal data. In IEEE International Conference on Data Engineering, pages 471--482, 2015.
[15]
Martin Kaufmann, Amin Amiri Manjili, Panagiotis Vagenas, Peter Michael Fischer, Donald Kossmann, Franz Färber, and Norman May. Timeline index: a unified data structure for processing queries on temporal data in sap hana. In ACM SIGMOD International Conference on Management of Data, pages 1173--1184. ACM, 2013.
[16]
Ji-Zhou Luo, Sheng-Fei Shi, Guang Yang, Hong-Zhi Wang, and Jian-Zhong Li. O2ijoin: An efficient index-based algorithm for overlap interval join. Journal of Computer Science and Technology, 33(5):1023--1038, 2018.
[17]
Burçak Otlu and Tolga Can. Joa: Joint overlap analysis of multiple genomic interval sets. BMC bioinformatics, 20(1):121, 2019.
[18]
Danila Piatov, Sven Helmer, and Anton Dignös. An interval join optimized for modern hardware. In Data Engineering (ICDE), 2016 IEEE 32nd International Conference on, pages 1098--1109. IEEE, 2016.

Cited By

View all
  • (2024)Temporal Subgraph Matching Method for Multi-Connected Temporal GraphInformation Sciences10.1016/j.ins.2024.121320(121320)Online publication date: Aug-2024
  • (2024)A Recursive Approach for Maximal ($$\varDelta , \gamma $$)-Clique Enumeration in Temporal NetworksAdvances in Databases and Information Systems10.1007/978-3-031-70626-4_6(79-92)Online publication date: 1-Sep-2024
  • (2023)Densest Periodic Subgraph Mining on Large Temporal GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.323378835:11(11259-11273)Online publication date: 1-Nov-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences
SSTD '19: Proceedings of the 16th International Symposium on Spatial and Temporal Databases
August 2019
245 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

  • TU Wien: TU Wien

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 August 2019

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. checkpoints
  2. query processing
  3. temporal clique
  4. temporal join

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Funding Sources

Conference

SSTD '19

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)15
  • Downloads (Last 6 weeks)2
Reflects downloads up to 26 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Temporal Subgraph Matching Method for Multi-Connected Temporal GraphInformation Sciences10.1016/j.ins.2024.121320(121320)Online publication date: Aug-2024
  • (2024)A Recursive Approach for Maximal ($$\varDelta , \gamma $$)-Clique Enumeration in Temporal NetworksAdvances in Databases and Information Systems10.1007/978-3-031-70626-4_6(79-92)Online publication date: 1-Sep-2024
  • (2023)Densest Periodic Subgraph Mining on Large Temporal GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.323378835:11(11259-11273)Online publication date: 1-Nov-2023
  • (2023)HINT: a hierarchical interval index for Allen relationshipsThe VLDB Journal10.1007/s00778-023-00798-w33:1(73-100)Online publication date: 1-Jun-2023
  • (2022)On Compressing Temporal Graphs2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00102(1301-1313)Online publication date: May-2022
  • (2022)On fast enumeration of maximal cliques in large graphsExpert Systems with Applications10.1016/j.eswa.2021.115915187(115915)Online publication date: Jan-2022
  • (2022)What’s New in Temporal Databases?Advances in Databases and Information Systems10.1007/978-3-031-15740-0_5(45-58)Online publication date: 5-Sep-2022
  • (2021)Leveraging Temporal and Topological Selectivities in Temporal-clique Subgraph Query Processing2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00064(672-683)Online publication date: Apr-2021

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media