Compact binary relation representations with rich functionality
From MaRDI portal
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.
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
Cites work
- scientific article; zbMATH DE number 5485435 (Why is no real title available?)
- scientific article; zbMATH DE number 2079421 (Why is no real title available?)
- scientific article; zbMATH DE number 2119724 (Why is no real title available?)
- scientific article; zbMATH DE number 1438578 (Why is no real title available?)
- Adaptive searching in succinctly encoded binary relations and tree-structured documents
- Alphabet partitioning for compressed rank/select and applications
- An experimental investigation of set intersection algorithms for text searching
- Compact rich-functional binary relation representations
- Compressed representations of permutations, and applications
- Compressed representations of sequences and full-text indexes
- Entropy-bounded representation of point grids
- Extended compact web graph representations
- Fully functional static and dynamic succinct trees
- New algorithms on wavelet trees and applications to information retrieval
- On compressing and indexing repetitive sequences
- On the Redundancy of Succinct Data Structures
- Optimal lower bounds for rank and select indexes
- Orthogonal range searching on the RAM, revisited
- Range selection and median: tight cell probe lower bounds and adaptive data structures
- Rank and select revisited and extended
- Rank/select operations on large alphabets
- Self-indexed grammar-based compression
- Sorted range reporting
- Space-efficient data-analysis queries on grids
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- Succinct indexes for strings, binary relations and multilabeled trees
- Succinct representation of labeled graphs
- Towards optimal range medians
Cited in
(13)- Grammar compressed sequences with rank/select support
- Longest common prefix with mismatches
- Wavelet trees for all
- Minimal storage representations for binary relations
- Collapsing binary data for algebraic multidimensional representation
- Adaptive searching in succinctly encoded binary relations and tree-structured documents
- The ring: worst-case optimal joins in graph databases using (almost) no extra space
- A succinct data structure for self-indexing ternary relations
- Compact rich-functional binary relation representations
- Compact representation for answer sets of \(n\)-ary regular queries
- Succinct posets
- Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents
- Grammar-compressed indexes with logarithmic search time
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)
