36
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 keys into the filter, and then analyzing as though that was the actual number. The point is that the number of cells that are 0 (or 1) are tightly ...
32
Here's a lower bound from sorting. Given an input set $S$ of length $n$ to be sorted, create an input to your running median problem consisting of $n-1$ copies of a number smaller than the minimum of $S$, then $S$ itself, then $n-1$ copies of a number larger than the maximum of $S$, and set $k=2n-1$. The running medians of this input are the same as the ...
23
The cells in a $kD$-tree can have high aspect ratio, whereas octree cells are guaranteed to be cubical. Since this is a theory board, I'll give you the theoretical reason why high aspect ratio is a problem: it makes it impossible to use volume bounds to control the number of cells that you have to examine when solving approximate nearest neighbor queries.
...
21
The answer to this question is "no". To see why, we can think about a very extreme case, and how a regular bloom filter would work vs. a theoretical "Bizzaro World" bloom filter, which we can call a "gloom filter".
What is great about a bloom filter is that you can do one-sided tests for membership of items (with false positives) using a data structure that ...
17
This is almost certainly impossible.
Suppose you could solve your problem with preprocessing time $P(n)$ and query time $Q(n)$. Then there is a simple algorithm to solve the 3SUM problem—Given a set of $n$ real numbers, do any three elements sum to zero?—in $P(n)+n\cdot Q(n)$ time. We pre-process all the numbers, then for each number $a_k$, we find the ...
16
You're right to think of hash functions in terms of "random bits produced". So if you have a hash function that produces a 64 bit hash, you can treat is as 4 16-bit hashes (by splitting), and so on.
For the scheme described above (which should be attributed to Dillinger and Manolios; Kirsch/Mitzenmacher just analyzed it), that means you're correct; if ...
16
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. Imagine Alice stores the data structure for the first set, and Bob stores the data structure for the second set; since they'll have to communicate $\Omega(n)$ ...
14
I wish I had a good answer for you. I use Book:Fundamental Data Structures (a collection of relevant Wikipedia articles) for my course on this subject but it's not really a complete textbook (for one thing, it has no exercises). CLRS is, I think, at a good level of detail for this sort of class but is missing too many of the important structures.
14
Probably not the best answer, but perhaps this is a useful starting point. If we wish to represent a non-negative integer, we can store it as a set of residues modulo sequential prime numbers starting from 2. In this form comparison is potentially hard, but multiplication and addition can be done pretty quickly. The product of the first $n$ primes is ...
14
A zipper, in general, is a data structure with a hole in it. Zippers are used for traversing/manipulating data structures, and the hole corresponds to the current focus of the traversal. Typically there is also an element of the data structure under consideration, so that one has a (list) zipper and a list or a (tree) zipper and a tree. The zipper allows the ...
14
Your problem is known in the learning literature as "learning monotone functions using membership queries". A class of monotone functions for which one can identify all minterms is known as "polynomially learnable using membership queries".
It seems that the existence of a polynomial time algorithm is still open. Schmulevich et al. prove that "Almost all ...
13
No, this is not new; range searching with multilevel B-trees is completely standard. See, for example, the following surveys:
Lars Arge.
External memory data structures. Handbook of Massive Data Sets (James Abello, Panos M. Pardalos, and Mauricio G. C. Resende, eds.), 313-357. Kluwer Academic Publishers, 2002. See especially sections 5 and 6.
Jeffrey ...
13
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 some tree called after-tree. For any element $a$, let $s(a)$ and $s'(a)$ be the size of subtree rooted at $a$ before and after the rearrangement respectively. ...
13
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.
12
I assume that you are interested in succinct external memory data structures that are efficient in practice. In that case, you can probably get what you want with a few basic techniques and some engineering.
For trees, I would start with reading Arroyuelo et al.: Succinct Trees in Practice. The paper deals with trees in main memory, but most of the ...
12
There isn't really a single formalization of the kind of thing you are asking. There are many, many aspects to truth, trust, lies, and fallible reasoning, and this leads to an enormous variety of logical formalisms, each handling different aspects of this problem.
If you want to account for uncertainty about your hypotheses, the traditional route is via ...
12
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. This is because the error probabilities for different hash functions become independent rather than correlated. The space/error trade-off for split Bloom ...
12
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)$, $\alpha_y(A_x(x)) > \alpha_x(A_x(x)) = x$. As a result $k(A_x(x)) = x$.
Now consider the value of $\alpha(k^{-1}(n)) = \alpha(A_n(n))$. By definition of $\alpha$,...
10
I propose Reed-Solomon coding. The basic idea is that you can encode your data as a polynomial over a finite field. You can then evaluate this polynomial at several different points and these values become the messages that you will send. If the degree of the polynomial is N, then a receiving party only needs to receive N+1 messages in order to reconstruct ...
10
There are $O(m^{3/2})$ triangles in any $m$-edge graph and that they can be found in $O(m^{3/2})$ time. There are many ways of doing this but I think one of the earliest is Itai and Rodeh (STOC 1977) who provide an algorithm that goes through a sequence of linear-time iterations, each of which removes a spanning forest from the graph. In the early iterations ...
10
Chazelle, Liu, and Magen's paper Sublinear Geometric Algorithms (STOC 2003, SICOMP 2006) has several clever applications of the following random sampling trick. Variations of the same trick were previously used by Gärtner and Welzl [DCG 2001], who cite the first edition of CLR (1990).
Suppose we are given a sorted circular linked list of numbers, stored in ...
10
The only advanced data structures book that I'm aware of is the one by Peter Braß (Advanced Data Structures). It's not a bad book, but I'm not convinced that it's truly advanced at the graduate level.
10
The "offline" version of this question is addressed in my SODA 2014 paper with Huacheng Yu, Finding orthogonal vectors in discrete structures. For the case of $\mathbb F_2$, we give an $O(nd)$ time algorithm for determining, given two sets of $n$ vectors $A$ and $B$, whether there is a vector in $A$ and vector in $B$ with zero inner product.
I'm sure you ...
10
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 case), you need a way to reverse the rear list and append it to the front list incrementally. Instead of doing the reverse&append all at once, taking O(N) ...
9
what are the advantages of octrees in spatial/temporal performance or otherwise, and in what situations are they most applicable (I've heard 3D graphics programming)?
k-D trees are balanced binary trees and octrees are tries so the advantages and disadvantages are probably inherited from those more general data structures. Specifically:
Rebalancing can be ...
9
The Handbook of Data Structures and Applications (Chapman & Hall/CRC Computer & Information Science Series) is mostly devoted to elementary data structures, but it also contains a few advanced materials that you may find useful for teaching a graduate level course. Given the huge size (1392 pages), this book may be classified as an encyclopedic ...
9
Edit: This algorithm is now presented here: http://arxiv.org/abs/1406.1717
Yes, to solve this problem it is sufficient to perform the following operations:
Sort $n/k$ vectors, each with $k$ elements.
Do linear-time post-processing.
Very roughly, the idea is this:
Consider two adjacent blocks of input, $a$ and $b$, both with $k$ elements; let the elements ...
9
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 introductory posts on the blog "Low Dimensional Topology" :
http://ldtopology.wordpress.com/2014/05/04/low-dimensional-topology-of-information/
9
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}$ to $\mathbb{R}$ has been studied, in a projectively dual form: if you think of each linear function $y=ax+b$ as being coordinatized by the pair of parameters $(...
9
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 that is independent of the hash function). The second one is worst-case analysis, for sets of keys that are not random but are instead specially chosen to make ...
Only top voted, non community-wiki answers of a minimum length are eligible
