We consider the problem of finding high-dimensional approximate nearest neighbors. We introduce an old style probabilistic formulation instead of the more general locality sensitive hashing (LSH) formulation, and show that at least for sparse problems it recognizes much more efficient algorithms than the sparseness destroying LSH random projections. Efficient algorithms for homogeneous (all coordinates have the same probability distribution) problems are well known, the most famous reference being the work by Broder in 1998. The main theme of this paper is to find its “best” generalization to heterogeneous (different coordinate probabilities) problems. We find a practical algorithm which is asymptotically best in a wide natural class of algorithms. Readers interested in the more complicated very best (at least up to date) can look up our previous work in 2010. The analysis of our algorithms reveals that its complexity is governed by an information like function, which we call “small leaves bucketing forest information.” Any doubts whether it is “information” are dispelled by the aforementioned work.

The problem of finding high-dimensional approximate nearest neighbors is considered when the data is generated by some known probabilistic model. A large natural class of algorithms (bucketing codes) is investigated, Bucketing information is defined, and is proven to bound the performance of all bucketing codes. The bucketing information bound is asymptotically attained by some randomly constructed bucketing codes. The example ofnBernoulli(1/2) very long (lengthd→ ∞) sequences of bits is singled out. It is assumed thatn- 2msequences are completely independent, while the remaining2msequences are composed ofmdependent pairs. The interdependence within each pair is that their bits agree with probability1/2 <; p≤ 1. It is well known how to find most pairs with high probability by performing order ofnlog22/pcomparisons. It is shown that order ofn1/p+∈comparisons suffice, for any ∈> 0. A specific 2-D inequality (proven in another paper) implies that the exponent1/pcannot be lowered. Moreover, if one sequence out of each pair belongs to a known set ofn(2p-1)2sequences, pairing can be done using ordern1+∈comparisons!

Moore and Shannon have shown that relays with arbitrarily high reliability can be built from relays with arbitrarily poor reliability. Valiant used similar methods to construct monotone read-once formulas of size $O(n^{\alpha+2})$ (where $\alpha=\log_{\sqrt{5}-1}2\simeq 3.27$) that amplify $(\psi-\frac{1}{n},\psi+\frac{1}{n})$ (where $\psi=(\sqrt{5}-1)/2\simeq0.62$) to $(2^{-n},1-2^{-n})$ and deduced as a consequence the existence of monotone formulas of the same size that compute the majority of n bits. Boppana has shown that any monotone read-once formula that amplifies $(p-\frac{1}{n},p+\frac{1}{n})$ to $(\frac{1}{4},\frac{3}{4})$ (where $0 < p < 1$ is constant) has size $\Omega(n^\alpha)$ and that any monotone, not necessarily read-once, contact network (and in particular any monotone formula) that amplifies $(\frac{1}{4},\frac{3}{4})$ to $(2^{-n},1-2^{-n})$ has size $\Omega(n^2)$. We extend Boppana's results in two ways. We first show that his two lower bounds hold for general read-once formulas, not necessarily monotone, that may even include exclusive-or gates. We are then able to join his two lower bounds together and show that any read-once, not necessarily monotone, formula that amplifies $(p-\frac{1}{n},p+\frac{1}{n})$ to $(2^{-n},1-2^{-n})$ has size $\Omega(n^{\alpha+2})$. This result does not follow from Boppana's arguments, and it shows that the amount of amplification achieved by Valiant is the maximal achievable using read-once formulas. In a companion paper we construct monotone read-once contact networks of size $O(n^{2.99})$ that amplify $(\frac{1}{2}-\frac{1}{n},\frac{1}{2}+\frac{1}{n})$ to $(\frac{1}{4},\frac{3}{4})$. This shows that Boppana's lower bound for the first amplification stage does not apply to contact networks, even if they are required to be both monotone and read-once.

Recently, R. Kosaraju gave an O(nm('7' polylog(m )) step algorithm for tree pattern matching.We Improve this result by designing a simple 0( nfipolylog( m)) algorithm, Categories and Suhjcct Descriptors: F.

The authors extend R.B. Boppana's results (1989) in two ways. They first show that his two lower bounds hold for general read-once formulae, not necessarily monotone, that may even include exclusive-or gates. They are then able to join his two lower bounds together and show that any read-once, not necessarily monotone, formula that amplifies (p-/sup 1///sub n/,p+/sup 1///sub n/) to (2/sup -n/,1-2/sup -n/) has size of at least Omega (n/sup alpha +2/). This result does not follow from Boppana's arguments and it shows that the amount of amplification achieved by L.G. Valiant (1984) is the maximal achievable using read-once formulae.>

Recently, R. Kosaraju (Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, p.178-83) gave an O(nm/sup 0.75/ polylog(m))-step algorithm for tree pattern matching. The authors improve this result by designing a simple O(n square root m polylog (m)) algorithm.>