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
1 vote
0 answers
63 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 ...
user avatar
  • 9,358
7 votes
2 answers
2k 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 ...
user avatar
  • 434
15 votes
0 answers
382 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 ...
user avatar
  • 1,035
3 votes
3 answers
429 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 \...
user avatar
  • 10.3k
4 votes
1 answer
164 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 ...
user avatar
5 votes
0 answers
145 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 ...
user avatar
5 votes
4 answers
768 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 ...
user avatar
  • 434
0 votes
1 answer
2k 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, ...
user avatar
  • 189
7 votes
0 answers
186 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 $...
user avatar
5 votes
1 answer
401 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$ ...
user avatar
  • 338
7 votes
1 answer
353 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....
user avatar
10 votes
1 answer
285 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 ...
user avatar
  • 303
6 votes
2 answers
178 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 ...
user avatar
  • 1,120
13 votes
0 answers
174 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 ...
user avatar
6 votes
0 answers
151 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 ...
user avatar
4 votes
1 answer
449 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-...
user avatar
3 votes
2 answers
188 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 ...
user avatar
6 votes
1 answer
214 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, ...
user avatar
2 votes
1 answer
462 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'} \...
user avatar
  • 1,085
8 votes
1 answer
143 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 ...
user avatar
1 vote
0 answers
72 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 ...
user avatar
  • 916
2 votes
1 answer
112 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 $...
user avatar
2 votes
0 answers
149 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 ...
user avatar
  • 185
5 votes
1 answer
158 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 ...
user avatar
  • 423
8 votes
3 answers
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 (...
user avatar
  • 501
2 votes
1 answer
565 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 ...
user avatar
4 votes
2 answers
231 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, ...
user avatar
  • 185
6 votes
1 answer
358 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 ...
user avatar
0 votes
2 answers
147 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 &...
user avatar
7 votes
2 answers
124 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) \...
user avatar
  • 11k
6 votes
1 answer
343 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 ...
user avatar
2 votes
1 answer
189 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 ...
user avatar
  • 185
6 votes
2 answers
1k 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 ...
user avatar
  • 113
0 votes
0 answers
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 ...
user avatar
  • 1
0 votes
0 answers
36 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 ...
user avatar
3 votes
0 answers
78 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 ...
user avatar
9 votes
0 answers
132 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 ...
user avatar
  • 303
6 votes
1 answer
242 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 ...
user avatar
4 votes
1 answer
317 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 ...
user avatar
  • 149
2 votes
1 answer
144 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 ...
user avatar
  • 161
1 vote
1 answer
285 views

How can I formalize key value stores with set theory? [closed]

I'm currently developing a simple key-value NoSQL store and want to build its formal model. I'm interested in knowing if there some work about formalization of key-value stores outside of category ...
user avatar
6 votes
1 answer
869 views

Array implementation of dictionary data structure

Is there a data structure that supports searching, inserting, deletion in worst-case O(log n) time and that satisfies the following "array implementation" property: at any point in time, the data ...
user avatar
  • 7,459
11 votes
2 answers
660 views

Fun with inverse Ackermann

The inverse Ackermann function occurs often when analyzing algorithms. A great presentation of it is here: http://www.gabrielnivasch.org/fun/inverse-ackermann. $$\alpha_1(n) = [n/2]$$ $$\alpha_2(n) = ...
user avatar
12 votes
2 answers
920 views

Data structure for dynamic memory allocation

Think of the cell-probe model. Is there a data structure that can allocate contiguous chunks of memory of any length (like e.g. malloc in C), and free them, while avoiding memory segmentation, and ...
user avatar
  • 7,459
7 votes
1 answer
243 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 ...
user avatar
  • 71
3 votes
1 answer
392 views

Sorted intervals query

I'm in search for a data structure which efficiently operates over closed intervals with the following properties: dynamically add or remove an interval set, and anytime change, a number ("depth") ...
user avatar
  • 289
2 votes
1 answer
243 views

Persistent data structures in RAM computational model

Always when I read about any efficient persistent data structures they use pointer computational model. I'm wondering if you know any efficient implementation which uses power of RAM model?
user avatar
  • 21
4 votes
1 answer
446 views

Array-like data structure with O(1) worst-case concatenate/join?

I am looking for a data structure $D$ which supports the following operations (preferably a (binary) tree-like structure): $D$ is indexed, i.e. there is a mapping from $\{1, \ldots, n\}$ to items ...
user avatar
  • 233
5 votes
0 answers
211 views

Rebalancing balanced binary search tree when decreasing all keys to the right of a path?

Given a balanced binary search tree, suppose I have an operation decrease-right-keys(k, s) that operates as follows: when I call this operation on a tree $T$, I decrease all keys by $s$ in the right ...
user avatar
7 votes
0 answers
773 views

Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?

Context: For fun and perhaps for actual use, I'm making my own programming language that would compile to Typed Racket, a statically-typed Lisp dialect. One of the major features I want to implement ...
user avatar
  • 181

1
2
3 4 5
7