World's most popular travel blog for travel bloggers.

# Approximate Nearest Neighbour Problem in Spherical Setting

, ,
Problem Detail:

There has been significant literature in solving the (Approximate) Nearest Neighbour Problem in the spherical setting in the $\mathbb{R}^n$ using Angular and Spherical LSH and other lattice sieving techniques. A proper definition of the problem is found in the image below. (The problem definition is borrowed from Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing by Laarhoven and Weger 2015. Here is the IACR page for the paper. )

(Refer to Sieving for shortest vectors in lattices using angular locality-sensitive hashing by Laarhoven 2015. The link is in the comments.)

I was curious if there is a way to have a similar spherical setting for the approximate NN problem for the finite field $\mathbb{Z}_2^n$. Particularly, I was wondering if there was a sphere definition relevant to $\mathbb{Z}_2^n$ that could be analogical or atleast very similar to the one in Definition 4. The one in definition 4 allows entire lattices to be embedded on the sphere i.e. $P$ is a lattice. The proposed distance measure could either be the $l_2$ norm or the hamming distance. It does not seem that it can be simply translated into finite fields.

I apologize if this is a naive question or does not make sense because I am a first time undergraduate researcher who is not very familiar with this forum and the level of questions asked here.

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.