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
3
votes
0answers
61 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 ...
11
votes
0answers
327 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 ...
0
votes
1answer
105 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
0answers
23 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
1answer
72 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
2answers
314 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
0answers
65 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
2answers
95 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 ...
0
votes
0answers
43 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 \...
4
votes
0answers
97 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 ...
0
votes
1answer
136 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 ...
6
votes
0answers
148 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
0answers
73 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 ...
3
votes
0answers
51 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
2answers
339 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
1answer
106 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 ...
7
votes
1answer
218 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 ...
4
votes
1answer
2k views

Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

While we usually use large e.g. 64 bit hashes, there are many techniques to reduce this size, e.g. for savings in storage and transmission. Popular Bloom filter instead of marking just 1 hash ...
2
votes
2answers
150 views

Suggested approach to cover data structure literature

I am not sure if this question is odd topic or too broad, but I have been wondering about this for a long time, and I would very much appreciate any valuable inputs. As a new grad student working on ...
10
votes
0answers
145 views

Bloom filter variant for constant-time subset/superset queries

Bloom filters make it easy to determine if an element is in a set, within some acceptable margin of error. I'm looking to solve a related problem for which Bloom filters are inadequate, but for which ...
1
vote
0answers
59 views

\alpha-path on Euclidean graphs

Consider the following problem: Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real $\alpha > 0$. For simplicity assume, there exists only one path whose summation of weights ...
0
votes
1answer
401 views

Data Structure to calculate which interval a point lies in? [closed]

I have a list of $n$ non-overlapping intervals, namely $[a_1,a_2],[a_2,a_3],...,[a_n,n_{n+1}], a_i \in \mathbb{N}$. Each of these intervals has a corresponding value $v_i$ corresponding to it. Now ...
4
votes
1answer
163 views

What is known about computing distinct count range queries?

Let $U=\{1,\ldots, u\}$ be a universe of elements for some $u\in \mathbb N$. Given some $n\in\mathbb N$, we are interested in computing some function $f:U^{\le n}\to\mathbb R$ over range queries. In ...
3
votes
1answer
101 views

Sublinear finite-precision sampling in a stream

I am looking to sample a single item from a stream such that each item in the stream has an equal probability of being selected. This is a restricted version of the reservoir sampling problem. On a ...
1
vote
0answers
127 views

Information theoretic lower-bound on object graph serialization

This might be a daft quesstion, but here comes. I became intriqued about data serialization formats and tried to look for research on what could be the information theoric lower bound on encoding ...
0
votes
1answer
98 views

Reachability in Dynamic Line Graph

Given a directed line graph $G = v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$, there are two operators, namely $\mathsf{move}(v_i, v_j)$: this operator moves $v_i$ to the position ...
1
vote
0answers
59 views

What is known about data structures for encoding a set while considering approximate Rank queries?

Consider a universe $\mathcal U\triangleq \{1,2,\ldots n\}$, and assume that we are given a set $S\subseteq \mathcal U$. There are many data structures that allow storing $S$ while answering Rank ...
7
votes
2answers
690 views

Random sampling data structure with removal

I'd like a data structure with the following operations: create a new instances from an array of floating point weights. randomly sample, returning an item with probability proportionate to its ...
15
votes
0answers
311 views

Set Intersection lower bounds

Consider $S_1, ...,S_n \subseteq [U]$ where size of $U$ is polylogarithmic in $n$. We allow infinite time to pre-process these sets and then ask queries of the form $S_i \cap S_j$ is empty or not. We ...
3
votes
3answers
313 views

Pairwise comparison of bit vectors

Define a partial order $\le$ on $\{0,1\}^d$ by pointwise comparison, i.e., we say $x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,d$. I am interested in the following problem: Given $x_1,\dots,x_n \...
4
votes
1answer
162 views

Algorithms in preprocessed universe [closed]

In celebrated paper Clustered integer 3SUM via additive combinatorics by TM Chan and M Lewenstein one of the provided algorithms is the one for preprocessed universe. They were able to provide an ...
5
votes
0answers
126 views

Online triangle counting

Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs. Given a graph $G$ and a collection $C$ of subsets of ...
5
votes
4answers
556 views

Purely(ish) functional data structure with fast append and forward iteration

I find I have need for a data structure with a specific set of requirements: It represents an immutable sequence of values (fixed sized integers if this matters) Appending a new value to the end (and ...
-1
votes
1answer
780 views

Reachability on DAG (best-known algorithm)

Task: To answer several reachability queries on large DAGs (millions or billions of vertices and edges) using a data structure that takes up as little space as possible, is not expensive to construct, ...
6
votes
0answers
140 views

Range min-gap query

The min-gap of an array $A[1..n]$ of $n \ge 2$ elements is defined as $\min_{1 \le i < j \le n}{|A_i - A_j|}$. Now, I am considering a query version of it. Given $A$, a query receives two integers $...
5
votes
1answer
332 views

Fast Algorithm to Check if a Set of Sets forms an Anti-chain

Given a set $S$ of sets, what is the fastest algorithm to check if elements of $S$ form an anti-chain with respect to subset ordering? That is, how can I quickly decide if there exists two sets $A$ ...
6
votes
1answer
249 views

For a given binary-search tree obtain an isomorphic splay tree

I will assume that the reader is familiar with some undergraduate algorithms and data structures. To people who are not familiar with splay trees I recommend to read through this link : https://en....
8
votes
1answer
228 views

What are the must-read search trees paper?

I would like to ask a help from researchers who conduct a research in an area of search trees. Could you please write the list of the must-read papers and most recent papers which are important to ...
6
votes
2answers
166 views

Quick-select contiguous subarray

Motivated by the question from this blog post, the following data structure question seems interesting and fun to me. Preprocess: A list of numbers $A = a_1,...,a_n$ Query(s,t,k): Return the $k$-th ...
12
votes
0answers
162 views

What is the curve of “search vs. insert”

Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $a<b, a>b, a=b$ in constant time. With this ...
5
votes
0answers
111 views

Framing the Count-Min Sketch as a Random Projection?

The count-min sketch data structure is used to estimate the frequencies of individual elements in a data stream. The authors note that the analysis of their data structure is simpler than other ...
3
votes
1answer
277 views

Why use two separate tables in cuckoo hashing?

I've been reading a number of papers on cuckoo hashing, including several that generalize it by talking about cuckoo hashing with multiple tables, cuckoo hashing with a stash, the (multi)graph-...
3
votes
2answers
156 views

Constant-time bounds on offline 2-choice hashing?

I'm reading up on cuckoo hashing and came across Michael Mitzenmacher's blog posts on the subject. In his motivation of why cuckoo hashing seems like a reasonable strategy, he mentions a connection to ...
6
votes
1answer
198 views

Two papers give contradictory bounds on linear probing. How do I resolve the disparity?

I've been reading over two papers recently. The first, "Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream" proves that, assuming there is sufficient entropy in a data source, ...
2
votes
1answer
277 views

maximizing inner product

Given two lists $L,L'\subseteq\mathbb{R}^d$ of $n$ vectors each, how fast can we compute for all $p\in L$ the vector of $L'$ that maximizes the inner product with $p$, i.e., $\arg\max_{p'\in L'} \...
8
votes
1answer
126 views

Sorted dictionary structure supporting efficient merges?

Many balanced tree structures (red/black trees, splay trees, etc.) and some other sorted dictionary structures (skiplists) support a join operation that takes in two dictionaries where all keys in the ...
1
vote
0answers
61 views

Best Asymptotic Complexity for Persistent Union Find

In this paper https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf, they claim to have a practically fast persistent union-find data structure for most use-cases, but it's still not polylogarithmic ...
1
vote
1answer
102 views

Data structure for storing points and finding a predecessor of a point

I am looking for a good data structure for storing a set of points $P\subset \mathbb{N}^n$ that is able to answer the following query: Given a point $x=(x_1,\cdots,x_n)$, does there exist a point $...
2
votes
0answers
134 views

Hashtable vs cache-oblivious [closed]

I'd like to know more about real performances of data structures, in particular two families attract my interests: hash tables cache oblivious My researches didn't find any "comprehensive" (let me ...
5
votes
1answer
138 views

Generalized Priority Queues

I was wondering if there is any literature on the following problem: Maintain a set $S$ where each element is a function from $\mathbb{R}$ to $\mathbb{R}$ supporting the following operations: Insert ...