Position heaps: a simple and dynamic text indexing data structure

DOI10.1016/J.JDA.2010.12.001zbMath1216.68083OpenAlexW2159613260MaRDI QIDQ533414

Nissa Osheim, Andrzej Ehrenfeucht, Sung-Whan Woo, Ross M. McConnell

Publication date: 3 May 2011

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.12.001

zbMATH Keywords

string searchingposition heap

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05) Algorithms on strings (68W32)

Related Items (9)

Linear-size suffix tries ⋮ Position heaps for Cartesian-tree matching on strings and tries ⋮ On-line construction of position heaps ⋮ Inferring strings from position heaps in linear time ⋮ The parameterized suffix tray ⋮ Permuted pattern matching algorithms on multi-track strings ⋮ Dynamic index and LZ factorization in compressed space ⋮ Online algorithms for constructing linear-size suffix trie ⋮ Constructing LZ78 tries and position heaps in linear time for large alphabets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamic extended suffix arrays
• On updating suffix tree labels
• Suffix Arrays: A New Method for On-Line String Searches
• Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure
• Complete inverted files for efficient text retrieval and analysis
• File structures using hashing functions

This page was built for publication: Position heaps: a simple and dynamic text indexing data structure