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 ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
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....
user avatar
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)$, $\...
user avatar
  • 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 ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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}$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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/...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$? ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible