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.
339
questions
605
votes
6
answers
125k
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 ...
- 8,721
379
votes
92
answers
113k
views
Algorithms from the Book
Paul Erdős 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 ...
73
votes
9
answers
16k
views
Powerful Algorithms too complex to implement
What are some algorithms of legitimate utility that are simply too complex to implement?
Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication ...
65
votes
10
answers
12k
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 ...
- 16.3k
57
votes
13
answers
3k
views
For which algorithms is there a large gap between the theoretical analysis and reality?
Two ways of analyzing the efficiency of an algorithm are
to put an asymptotic upper bound on its runtime, and
to run it and collect experimental data.
I wonder if there are known cases where there ...
53
votes
2
answers
6k
views
What are the outstanding questions in purely functional data structures?
This question is inspired by another question about what's new in PFDS since the publication of Okasaki's book in 1998.
I'll start with two questions I have:
Is there a purely functional set data ...
44
votes
4
answers
41k
views
Why would one ever use an Octree over a KD-tree?
I have some experience in scientific computing, and have extensively used kd-trees for BSP (binary space partitioning) applications. I have recently become rather more familiar with octrees, a similar ...
- 857
41
votes
4
answers
12k
views
Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?
I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally:
It uses O(1) space
It can be updated to reflect an insertion or deletion in O(...
- 747
40
votes
10
answers
13k
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, ...
Chris
39
votes
6
answers
8k
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" ...
- 1,042
38
votes
8
answers
2k
views
Higher-order algorithms
Most of the well-known algorithms are first-order, in the sense that their input and output are "plain" data.
Some are second-order in a trivial way, for example sorting, hashtables or the map and ...
- 8,721
34
votes
3
answers
2k
views
Comparison-based data structure for finding items
Is there a data structure that takes an unordered array of $n$ items, performs preprocessing in $O(n)$ and answers queries: is there some element $x$ on the list, each query in worst time $O(\log n)$?
...
- 443
34
votes
6
answers
10k
views
Is there a stable heap?
Is there a priority queue data structure that supports the following operations?
Insert(x, p): Add a new record x with priority p
StableExtractMin(): Return and delete the record with minimum ...
- 22.9k
30
votes
5
answers
4k
views
Binary search generalizations for posets?
Suppose I have a poset "S" and a monotonic predicate "P" on S.
I want to find one or all maximal elements of S satisfying P.
EDIT: I'm interested in minimizing the number of evaluations of P.
What ...
- 8,721
27
votes
2
answers
3k
views
I dreamt of a data structure, does it exist?
I haven't managed to find this data structure, but I'm not an expert in the field.
The structure implements a set, and is basically an array of comparable elements with an invariant. The invariant is ...
- 653
25
votes
3
answers
4k
views
Nontrivial algorithm for computing a sliding window median
I need to calculate the running median:
Input: $n$, $k$, vector $(x_1, x_2, \dotsc, x_n)$.
Output: vector $(y_1, y_2, \dotsc, y_{n-k+1})$, where $y_i$ is the median of $(x_i, x_{i+1}, \dotsc, x_{i+k-...
- 11.4k
24
votes
4
answers
2k
views
Handbook of advanced data structures
I am looking for a book on advanced data structures that goes beyond what is covered in standard textbooks like Cormen, Leiserson, Rivest, and Stein's "Introduction to Algorithms".
A book that can be ...
- 21.3k
24
votes
2
answers
551
views
Parallel Dynamic Search
Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?
More generally, what's the best we can do ...
- 31.9k
22
votes
6
answers
1k
views
Analogs of compressed sensing
In compressed sensing, the goal is to find linear compression schemes for huge input signals that are known to have a sparse representation, so that the input signal can be recovered efficiently from ...
- 6,960
22
votes
9
answers
18k
views
What is the recommended software for drawing data structures such as graphs and trees?
When putting together results, it's often desirable to have some professional looking diagrams, rather than diagrams put together in MS Paint. What is the standard for drawing data structures?
- 323
22
votes
2
answers
862
views
Can the cost of GC be neglected when analyzing the running time of worst-case data structures specified in a garbage-collected programming language?
I just realized that I have been assuming the answer to my question is "yes" but I don't have a good reason. I imagine that maybe there is a garbage collector that provably introduces only $O(1)$ ...
- 591
22
votes
1
answer
962
views
Splittable stack
What is known about data structures that can maintain a sequence of items subject to the following two operations?
Push(x): add x to the end of the sequence, and return an identifier for its position ...
- 50.5k
20
votes
4
answers
3k
views
Data Structure isomorphisms
Disclaimer: I am not a CS theorist.
Coming from abstract algebra, I'm used to dealing with things that are equal up to a isomorphism - but I'm having a trouble translating this concept to data ...
- 203
20
votes
5
answers
459
views
Reducing space usage of st-connectivity with multiple passes?
Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream.
Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar
Rajagopalan ...
- 18.8k
20
votes
1
answer
773
views
How close can we get to linear multiply, add, and compare (on integers)?
Accoring to K. W. Regan's article "Connect the Stars", he mentions at the end that it is still an open problem to find a representation of integers such that the addition, multiplication, and ...
- 2,080
20
votes
2
answers
2k
views
Data structure for shortest paths
Let $G$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Is it possible to preprocess $G$ and produce a data structure of size $m \cdot \mathrm{polylog}(n)$ so that it can answer ...
- 1,559
20
votes
2
answers
863
views
maintaining a balanced spanning tree of a growing undirected graph
I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph.
I have an undirected graph that starts as a single node, the "root".
At each ...
- 331
20
votes
1
answer
933
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 ...
- 1,319
19
votes
2
answers
2k
views
A data structure for minimum dot product queries
Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of ...
- 1,559
18
votes
2
answers
2k
views
Is the traditional analysis of Bloom filters wrong?
This paper claims that the traditional analysis of the error rate in Bloom filters is incorrect, then provides a lengthy and nontrivial analysis of the actual error rate. The linked paper was ...
- 1,921
18
votes
2
answers
3k
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 ...
- 803
18
votes
1
answer
1k
views
Splay tree potential function: why sum the logs of the sizes?
I'm teaching a course on data structures and will be covering splay trees early next week. I've read the paper on splay trees many times and am familiar with the analysis and intuition behind the data ...
- 1,921
17
votes
3
answers
5k
views
Merging Two Binary Search Trees
I'm looking for an algorithm to merge two binary search trees of arbitrary size and range. The obvious way I would go about implementing this would be to find entire subtrees whose range can fit into ...
- 273
17
votes
1
answer
1k
views
Online transitive closure better than O(N^2) per edge addition
I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this:
...
- 696
17
votes
3
answers
904
views
Succinct data structures survey?
Fischer's paper this month reminded me how little I know about the art of succinct data structures, and algorithms to use them.
For those that don't know about succinct data structures:
Given a ...
- 2,351
17
votes
0
answers
295
views
Sequences with sublogarithmic concat and approximate split
Is there a data structure for representing sequences that supports the operations:
concat takes two sequences of size $m$ and $n$ and produces a new sequence of size $m+n$ by joining them in time $o(\...
- 11.1k
16
votes
3
answers
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 ...
- 308
16
votes
2
answers
942
views
Faster join of treap-like data structures with approximately the same size
Given two AVL trees $T_1$ and $T_2$ and a value $t_r$ such that $\forall x \in T_1, \forall y \in T_2, x < t_r < y$, it is easy to construct a new AVL tree containing $t_r$ and the values in $...
- 11.1k
15
votes
2
answers
1k
views
Notable examples of the square root idea in complexity analysis
There are a number of algorithms and data structures which exploit the idea that $\max \left\{k, n/k\right\}$ gets its minimum value at $k=\sqrt n$. Common examples include
baby-step giant-step ...
15
votes
2
answers
3k
views
What is a zipper, and how does it relate to a tree-like structure?
I was reading a chapter in LYAH which didn't really make sense to me. I understand that zippers can arbitrarily traverse a tree-like structure, but I need some clarification on it. Also, can zippers ...
- 151
15
votes
1
answer
638
views
Bloom filter hashes: more or bigger?
In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions. Kirsch and Mitzenmacher showed that you actually only need two, and can generate the rest as ...
- 303
15
votes
1
answer
302
views
Maintaining order in a list in $AC^0$ in $O(1)$ time
The order maintenance problem (or "maintaining order in a list") is to support the operations:
singleton: creates a list with one item, returns a pointer to it
<...
- 11.1k
15
votes
3
answers
685
views
Associative hash mixing
Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths ...
- 2,161
15
votes
2
answers
543
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. (...
- 11.1k
15
votes
0
answers
390
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 ...
- 1,167
15
votes
2
answers
612
views
Exponential Speedup in External Memory
Background
The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses). These running times are generally given in ...
- 1,657
14
votes
3
answers
2k
views
Lower Bounds for Data Structures
Are results known which rule out the existence of "too-good-to-be-true" data structures?
For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see Dietz ...
- 800
14
votes
4
answers
2k
views
Subrange of a Red and Black Tree
While trying to fix a bug in a library, I searched for papers on finding subranges on red and black trees without success. I'm considering a solution using zippers and something similar to the usual ...
- 242
14
votes
2
answers
1k
views
Difference lists in functional programming
The question What's new in purely functional data structures since Okasaki?, and jbapple's epic answer, mentioned using difference lists in functional programming (as opposed to logic programming), ...
- 2,386
14
votes
2
answers
2k
views
Purely Functional Equivalent of B-Tree?
I am exploring the idea of writing a DBMS in purely functional way. The traditional data structure used for indexing is B-Tree. I'd like to know some purely functional equivalent of B-Tree that would ...
- 353