Approximate Nearest Neighbour Problem in Spherical Setting
There is a reasonable distance metric on $\mathbb{Z}_2^n$ that allows one to define something that can be viewed as the analog of a sphere.  In particular, use the Hamming distance.  Then given any vector $c \in \mathbb{Z}_2^n$ and any positive integer $k$, the set $\{x \in \mathbb{Z}_2^n : d(x,c) \le k\}$ can be a ball centered at $c$ with radius $k$.  You could even call it a Hamming ball.

You can also define a version of nearest-neighbor search, using the Hamming distance on $\mathbb{Z}_2^n$ instead of the ordinary Euclidean distance on $\mathbb{R}^n$.  Everything carries over.  The algorithms/solutions may need to be different, though.  For approaches to this problem, you could look at metric trees and locality sensitive hashing.