# 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.

328 questions
Filter by
Sorted by
Tagged with
113 views

81 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 ...
164 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 ...
30 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 ...
33 views

### Intuition on context free and other kinds of a forests? Data structures perspective

I am trying to gain intuition on formal forests, also called tree languages, i.e., sets of trees. There are regular tree languages, and there are context free tree languages. They both come in a ...
25 views

### Given an input sequence of real numbers, how to find the closest sequence in a large set of sequences

We are given a set $S$ of $m\gg 1$ sequences (arrays) of $n$ elements, where each sequence $s\in S$ belongs to $\mathbb{R}^n$. In the problem I am trying to solve, in a sequential fashion, we obtain a ...
12k views

### Data for testing graph algorithms

I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
64 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$....
100 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 ...
77 views

### Calculation of sum of weights of nodes in a tree graph

Updated There's a real production project related to real estate properties around the world. The data has a structure of nested nodes. E.g. end nodes which have no outgoing edges (red) are properties ...
40 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 ...
498 views

### Reusing 5-independent hash functions for linear probing

In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. (...
120 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 ...
156 views

130 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 ...
369 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 ...
153 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 ...
111k views

### Algorithms from the Book.

Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book. If ...
76 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 ...
74 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. ...
540 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 ...
11k views

### One Stack, Two Queues

background Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...
112 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 ...