Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

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
14
votes
1answer
396 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. (...
4
votes
1answer
294 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-...
5
votes
0answers
127 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
0answers
141 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
339 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
260 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....
6
votes
2answers
167 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 ...
8
votes
1answer
231 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 ...
12
votes
0answers
166 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 ...
565
votes
6answers
116k views

What's new in purely functional data structures since Okasaki?

Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few: IntMap (also invented by ...
5
votes
0answers
114 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
2answers
158 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
199 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, ...
5
votes
1answer
340 views

Patience Sort+ ping pong merge implementation

A recent paper out of Microsoft Research describes a new, faster implementation of the patience sort algorithm. A key part of the implementation is an improved merging strategy dubbed the "ping-pong" ...
12
votes
6answers
690 views

Computing the approximate population of a bloom filter

Given a bloom filter of size N-bits and K hash functions, of which M-bits (where M <= N) of the filter are set. Is it possible to approximate the number of elements inserted into the bloom filter? ...
2
votes
1answer
286 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'} \...
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 $...
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
63 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 ...
36
votes
9answers
11k 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, ...
2
votes
0answers
136 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 ...
8
votes
3answers
1k 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 (...
5
votes
1answer
143 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 ...
16
votes
3answers
2k views

Bootstrapping a Finger Tree Structure

After working with 2-3 finger trees for quite a bit I have been impressed by their speed in most operations. However, the one issue I have run into is the large overhead associated with the initial ...
4
votes
2answers
195 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, ...
15
votes
2answers
2k views

What persistent data structure for a set of partially ordered elements?

I need to store sets of elements of type a. Type a is partially ordered, so comparing $a_1$ and $a_2$ can return smaller, greater, equal or incomparable. One problem with hashtables is that two equal ...
1
vote
1answer
291 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 ...
0
votes
2answers
134 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
207 views

Maintain mex with efficient union

Do you know of any data structure $S[A]$, that maintains a (finite) set $A \subset \mathbb{Z}_{\geq0}$ of non-negative integers, subject to the following operations: Given $S[A],$ calculate minimal ...
1
vote
1answer
174 views

Give a simple way to augment Van emde boas tree, to find/delete median in O(log log u) time

I need a simple augmentation to support median/order statistic queries in O(log log n) time,without increasing the time for other operations.
7
votes
1answer
64 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) \...
9
votes
2answers
299 views

Almost universal string hashing in $Z_{2^n}$ and sublinear space

Here are two families of hash functions on strings $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$: For $p$ prime and $x_i \in \mathbb{Z_p}$, $h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$ for $a \in \...
6
votes
1answer
261 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
133 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 ...
4
votes
2answers
926 views

Min Hamming distance of a given string from substrings of another string

Let $U$ be a small finite set. Consider the following problem: Input: two strings $u \in U^k$ and $v\in U^n$ with $k \leq n$. Output: a (contiguous) substring of $v$ of length $k$ with the minimum ...
0
votes
0answers
43 views

Equilvalence among two Scheduling problems

I have two problems for scheduling: Packets arrive at a router. Router schedules them i.e. router determines which one will go out first and which one last. Here, the problem is which packet to send ...
0
votes
0answers
34 views

Self-Aggregating Tree

Say I have a finite $n$-ary tree where each node contains state. For the sake of argument, let's say a key-value store. If we are interested in the aggregation of some key(s) at some node, then we ...
11
votes
1answer
277 views

Implementation of partition trees?

Have partition trees ever been implemented? Here, I'm talking about the partition trees from computational geometry. The earliest (near-)optimal versions of which were due to Matousek and others, ...
3
votes
0answers
76 views

Triangular range counting query in poly-logarithmic time

What is the minimal space requirement for triangular range counting queries in plane if one wants to process each query in poly-logarithmic time? In [Goswami et al, 2004] they preprocess the ...
1
vote
2answers
2k views

Where can I find a copy of Guy Jacobson's thesis “Succinct Static Data Structures”?

I'm looking for a copy of Guy Jacobson's PhD thesis: http://dl.acm.org/citation.cfm?id=915547 but I couldn't find it so far. Does anybody know where can I access it ? I really need it. Thanks in ...
35
votes
6answers
6k views

A probabilistic set with no false positives?

So, Bloom filters are pretty cool -- they are sets that support membership checking with no false negatives, but a small chance of a false positive. Recently though, I've been wanting a "Bloom filter" ...
7
votes
1answer
209 views

Looking for easy applications of fractional cascading

I want to give a couple of talks on fractional cascading, one of which will focus on applications. I'm looking for applications that make use of the full version of fractional cascading, not just the ...
20
votes
1answer
825 views

How fast can we compute the set inclusion poset of a set family?

Given a set family $\mathcal{F}$ of subsets of a universe $U$. Let $S_1,S_2 \in \mathcal F$ and we want to answer is $S_1 \subseteq S_2$. I am looking for a data-structure that will allow me to ...
8
votes
0answers
118 views

Purely Functional Representations of Catenable Sorted Lists question

Good day. I'm currently reading the paper "Purely Functional Representations of Catenable Sorted Lists" by Tarjan and Kaplan[link to the paper]. But I have a question about the modified 2-3 finger ...
14
votes
1answer
3k views

Need a good overview for Succinct Data Structure algorithms

(already asked on main site, but asking also here for better coverage, sorry) Since I knew about Succinct Data Structures I'm in a desperate need of a good overview of most recent developments in ...
6
votes
1answer
175 views

Split find-min data structure that finds several small elements?

The split find-min data structure is initialized with a sequence of elements $e_1,\ldots,e_n$, each associated with a key. The data structure supports three operations: (1) $Split(e_i)$ that splits ...
3
votes
1answer
220 views

Defintion of a Data Structure? [closed]

Lately I have been looking around for a formal definition of a what a data structure is. I cannot find neither a paper, nor a book with such a definition. Even the famous "The Art of Computer ...
2
votes
1answer
138 views

Set query in a universe with overlapping sets

Suppose we have a universe $U$ of $n$ items $u_1,u_2,u_3,...,u_n$. And a collection of sets (no restriction on being disjoint or exhaustive etc.) which cover some items. Size of each set is bounded by ...
13
votes
2answers
362 views

Data structure for updates on intervals and querying number of zeros

I am looking for a data structure that would maintain an integer table $t$ of size $n$, and allowing the following operations in time $O(\log n)$. $\text{increase}(a,b)$, which increases $t[a],t[a+1],...
4
votes
0answers
423 views

Dynamic shortest path data structure for DAG

Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted. I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...