Managing unbounded-length keys in comparison-driven data structures with applications to online indexing

DOI10.1137/110836377zbMATH Open1305.68066arXiv1306.0406OpenAlexW2039208882MaRDI QIDQ2929702FDOQ2929702

Authors: Amihood Amir, Gianni Franceschini, Roberto Grossi, Tsvi Kopelowitz, Noa Lewenstein, Moshe Lewenstein 

Publication date: 14 November 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: This paper presents a general technique for optimally transforming any dynamic data structure that operates on atomic and indivisible keys by constant-time comparisons, into a data structure that handles unbounded-length keys whose comparison cost is not a constant. Examples of these keys are strings, multi-dimensional points, multiple-precision numbers, multi-key data (e.g.~records), XML paths, URL addresses, etc. The technique is more general than what has been done in previous work as no particular exploitation of the underlying structure of is required. The only requirement is that the insertion of a key must identify its predecessor or its successor. Using the proposed technique, online suffix tree can be constructed in worst case time $O(logn)$ per input symbol (as opposed to amortized $O(logn)$ time per symbol, achieved by previously known algorithms). To our knowledge, our algorithm is the first that achieves $O(logn)$ worst case time per input symbol. Searching for a pattern of length $m$ in the resulting suffix tree takes $O(min(mlog|Sigma|,m+logn)+tocc)$ time, where $tocc$ is the number of occurrences of the pattern. The paper also describes more applications and show how to obtain alternative methods for dealing with suffix sorting, dynamic lowest common ancestors and order maintenance.

Full work available at URL: https://arxiv.org/abs/1306.0406

Recommendations

• Automata, Languages and Programming
• Suffix trees on words
• Dynamic Text Indexing under String Updates
• On-line construction of suffix trees
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching

zbMATH Keywords

stringssuffix treetext indexingsearch treessuffix sorting

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Cited In (8)

• Towards a real time algorithm for parameterized longest common prefix computation
• The property suffix tree with dynamic properties
• Cross-document pattern matching
• Alphabet-dependent string searching with wexponential search trees
• The online house numbering problem: min-max online list labeling
• Orthogonal range searching for text indexing
• Automata, Languages and Programming
• Engineering parallel string sorting

This page was built for publication: Managing unbounded-length keys in comparison-driven data structures with applications to online indexing

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