Questions tagged [ds.data-structures]
Properties and applications of data structures, such as space lower bounds, or time complexity of insertion and deletion of objects.
82
questions with no upvoted or accepted answers
17
votes
0
answers
295
views
Sequences with sublogarithmic concat and approximate split
Is there a data structure for representing sequences that supports the operations:
concat takes two sequences of size $m$ and $n$ and produces a new sequence of size $m+n$ by joining them in time $o(\...
- 11.1k
15
votes
0
answers
390
views
Set Intersection lower bounds
Consider $S_1, ...,S_n \subseteq [U]$ where size of $U$ is polylogarithmic in $n$. We allow infinite time to pre-process these sets and then ask queries of the form $S_i \cap S_j$ is empty or not. We ...
- 1,167
13
votes
0
answers
175
views
What is the curve of "search vs. insert"
Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $a<b, a>b, a=b$ in constant time.
With this ...
- 369
13
votes
0
answers
176
views
Minimal rare subgraphs
I am looking for any related work to the following problem. Say you have a large directed graph $G$ and you want to find rare (or unique) subgraphs of minimal size that are not isomorphic to any other ...
- 161
13
votes
0
answers
532
views
Lock-free, constant update-time concurrent tree data-structures?
I've been reading a bit of the literature lately, and have found some rather interesting data-structures.
I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
- 566
13
votes
0
answers
408
views
Exact nearest neighbor in $d$-dimensional Euclidean space
Suppose that we have $n$ points in $d$-dimensional Euclidean space $\mathbb{R}^d$. We wish to solve the standard exact nearest neighbor problem: build a data structure such that on any query $q\in \...
- 181
13
votes
0
answers
366
views
Applications of an access lemma for dynamic forests?
Sleator and Tarjan's amortized analysis of splay trees builds on their so-called Access Lemma. For purposes of analysis, assign an arbitrary weight to each node $v$, and let $size(v)$ denote the sum ...
- 22.9k
11
votes
0
answers
344
views
A dynamic data structure to list triangles
Consider an undirected graph with $n$ nodes. Is there an efficient data structure that supports the following operations?
Insert an edge into the graph
Delete an edge from the graph
Given a query ...
user15587
11
votes
0
answers
276
views
Bloom filter variant for constant-time subset/superset queries
Bloom filters make it easy to determine if an element is in a set, within some acceptable margin of error. I'm looking to solve a related problem for which Bloom filters are inadequate, but for which ...
- 199
9
votes
0
answers
134
views
Purely Functional Representations of Catenable Sorted Lists question
Good day.
I'm currently reading the paper "Purely Functional Representations of Catenable Sorted Lists" by Tarjan and Kaplan[link to the paper]. But I have a question
about the modified 2-3 finger ...
- 303
9
votes
0
answers
210
views
References for de-amortization
I've been interested in looking into the area of de-amortization recently (i.e. finding data structures with matching worst-case and amortized running time bounds, or exhibiting lower bounds against ...
- 525
8
votes
0
answers
1k
views
Data structures for Finite Automata
I am a Control Engineer and I have been working on Discrete Event Systems and Supervisory Control, based on Finite Automata Theory. My problem is to represent large automata (about $2 \times 10^6$ ...
- 89
8
votes
0
answers
110
views
Rank Queries of Uniformly Drawn Order Statistics
Put a uniform distribution on the integers $\{1,\cdots, M\}$. Draw $N$ samples, and sort them as $x_1 \leq \cdots \leq x_N$. A rank query calculates $rank(j) = \mbox{card} \{ i : x_i \leq x_j \}$ for ...
- 800
7
votes
0
answers
82
views
Is there a name for trees were siblinghood cannot happen between a leaf and a non-leaf?
The title of this question pretty much says it all.
I would like to know if there is some standard name for trees in which, if any two nodes are siblings, then either they are both leaves, or they are ...
- 531
7
votes
0
answers
191
views
Range min-gap query
The min-gap of an array $A[1..n]$ of $n \ge 2$ elements is defined as $\min_{1 \le i < j \le n}{|A_i - A_j|}$. Now, I am considering a query version of it. Given $A$, a query receives two integers $...
- 71
7
votes
0
answers
245
views
Data structures lower bounds on Turing machines
Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ?
I guess that people are mostly interested in models with random access, but ...
- 71
7
votes
0
answers
227
views
Relational model for data structure reasoning
I am trying to find out if there is any work on applying the Codd's relational model (underlying relational databases) for reasoning about linked data structures. Any connections with UML models and ...
- 4,776
7
votes
0
answers
156
views
Does the cohomological approach to Boolean complexity nicely model any BDD heuristics?
In this question, I learned that complexity theorists had considered using Grothendieck topologies to model Boolean circuits. This has not, apparently, led to any new lower bounds yet, but I'm not so ...
- 32.1k
6
votes
0
answers
165
views
Immutable Space Model
I have heard it said that time is more precious than space because we can reuse space but not time. What if we treat space with this much reverence?
What is generally known about models of ...
- 4,258
6
votes
0
answers
155
views
Framing the Count-Min Sketch as a Random Projection?
The count-min sketch data structure is used to estimate the frequencies of individual elements in a data stream. The authors note that the analysis of their data structure is simpler than other ...
- 1,921
6
votes
0
answers
218
views
Purely functional uniquely-represented deques
There are a number of purely functional deques that support $O(1)$ operations at each end. None that I know of are "uniquely represented" - deques with the same number of items can have different ...
- 11.1k
5
votes
0
answers
101
views
Data structures to store monotone functions
I am looking for approaches storing strictly increasing natural-valued functions defined on a (subset of) $[0..N]$:
$$
\forall x \in X: 0 \le x \le N\\
f: X \to \mathbb N\\
\forall x,y\in X:\quad x<...
- 151
5
votes
0
answers
91
views
Optimal point placement on integer lattice
What is known about the following point placement problem?
For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute
\begin{eqnarray*}
\mu_1(N,n)\triangleq\min_{\mathcal{P}\...
- 51
5
votes
0
answers
149
views
Is there a history-independent rope data structure?
I'm experimenting with a toy (functional) programming language. One of my ideas is to aggressively hash cons everything, thus representing any data structure as a single integer. In that context, data ...
- 375
5
votes
0
answers
149
views
Online triangle counting
Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs.
Given a graph $G$ and a collection $C$ of subsets of ...
- 829
5
votes
0
answers
211
views
Rebalancing balanced binary search tree when decreasing all keys to the right of a path?
Given a balanced binary search tree, suppose I have an operation decrease-right-keys(k, s) that operates as follows: when I call this operation on a tree $T$, I decrease all keys by $s$ in the right ...
- 313
5
votes
0
answers
131
views
Why is it necessary to maintain a collection of forests in the dynamic graph data structure?
In their paper "Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity", Holm, de Lichtenberg, and Thorup describe a data structure ...
- 1,921
5
votes
0
answers
97
views
Dynamic 2-dimensional orthogonal range reporting in external memory and linear space
Orthogonal 2-dimensional range reporting is the problem of storing a set of values from $U \times V$, where $U$ and $V$ are totally ordered universes, subject to queries of the form "Return all stored ...
- 11.1k
4
votes
0
answers
102
views
Simple randomized priority queue matching the Fibonacci heap time bounds?
Since the Fibonacci heap was developed, many other priority queues have been invented with equivalent time bounds and a simpler design (e.g. hollow heaps, quake heaps, etc.).
Many classical worst-case ...
- 1,921
4
votes
0
answers
123
views
What degree of hash function independence is needed for Bloom filters?
In the traditional analysis of Bloom filters, it's assumed that the hash functions are truly random functions, meaning that each hash function distributes each key uniformly and independently of each ...
- 1,921
4
votes
0
answers
63
views
Has there been any work done on incremental connectivity in path graphs?
This set of lecture notes describes a data structure for decremental connectivity in path graphs that supports queries and removals in amortized O(1) each. Has there been any work done on incremental ...
- 1,921
4
votes
0
answers
498
views
Dynamic shortest path data structure for DAG
Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted.
I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
- 141
4
votes
0
answers
167
views
On aB-trees and its practical implementation
I'm reading the paper Succincter by M. Patrascu (link).
It introduces on page 7 the aB-tree. This is a regular B-ary tree that represents an array of values. It stores the element of the array in the ...
- 141
4
votes
0
answers
469
views
worst case external fragmentation in buddy memory systems
Unfortunately, I can't find any freely available text with an estimation of exact upper bound of (external) fragmentation overhead for (binary) buddy memory allocator. Estimation $M(1+ \log 2 m)$ (...
- 206
4
votes
1
answer
1k
views
Given a B-Tree, determine the order keys were inserted
Given a B-tree, determine what order the keys were inserted in. There may be multiple answers: I'd like to generate them all.
Is there any known method for this? Or similar problems?
Clarification:...
- 171
3
votes
0
answers
196
views
HyperLogLog: Why “Hyper?”
I was teaching the HyperLogLog estimator in class earlier this week and a student asked where the “hyper” bit came from. I know that HyperLogLog is a refinement/improvement to the LogLog estimator, so ...
- 1,921
3
votes
0
answers
50
views
Unique fixed-length substrings
Input: A single long string (<10MB) and a number k
Definition: A unique k-substring is a substring of length k, which occurs exactly once in the input document.
Output (Approach 1): Either print ...
- 353
3
votes
0
answers
604
views
Time Complexity for Nearest Neighbor Searches in kd-trees
Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof.
In order to calculate the average number of ...
- 131
3
votes
0
answers
90
views
Data structure to report points in the intersection of two circles
The circular range reporting is defined as follow: preprocess $n$ points in the plane so that the points inside a query circle, of any radius, can be reported quickly.
This was solved beautifully ...
- 3,940
3
votes
0
answers
89
views
Lower bound for reversing a list using queues
How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues?
Each queue is FIFO. Time refers to the number of operations on the queues.
...
- 2,402
3
votes
0
answers
87
views
Triangular range counting query in poly-logarithmic time
What is the minimal space requirement for
triangular range counting queries in plane
if one wants to process each query in poly-logarithmic time?
In [Goswami et al, 2004]
they preprocess the ...
3
votes
0
answers
250
views
efficient data structures for generalized tensor products
The usual tensor product of vectors is a matrix. There has been tons of research into efficiently storing and operating on matrices in computers.
But we can generalize the tensor product quite a bit....
- 1,063
3
votes
0
answers
263
views
Atomic snapshot algorithms on tree-structured shared registers
Background:
Atomic snapshot memory is a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (scanned) in its entirety.
The Gang of Six algorithm ...
- 2,319
3
votes
0
answers
75
views
Load-balancing; Alternate methods of keeping track of nodes?
Reading various articles in the literature have given me only a few decent methods of keeping track of nodes before->after load-balancing them on a very large network.
One popular method uses virtual-...
- 131
3
votes
0
answers
212
views
Optimal term frequency analysis
I'm looking for a term-frequency analysis structure which is more efficient than a hash table in terms of worst-case performance and speed in practice. I specifically care about the operations insert ...
- 566
3
votes
0
answers
361
views
Connected Components over Graph with "colored" edges.
We have an undirected graph $G(V,E)$. Each edge $e \in E$ is associated with a set $C_{e}\neq \emptyset$ of colors, $C_{e} \subseteq C$. The problem is to find all the colored connected components. ...
- 31
2
votes
0
answers
83
views
Approximate (in hamming distance) subset representation
Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
- 600
2
votes
0
answers
41
views
Efficiency of building orthogonal range search structures?
I've been reading up on data structures for 2D range searching. I've noticed that, in many of the papers I've read, there's close attention paid to the query cost and the space usage required, but ...
- 1,921
2
votes
0
answers
101
views
Lower bounds for list/set data structures without delete
I'm interested in lower bounds on the amortized time cost for either of the following dynamic data structure problems, in the cell probe or RAM model, or any model that lets us do operations on words ...
- 203
2
votes
0
answers
54
views
2-dimensional dynamic set retrieval
For the following, $(w,x) >= (y,z)$ iff $w >= y$ and $x >= z$.
I have a list, $L$, of $k$ points with integer coordinates ranging from $0$ to $n-1$. Each point has an associated set. I ...
- 1,099