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.
349
questions
4
votes
0
answers
91
views
$\log^\star n$ is somewhat common in runtimes. Does the superroot ever make an appearance?
Many algorithms and data structures have iterated logarithms ($\log^\star n$) in their runtimes. This function is the discrete inverse of tetration, in that
$$\log_a^\star (a \uparrow \uparrow b) = b$$...
- 2,121
57
votes
10
answers
18k
views
Recent advances in computer science since 2010?
Since I left school (early 2010s) a couple of recently developed techniques were widely adopted by the industry. For example,
Asymmetric numeral systems for compression (e.g. Ubuntu ships with ...
- 651
0
votes
0
answers
46
views
Deamortization of basic COLA (Cache oblivious lookahead array)
I am reading the paper titled Cache Oblivious Streaming B-trees. I am trying to understand the deamortization technique used for basic COLA.
The paper says that for every level k, for deamortization, ...
20
votes
10
answers
3k
views
What are examples of recent relatively simple 'toolbox algorithms'?
Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, Ford–Fulkerson algorithm etc.
There are also several relatively standard data structures, such ...
0
votes
0
answers
58
views
kd-tree optimality for orthogonal range search
It is known that a kd-tree can be constructed for $n$ points ($k$-dimensional) in $O(n \log n)$ time and searching of any axis-aligned hyperrectangle can be done in time $O(n^{1-1/k} + out)$ time ...
- 1,177
0
votes
0
answers
42
views
Speed networking algorithm
I have 40 people and 10 tables that can accommodate 4 people at a time. The task is to make sure that every person seats with every other person at the same table exactly once, that is every person ...
- 101
1
vote
1
answer
200
views
Is data structure necessarily a functor?
The justification of my conjecture is that (seemly) any data structure can have a mapper that applies a given function $f$ to each element of the structure. A data structure in the end is a container ...
- 111
3
votes
1
answer
195
views
Priority queue implementation with both find-min and delete-min $o(\log n)$
Question: There are several priority queue implementations listed on Wikipedia, along with amortized complexities of each of their basic operations: Does anyone know of an implementation in which the ...
0
votes
1
answer
115
views
Formal differences between emulation and simulation?
Recently this question came up, and I've been unable to find a concrete answer.
When I was reading this paper on CRDTs, I was a little perplexed by the notion of emulation here in theorems 3.1 and 3.2....
- 11
0
votes
0
answers
62
views
Are there data structures that cannot be serialized / deserialized using a context free grammar?
I understand that deserializing data from a string or binary stream into a data structure is effectively the same parsing. When you deserialize the input string, you use a grammar to create a parse ...
0
votes
0
answers
45
views
What Data Structure storing points in space for fast lookup of stored points "near" a query point?
In NLP a common problem is that you have vector embeddings of large vocabularies, and you do manipulations on these vector embeddings to compute some result vector, and then you want to find which ...
- 101
0
votes
1
answer
197
views
Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties
Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define
$$
f_{\mathfrak S}(z) := \sum_{\...
- 291
3
votes
2
answers
160
views
Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity
Let $n$ be a large positive integer. Give a nonempty collection $\mathcal S$ of subsets of $[n] := \{1,2,\ldots,n\}$, define an inner-product on $\mathbb R^n$ by
\begin{eqnarray}
\langle x,y\rangle_{\...
- 291
1
vote
0
answers
269
views
Did I discover a new data structure?
For context, I am working on an application in an environment where storage is prohibitively expensive (Ethereum smart contract) and I have some odd requirements:
I need to store a potentially ...
- 11
0
votes
0
answers
79
views
How does laziness help functional data structure?
Functional data structures, or immutable data structures, are often achieved by copying old data to new data upon operation. Naively, it looks much less efficient than their imperical counterpart. ...
- 127
1
vote
0
answers
49
views
Diameter queries for stream of points
Given an online stream of $k$ points $x_1, x_2,\ldots,x_k$ with $x_i \in \mathbb{R}^2$. By online we mean that when $x_i$ arrives we have no knowledge of points $x_j$ for $j > i$. Denote by $S_i$ ...
- 11
1
vote
1
answer
65
views
Indexed access with deletion
As part of a larger data structure that I am working on, I have the following sub-problem:
I start with $n$ slots in an array. Initially all slots are valid. I want to support two operations:
...
- 61
1
vote
0
answers
29
views
Existing results and hardness for dynamic dominance reporting
I am looking for state-of-the-art results on dynamic dominance reporting. In the dynamic dominance reporting problem, we have a set of k dimensional points and the goal is to maintain a data structure ...
- 1,177
9
votes
2
answers
373
views
O(n)-space, polylog-time subtree sums in incremental forests?
Consider a forest $G$ of $n$ vertices $v_1, \dots, v_n$ arranged left to right with edges from child to parent always going to the left, i.e. if the parent of vertex $v_i$ is $v_j$, then $j < i$.
...
- 393
5
votes
0
answers
104
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
-1
votes
1
answer
201
views
Alternative to binary search trees: A sorted array with empty spaces
There are many data structures that have O(log(n)) insert, delete and find operations: Self balancing binary search trees, skip lists and others. My question is: Why doesn't the following simple thing ...
- 359
6
votes
2
answers
305
views
How to show that the median cannot be maintained in $O(1)$ time?
Suppose that we have a stream of numbers $x_1,x_2,\ldots$ such that we wish to track the median of the values observed so far.
This task is easy to do with $O(\log n)$ update time (where $n$ is the ...
- 63
2
votes
0
answers
86
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 ...
- 630
4
votes
1
answer
181
views
Does a graph resulting from the union of triangles has a particular name?
I have different simple triangle graphs. As an instance, $G_1=(V_1,E_1)=(\{1,2,3\},\{\{1,2\},\{2,3\},\{3,1\}\})$ and $G_2=(V_2,E_2)=(\{1,4,5\},\{\{1,4\},\{4,5\},\{5,1\}\})$.
The union of both graphs ...
- 69
0
votes
1
answer
58
views
How to build the tree with the "most different" solutions of a clustering?
Illustrate the question with an example : we have a similarity matrix for 1000 people, and the similarity represents how much their hobbies are the same (it does not really matter how it's built).
Let'...
- 109
9
votes
3
answers
283
views
Sublinear Time Regular Expression Search
Does there exist a data structure with the following properties. Given a string $s$, it performs some polynomial amount of precomputation to construct the data structure. After construction, it allows ...
- 91
1
vote
2
answers
222
views
Finding the point that maximizes a linear function
Consider $N$ two-dimensional points of the form $(x_i, y_i)$ where all $x_i, y_i > 0$ are positive integers. We will be given a workload of queries $Q = \{c_1, \dots, c_k\}$ where for each $c_j \in ...
- 1,177
4
votes
0
answers
115
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 ...
- 2,121
3
votes
0
answers
201
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 ...
- 2,121
2
votes
0
answers
53
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 ...
- 2,121
1
vote
1
answer
79
views
Separating DAGs using separators consisting of lists of nodes and all ancestors
Suppose we are given a DAG, $G = (V, E)$ where $n = |V|$. We consider the sets $J_1, J_2, \dots, J_n$ to be lists of vertices where list $J_i$ consists of vertex $v_i \in V$ and all ancestors of $v_i$....
- 87
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
0
votes
1
answer
318
views
Graphs-like data structure with weighted vertices
I am searching for literature related to a graph-like data structure where vertices are weighted instead of edges.
Formally, we can define a weighted-(edge)-graph $G=(V,E, w(\cdot))$ as a tuple of ...
- 3
3
votes
2
answers
198
views
Complexity of Set Difference
Given $k$ sets $S_1$, $S_2$, $\dots$, $S_k$ in the universe $U = \{1, 2, \dots, n\}$, is there a way to preprocess the $k$ sets such that there is an output-sensitive query algorithm that computes $...
- 31
1
vote
0
answers
44
views
Practical worst-case polylogarithmic dynamic orthogonal range queries?
There are a number of data structures in the literature that solve the dynamic orthogonal range search problem in polylogarithmic time (say, range trees). My understanding is that these structures ...
- 2,121
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
5
votes
1
answer
799
views
Is there a simple, intuitive explanation for why trees in Fibonacci heaps have the sizes they do?
Fibonacci heaps have a simple rule that ensures its tree sizes grow exponentially with their ranks:
A node can lose at most one child. Once that child is lost, the node must be cut from its parent.
...
- 2,121
5
votes
0
answers
92
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
3
votes
0
answers
617
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
2
votes
1
answer
134
views
Data structures for embedded simplicial complexes
I am looking for a data structure to encode an $n$-dimensional simplicial complex with an embedding in $\mathbb{R}^{n+1}$. I am aware of combinatorial maps, which generalize rotation systems of planar ...
- 215
2
votes
0
answers
102
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 ...
- 213
0
votes
1
answer
76
views
Data structure for getting all matches of a prefix from a large list of strings [closed]
Suppose I have a very long list of strings (millions of them), ordered by importance. For example:
...
barracudas
oftwalj
velasp
offso
skenep
vitriolic
offscre
...
...
- 109
0
votes
0
answers
45
views
Updating set of lists dependent upon a few indices
I'm curious about a data structure for a set of "valid lists", where you have a set of lists of length $i$ $S_i$, have a list $L$ of possible items to append, and a boolean function $f$, and wish to ...
- 603
3
votes
0
answers
93
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,950
11
votes
0
answers
346
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
0
votes
1
answer
306
views
Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?
I'm following course material from the course Advanced Data Structures.
The result by Driscoll et al 1989 states the following (wording of the following theorem taken from lec notes, page 4, which ...
- 103
1
vote
0
answers
44
views
Splay trees as dynamic weight-balanced trees?
Given a collection of keys $x_1 < x_2 < \dots < x_n$ with associated weights $w_1, w_2, \dots, w_n$, a weight-balanced tree for the keys $x_i$ with weights $w_i$ is defined as follows:
The ...
- 2,121
7
votes
1
answer
228
views
Simple proof that splay trees have the dynamic finger property?
Splay trees are conjectured to be dynamically optimal, and they're known to have a number of nice properties, including the dynamic finger property, which says that the amortized cost of an access in ...
- 2,121
9
votes
2
answers
1k
views
Can three stacks be implemented in one array, with O(1) push/pop time?
Two stacks can be efficiently implemented using one fixed sized array: stack #1 starts from the left end and grows to the right, and stack #2 starts from the right end and grows to the left. Is the ...
- 93
4
votes
0
answers
150
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 ...
- 2,121