Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [succinct-data-structures]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
134 views

Is this an example of a natural, strictly NP-intermediate language (assuming EXP ≠ NEXP)?

In the wikipedia page for the NP-intermediate complexity class, the following observation is made: Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this ...
Federico's user avatar
0 votes
1 answer
61 views

How many bits do the pointers take?

So I am covering succinct trees, and in the lecture, it mentioned that "An n-node tree takes 2n pointers or 2n lg n bits (can be easily reduced to n lg n + O(n) bits). First, question is why ...
kjkjkjkjkj's user avatar
0 votes
0 answers
24 views

Succinct array datastracture

Is it true that there is no known succinct data structure that has integer array (vector) functionality? Desirable operations would be: append O(1) access(i) - returns i-th item O(1) iterate(i..j) - ...
mcmayer's user avatar
  • 141
0 votes
1 answer
192 views

How to analyze the amortized running time of indexed linked list operations using potential method?

I have implemented an indexed linked list that runs (under mild assumptions) all single-element operations in $\mathcal{O}(\sqrt{n})$ time. The description is here and Java implementation is here. It’...
coderodde's user avatar
2 votes
0 answers
111 views

$y$-Fast Tries: Why not partition into groups of $\Theta(\log^2 M)$ elements?

The $y$-fast trie is a data structure for storing a sorted collection of $n$ integers from the range $[0, M)$. It builds on the $x$-fast trie, which also stores elements in this range. The space usage ...
templatetypedef's user avatar
2 votes
1 answer
140 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 ...
jschoi's user avatar
  • 123
1 vote
1 answer
113 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 \...
alan's user avatar
  • 133
0 votes
0 answers
22 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}$ ...
user avatar
-3 votes
1 answer
52 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|$ ...
Zirui Wang's user avatar
2 votes
0 answers
54 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 ...
user avatar
3 votes
1 answer
176 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 ...
Piezoid's user avatar
  • 133
4 votes
1 answer
123 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/...
John Doe the Righteous's user avatar
4 votes
2 answers
91 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 ...
Ori Refael's user avatar
1 vote
1 answer
184 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 ...
ddnomad's user avatar
  • 145
3 votes
0 answers
273 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 ...
Realz Slaw's user avatar
  • 6,191