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.
339
questions
0
votes
1
answer
159
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
144
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
249
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
70
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
45
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
61
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
27
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,167
9
votes
2
answers
366
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
99
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
157
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
0
votes
0
answers
63
views
Did anyone ever adapt TCS data structure results (e.g. vEB trees) into Governance structures?
Did anyone ever adapt TCS data structure results (e.g. vEB trees) into Governance structures?
Many of the structures underlying current societies and their governance were designed more than 100 years ...
- 2,723
6
votes
2
answers
269
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
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
4
votes
1
answer
177
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
57
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
278
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
219
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,167
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
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
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
1
vote
1
answer
77
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
191
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
187
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
43
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 ...
- 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
5
votes
1
answer
659
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.
...
- 1,921
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
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
2
votes
1
answer
125
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
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
0
votes
1
answer
70
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
44
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 ...
- 518
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
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
0
votes
1
answer
296
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
37
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 ...
- 1,921
7
votes
1
answer
197
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 ...
- 1,921
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
122
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
3
votes
2
answers
149
views
Data structure for radial orderings of points on the plane
Assume points are always in general position.
For a set of $n$ points $S$ on the plane, a radial ordering with respect to $x\in S$ is a total ordering of the elements in $S-x$.
Consider shooting an ...
- 4,327
0
votes
0
answers
45
views
Arranging sets in a hierarchy
Suppose you have sets $S_1, \dots S_m$ such that $\sum_i |S_i| = n$. The goal is to arrange all the sets into a (possible unconnected) DAG such that $S_i$ is a parent (or ancestor) of $S_j$ iff $S_j \...
- 1,167
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
0
votes
1
answer
476
views
Data Strcuture to represent dependencies amongst modules
Consider several software modules $m_1, m_2, ... m_n$. Each module has some inputs and outputs and the inputs to some of the modules are dependent on the outputs of some other modes. For example, in ...
- 125
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
1
vote
0
answers
78
views
Points of a finite set wihtin a ball
I am looking for data-structures to store efficiently a set of points $E$ in an euclidean space of dimension $d$.
In particular, I would like to be able to solve the problem of finding all the point ...
- 992
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
5
votes
2
answers
627
views
Data structure to determine if sets are disjoint in o(n) time
My initial question was exactly the title of this post, but after feedback from commenters I have formulated a more precise version of the question that attempts to capture its essence.
Does there ...
- 159
5
votes
1
answer
126
views
Topology/Space of Recursive Algebraic Datatypes
I have a recursive algebraic datatype. I (somewhat arbitrarily) defined one function to compute distance between instances, and am trying to define a function to approximate a "vector" between ...
- 433
7
votes
1
answer
262
views
How fast can we find and disconnect roots in a forest?
Consider a forest of rooted trees. The problem is to support two operations:
disconnect(v): if v is the root of some tree in the forest, remove all edges of v;
findroot(v): find root of the tree ...
