Adaptive searching in succinctly encoded binary relations and tree-structured documents

DOI10.1016/j.tcs.2007.07.015zbMath1144.68014OpenAlexW2161403911MaRDI QIDQ2465061

Jérémy Barbay, S. Srinivasa Rao, Alexander Golynski, J. Ian Munro

Publication date: 19 December 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.07.015

zbMATH Keywords

adaptive algorithmsintersection problemlabeled treesconjunctive queriessuccinct data structurespath queriesmulti-labeled trees

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (7)

Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing ⋮ Compact binary relation representations with rich functionality ⋮ Space efficient data structures for dynamic orthogonal range counting ⋮ Succinct data structures for nearest colored node in a tree ⋮ Efficient fully-compressed sequence representations ⋮ Succinct representation of labeled trees ⋮ A framework for succinct labeled ordinal trees over large alphabets

Cites Work

• On general minimax theorems
• Representing trees of higher degree
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Succinct Representation of Balanced Parentheses and Static Trees
• Rank/select operations on large alphabets
• The Ultimate Planar Convex Hull Algorithm?
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Alternation and redundancy analysis of the intersection problem
• Combinatorial Pattern Matching
• Automata, Languages and Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Adaptive searching in succinctly encoded binary relations and tree-structured documents