I/O efficient dynamic data structures for longest prefix queries

DOI10.1007/s00453-011-9594-2zbMath1259.68040OpenAlexW1969605837MaRDI QIDQ1939656

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)

Uses Software

• PATRICIA

Cites Work

• Unnamed Item
• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• A data structure for dynamic trees
• Multiway range trees: scalable IP lookup with fast updates
• Worst-case optimal tree layout in external memory
• Organization and maintenance of large ordered indexes
• The string B-tree
• Cache-Oblivious Algorithms
• Dynamic rectangular intersection with priorities
• Cache-oblivious string dictionaries
• Self-adjusting binary search trees
• Obtaining Provably Good Performance from Suffix Trees in Secondary Storage
• Cache-Oblivious B-Trees

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