Compact binary relation representations with rich functionality
From MaRDI portal
Publication:386006
DOI10.1016/J.IC.2013.10.003zbMATH Open1277.68063arXiv1201.3602OpenAlexW2116258248MaRDI QIDQ386006FDOQ386006
Authors: Jérémy Barbay, Francisco Claude, Gonzalo Navarro 
Publication date: 13 December 2013
Published in: Information and Computation (Search for Journal in Brave)
Abstract: Binary relations are an important abstraction arising in many data representation problems. The data structures proposed so far to represent them support just a few basic operations required to fit one particular application. We identify many of those operations arising in applications and generalize them into a wide set of desirable queries for a binary relation representation. We also identify reductions among those operations. We then introduce several novel binary relation representations, some simple and some quite sophisticated, that not only are space-efficient but also efficiently support a large subset of the desired queries.
Full work available at URL: https://arxiv.org/abs/1201.3602
Recommendations
- Compact rich-functional binary relation representations
- Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents
- A succinct data structure for self-indexing ternary relations
- Collapsing binary data for algebraic multidimensional representation
- Adaptive searching in succinctly encoded binary relations and tree-structured documents
Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Cites Work
- Fully functional static and dynamic succinct trees
- Compressed representations of sequences and full-text indexes
- Alphabet partitioning for compressed rank/select and applications
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Title not available (Why is that?)
- Range selection and median: tight cell probe lower bounds and adaptive data structures
- Towards optimal range medians
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- Succinct indexes for strings, binary relations and multilabeled trees
- Orthogonal range searching on the RAM, revisited
- Sorted range reporting
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- Extended compact web graph representations
- Rank/select operations on large alphabets
- On compressing and indexing repetitive sequences
- Space-efficient data-analysis queries on grids
- New algorithms on wavelet trees and applications to information retrieval
- Title not available (Why is that?)
- Compressed representations of permutations, and applications
- An experimental investigation of set intersection algorithms for text searching
- Succinct representation of labeled graphs
- Adaptive searching in succinctly encoded binary relations and tree-structured documents
- Rank and select revisited and extended
- Optimal lower bounds for rank and select indexes
- Entropy-bounded representation of point grids
- Self-indexed grammar-based compression
- On the Redundancy of Succinct Data Structures
- Title not available (Why is that?)
- Compact rich-functional binary relation representations
- Title not available (Why is that?)
Cited In (13)
- Grammar compressed sequences with rank/select support
- Collapsing binary data for algebraic multidimensional representation
- Compact rich-functional binary relation representations
- Longest common prefix with mismatches
- Adaptive searching in succinctly encoded binary relations and tree-structured documents
- Succinct posets
- Grammar-compressed indexes with logarithmic search time
- A succinct data structure for self-indexing ternary relations
- Minimal storage representations for binary relations
- Wavelet trees for all
- Compact representation for answer sets of \(n\)-ary regular queries
- The ring: worst-case optimal joins in graph databases using (almost) no extra space
- Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents
Uses Software
This page was built for publication: Compact binary relation representations with rich functionality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386006)
