  In this paper, we study the two choice balls and bins process when balls are
not allowed to choose any two random bins, but only bins that are connected by
an edge in an underlying graph. We show that for $n$ balls and $n$ bins, if the
graph is almost regular with degree $n^\epsilon$, where $\epsilon$ is not too
small, the previous bounds on the maximum load continue to hold. Precisely, the
maximum load is $\log \log n + O(1/\epsilon) + O(1)$. For general
$\Delta$-regular graphs, we show that the maximum load is $\log\log n +
O(\frac{\log n}{\log (\Delta/\log^4 n)}) + O(1)$ and also provide an almost
matching lower bound of $\log \log n + \frac{\log n}{\log (\Delta \log n)}$.
  V{\"o}cking [Voc99] showed that the maximum bin size with $d$ choice load
balancing can be further improved to $O(\log\log n /d)$ by breaking ties to the
left. This requires $d$ random bin choices. We show that such bounds can be
achieved by making only two random accesses and querying $d/2$ contiguous bins
in each access. By grouping a sequence of $n$ bins into $2n/d$ groups, each of
$d/2$ consecutive bins, if each ball chooses two groups at random and inserts
the new ball into the least-loaded bin in the lesser loaded group, then the
maximum load is $O(\log\log n/d)$ with high probability.
