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.

Filter by
Sorted by
Tagged with
2 votes
0 answers
164 views

Can an $n$-element subset of a $2n$-element set be stored in $2n - \omega(1)$ bits?

There are $\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \cdot (1 - o(1))$ possible $n$-element subsets of a $2n$-element set. Therefore, any data structure storing such a set must use at least $2n - O(\...
templatetypedef's user avatar
4 votes
2 answers
275 views

What is the relevance of Real Analysis in TCS?

I'm a recent Math major who switched to a double major with Computer Science. I'm petitioning my CS Department Chair to allow me to take Real Analysis in place of Algorithms. I've already taken Data ...
wonderinghuh's user avatar
2 votes
0 answers
35 views

Homeomorphic subtree extraction in integer sorting time

Background Given a rooted, binary tree $T$ with leaves bijectively labeled by $\{1, \ldots, n\}$ (a "phylogenetic tree"). Let $L \subseteq \{1, \ldots, n\}$, and $|L| = k$. The homeomorphic ...
StubbornSnail's user avatar
0 votes
0 answers
49 views

Data structure for storing set of sets

Let key space $K_n =$ { $1, 2,...,n$ } Let Data Structure $D$ implementing a set $S$ of sets such that All sets in $S$ are of same size $l$, $1 \le l \le n$ All sets in $S$ contain keys belonging to $...
Yolov4's user avatar
  • 1
4 votes
0 answers
101 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$$...
templatetypedef's user avatar
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 ...
0 votes
0 answers
51 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, ...
debasishg's user avatar
21 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 ...
Per Alexandersson's user avatar
0 votes
0 answers
60 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 ...
karmanaut's user avatar
  • 1,177
0 votes
0 answers
44 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 ...
Helen Grey's user avatar
1 vote
1 answer
206 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 ...
XQY's user avatar
  • 111
3 votes
1 answer
239 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 ...
Franklin Pezzuti Dyer's user avatar
0 votes
1 answer
125 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....
NathanLiitt's user avatar
0 votes
0 answers
70 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 ...
bcarlborg's user avatar
0 votes
0 answers
48 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 ...
John_Krampf's user avatar
0 votes
1 answer
201 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_{\...
dohmatob's user avatar
  • 291
3 votes
2 answers
162 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_{\...
dohmatob's user avatar
  • 291
1 vote
0 answers
275 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 ...
Brad Brown's user avatar
0 votes
0 answers
81 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. ...
Student's user avatar
  • 127
1 vote
0 answers
50 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$ ...
NLR's user avatar
  • 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: ...
Matthias's user avatar
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 ...
karmanaut's user avatar
  • 1,177
9 votes
2 answers
379 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$. ...
Mathias Rav's user avatar
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<...
TZakrevskiy's user avatar
-1 votes
1 answer
218 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 ...
Zur Luria's user avatar
  • 359
6 votes
2 answers
318 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 ...
Eli's user avatar
  • 63
2 votes
0 answers
87 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 ...
user2316602's user avatar
4 votes
1 answer
186 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 ...
jesús garcía's user avatar
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'...
Vincent's user avatar
  • 109
9 votes
3 answers
293 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 ...
user62586's user avatar
1 vote
2 answers
224 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 ...
karmanaut's user avatar
  • 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 ...
templatetypedef's user avatar
3 votes
0 answers
205 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 ...
templatetypedef's user avatar
2 votes
0 answers
54 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 ...
templatetypedef's user avatar
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$....
user1246462's user avatar
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 ...
kjo's user avatar
  • 531
0 votes
1 answer
370 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 ...
karl's user avatar
  • 3
3 votes
2 answers
200 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 $...
tamalet's user avatar
  • 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 ...
templatetypedef's user avatar
3 votes
0 answers
51 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 ...
Zachary Vance's user avatar
5 votes
1 answer
864 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. ...
templatetypedef's user avatar
5 votes
0 answers
93 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}\...
user56067's user avatar
3 votes
0 answers
628 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 ...
user1494080's user avatar
2 votes
1 answer
136 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 ...
Will's user avatar
  • 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 ...
Dustin Wehr's user avatar
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 ... ...
Flux's user avatar
  • 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 ...
Zach Hunter's user avatar
3 votes
0 answers
94 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 ...
Simd's user avatar
  • 3,902
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 ...
user avatar
0 votes
1 answer
307 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 ...
Peeyush Kushwaha's user avatar

1
2 3 4 5
8