Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Properties and applications of data structures, such as space lower bounds, or time complexity of insertion and deletion of objects.

0
votes
0answers
32 views

(Conditional) Lower Bounds for Space-Bounded Data Structures

I have a data structure problem which is solvable in $\tilde{O}(n^3)$ space with $\tilde{O}(1)$ query time, and I suspect that it's not solvable in $\tilde{O}(n^2)$ space with $\tilde{O}(1)$ query ...
3
votes
0answers
40 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
213 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
91 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
211 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 ...
0
votes
0answers
63 views

Algorithm for solving majority of a group of k hidden elements

You may already be familiar with algorithms to compute the majority using multiple queries. The way these problems work is that you are given a bin of $n$ marbles of binary colors, whose colors you ...
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 ...
0
votes
0answers
30 views

Skip List with multiple express lanes on 1 pointer

I really don't know where to post/ask this so I figured out this may be the place. I came out with an idea of different implementation of a Skip List. This is how default Skip List is defined Skip ...
0
votes
0answers
140 views

Data structure to search name of files and get its path

I will be inserting names of files in a dynamically way, approximately till 1 billion of names. Besides, I do also want to store the path where the files are located in order to do the following ...
3
votes
2answers
134 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 ...
9
votes
0answers
127 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 ...
0
votes
0answers
71 views

Data structures for subset and superset queries over a set of multisets

I am interested in papers discussing efficient data structures for storing and querying a set of multisets. I am particularly interested in the following two operations: Subset query: retrieve all ...
1
vote
0answers
56 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
305 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
149 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 ...
4
votes
1answer
93 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
106 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
97 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
58 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 ...
8
votes
2answers
454 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
289 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 ...
4
votes
3answers
274 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
161 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
123 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 ...
6
votes
4answers
448 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
606 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, ...
7
votes
0answers
134 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
311 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
224 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
208 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 ...
7
votes
2answers
161 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
159 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 ...
6
votes
0answers
102 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
215 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-...
4
votes
2answers
144 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
186 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, ...
3
votes
1answer
234 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
124 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
50 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
100 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 $...
3
votes
0answers
121 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 ...
6
votes
1answer
129 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 ...
9
votes
3answers
917 views

How to design concurrent data structures?

I previously asked this question on Programmers.SE, without success. I'm looking for written learning resources on how to design concurrent data structures. I'm more interested in the design process (...
1
vote
1answer
236 views

Huffman Tree Depth, Is there any theory?

I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without ...
5
votes
2answers
178 views

Ordered-file maintenance

I am studying the Advanced Data Structures material and I'd like to implement the Ordered-file maintenance data structure. I have few questions in order to start. The papers rely on a static view, ...
4
votes
1answer
256 views

Algebra and algebraic data types

Which of the well-known structures of modern algebra (monoids, groups, rings etc) can be expressed as algebraic data types (ADTs)? Presumably a free monoid can be considered to be isomorphic to the ...
0
votes
2answers
128 views

Mergeable Exact Order Statistics Data Structure

Given $n$ sets of integers $S_1, S_2, \cdots, S_n$, it is guaranteed that $$ x < y, \text{ for } \forall x \in S_i \text{ and } \forall y \in S_{i+1} $$ and let's denote this relationship as $S_i &...
7
votes
1answer
59 views

Shoup-style hashing without one-wayness

Let $H$ be an almost universal hash family of functions from $D^2$ to $D$. For any functions $f,g \in H$ define the function $\langle f,g \rangle : D^4 \to D$ by $\langle f,g \rangle(a,b,c,d) \...
6
votes
1answer
220 views

Improved lower bounds or upper bounds on union-find structures since Tarjan?

In 1979, Robert Tarjan published "A Class of Algorithms Which Require Nonlinear Time To Maintain Disjoint Sets", which proved an upper bound of $O(m \alpha(n))$ time on the time complexity of ...
2
votes
1answer
124 views

Lossless Compression Books

I am intrigued by compression techniques and I'd like some recommendations about books to study, specifically, on lossless compression algorithms and data structures. I don't know if there is a ...