I/O efficient dynamic data structures for longest prefix queries

DOI10.1007/S00453-011-9594-2zbMATH Open1259.68040OpenAlexW1969605837MaRDI QIDQ1939656FDOQ1939656

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

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

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)

Cites Work

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

Cited In (4)

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

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)