Fully-online Construction of Suffix Trees for Multiple Texts

Takuya Takagi, Shunsuke Inenaga, Hiroki ArimuraCPM 2016 · OpenReview

TL;DR

This paper tackles the challenge of building suffix trees for multiple, simultaneously growing text collections in a "fully-online" manner, meaning characters can be added to any text at any time. They achieve this by developing a novel algorithm that synchronizes the maintenance of Directed Acyclic Word Graphs (DAWGs) and suffix trees, resulting in an efficient O(N log σ) time and O(N) space construction.

What Problem Does This Paper Address?

Maintaining efficient data structures for text analysis is crucial in many fields, from bioinformatics to data stream processing. Suffix trees are powerful tools for tasks like pattern matching. However, existing methods for building suffix trees for multiple texts typically assume a "semi-online" setting, where only one text grows at a time, and previous texts are static. This paper addresses the more complex "fully-online" scenario, where multiple texts can grow concurrently and independently. This is particularly relevant for applications like analyzing data from multiple sensors or tracking multiple evolving entities, where data arrives continuously and from various sources simultaneously. The challenge lies in efficiently updating the suffix tree structure as characters are appended to any of the texts, without a significant performance penalty.

Methods

The authors propose a two-pronged approach. First, they show that the existing semi-online algorithm for constructing Directed Acyclic Word Graphs (DAWGs) by Blumer et al. can be readily adapted to the fully-online setting, maintaining O(N log σ) time and O(N) space complexity.

The core innovation is their fully-online suffix tree construction algorithm. This algorithm is inspired by Ukkonen's single-text online construction but faces significant challenges in the multi-text, fully-online context. Key difficulties include:

  • Non-monotonicity of the "active point": In single-text algorithms, the active point (tracking insertion locations) moves predictably. In the multi-text setting, updates to one text can drastically alter the context for others, breaking this predictability.
  • Amortization breakdown: Ukkonen's technique for efficiently handling suffix insertions relies on predictable active point movement, which is lost here.
  • "Open edge" representation issues: Representing edges leading to leaves becomes problematic as texts grow and edge labels might need to be re-associated with different texts.

To overcome these, the paper introduces several novel techniques:

  • Synchronized DAWG and Suffix Tree Maintenance: The algorithm constructs the suffix tree in tandem with the DAWG. This allows leveraging the DAWG's structure to guide suffix tree updates.
  • Longest Path Tree (LPT): A data structure derived from the DAWG, used to efficiently navigate and find relevant nodes.
  • Nearest Marked Ancestor (NMA) queries: Used in conjunction with LPT to quickly locate corresponding nodes in the suffix tree.
  • Lazy Leaf Representation: Edge labels leading to leaves are initially represented minimally (e.g., by their first character), with full labels being determined later. This addresses the issue of re-associating edge labels with growing texts.
  • Suffix Tree Oracle: A specialized data structure to efficiently find insertion points for suffixes.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and does not present experimental evaluations on specific datasets.

Key Insights and Ideas

  • The DAWG is a powerful ally for online suffix tree construction: By maintaining the DAWG alongside the suffix tree, the algorithm gains crucial structural information that helps overcome the complexities of the fully-online setting.
  • "Lazy" representation is key for dynamic edge labels: The problem of edge labels needing to be re-associated with different texts as they grow is elegantly solved by deferring the full determination of leaf edge labels.
  • Synchronized updates are essential: The core idea is that updates to the DAWG and suffix tree must be tightly coupled to maintain consistency and efficiency in a fully-online environment.
  • The fully-online suffix tree problem is significantly harder than semi-online: The paper highlights specific algorithmic hurdles that arise from concurrent text growth, requiring novel solutions beyond simple extensions of existing methods.

Key Results

The paper presents two main theoretical results:

  1. Fully-online DAWG construction: An algorithm that constructs a DAWG for a collection of K texts under a fully-online sequence of N update operators in O(N log σ) time and O(N) space.
  2. Fully-online Suffix Tree construction: A sophisticated algorithm that constructs the suffix tree for the same setting in O(N log σ) time and O(N) space. This is presented as the first optimal fully-online left-to-right construction algorithm for multiple texts.

Limitations and Future Work

  • Amortized time complexity: The presented suffix tree construction algorithm has an amortized time complexity of O(log σ) per character insertion. The authors pose the open problem of whether this can be de-amortized.
  • Complete leaf edge labels: A key open problem is whether it's possible to efficiently maintain complete labels for edges leading to leaves, rather than using a lazy representation.
  • Alphabet size dependency: The O(log σ) factor in the time complexity is dependent on the alphabet size. Future work might explore algorithms with better dependency on σ, especially for large alphabets.

Summary updated

Abstract

We consider fully-online construction of indexing data structures for multiple texts. Let T = {T_1, ..., T_K} be a collection of texts. By fully-online, we mean that a new character can be appended to any text in T at any time. This is a natural generalization of semi-online construction of indexing data structures for multiple texts in which, after a new character is appended to the kth text T_k, then its previous texts T_1, ..., T_k-1 will remain static. Our fully-online scenario arises when we maintain dynamic indexes for multi-sensor data. Let N and sigma denote the total length of texts in T and the alphabet size, respectively. We first show that the algorithm by Blumer et al. [Theoretical Computer Science, 40:31-55, 1985] to construct the directed acyclic word graph (DAWG) for T can readily be extended to our fully-online setting, retaining O(N log sigma)-time and O(N)-space complexities. Then, we give a sophisticated fully-online algorithm which constructs the suffix tree for T in O(N log sigma) time and O(N) space. A key idea of this algorithm is synchronized maintenance of the DAWG and the suffix tree.
BibTeX
@inproceedings{takagi2016fully,
  author = {Takuya Takagi and Shunsuke Inenaga and Hiroki Arimura},
  title = {{Fully-online Construction of Suffix Trees for Multiple Texts}},
  booktitle = {CPM},
  year = {2016},
  url = {https://openreview.net/forum?id=IP1Hdrqv0n},
}
Figure