37
votes
Accepted
Is the traditional analysis of Bloom filters wrong?
The traditional analysis is fine. The "traditional" analysis is, if it is explained correctly, an approximation; it's based on calculating the expected number of cells that are 0/1 when you hash the ...
16
votes
Data structure to determine if sets are disjoint in o(n) time
The communication complexity of the set disjointness problem is $\Omega(n)$. The communication complexity is a lower bound on the time complexity of testing whether the two instances are disjoint. ...
- 10.4k
14
votes
Accepted
Splay tree potential function: why sum the logs of the sizes?
How to come up with sum-of-logs potential
Let's consider the BST algorithm $A$ that for each access for element $x$, it rearranges only elements in the search path $P$ of $x$ called before-path, into ...
- 1,120
13
votes
Accepted
Improved lower bounds or upper bounds on union-find structures since Tarjan?
There's a matching lower bound in the cell probe model (with a logarithmic number of bits per memory cell); see Fredman and Saks, "The cell probe complexity of dynamic data structures", STOC 1989.
- 50.2k
12
votes
Is the traditional analysis of Bloom filters wrong?
Let me add to Michael's answer that for split Bloom filters, where the hash functions have disjoint ranges, the traditional analysis is indeed correct without approximation or any concentration bounds....
- 932
12
votes
Accepted
Fun with inverse Ackermann
Let $A_k$ be the inverse of $\alpha_k$. $A_1(x) = 2x, A_2(x) = 2^x, \dots$. I claim that $k^{-1}(x) = A_x(x)$.
Since $x = \alpha_x(A_x(x))$, and since $\forall z, \alpha_y(z) > \alpha_x(z)$, $\...
- 11k
11
votes
Purely(ish) functional data structure with fast append and forward iteration
You're quite right that the "queue = two lists" approaches don't give you the running time you want when you have the ability to re-use earlier versions. To get O(1) running time (amortized or worst ...
- 211
11
votes
Accepted
How to show that the median cannot be maintained in $O(1)$ time?
If you can maintain the median of $n$ objects in $O(1)$, then you can sort a sequence $x_1, \dots, x_n$ in $O(n)$:
first you compute a value $a$ smaller than all elements in the sequence and a value $...
- 685
9
votes
Would a purely topological computational model be useful in decision problems in topology?
Avishy Carmi and Daniel Moskovich have been developing tangle machines very recently, which is a topological model to describe information. There are two papers on the arXiv, as well as three ...
- 824
9
votes
Accepted
Generalized Priority Queues
You will need to make some assumptions about what kinds of functions are allowed to get anywhere with this.
The version of the problem where the elements of $S$ are linear functions from $\mathbb{R}$ ...
- 50.2k
9
votes
Accepted
Two papers give contradictory bounds on linear probing. How do I resolve the disparity?
The first one is average-case analysis, for sets of keys that are already somewhat randomly distributed (chosen either before or after the choice of hash function but with a probability distribution ...
- 50.2k
8
votes
Accepted
Would a purely topological computational model be useful in decision problems in topology?
I'm not sure whether this qualifies as a purely topological computational model, but there is a topological approach to anyonic quantum computation within the framework of which Aharonov-Jones-Landau ...
- 357
8
votes
Sorted dictionary structure supporting efficient merges?
If you have a balanced binary search tree data structure with the finger search tree property (a search for an item $d$ positions away takes time $O(\log d)$), such as for instance a splay tree, then ...
- 50.2k
8
votes
Accepted
Quick-select contiguous subarray
$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.
- 4,256
8
votes
Accepted
Fast Algorithm to Check if a Set of Sets forms an Anti-chain
This problem is SETH-hard at time $n^2$ (Williams 04). There is is no $n^{2-\epsilon}$ algorithm for any $\epsilon > 0$ if the universe has size $\omega(\log n)$.
For small universe size ($c \log ...
- 349
8
votes
Accepted
Random sampling data structure with removal
Copying my comment on that from here:
There exist published algorithms that support sampling from discrete probability distributions in O(1) time, AND modifying the distribution in O(1) time per ...
- 8,143
8
votes
Sublinear Time Regular Expression Search
Consider the following setup. Let $s$ be a string in the pattern <w1><w2>... for words $w_1, w_2, \dots$ that don't include ...
- 690
7
votes
What's new in purely functional data structures since Okasaki?
Following up on the 2012 paper linked above, the work on RRB vectors has since been extended and published in ICFP'15.
RRB vector: a practical general purpose immutable sequence
http://dl.acm.org/...
- 71
7
votes
Accepted
Isomorphism between algebraic data-types
Spoiler: the types are isomorphic.
First let me clarify what might be meant by "isomorphic". Say that two datatypes $S$ and $T$ are isomorphic if there are maps $f : S \to T$ and $g : T \to S$ such ...
- 26.6k
7
votes
Accepted
What are the must-read search trees paper?
Sleator-Tarjan '85 and Demaine et al '09 definitely belong on any such list.
There is a lot of other recent work related to splay trees and dynamic optimality, for instance:
Applications of forbidden ...
- 50.2k
7
votes
Pairwise comparison of bit vectors
This problem is sometimes called Subset Containment and it is computationally equivalent to: given $n$ sets $S_1,\ldots,S_n \subseteq [d]$, are there $i \neq j$ such that $S_i \cap S_j = \varnothing$? ...
- 26.3k
7
votes
Accepted
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
2.09 bits per element is practically achievable. See http://cmph.sourceforge.net/: "[Compress, Hash, Displace] can generate MPHFs that can be stored in approximately 2.07 bits per key."
1.44 bits per ...
- 11k
7
votes
Accepted
How fast can we find and disconnect roots in a forest?
The problem has name "fringe marked ancestor problem" and indeed has $O(\log \log n)$ worst-case solution for both operations [1], thus overcoming the lower bound for generic version of the problem. ...
6
votes
Accepted
Shortest distance/path between two households
This problem is well considered and learned in recent decades as every GPS device faces this problem.
In practice (AFAIK), the standard way of facing this problem is by the usage of distance oracles, ...
- 9,378
6
votes
Data structure for dynamic memory allocation
Even without the time bound, it is impossible to "avoid memory segmentation" unless you can move the allocated objects around, like in a compacting garbage collector. See Robson's "Bounds for Some ...
- 11k
6
votes
Accepted
How can I formalize key value stores with set theory?
You did not say why you want a formalization, but presumably you want to do things with it, for instance prove properties of dictionaries and operations on them. In fact, your question can be ...
- 26.6k
6
votes
Accepted
Min Hamming distance of a given string from substrings of another string
Elaborating Paul's suggestion for a $O(n \log n)$-time algorithm:
Input: Let $u \in [m]^k$ and $v \in [m]^n$ with $k \leq n$, where $U=[m]=\{1,2,\cdots,m\}$.
Define polynomials $$p(x,y) = \sum_{i \...
- 2,743
6
votes
Huffman Tree Depth, Is there any theory?
I don't know of a way to compute the length of the code exactly without constructing a Huffman code. And there may be more than one optimal Huffman code for a given set of weighted items, with ...
- 50.2k
6
votes
Accepted
maximizing inner product
For three-dimensional vectors, construct the three-dimensional convex hull of the vectors in $L'$ in time $O(n\log n)$. The maximizer for a vector $v$ in $L$ is the point of the convex hull that is ...
- 50.2k
6
votes
Accepted
Constant-time bounds on offline 2-choice hashing?
You're missing the (obvious but) unstated caveat of "with high probability", I think. If you're hashing randomly, there's some chance all items choose the same two buckets. With high probability, ...
Only top scored, non community-wiki answers of a minimum length are eligible