Skip to main content
Springer Nature Link
Log in

TIRPClo: efficient and complete mining of time intervals-related patterns

  • Published:
Data Mining and Knowledge Discovery Aims and scope Submit manuscript

Abstract

Mining frequent Time Intervals-Related Patterns (TIRPs) from series of symbolic time intervals offers a comprehensive framework for heterogeneous, multivariate temporal data analysis in various application domains. While gaining a growing interest in recent decades, the efficient mining of frequent TIRPs is still a high computational challenge which has also not yet been investigated in its full complexity. The majority of previous methods discover only the first instances of the TIRPs within each series of symbolic time intervals, whereas their re-occurring instances are ignored. This eventually results in an incomplete discovery of frequent TIRPs, a problem that lies also in the challenge of mining only the frequent closed TIRPs, which was only recently investigated for the first time. In this paper, we introduce TIRPClo—an efficient algorithm for the complete mining of either the entire set of frequent TIRPs, or only the frequent closed TIRPs. The algorithm proposes a non-ambiguous sequential representation of symbolic time intervals series through the intervals’ end-points, as well as a memory-efficient index and a novel method for data projection, due to which it is the first algorithm to guarantee a complete discovery of frequent closed TIRPs. The experimental evaluation conducted on eleven real-world and four synthetic datasets demonstrates that TIRPClo is up to 10 times faster when mining the entire set of frequent TIRPs, and up to more than 100 times faster when mining only the frequent closed TIRPs compared to four state-of-the-art methods, while also reporting lower memory measurements.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Data availibility

To allow the complete reproducibility of our experimental results and contribute to future research in the field of frequent TIRP mining, all the real-world and synthetic datasets used in the paper, as well as our synthetic datasets generator, were made publicly available through the online repository referenced in the Introduction Sect. 1.

Code availability

The source code of the TIRPClo algorithm was also made publicly available through the online repository referenced in the Introduction Sect. 1.

Notes

  1. https://github.com/TIRPClo/Complete-Time-Intervals-Related-Patterns-Mining.

References

  • Allen JF (1983) Maintaining knowledge about temporal intervals. Commun ACM 26(11):832–843. https://doi.org/10.1145/182.358434

    Article  MATH  Google Scholar 

  • Ayres J, Flannick J, Gehrke J, et al (2002) Sequential pattern mining using a bitmap representation. In: Proceedings of the Eighth ACM SIGKDD international conference on knowledge discovery and data mining. Association for Computing Machinery, New York, NY, USA, KDD ’02, pp 429–435, https://doi.org/10.1145/775047.775109

  • Batal I, Sacchi L, Bellazzi R, et al (2009) A temporal abstraction framework for classifying clinical temporal data. In: AMIA Annual Symposium Proceedings, vol 2009. American Medical Informatics Association, Rockville, MD, p 29

  • Benavoli A, Corani G, Mangili F (2016) Should we really use post-hoc tests based on mean-ranks? J Mach Learn Res 17(1):152–161

    MathSciNet  MATH  Google Scholar 

  • Chang L, Wang T, Yang D, et al (2008) Seqstream: mining closed sequential patterns over stream sliding windows. In: 2008 Eighth IEEE International Conference on Data Mining. IEEE Computer Society, Washington, DC, USA, ICDM ’08, pp 83–92, https://doi.org/10.1109/ICDM.2008.36

  • Chen YC, Peng WC, Lee SY (2015) Mining temporal patterns in time interval-based data. IEEE Trans Knowl Data Eng 27(12):3318–3331. https://doi.org/10.1109/TKDE.2015.2454515

    Article  Google Scholar 

  • Chen YC, Weng JTY, Hui L (2016) A novel algorithm for mining closed temporal patterns from interval-based data. Knowl Inf Syst 46(1):151–183. https://doi.org/10.1007/s10115-014-0815-2

    Article  Google Scholar 

  • Demšar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30

    MathSciNet  MATH  Google Scholar 

  • Ezeife CI, Lu Y, Liu Y (2005) Plwap sequential mining: open source code. In: Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations. Association for Computing Machinery, New York, NY, USA, OSDM ’05, pp 26–35, https://doi.org/10.1145/1133905.1133910

  • Fournier-Viger P, Lin JCW, Kiran RU et al (2017) A survey of sequential pattern mining. Data Sci Pattern Recogn 1(1):54–77

    Google Scholar 

  • Fumarola F, Lanotte PF, Ceci M et al (2016) Clofast: closed sequential pattern mining using sparse and vertical id-lists. Knowl Inf Syst 48(2):429–463. https://doi.org/10.1007/s10115-015-0884-x

    Article  Google Scholar 

  • Garcia S, Herrera F (2008) An extension on" statistical comparisons of classifiers over multiple data sets" for all pairwise comparisons. J Mach Learn Res 9(12):2677

    MATH  Google Scholar 

  • Gomariz A, Campos M, Marin R, et al (2013) Clasp: An efficient algorithm for mining frequent closed sequences. In: Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Berlin, pp 50–61, https://doi.org/10.1007/978-3-642-37453-1_5

  • Han J, Pei J, Mortazavi-Asl B, et al (2000) Freespan: Frequent pattern-projected sequential pattern mining. In: Proceedings of the Sixth ACM SIGKDD international conference on knowledge discovery and data mining. Association for Computing Machinery, New York, NY, USA, KDD ’00, pp 355–359, https://doi.org/10.1145/347090.347167

  • Han J, Pei J, Mortazavi-Asl B, et al (2001) Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth. In: proceedings of the 17th international conference on data engineering. IEEE Computer Society, Washington, DC, USA, pp 215–224

  • Harel OD, Moskovitch R (2021) Complete closed time intervals-related patterns mining. In: proceedings of the 35th AAAI conference on artificial intelligence. AAAI Press, Palo Alto, CA

  • Höppner F (2001) Learning temporal rules from state sequences. In: IJCAI Workshop on Learning from Temporal and Spatial Data, Citeseer

  • Höppner F (2002) Time series abstraction methods: a survey. Informatik bewegt: Informatik 2002–32 Jahrestagung der Gesellschaft für Informatik ev (GI)

  • Huang JW, Jaysawal BP, Chen KY et al (2019) Mining frequent and top-k high utility time interval-based events with duration patterns. Knowl Inf Syst 61(3):1331–1359. https://doi.org/10.1007/s10115-019-01333-6

    Article  Google Scholar 

  • Huang KY, Chang CH, Tung JH, et al (2006) Cobra: Closed sequential pattern mining using bi-phase reduction approach. In: International Conference on data warehousing and knowledge discovery. Springer, Berlin, pp 280–291, https://doi.org/10.1007/11823728_27

  • Hui L, Chen YC, Weng JTY et al (2016) Incremental mining of temporal patterns in interval-based database. Knowl Inf Syst 46(2):423–448. https://doi.org/10.1007/s10115-015-0828-5

    Article  Google Scholar 

  • Itzhak N, Jaroszewicz S, Moskovitch R (2023) Continuously predicting a time intervals based pattern completion towards event prediction. PAKDD, Osaka, Japan

    Google Scholar 

  • Jakkula VR, Cook DJ (2011) Detecting anomalous sensor events in smart home data for enhancing the living experience. Artif Intell Smart Living 11(201):1

    Google Scholar 

  • Kam PS, Fu AWC (2000) Discovering temporal patterns for interval-based events. In: International conference on data warehousing and knowledge discovery. Springer, Berlin, pp 317–326, https://doi.org/10.1007/3-540-44466-1_32

  • Kostakis O, Gionis A (2017) On mining temporal patterns in dynamic graphs, and other unrelated problems. In: International conference on complex networks and their applications. Springer, Berlin, pp 516–527, https://doi.org/10.1007/978-3-319-72150-7_42

  • Kostakis O, Papapetrou P, Hollmén J (2011) Artemis: Assessing the similarity of event-interval sequences. In: Joint European conference on machine learning and knowledge discovery in databases, Springer, pp 229–244, https://doi.org/10.1007/978-3-642-23783-6_15

  • Kotsifakos A, Papapetrou P, Athitsos V (2013) ibsm: interval-based sequence matching. in: proceedings of the 2013 siam International Conference on Data Mining, SIAM, pp 596–604, https://doi.org/10.1137/1.9781611972832.66

  • Lavrac N, Keravnou E, Zupan B (2000) Intelligent data analysis in medicine. Encycl Comput Sci Technol 42(9):113–157

    MATH  Google Scholar 

  • Lee Z, Lindgren T, Papapetrou P (2020) Z-miner: An efficient method for mining frequent arrangements of event intervals. In: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. Association for Computing Machinery, New York, NY, USA, KDD ’20, pp 524–534, https://doi.org/10.1145/3394486.3403095

  • Lin J, Keogh E, Lonardi S, et al (2003) A symbolic representation of time series, with implications for streaming algorithms. In: Proceedings of the 8th ACM SIGMOD workshop on research issues in data mining and knowledge discovery. Association for Computing Machinery, New York, NY, USA, DMKD ’03, pp 2–11, https://doi.org/10.1145/882082.882086

  • Lin MY, Lee SY (2002) Fast discovery of sequential patterns by memory indexing. In: International conference on data warehousing and knowledge discovery. Springer, Berlin, pp 150–160, https://doi.org/10.1007/3-540-46145-0_15

  • Mabroukeh NR, Ezeife CI (2010) A taxonomy of sequential pattern mining algorithms. ACM Comput Surv 43(1):1–41. https://doi.org/10.1145/1824795.1824798

    Article  Google Scholar 

  • Mirbagheri SM, Hamilton HJ (2020a) High-utility interval-based sequences. In: International Conference on big data analytics and knowledge discovery, Springer, pp 107–121, https://doi.org/10.1007/978-3-030-59065-9_9

  • Mirbagheri SM, Hamilton HJ (2020b) Similarity matching of temporal event-interval sequences. In: Canadian conference on artificial intelligence, Springer, pp 420–425, https://doi.org/10.1007/978-3-030-47358-7_43

  • Mirbagheri SM, Hamilton HJ (2021) Mining high utility patterns in interval-based event sequences. Data Knowl Eng 135(101):924. https://doi.org/10.1016/j.datak.2021.101924

    Article  Google Scholar 

  • Mörchen F, Fradkin D (2010) Robust mining of time intervals with semi-interval partial order patterns. In: Proceedings of the 2010 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp 315–326, https://doi.org/10.1137/1.9781611972801.28

  • Mörchen F, Ultsch A (2005) Optimizing time series discretization for knowledge discovery. In: Proceedings of the Eleventh ACM SIGKDD international conference on knowledge discovery in data mining. Association for Computing Machinery, New York, NY, USA, KDD ’05, pp 660–665, https://doi.org/10.1145/1081870.1081953

  • Mordvanyuk N, López B, Bifet A (2021) verttirp: Robust and efficient vertical frequent time interval-related pattern mining. Expert Syst Appl 168(114):276. https://doi.org/10.1016/j.eswa.2020.114276

    Article  Google Scholar 

  • Mordvanyuk N, López B, Bifet A (2022) Ta4l: efficient temporal abstraction of multivariate time series. Knowl-Based Syst 244(108):554. https://doi.org/10.1016/j.knosys.2022.108554

    Article  Google Scholar 

  • Moskovitch R (2022) Multivariate time series mining. Wiley’s Data Mining and Knowledge Discovery

  • Moskovitch R, Shahar Y (2015a) Classification-driven temporal discretization of multivariate time series. Data Min Knowl Disc 29(4):871–913. https://doi.org/10.1007/s10618-014-0380-z

    Article  MathSciNet  Google Scholar 

  • Moskovitch R, Shahar Y (2015b) Classification of multivariate time series via temporal abstraction and time intervals mining. Knowl Inf Syst 45(1):35–74. https://doi.org/10.1007/s10115-014-0784-5

    Article  Google Scholar 

  • Moskovitch R, Shahar Y (2015) Fast time intervals mining using the transitivity of temporal relations. Knowl Inf Syst 42(1):21–48. https://doi.org/10.1007/s10115-013-0707-x

    Article  Google Scholar 

  • Moskovitch R, Peek N, Shahar Y (2009) Classification of ICU patients via temporal abstraction and temporal patterns mining. Notes of the intelligent data analysis in medicine and pharmacology (IDAMAP 2009) Workshop. American Medical Informatics Association, Verona, Italy, pp 35–40

    Google Scholar 

  • Moskovitch R, Walsh C, Wang F, et al (2015) Outcomes prediction via time intervals related patterns. In: 2015 IEEE international conference on data mining. IEEE Computer Society, Washington, DC, USA, pp 919–924, https://doi.org/10.1109/ICDM.2015.143

  • Novitski P, Cohen CM, Karasik A, et al (2020) All-cause mortality prediction in t2d patients. In: International conference on artificial intelligence in medicine. Springer, Berlin, pp 3–13, https://doi.org/10.1007/978-3-030-59137-3_1

  • Papapetrou P, Kollios G, Sclaroff S et al (2009) Mining frequent arrangements of temporal intervals. Knowl Inf Syst 21(2):133. https://doi.org/10.1007/s10115-009-0196-0

    Article  Google Scholar 

  • Patel D, Hsu W, Lee ML (2008) Mining relationships among interval-based events for classification. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data. Association for Computing Machinery, New York, NY, USA, SIGMOD ’08, pp 393–404, https://doi.org/10.1145/1376616.1376658

  • Pei J, Han J, Mortazavi-Asl B, et al (2000) Mining access patterns efficiently from web logs. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, Berlin, pp 396–407, https://doi.org/10.1007/3-540-45571-X_47

  • Rebane J, Karlsson I, Bornemann L et al (2021) Smile: a feature-based temporal abstraction framework for event-interval sequence classification. Data Min Knowl Disc 35(1):372–399. https://doi.org/10.1007/s10618-020-00719-3

    Article  MathSciNet  Google Scholar 

  • Sacchi L, Larizza C, Combi C et al (2007) Data mining with temporal abstractions: Learning rules from time series. Data Min Knowl Disc 15(2):217–247. https://doi.org/10.1007/s10618-007-0077-7

    Article  MathSciNet  Google Scholar 

  • Shahar Y (1997) A framework for knowledge-based temporal abstraction. Artif Intell 90(1–2):79–133. https://doi.org/10.1016/S0004-3702(96)00025-2

    Article  MATH  Google Scholar 

  • Sharma AK, Patel D (2018) Stipa: A memory efficient technique for interval pattern discovery. In: 2018 IEEE International conference on big data (Big Data). IEEE Computer Society, Washington, DC, USA, pp 1767–1776, https://doi.org/10.1109/BigData.2018.8622421

  • Shknevsky A, Shahar Y, Moskovitch R (2021) The semantic adjacency criterion in time intervals mining. arXiv preprint arXiv:2101.03842

  • Srikant R, Agrawal R (1996) Mining sequential patterns: Generalizations and performance improvements. In: International conference on extending database technology. Springer, Berlin, pp 1–17, https://doi.org/10.1007/BFb0014140

  • Tzvetkov P, Yan X, Han J (2005) Tsp: mining top-k closed sequential patterns. Knowl Inf Syst 7(4):438–457. https://doi.org/10.1007/s10115-004-0175-4

    Article  Google Scholar 

  • Villafane R, Hua KA, Tran D et al (2000) Knowledge discovery from series of interval events. J Intell Inf Syst 15(1):71–89. https://doi.org/10.1023/A:1008781812242

    Article  Google Scholar 

  • Wang J, Han J (2004) Bide: Efficient mining of frequent closed sequences. In: Proceedings. 20th international conference on data engineering. IEEE Computer Society, Washington, DC, USA, pp 79–90, https://doi.org/10.1109/ICDE.2004.1319986

  • Winarko E, Roddick JF (2007) Armada: an algorithm for discovering richer relative temporal association rules from interval-based data. Data Knowl Eng 63(1):76–90. https://doi.org/10.1016/j.datak.2006.10.009

    Article  Google Scholar 

  • Wu SY, Chen YL (2007) Mining nonambiguous temporal patterns for interval-based events. IEEE Trans Knowl Data Eng 19(6):742–758. https://doi.org/10.1109/TKDE.2007.190613

    Article  Google Scholar 

  • Yan X, Han J, Afshar R (2003) Clospan: mining: closed sequential patterns in large datasets. In: Proceedings of the 2003 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp 166–177, https://doi.org/10.1137/1.9781611972733.15

  • Yang CW, Jaysawal BP, Huang JW (2017) Subsequence search considering duration and relations of events in time interval-based events sequences. In: 2017 IEEE International conference on data science and advanced analytics (DSAA), IEEE, pp 293–302, https://doi.org/10.1109/DSAA.2017.47

  • Yang Z, Wang Y, Kitsuregawa M (2007) Lapin: effective sequential pattern mining algorithms by last position induction for dense databases. In: International conference on database systems for advanced applications. Springer, Berlin, pp 1020–1023, https://doi.org/10.1007/978-3-540-71703-4_95

  • Zaki MJ (2001) Spade: an efficient algorithm for mining frequent sequences. Mach Learn 42(1–2):31–60. https://doi.org/10.1023/A:1007652502315

    Article  MATH  Google Scholar 

  • Zhang J, Wang Y, Yang D (2015) Ccspan: mining closed contiguous sequential patterns. Knowl-Based Syst 89:1–13. https://doi.org/10.1016/j.knosys.2015.06.014

    Article  Google Scholar 

  • Zhao Q, Bhowmick SS (2003) Sequential pattern mining: a survey. ITechnical Report CAIS Nayang Technological University Singapore 1(26):135

Download references

Acknowledgements

The authors wish to thank Prof. Panagiotis Papapetrou and Prof. Diane J Cook for providing datasets for the evaluation. This research was partially funded by a grant of the Israeli Ministry of Science and Technology (Grant 8760441). Omer Harel was funded also by the Darom-Lachish scholarship of Kreitman School of Advanced Graduate Studies at Ben Gurion University (No. 1955129).

Funding

This research was partially funded by a grant of the Israeli Ministry of Science and Technology (grant 8760441). Omer Harel was also funded by the Darom-Lachish scholarship of Kreitman School of Advanced Graduate Studies at Ben Gurion University (No. 1955129).

Author information

Authors and Affiliations

  1. Software and Information Systems Engineering, Ben Gurion University of the Negev, Be’er Sheva, Israel

    Omer Harel & Robert Moskovitch

  2. Population Health Science and Policy, Icahn School of Medicine at Mount Sinai, New York, NY, USA

    Robert Moskovitch

Authors
  1. Omer Harel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Robert Moskovitch
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Omer Harel.

Ethics declarations

Conflicts of interest

The authors have no relevant financial or non-financial interests to disclose.

Additional information

Responsible editor: Michelangelo Ceci.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Appendix A: Real-world datasets

Detailed information is provided on the real-world datasets which have been used to evaluate the proposed TIRPClo algorithm (datasets 1–11 in Table 1).

  • American Sign Language (ASL) The dataset was created by the National Center for Sign Language and Gesture Resources at Boston University (Papapetrou et al. 2009). It consists of a collection of 884 utterances, in which each utterance associates a segment of video with a detailed transcription and contains several ASL gestures and grammatical fields (e.g., eyebrow raised, head tilted forward) occurring over a time interval.

  • Diabetes The dataset was provided by Moskovitch and Shahar (2015c) as part of a collaboration with Clalit Health Services (Israel’s largest HMO). It contains data on 2038 patients having type II diabetes, collected monthly from 2002 to 2007. The dataset contains six variables recorded over time for each patient: hemoglobin-A1c values, blood glucose levels, cholesterol values, and several medications the patients purchased: diabetic (insulin-based) medications, cholesterol reducing statins, and beta blockers.

  • MavLab Smart-home The dataset was provided by Jakkula and Cook (2011). It contains data from the readings of ninety-nine sensors installed in a computerized apartment, describing the activity of people and various appliances scattered around the apartment.

  • ASL-BU (Mörchen and Fradkin 2010) The dataset contains STIs which are transcriptions from videos of American Sign Language expressions. An entity’s series of STIs represents a single sentence.

  • ASL-GT (Mörchen and Fradkin 2010) STIs were derived from sixteen dimensional numerical time series with features extracted from videos of American Sign Language expressions. The dataset includes a larger number of entities’ STIs series and a smaller number of symbol types compared to the previous dataset.

  • Auslan2 (Mörchen and Fradkin 2010) STIs were derived from the publicly available Australian Sign Language dataset in the UCI repository. An entity’s series of STIs represents a single word.

  • Blocks (Mörchen and Fradkin 2010) Contains STIs which represent visual primitives drawn from videos of a human hand stacking colored blocks. An entity’s STIs series represents one of eight different scenarios including either atomic actions (e.g., move-right) or complete scenarios (e.g., assemble).

  • Context (Mörchen and Fradkin 2010) STIs were derived from categorical and numerical data that describe the context of a mobile device carried by humans in different situations. An entity’s series of STIs represents one of five scenarios (e.g., meeting or street).

  • Pioneer (Mörchen and Fradkin 2010) STIs were derived from the Pioneer-1 dataset in the UCI repository, which contains data collected from sensor readings of the Pioneer-1 mobile robot. An entity’s STIs series describes one of the robot’s three moving scenarios—either gripper, move or turn.

  • Skating (Mörchen and Fradkin 2010) The dataset contains STIs derived from fourteen dimensional numerical time series, which describe the muscle activity and leg position of six professional In-Line Speed Skaters during controlled tests. An entity’s series of STIs describes a complete movement cycle.

  • Hepatitis (Patel et al. 2008) The dataset contains STIs describing tests conducted to patients suffering from either Hepatitis B or C over a time period of 10 years. An entity’s STIs series represents the tests conducted to a single patient.

Appendix B: Distribution of time gaps between non-overlapping STIs

Figure 18 shows the distribution of time durations of the before temporal relation, i.e., the time gaps between non-overlapping pairs of STIs, in the ASL, diabetes, smart-home, context, and pioneer datasets which have been used for the maximal gap analysis in experiment 5.

Fig. 18
figure 18

Histograms showing the distribution of time durations of the before temporal relation, i.e., the time gaps between non-overlapping pairs of STIs in the datasets used for the maximal gap analysis in experiment 5

Full size image

Appendix C: Worst-case complexity analysis of sequential pattern mining

In Sect. 3.6.2, a simplified worst-case assessment of the complexity of the proposed TIRPClo algorithm, as a representative of sequence-based TIRP mining methods, was provided. In this appendix, we follow similar notations to those introduced in Sect. 3.6.2, and also concisely assess the complexity of the more basic task of sequential pattern mining.

Assume:

  • S—number of event-types

  • N—total number of events in the dataset

  • n—maximal number of events within an entities’ event-sequence

  • L—maximal number of events within a frequent sequential pattern

In sequential pattern mining, both the input data and the discovered patterns only consist of time point-based events. Thus, the discovery of a k-sized sequential pattern requires k pattern extension steps, i.e., by a single event at a time, while having at most S candidates generated in each step, given a total of S event-types or symbols. That is unlike in sequence-based TIRP mining, where the input STIs data are broken into their start and finish tieps, which consequently doubles the number of pattern extension steps required to discover a k-sized TIRP as well as the maximal number of generated candidates, as described in Sect. 3.6.2. Hence, including the initial sorting of entities’ event-sequences, the overall time complexity of the more basic task of sequential pattern mining can be typically assessed by \(O(N\cdot S^{L}+n\cdot log(n))\) in the worst-case.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Harel, O., Moskovitch, R. TIRPClo: efficient and complete mining of time intervals-related patterns. Data Min Knowl Disc 37, 1806–1857 (2023). https://doi.org/10.1007/s10618-023-00944-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10618-023-00944-6

Keywords

Search

Navigation