2026-08-07T12:28:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13975 2024-03-06T10:53:02Z ddc:004 open_access

AWLCO: All-Window Length Co-Occurrence Sobel, Joshua Bertram, Noah Ding, Chen Nargesian, Fatemeh Gildea, Daniel Itemsets Data Sequences Co-occurrence Analyzing patterns in a sequence of events has applications in text analysis, computer programming, and genomics research. In this paper, we consider the all-window-length analysis model which analyzes a sequence of events with respect to windows of all lengths. We study the exact co-occurrence counting problem for the all-window-length analysis model. Our first algorithm is an offline algorithm that counts all-window-length co-occurrences by performing multiple passes over a sequence and computing single-window-length co-occurrences. This algorithm has the time complexity O(n) for each window length and thus a total complexity of O(n²) and the space complexity O(|I|) for a sequence of size n and an itemset of size |I|. We propose AWLCO, an online algorithm that computes all-window-length co-occurrences in a single pass with the time complexity of O(n) and space complexity of O(√{n|I|}), assuming perfect hashing. Following this, we generalize our use case to patterns in which we propose an algorithm that computes all-window-length co-occurrence with time complexity O(n|I|), assuming perfect hashing, with an additional pre-processing step and space complexity O(√{n|I|}+|I|), plus the overhead of the Aho-Corasick algorithm [Aho and Corasick, 1975]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joshua Sobel and Noah Bertram and Chen Ding and Fatemeh Nargesian and Daniel Gildea 2021 Is Part Of LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2021.24 urn:nbn:de:0030-drops-139759 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.24 eng https://creativecommons.org/licenses/by/4.0/legalcode