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
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 ...
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: ...
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$. ...
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<...
-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 ...
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 ...
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 ...
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 ...
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 ...
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 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$....
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 ...
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 ...
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. ...
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}\...
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 ...
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 ...
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 ...
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 ...
user avatar
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...

1
2 3 4 5
7