Sparse text indexing in small space

DOI10.1145/2836166MaRDI QIDQ4962616zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2836166

zbMATH Keywords

Karp-Rabin fingerprintssparse position heapsparse suffix arraysparse suffix sortingsparse suffix treesparse text indexing

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32) Analysis of algorithms (68W40)

Recommendations

• Sparse suffix tree construction in small space
• Sparse suffix tree construction in optimal time and space
• Space efficient suffix trees
• Breaking a time-and-space barrier in constructing full-text indices
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching

Cited in

(19)

• Text sparsification via local maxima.
• Extracting the sparse longest common prefix array from the suffix binary search tree
• Faster sparse suffix sorting
• scientific article; zbMATH DE number 6719695 (Why is no real title available?)
• scientific article; zbMATH DE number 2080210 (Why is no real title available?)
• Sparse suffix tree construction in optimal time and space
• In-place sparse suffix sorting
• New algorithms for position heaps
• Optimal Substring Equality Queries with Applications to Sparse Text Indexing
• Sparse suffix tree construction in small space
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Deterministic Sparse Suffix Sorting in the Restore Model
• Sparse suffix trees
• Sparse suffix and LCP array: simple, direct, small, and fast
• A sparse enhanced indexation model with chance and cardinality constraints
• Space efficient construction of Lyndon arrays in linear time
• Construction of sparse suffix trees and LCE indexes in optimal time and space
• Locally consistent parsing for text indexing in small space
• Sparse suffix and LCP array: simple, direct, small, and fast

This page was built for publication: Sparse text indexing in small space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962616)