Questions tagged [succinct-data-structures]
The succinct-data-structures tag has no usage guidance.
10
questions
2
votes
1answer
89 views
Information-theoretic lower bound for succinct string dictionary of the Unicode Name property
Background
The literature on succinct data structures refers often to the “information-theoretic lower bound” of encoding data, i.e., the minimum number of bits needed to store the data – a concept ...
1
vote
1answer
36 views
Subintervals during backward search of a BWT
A Burrows-Wheeler Transform (BWT) can be used to find the suffix array intervals for a pattern $P$ by issuing $p=|P|$ paired $rank$ queries
\begin{align}
s^\prime &= C[P[i]] + rank(s-1, P[i]) + 1 \...
0
votes
0answers
20 views
What are the graph classes which takes logarithmic space in $|V|$ in circuit representation?
The $\text{SCR}$ representation of a graph $G=(V,E)$ is $C_{G}$ id the following conditions hold:
$C_{G}$ is a combinatorial circuit with memory.
$C_{G}$ has two inputs of length $n$ bits.
$C_{G}$ ...
-3
votes
1answer
46 views
Exponential amount of information in polynomial size? Impossible!
I'm reading A note on succinct representations of graphs by Papadimitriou and Yannakakis. Let me quote the following paragraph on page 183:
Formula $F$ has a highly regular structure. It has $|x|$ ...
2
votes
0answers
52 views
Storing relations space efficiently?
Let $f$ be a binary relation defined on set $S$, which contains numbers from $1$ to $n$. It is also given that number of $|\text{Img}(f)| \le k$. I want to store the function $f$ such in way such that ...
3
votes
1answer
130 views
Compact mapping from an involuted set
Let $S$ be a set (say positive integers $\leq$ N) and $f$ an involution ($f$ is bijective, $f\cdot f=id$, e.g. xor with a constant). $g$ is a idempotent mapping choosing an arbitrary representative ...
4
votes
1answer
112 views
Looking for a succinct dynamic sorted dictionary
I was digging through research articles to find a data structure that solves the dynamic sorted dictionary problem (representing any subset $S$ of a universe $U = \{0, \ldots, u\}$ with member/...
4
votes
2answers
82 views
Succinct data structure to return occurences of letters until an index
I want to try and use a succinct type data structure in order to find the amount of occurences of a letter $C$ in a string $S$ until a given index $I$.
Assume we have a string $S$ of length $n$ over ...
1
vote
1answer
174 views
Heap-like notation of a BST (BFT bit-vectors) for succinct representation
I'm researching the topic of succinct tree representations right now and came across this presentation. On slide 17 there is an example of heap-like notation of a BST (using BFT bit-vectors) and the ...
3
votes
0answers
261 views
Generalization of XOR Linked Lists
Are there any results generalizing XOR Linked Lists to other types of data structures?
For example, just like an XOR Linked List requires two pointers and can iterate a 1 dimensional list, I can ...
