I/O efficient dynamic data structures for longest prefix queries

DOI10.1007/S00453-011-9594-2MaRDI QIDQ1939656zbMATH OpenOpenAlexFDO

Authors Moshe Hershcovitch, Haim Kaplan

Publication date 5 March 2013

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-011-9594-2

zbMATH Keywords

algorithmsdata structuresI/O modelsegment treelongest prefixstring B-tree

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• I/O Efficient Dynamic Data Structures for Longest Prefix Queries
• Fast prefix matching of bounded strings
• Dynamic string searching
• A data structure for a sequence of string accesses in external memory
• c-trie++: a dynamic trie tailored for fast prefix searches

Cites work

• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• A class of algorithms which require nonlinear time to maintain disjoint sets
• A data structure for dynamic trees
• An optimal dynamic interval stabbing-MAX data structure?
• Cache-Oblivious B-Trees
• Cache-oblivious algorithms
• Cache-oblivious string dictionaries
• Dynamic rectangular intersection with priorities
• Multiway range trees: scalable IP lookup with fast updates
• Obtaining Provably Good Performance from Suffix Trees in Secondary Storage
• Organization and maintenance of large ordered indexes
• Self-adjusting binary search trees
• The string B-tree
• Worst-case optimal tree layout in external memory

Cited in

(4)

• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• Fast prefix matching of bounded strings
• DMP-tree: A dynamic M-way prefix tree data structure for strings matching
• I/O Efficient Dynamic Data Structures for Longest Prefix Queries

Describes a project that uses

Uses Software

• PATRICIA

This page was built for publication: I/O efficient dynamic data structures for longest prefix queries

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