2013/06/03 by Amihood Amir, Gianni Franceschini, Amir, Amihood +9
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization #Peer-to-Peer Network Technologies #Web Data Mining and Analysis #cs.DS
paper · pdf · doi:10.48550/arxiv.1306.0406
arxiv created 2013/06/03 · openalex publication_date 2013/06/03 · arxiv updated 2013/06/04 · openalex created_date 2022/09/30 · openalex updated_date 2026/07/28
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(log n) per input symbol (as opposed to amortized O(log n) time per symbol, achieved by previously known algorithms). To our knowledge, our algorithm is the first that achieves O(log n) worst case time per input symbol. Searching for a pattern of length m in the resulting suffix tree takes O(min(mlog |Σ|, m + log n) + 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.