2021/04/18 by I Tomohiro, Dominik Köppl, I, Tomohiro +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #Network Packet Processing and Optimization
paper · pdf · doi:10.48550/arxiv.2104.08751
openalex publication_date 2021/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a B tree representation storing n keys, each of k bits, in either (a) nk + O(nk / \lg n) bits or (b) nk + O(nk \lg \lg n/ \lg n) bits of space supporting all B tree operations in either (a) O(\lg n ) time or (b) O(\lg n / \lg \lg n) time, respectively. We can augment each node with an aggregate value such as the minimum value within its subtree, and maintain these aggregate values within the same space and time complexities. Finally, we give the sparse suffix tree as an application, and present a linear-time algorithm computing the sparse longest common prefix array from the suffix AVL tree of Irving et al. [JDA'2003].