AWLCO: All-Window Length Co-Occurrence
AWLCO: All-Window Length Co-Occurrence
复制标题
DOI：
10.4230/lipics.cpm.2021.24
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Joshua Sobel;Noah Bertram;C. Ding;F. Nargesian;D. Gildea
中科院分区：
文献类型：
--
作者：
Joshua Sobel;Noah Bertram;C. Ding;F. Nargesian;D. Gildea
分析一系列事件的模式在文本分析、计算机编程和基因组研究中都有应用。在这篇文章中，我们考虑了全窗口长度分析模型，它分析了关于所有长度窗口的事件序列。我们研究了全窗长分析模型的精确共现计数问题。我们的第一个算法是一个离线算法，它通过在序列上执行多次遍历并计算单窗口长度的共现来计算所有窗口长度的共现。对于每个窗口长度，该算法的时间复杂度为$O(N)$，因此对于大小为n的序列和大小为$|i|$的项集，总复杂度为$O(n^2)$，空间复杂度为$O(|i|)$。我们提出了一种在线算法AWLCO，该算法一次计算所有窗口长度的共现，预计时间复杂度为$O(N)$，空间复杂度为$O(\sqrt{n|i|})$。然后，我们将用例推广到模式，其中我们提出了一个算法，该算法以预期的时间复杂度$O(n|i|)$和空间复杂度$O(\sqrt{n|i|}+e_{max}|i|)$计算所有窗口长度的共现，其中$e_{max}$是最大模式的长度。
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^2)$ 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 expected time complexity of $O(n)$ and space complexity of $O( \sqrt{ n|I| })$. Following this, we generalize our use case to patterns in which we propose an algorithm that computes all-window-length co-occurrence with expected time complexity $O(n|I|)$ and space complexity $O( \sqrt{n|I|} + e_{max}|I|)$, where $e_{max}$ is the length of the largest pattern.