Lower Bounds on Near Neighbor Search via Metric Expansion

Introduction

In the Nearest Neighbor Problem we are given a data set of $n$ points $x_{1},...,x_{n}$ lying in a metric space $V$. The goal is to preprocess the data set into a data structure such that when given a query point $y\in V$, it is possible to recover the data set point which is closest to $y$ by querying the data structure at most $t$ times. The goal is to keep both the querying time $t$ and the data structure space $m$ as small as possible. Nearest Neighbor Search is a fundamental problem in data structures with numerous applications to web algorithms, computational biology, information retrieval, machine learning, etc. As such it has been researched extensively.

There is a substantial body of work on lower bounds covering various metric spaces and parameter settings; we discuss the known bounds in Section 1.3. Traditionally, cell probe lower bounds for data structures have been shown using communication complexity arguments . Pătraşcu and Thorup use a direct sum theorem along with the richness technique to obtain lower bounds for deterministic algorithms. Andoni, Indyk and Pătraşcu showed randomized lower bounds using communication complexity lower bounds for Lopsided Set Disjointness. In a previous work , the authors used a more direct geometric argument to show lower bounds for randomized algorithms for the search version of the problem.

In this work we strengthen and significantly generalize our previous results. We give a common framework that unifies almost all known cell probe lower bounds for near neighbor search. At one extreme, it gives us the communication complexity lower bounds, and implies e.g. the result of . At the other extreme, we get direct data structure lower bounds leading to a strengthening to the decision problem of our results in . Our work in fact shows that all near neighbor lower bounds follow from basic expansion properties of the metric space. Vertex expansion translates to lower bounds for deterministic data structures. Edge expansion can be translated to lower bounds for randomized data structures, and this lets us strengthen . We also identify a new (to our knowledge) graph parameter that interpolates between vertex and edge expansion, that we call robust expansion. We show that robust expansions suffices to prove NNS lower bounds. Additionally, for random inputs in highly symmetric metrics, robust expansion also translates to upper bounds in the cell probe model, that match our lower bounds for constant $t$. Finally, we present a natural conjecture regarding the complexity of approximate near neighbor search and show tight bounds for dynamic low contention data structures.

The Near Neighbor Problem is parameterized by a number $r$. As in the Nearest Neighbor Search Problem the input to the preprocessing phase is a data set of $n$ points in a metric space. Given a query point $y$ the goal is to determine whether the data set contains a point of distance at most $r$ from $y$. In the approximation version (ANNS) the preprocessing phase receives as input also an approximation ratio $c$. Given a query point $y$ the goal is to differentiate between the case where the closest data set point is of distance at most $r$ from $y$, to the case where the closest data set point is of distance at least $cr$ from $y$. Clearly a lower bound for these problems holds also for nearest neighbor search.

We prove lower bounds for a generalization we call Graphical Neighbor Search (GNS) which we define shortly. We then show that lower bounds on GNS imply ANNS lower bounds. In the GNS problem we are given an undirected bipartite graph $G=(U,V,E)$ where the data set comes from $U$ and queries come from $V$. For a node $u$ the set $N(u)$ denotes its neighbors in $G$. In the preprocessing phase we are given a set of pairs $(x_{1},b_{1}),\ldots,(x_{n},b_{n})$ where $x_{i}$ is a vertex in $U$ and $b_{i}\in\{0,1\}$. The goal is to build a data structure such that given a node $y\in V$, if there is a unique $i$ such that $y\in N(x_{i})$ then it is possible to query the data structure $t$ times and output $b_{i}$. If there is no such $i$ or it is not unique any output is considered correct.

We observe that ANNS reduces to GNS when assuming a query point is at distance at most $r$ from some $x_{i}$ and a least $cr$ from all other $x_{j}$. In this case we have the nodes of $U$ and $V$ correspond to the points in the metric space, and the set of edges consists of all pairs of nodes at distance at most $r$. A formal reduction is proven in Section 4 where we also show that average instances of ANNS translate to average instances of GNS for which our lower bounds hold. The bounds we show depend only on the expansion properties of $G$. We need the following definitions:

Let $\mu$ be a probability measure over $U$ and $\nu$ be a probability measure over $V$. The $\delta-$vertex expansion of the graph with respect to $\mu,\nu$ is defined as

The vertex-expansion $\Phi_{v}$ is defined as the largest $k$ such that for all $\delta\leq\frac{1}{2k}$, $\Phi_{v}(\delta)\geq k$.

Let $A\subset V$, $B\subset U$ and $\delta=\nu(A)$. Observe that if $E(A,B)=E(A,U)$ then $\mu(B)\geq\Phi_{v}(\delta)\nu(A)$. In other words $\Phi_{v}(\delta)$ bounds the measure of the sets that cover all the edges incident on a set of measure $\delta$. The notion of robust expansion relaxes this by requiring $B$ to cover at least a $\gamma$-fraction of the edges incident on $A$. This idea is captured in the definition below. For simplicity we assume that $V=U$ and that $\mu$ and $\nu$ are the uniform distribution and that $G$ is regular. A more subtle definition which takes into account other measures is presented in Section 3.

$G$ has robust-expansion $\Phi_{r}(\delta,\gamma)$ if $\forall A,B\subseteq V$ satisfying $|A|\leq\delta|V|,|B|\leq\Phi(\delta,\gamma)|A|$, it is the case that $\frac{|E(A,B|}{|E(A,V)|}\leq\gamma$. Note that $\Phi_{r}(\delta,1)=\Phi_{v}(\delta)$.

2 Our Contributions

In this section we require that the algorithm always output the correct answer. We show time space tradeoffs based on the vertex expansion properties of $G$. Our lower bounds are in the average case. Given a distribution $\mu$ over $U$, a data set is built by sampling $n$ data set points independently from $\mu$.

Note that in order for the problem to be interesting we must have that $N(x_{i})$ and $N(x_{j})$ are likely to be disjoint. We thus have the following definition:

A distribution $\mu$ over $U$ is said to be strongly independent for $G$ if

Note that if $\mu$ is strongly independent and $x_{1},\ldots,x_{n}$ are sampled independently by $\mu$ then with probability at least $0.99$ $N(x_{i})\cap N(x_{j})=\emptyset$ for all $i\neq j$. In the following $m$ denotes the number of cells in the data structure and $w$ denotes the word size in bits, $t$ is the number of cell probes used by the algorithm.

For a given $G$, let $\mu,\nu$ be probability measures such that $\mu$ is strongly independent, and the vertex expansion with respect to $\mu,\nu$ is $\Phi_{v}(\cdot)$. Then any deterministic algorithm solving GNS must satisfy the following inequalities

These theorems, combined with known isoperimetric inequalities yield most known cell probe lower bounds for near neighbor problems, and generalize them to general expanding metrics. To see this consider for example the $d-$dimensional hypercube equipped with the Hamming distance. It is shown in , that any deterministic solution for ANNS with approximation $1/\epsilon$ must satisfy $t\geq d\epsilon^{3}/\log(mwd/n)$. This bound can be slightly improved by creating the following GNS instance: Let $U$ and $V$ both equal the set of nodes of the hypercube, and let $E=\{(u,v)~{}:~{}|u-v|_{1}\leq\epsilon d\}$. Let $\mu$ and $\nu$ be the uniform distribution. Chernoff bounds implies that for $d=\Omega(\log n)$, $|u-v|_{1}\geq 0.49d$ with overwhelming probability, so $(G,\mu)$ is a strongly independent instance. A lower bound on this instance of GNS implies a lower bound on ANNS with approximation $1/\epsilon$.

Now we use known isoperimetric properties: Harper’s theorem (see e.g. ) implies that there is a constant $a>1$ such that $\Phi_{v}\geq a^{\epsilon^{2}d}$. Plugging this in (1) we have that $t\geq d\epsilon^{2}\log a/\log(mwd/n)$. In Section 4 we discuss how to apply these theorems in greater length.

2.2 Bounds for Randomized Algorithms

Assume that $G$ is regular. Let $x$ and $z$ be vertices drawn uniformly at random, and $y$ be a random neighbor of $x$. We say $G$ has the property of being weakly independent if $\Pr[y\in N(z)]\leq\gamma/n$ for a small enough constant $\gamma$.

There exists an absolute constant $\gamma$ such that the following holds. Any randomized algorithm for a weakly independent instance of GNS which is correct with probability at least half (where the probability is taken over the sampling of the input and the algorithm), satisfies the following inequalities:

As an example, we show in Section 4 that for the Hypercube with $E=\{(u,v)~{}:~{}|u-v|_{1}\leq(\frac{1}{2}-\epsilon)d\}$, the robust expansion $\Phi_{r}(\frac{1}{m^{t}},o(1))\geq\frac{1}{m^{t(1-4\epsilon^{2})}}$. For $d=\Omega(\log n/\epsilon^{2})$, the weak independence property is easy to verify. Plugging this into Equations 4, we conclude that $m^{4t\epsilon^{2}}w\geq n$ so that $m\geq(\frac{n}{w})^{\frac{1}{4t\epsilon^{2}}}$. This result was previously shown by for slightly larger $d$.

Our framework suggests a natural conjecture on the complexity of approximate near neighbor problems.

Any randomized $t$-probe datastructure for a weakly independent GNS instance must satisfy $\frac{mw}{n}t\geq\Phi_{r}(\tfrac{1}{m},\tfrac{1}{2t})^{\Omega(1)}$.

We point out that for some interesting metric spaces such as the Hamming cube and Euclidean space, the known upper bound matches the lower bound in the conjecture for a wide range of parameters. We next present some evidence in support of this conjecture.

2.3 An Upper Bound

There are cases where the bounds above are known to be tight when $t=O(1)$. We show that this is no coincidence: In Section 5 we show that if $G$ is symmetric, there is an algorithm in the cell probe model that solves random instances of GNS using space that matches the lower bound in equation (4) for $t=1$.

2.4 Dynamic Data Structure

In the dynamic version of the problem we want the data structure to support the operation of inserting and deleting a point in the data-set. Let $t_{U}$ denote the update time. A weaker version of the conjecture is the following:

For any dynamic randomized $t$-probe data-structure for weakly independent GNS on $n$ points, it holds that $t_{U}t\geq\Phi_{r}(\tfrac{1}{nt_{U}},\tfrac{1}{2t})^{\Omega(1)}$

To see why this conjecture follows from the stronger one, observe that a data structure with update time $t_{U}$ uses space $mw\leq nt_{U}$ after $n$ inserts. We show that this weaker conjecture holds for a restricted family of algorithms which we call low contention; i.e., on those where no memory location of the data structure is accessed by too many query points (see Section 6 for a formal definition). While this may seem like a severe limitation, we remark that known LSH data structures, and our upper bound in Section 5, are in fact dynamic and low contention under our definition.

For any low contention, dynamic $t$-probe datastructure for GNS on $n$ points, the update time is at least $\Omega\left(\Phi_{r}(\tau,\frac{1}{4t^{2}})/32t^{4}\right)$.

Plugging in the expansion of the hypercube, we see that for a wide range of parameters Locality Sensitive Hashing is optimal for the class of the low contention dynamic data structures over the hypercube.

3 Related Work

We are aware of only two papers which prove time-space lower bounds for near neighbor problems where both randomization and approximation are allowed.

Andoni, Indyk and Pătraşcu show that for small $\epsilon>0$, any $O(1)$-probe algorithm for $(1+\epsilon)$-approximate near neighbor problem must use space $n^{\Omega(\frac{1}{\epsilon^{2}})}$. This bound is tight for small enough $\epsilon>0$ . Panigrahy et al. show that space $n^{1+\Omega(\frac{1}{\epsilon t})}$ is needed for any algorithm with $t$ queries and $\epsilon$ approximation, for the search version of the problem. This bound is tight for constant $t$.

With the exception of all previous bounds were proven using communication complexity framework , and in particular the richness lemma.

4 Notation and Preliminaries

A data structure for Graph neighbor search is defined as follows. Given a database of $n$ points $x_{1},\ldots,x_{n}\in U$, and $b_{1},\ldots,b_{n}\in\{0,1\}$ the preprocessing algorithm computes a set of $t$ tables $T_{1},\ldots,T_{t}$, where each table stores $m$ words of $w$ bits each. We often call each such word a cell of the table. In practice there is only one table, but for notational convenience and with out loss of generality we let the data structure construct a different table for each query.

The query algorithm is specified by $t$ lookup functions $F_{1},\ldots,F_{t}$, where $F_{i}$ takes in the query point $y$ and $(i-1)$ words of $w$ bits each, and outputs an integer in $[m]$, and function $F_{*}:V\times(2^{w})^{t}\rightarrow\{0,1\}$. On a query $y$, the data structure looks up $c_{1}=T_{1}[F_{1}(y)]$, $c_{2}=T_{2}[F_{2}(y,c_{1})],\ldots,c_{t}=T_{t}[F_{t}(y,c_{1},\ldots,c_{t-1})]$. Finally it computes $F_{*}(y,c_{1},\ldots,c_{t})$. Note that the lookup functions, $F_{i}$’s and $F_{*}$ are fixed independent of the database, only the tables $T_{1},\ldots,T_{t}$ can depend on $x_{1},\ldots,x_{t},b_{1},\ldots,b_{t}$. We say the algorithm is non adaptive if the lookup functions are independent of the content of the tables, i.e. of the $c$ values.

5 Overview of Techniques

The core idea behind our approach is quite simple. We demonstrate it by showing a simple argument that the vertex expansion of $G$ provides a lower bound on the space of $1$-probe data structures for deterministic algorithms. By the definition of vertex expansion, every set of $|V|/\Phi_{v}$ nodes is incident to at least half of the nodes of $G$. Let $L$ be a uniformly random sample of a $1/\Phi_{v}$ fraction of the cells of the table $T$, and let $Q$ be the set of nodes in $V$ for which the algorithm probes a cell in $L$. Clearly $Q$ is expected to contain a $1/\Phi_{v}$ fraction of the nodes in $G$. Now consider a sample data set $(x_{1},b_{1}),\ldots,(x_{n},b_{n})$ where $x_{1},\ldots,x_{n}$ are randomly sampled nodes in the graph and $b_{1},\ldots,b_{n}$ are random bits. With overwhelming probability at least a quarter of the $x_{i}$’s have a neighbor in the set $Q$, and thus the random bits associated with these points should be retrievable from the contents of $L$ alone. We conclude that the total number of bits in $L$ is at least $n/4$ and thus the space of the data structure is at least $n\Phi_{v}/4$ bits.

This basic sampling approach for $1$-probe data structures can be extended to $t$-probe data structures in two different ways.

Cell Sampling: Here we sample a $\Phi_{v}^{-\frac{1}{t}}$ fraction of the cells in each table. Thus a $1/\Phi_{v}$ fraction of $V$ is expected to access only the sampled cells. This immediately gives bound (1) for non-adaptive algorithms.

Path Sampling: Here we sample a path as follows: we pick a cell randomly from the first table so that a $\frac{1}{m}$ fraction of the vertices $Q_{1}$ lookup this cell. Then we sample a cell from the second table in such a way that a $\frac{1}{m}$ fraction of $Q_{1}$ looks up this cell in the second read, and so on. This immediately leads to the lower bound in (2) for non-adaptive algorithms.

We remark that the path sampling approach actually leads to communication complexity lower bounds for the 2-player version of the problem where Alice has the query point and Bob has the database. Any $t$-probe data structure with $m$ cells of $w$ words each implies the existence of a $t$-round communication protocol where Alice sends $\log m$ bits, and Bob sends $w$ bits, in each round. A communication protocol has more freedom however; unlike in a data structure, where the same table $T_{2}$ is used to answer any second query, in a communication protocol, the message Bob sends in the second round may depend not just on the second message from Alice, but also on the first. Path sampling can be immediately translated to a “transcript sampling” technique and thus gives lower bounds for communication protocols. There is no similarly obvious translation for cell sampling.

We can extend these ideas and provide lower bounds for adaptive algorithms by observing the following two facts. Firstly, for a fixed data structure, the probability over a random data set that the data structure succeeds is exponentially small in $n$. On the other hand, the number of bits read by the sampling procedures above is sublinear, thus the number of all possible non-adaptive algorithms is sub exponential. Informally, this allows us to do a union bound over all possible values of the bits read.

In randomized algorithms not all points in $N(x)$ are good query points for $x$. In particular, the specific query point that queries the cells that are sampled may be a point on which the algorithm errs. The notion of shattering plays a major role in extending the bound for this case: Given any fixed partitioning $A_{1},\ldots,A_{m}$ of $V$ such that each set is of cardinality $O(|V|/m)$, a randomly chosen $x$ has (with high probability) the property that $\max_{i}|N(x)\cap A_{i}|$ is at most $|N(x)|/K$, for a $K$ that depends on the edge expansion. In other words, $N(x)$ is shattered by the partitioning. Given that the lookup algorithm is correct for a large fraction of $N(x)$, shattering suffices to show that the algorithm still gives the right answer for a majority of the points in $N(x)$ which can be looked up from the cell sample (or the path sample).

In order to prove lower bounds for randomized adaptive algorithms we need to combine the ideas outlined in the two previous paragraphs, which requires more work. Intuitively, for every $x$ such the $N(x)$ is shattered, and for any fixed subset $N^{\prime}(x)$ on which the algorithm succeeds, the sampling is very likely to recover the correct answer. Moreover, for every collection of bits read, almost all points shatter. While it would be tempting to use a union bound at this point, that does not quite work. Informally, there are dependencies everywhere: the part of $N(x_{i})$ that the algorithm gets right depends on all the other $x_{j}$’s, the bits that are read depend on the sampled cells, etc. The proof carefully defines a notion of shattering that depends only on the $x$’s and not on $N^{\prime}(x)$’s and argues (over the randomness in picking the $x_{i}$’s) that most points get shattered. Separately, we argue that for a point that gets shattered, and for any fixed $N^{\prime}(x)$, the majority answer is correct with high probability (over the sampling procedure alone).

The notion of edge expansion does not quite suffice: for the hypercube when $r=(\frac{1}{2}-\epsilon)d$, for fixed partitioning $A_{1},\ldots,A_{m}$ of $V$ into cells of size $|V|/m$, the largest $|N(x)\cap A_{i}|/|N(x)|$ is likely to be quite large ($\approx\frac{1}{m^{\epsilon}}$), whereas we would need it to be $\frac{1}{m^{\epsilon^{2}}}$ to get the correct bound. The definition of robust expansion $\Phi_{r}$ comes to our rescue here. We can show that while the largest $|N(x)\cap A_{i}|$ is usually large, the large pieces account for a very small fraction of $N(x)$. In fact, after removing a vanishingly small fraction of $|N(x)|$, every other piece is only about $\frac{1}{m^{\epsilon^{2}}}$. We show that our lower bound proofs are robust enough to handle this weaker notion of shattering.

Deterministic Lower bounds

In this section we prove Theorem 1.4. The analysis of deterministic algorithms involves node expansion and does not require shattering. It allows us to demonstrate the techniques of cell sampling and path sampling in a simple setting.

The following theorem is a restatement of inequality (1)

Let $\mu$ be such that $(G,\mu)$ is a strongly independent instance, and $\Phi_{v}$ be the vertex expansion with respect to $\mu,\nu$. Then any deterministic algorithm solving GNS must satisfy $(\frac{8mwt}{n})^{t}\geq\Phi_{v}$.

Recall that $T_{i}$ represents a table with $m$ cells, from which the $i^{\prime}th$ query reads, and $F_{i}:V\rightarrow T_{i}$ denotes the $i$’th lookup function. We will state a procedure that obtains a set of at most $tm/\Phi_{v}^{1/t}$ cells so that at least a $1/\Phi_{v}$ fraction of the query points only access these cells. We call this procedure cell sampling. Note that here this procedure is entirely deterministic. A probabilistic variant is used in the next section.

Cell sampling procedure: The cells are obtained iteratively in $t$ phases, each phase corresponds to a query of the table. In each phase at most $m/\Phi_{v}^{1/t}$ cells are chosen. The first lookup function $F_{1}$ induces a partition over $V$. The set $L_{1}$ is chosen to be the $m/\Phi_{v}^{1/t}$ cells in $T_{1}$ that maximize $\nu(F_{1}^{-1}(L_{1}))$. In other words, the first lookup function partitions $V$ according to its image in $T_{1}$. We choose $L_{1}$ to be the cells corresponding to the $m/\Phi_{v}^{1/t}$ largest partitions, as measured by $\nu$. Set $Q_{1}\subset V$ to be those vertices; i.e. $F_{1}^{-1}(L_{1})$. The selection process continues iteratively in a similar manner. Let $L_{i}$ denote the set of cells obtained in the $i$’th phase and let $Q_{i}\subseteq V$ denote the set of vertices that (if given as a query) access only cells in $L_{1},\ldots,L_{i}$ In the $(i+1)$’th phase we consider $F_{i+1}$ and set $L_{i+1}$ to be the $m/\Phi_{v}^{1/t}$ cells with highest measure, where we restrict $\nu$ to $Q_{i}$. In other words, when measuring $F_{i}^{-1}(L_{i+1})$ we assign a measure of for vertices outside $Q_{i}$. It is easy to inductively argue that $\nu(Q_{i})\geq\Phi_{v}^{-i/t}$, so that $\nu(Q_{t})\geq 1/\Phi_{v}$ and thus $\mu(N(Q_{t}))\geq\frac{1}{2}$.

Intuitively, the set of cells in $L_{1},\ldots,L_{t}$ encode half of the $b_{i}$ bits and therefore must contain $\Omega(n)$ bits, which would imply the lower bound. Of course, $L_{1},\ldots,L_{t}$ depends upon the content of the table which depends upon the points in the data set. These dependencies can be handled by using a union bound over all the possible values of $L_{t}$: To see this, fix the values written in the cells $L_{1},\ldots,L_{t}$ to some string $\omega$ and sample the $n$ data set points from $U$ independently according to $\mu$. Let $A_{\omega}$ denote the event that when the value of the cells $L_{1},\ldots,L_{t}$ is $\omega$, an algorithm reading $\omega$ succeeds in guessing the $b_{i}$ bits for the data set points that fall in $N(Q_{t})$. Note that $Q_{t}$ depends only upon $\omega$ and that since the procedure of obtaining $L_{t}$ is deterministic, the locations of the cells obtained also depends only on $\omega$. Vertex expansion implies that $\mu(N(Q_{t}))\geq\frac{1}{2}$. Also, since $\mu$ is strongly independent and the algorithm is assumed to be correct, $\Pr[\cup_{\omega}A_{\omega}]\geq\frac{1}{2}$. By Chernoff’s bound, the probability that less than $n/8$ points fall in $N(Q_{t})$ is at most $2^{-n/8}$. Note that the $b_{i}$’s are chosen independently, therefore, for a fixed table, if $n/8$ points indeed fall in $N(Q_{t})$, then the probability that the sampled $b_{i}$’s match the output of the algorithms is $2^{-n/8}$. We conclude that $\Pr[A_{\omega}]\leq 2^{-n/8}+2^{-n/8}$. Now, let $K=1/\Phi_{v}^{1/t}$. There are $2^{Kmtw}$ ways of choosing $\omega$, so we must have $2^{1-n/8}2^{Kmtw}\geq\frac{1}{2}$. We conclude that $Kmtw\geq n/8$ which implies the theorem. ∎

2 Path Sampling

Let $\mu$ be strongly independent, and $\Phi_{v}$ be the vertex expansion with respect to $\mu,\nu$, then any data structure with a deterministic querying algorithm must satisfy $\frac{9m^{t}wt}{n}\geq\Phi_{v}(1/m^{t})$.

The proof is similar to that of Theorem 2.1 with a different choice of parameters. We present it here separately because the two approaches diverge in the next section when we deal with the randomized case. We use the cell sampling technique to select a set of cells from the tables, only this time, each phase we select a single cell from the table (as opposed to selecting $m\Phi_{v}^{-1/t}$ cells in Theorem 2.1). We call the approach of sampling a single cell from each table path sampling because we sample a single possible “query path” along the $t$ tables. We also observe that lower bounds based on this approach imply communication complexity lower bounds.

Now the contents of $L_{1},\ldots,L_{t}$ are $tw$ bits, and $\nu(Q_{t})\geq m^{-t}$ so that $\mu(N(Q_{t}))\geq\Phi_{v}(m^{-t})m^{-t}$. When fixing the bits of $L_{t}$ to be the string $\omega$, the expected number of data set points that fall in $N(Q_{t})$ is at least $n\Phi_{v}(m^{-t})m^{-t}$. Define $A_{\omega}$ as before and recall that we have $\Pr[\cup A_{\omega}]\geq\frac{1}{2}$. Let $Z_{\omega}$ be the number of data set points falling in $N(Q_{t})$. Chernoff’s bound implies that $\Pr[Z_{\omega}\leq\frac{1}{2}n\Phi_{v}(m^{-t})m^{-t}]\leq 2^{-\Phi_{v}(m^{-t})m^{-t}/8}$. Since the string $\omega$ now encodes $Z_{\omega}$ random bits, $\Pr[A_{\omega}]\leq 2^{-\Phi_{v}(m^{-t})m^{-t}/8}+2^{-\Phi_{v}(m^{-t})m^{-t}/2}$. There are $2^{tw}$ ways of choosing $\omega$, so we have $2^{tw}\cdot 2^{-\Phi_{v}(m^{-t})m^{-t}/8}\geq\frac{1}{2}$ which implies the theorem. ∎

Randomized Lower bounds

To prove lower bounds for randomized data structure, we will use Yao’s minimax theorem, and instead show a distribution over instances such that for some constant $\delta>0$, any deterministic $t$-probe data structure that succeeds with probability $(1-\delta)$ needs large space.

We consider the following randomized version of the Graph Neighbor Search (GNS) problem on a bipartite graph $G=(U,V,E)$. We are given a set of $n$ tuples $(x_{1},b_{1}),\ldots,(x_{n},b_{n})$, where $x_{i}\in U$ and $b_{i}\in\{0,1\}$ to preprocess into a data structure. Then given a query $y\in V$, the query algorithm makes $t$ probes into the data structure, and is expected to return $b_{i}$ if $x_{i}$ is the unique neighbor in $G$ of $y$ in $\{x_{1},\ldots,x_{n}\}$ (if there is no unique neighbor, any output is considered valid).

Let $G=(U,V,E)$ be a bipartite graph and let $e$ be a probability distribution over $E$. Let $\mu(u)=e(u,V)=\sum_{v\in V}e(u,v)$ be the induced distribution on $U$, and let $\nu(v)=e(U,v)$ be the induced distribution on $V$. For $x\in U$, we denote by $\nu_{x}$ the conditional distribution of the endpoints in $V$ of edges incident on $u$, i.e. $\nu_{x}(y)=e(x,y)/e(x,V)$.

Suppose we have a graph $G=(U,V,E)$, and the distribution $e$ on $E$. Then $(G,e)$ define a distribution over instances of GNS as follows. We select $n$ points $x_{1},\ldots,x_{n}$ independently from the distribution $\mu$ uniformly at random and pick $b_{1},\ldots,b_{n}$ independently and uniformly from $\{0,1\}$. This defines the database distribution. To generate the query, we pick an $i\in[n]$ uniformly at random, and sample $y$ independently from $\nu_{x_{i}}$.

We say the tuple $(G,e)$ satisfies $\gamma$-weak independence (WI) if $\Pr_{x,z\sim\mu,y\sim\nu_{x}}[(y,z)\in E]\leq\frac{\gamma}{n}$. In other words, WI ensures that with probability $(1-\gamma)$, for the instance generated as above, $x$ is indeed the unique neighbor in $G$ of $y$ in $\{x_{1},\ldots,x_{n}\}$.

We next define the notion of expansion that we use. Recall that the vertex expansion of a set $A\subseteq V$ in an unweighted graph $G$ is the ratio $\frac{|B|}{|A|}$, where $B=N(A)$ is the smallest set such that all edges incident on $A$ are captured by $B$, i.e. $|E(B,A)|=|E(U,A)|$. A relaxation of this definition, which we call $\gamma$-robust expansion, is the ratio $\frac{|B|}{|A|}$ where $B$ is now the smallest set that captures a $\gamma$ fraction of the edges incident on $A$, i.e. $e(B,A)\geq\gamma e(U,A)$. The following definition generalizes this notion to weighted bipartite graphs.

The $\gamma$-robust expansion of a set $A\subseteq V$ is defined as $\phi_{r}(A,\gamma)\stackrel{{\scriptstyle def}}{{=}}\min_{B\subseteq U:e(B,A)\geq\gamma e(U,A)}\mu(B)/\nu(A)$.

Let $w$ be an auxiliary weight function on $U$ with $\sum_{u\in U}w(u)=1$. The $\gamma$-robust expansion with respect to $w$ is defined as $\phi^{w}_{r}(A,\gamma)\stackrel{{\scriptstyle def}}{{=}}\min_{B\subseteq U:e(B,A)\geq\gamma e(U,A)}w(B)/\nu(A)$.

We say that $(G,e)$ has $(\beta,\gamma)$-robust expansion $\phi^{w}_{r}=\phi^{w}_{r}(\beta,\gamma)$ at least $K$ if for every subset $A\subseteq V$ such that $\nu(A)\leq\beta$, we have $\phi^{w}_{r}(A,\gamma)\geq K$.

For intuition, consider the setting where $G=(U,V,E)$ is derived naturally from an undirected graph $H=(V_{H},E_{H})$ by making two copies of $V_{H}$ and for each edge $(u,v)\in E_{H}$, placing the edges $(u_{1},v_{2})$ and $(v_{1},u_{2})$. Formally, $U_{G}=V_{H}\times\{1\},V_{G}=V_{H}\times\{2\}$, and $E_{H}=\{((u,1),(v,2))\in U_{G}\times V_{G}:(u,v)\in E_{H}\}$. Then for any set $A\subseteq V$, we have $\phi^{w}_{r}(A,1)=w(N(A))/\nu(A)$, which is the vertex expansion of $A$ in $H$ under $\nu$, for $w=\nu$. Similarly, if a set $A$ has conductance $e(A,A^{c})/e(A,V_{H})$ at most $1-\gamma$, then $e(A,A)\geq\gamma e(A,V)$ so that $\phi^{w}_{r}(A,\gamma)\leq w(A)/\nu(A)$. A similar correspondence holds for directed graphs.

A collection $A_{1},\ldots,A_{k}$ of disjoint subsets of $V$ is said to be $\beta$-sparse with respect to $(G,e)$ if $\max_{i}\nu(A_{i})\leq\beta$.

We now recall the notion of strong shattering.

Given $(G,e)$ and a collection $A_{1},\ldots,A_{k}$ of disjoint subsets of $V$, we say the collection $\{A_{i}\}_{i}$ $K$-strongly shatters a point $x\in V$ if $\max_{i}\nu_{x}(A_{i})\leq\frac{1}{K}$.

We shall in fact show our lower bounds using a weaker notion of shattering, which allows a small probability mass from $\nu_{x}$ to be in $A_{i}$’s with $\nu_{x}$ measure larger than $\frac{1}{K}$. For a real number $a$, let $(a)^{+}\stackrel{{\scriptstyle def}}{{=}}\max(a,0)$ denote the positive part of $x$. Note that strong shattering says that each of the $\nu_{x}(A_{i})$’s is at most $\frac{1}{K}$ so that $\sum_{i}(\nu_{x}(A_{i})-\frac{1}{K})^{+}$ is zero. We relax this condition.

Given $(G,e)$ and a collection $A_{1},\ldots,A_{k}$ of disjoint subsets of $V$, we say the collection $\{A_{i}\}_{i}$ $(K,\gamma)$-weakly shatters a point $x\in V$ if $\sum_{i}(\nu_{x}(A_{i})-\frac{1}{K})^{+}\leq\gamma\nu(\cup_{i}A_{i})$.

We say a tuple $(G,e)$ satisfies the $(K,\beta,\gamma)$-weak shattering (WS) property if for every $\beta$-sparse collection $A_{1},\ldots,A_{k}$ of disjoint subsets of $V$,

We record the following implication of weak shattering.

If $(G,e)$ satisfies $(K,\beta,\gamma)$-weak shattering property, then it also satisfies $(K/\lceil\frac{\beta^{\prime}}{\beta}\rceil,\beta^{\prime},\gamma)$-weak shattering for any $\beta^{\prime}>0$.

For $\beta^{\prime}<\beta$, there is nothing to prove since every $\beta^{\prime}$-sparse collection is also $\beta$-sparse. For $\beta^{\prime}>\beta$, we can arbitrarily break each set $A_{i}$ into $s=\lceil\frac{\beta^{\prime}}{\beta}\rceil$ pieces to derive a $\beta$-sparse collection; the shattering follows using the identity $(\sum_{i=1}^{s}a_{i})^{+}\geq\sum_{i=1}^{s}(a_{i})^{+}$. ∎

Let $A_{1},\ldots,A_{k}$ be a collection of disjoint subsets of $V$. Then for any $x\in V$, there is a measure $\hat{\nu}_{x}$ such that (a) $\nu_{x}$ dominates $\hat{\nu}_{x}$, i.e. $\hat{\nu}_{x}(A)\leq\nu_{x}(A)$ for all $A\subseteq V$, (b) $\hat{\nu}_{x}(A_{i})\leq\frac{1}{K}$ for all $i\in[k]$, and (c) If $x$ is $(K,\gamma)$-weakly shattered, then $\hat{\nu}_{x}(\cup A_{i})\geq\nu_{x}(\cup A_{i})-\gamma\nu(\cup A_{i})$.

Note that $\hat{\nu}$ is not necessarily a probability measure. Intuitively, $\hat{\nu}$ is a part of the measure $\nu$ that gets shattered. Such a measure can be obtained by shaving the mass on $y$ that fall in clusters with large $\nu_{x}$ mass.

For each $A_{i}$ with $\nu_{x}(A_{i})\geq\frac{1}{K}$, we set $\hat{\nu}_{x}(y)=\frac{\frac{1}{K}}{\nu_{x}(A_{i})}\nu_{x}(y)$ for each $y\in A_{i}$. $\hat{\nu}_{x}(y)$ is set $\nu_{x}(y)$ for the remaining $A_{i}$’s. The dominance is immediate, and the small loss property follows from the fact that $\hat{\nu}_{x}(A_{i})=\frac{1}{K}$ for every $A_{i}$ of the first type so that $\nu_{x}(A_{i})-\hat{\nu}_{x}(A_{i})=(\nu_{x}(A_{i})-\frac{1}{K})^{+}$. ∎

Finally, we shall use the following simple information-theoretic lemma:

Let $\delta<\frac{1}{4}$, and let $Enc:\{0,1\}^{n}\rightarrow\{0,1\}^{N}$ and $Dec:\{0,1\}^{N}\rightarrow\{0,1\}^{n}$ be functions such that $|b-Dec(Enc(b))|_{1}<\delta n$ with probability at least $\frac{1}{2}$ when $b$ is drawn at random. Then there exists a constant $r=r(\delta)>0$ such that $N\geq rn$, where $\lim_{\delta\rightarrow 0}r(\delta)=1$.

Let $C\subseteq\{0,1\}^{n}$ be a binary error correcting code with positive rate and minimum distance $2\delta<\frac{1}{2}$. Then for a random $v\in\{0,1\}^{n}$, $\hat{C_{v}}=\{b\in v+C:|Dec(Enc(b))-b|_{1}<\delta n\}$ has expected size $2^{rn}$ for an $r=r(\delta)>0$. Since the minimum distance of $\hat{C_{v}}$ is $2\delta n$, the values $Enc(b):b\in\hat{C_{v}}$ are all distinct, leading to the claim bound. ∎

The lemma can be extended to the setting where the encoder and the decoder share some randomness.

2 Main Result

The main result of this section is the following.

There exists an absolute constant $\gamma$ such that the following holds. Let $(G,e)$ satisfy $\gamma$-weak independence (WI). Then for $t\leq n^{\frac{1}{4}}$, any deterministic $t$-probe data structure for the distribution over GNS instances defined by $(G,e)$ that succeeds with probability $(1-\gamma)$ must satisfy

where $w$ is an arbitrary auxiliary weight function, and $t$ is $o(n^{\frac{1}{4}})$.

The theorem will follow from Lemma 3.11, and Theorems 3.12 and 3.22 that we prove next.

3 Expansion to Shattering

Let $A_{1},\ldots,A_{k}$ be a $\beta$-sparse collection of disjoint subsets of $V$. Then

for $K=\Phi_{r}(\beta,\frac{\gamma^{2}}{4})\gamma^{3}/16$

We will show that if $\Pr_{x\sim\mu}[x\;\;\;{\mbox{i}s}\;\;\;(K,\gamma){\mbox{-}weaklyshattered}]\leq(1-\gamma)$, then one of the $A_{i}$’s does not expand enough, thus deriving a contradiction.

Suppose that $\Pr_{x\sim\mu}[x\;\;\;{\mbox{i}s}\;\;\;(K,\gamma){\mbox{-}weaklyshattered}]\leq(1-\gamma)$. Thus for at least $\frac{\gamma}{2}$ fraction of $x$’s (drawn from $\mu$), $\nu_{x}(\cup A_{i})\leq\frac{2\eta}{\gamma}$ and yet $x$ is not $(K,\gamma)$-weakly shattered. Let $B$ be the set of such $x$’s. In other words, the set $B$ satisfies

For each $x\in B$, $\nu_{x}(\cup A_{i})\leq\frac{2\eta}{\gamma}$.

For each $x\in B$, $\sum_{i}(\nu_{x}(A_{i})-\frac{1}{K})^{+}\geq\gamma\eta$.

Construct an weighted graph $H_{0}$ on $B\times[k]$, where we put an edge between $(x,i)$ with weight $\mu(x)\nu_{x}(A_{i})=e(x,A_{i})$ if $\nu_{x}(A_{i})\geq\frac{1}{K}$. Thus $e_{H_{0}}(x,i)\leq e(x,A_{i})$ so that $e_{H_{0}}(B,i)\leq\nu(A_{i})$.

The (unweighted) degree of each node $x\in B$ in $H_{0}$ is at most $\frac{\nu_{x}(\cup A_{i})}{\frac{1}{K}}\leq 2\eta K/\gamma$, since each edge incident on $x$ in $H_{0}$ contributes at least $\frac{1}{K}$ to $\nu_{x}(\cup A_{i})$. Moreover, by the properties of $B$ above the total edge weight in $H_{0}$ $e_{H_{0}}(B,[k])$ is at least $(\frac{\gamma}{2})(\gamma\eta)=\frac{\gamma^{2}\eta}{2}$.

Let $H_{1}$ be the subgraph of $H_{0}$ formed by deleting all nodes $i\in[k]$ such that the total edge weight $e_{H_{0}}(B,i)$ incident on $i$ is at most $\frac{\gamma^{2}}{4}\nu(A_{i})$. The total edge weight deleted in the process is at most $\frac{\gamma^{2}}{4}\eta$ so that the total edge weight in $H_{1}$ $e_{H_{1}}(B,[k])$ is at least $\frac{\gamma^{2}\eta}{4}$.

Let $R\subseteq[k]$ be the set of nodes on the right surviving in $H_{1}$. Since each node in $B$ has unweighted degree at most $2\eta K/\gamma$ in $H_{1}$, $\sum_{i\in R}w(N_{H_{1}}(i))\leq(2\eta K/\gamma)\sum_{x\in B}w(x)\leq 2\eta K/\gamma$. On the other hand, $\sum_{i\in R}\nu(A_{i})$ is at least the total weight $e_{H_{1}}(B,R)$ of edges in $H_{1}$ which is lower bounded by $\frac{\gamma^{2}\eta}{4}$. It follows by an averaging argument that there is a node $i^{*}\in S$ such that

Let $B_{i^{*}}=N_{H_{1}}(i^{*})$. Since $i^{*}\in R$, we have $e(B_{i^{*}},A_{i^{*}})\geq\frac{\gamma^{2}}{4}\nu(A_{i^{*}})$. Since $\nu(A_{i^{*}})\leq\beta$ by assumption,

which contradicts the definition of $K$. ∎

4 Path Sampling

In this section, we show the following theorem

There exists a constant $\gamma>0$ such that the following holds. Let $(G,e)$ satisfy $\gamma$-weak independence (WI) and $(K,\frac{1}{m^{t}},\frac{\gamma}{t})$-weak shattering property. Then for $t\leq n^{\frac{1}{4}}$, any deterministic $t$-probe data structure for the distribution over GNS instances defined by $(G,e)$ that succeeds with probability $(1-\gamma)$ must use space $m$ at least $\Omega((nK^{2}/w)^{\frac{1}{t}})$.

Proof Sketch: Suppose that a datastructure with $m<(\gamma^{6}nK/4t^{4}w)^{\frac{1}{t}}$ exists that succeeds with probability $(1-\gamma^{3})$. We use it construct a randomized encoding and decoding algorithm for a random binary vector $b\in\{0,1\}^{n}$. We sample $x_{1},\ldots,x_{n}$ from $\mu$, and build the data structure for the database $(x_{1},b_{1}),\ldots,(x_{n},b_{n})$ to get $t$ tables $T_{1},\ldots,T_{t}$ where each $T_{i}$ contains $m$ cells of $w$ bits each.