1
$\begingroup$

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. enter image description here (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.

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$ – D.W. Jul 21 '16 at 17:50
  • 1
    $\begingroup$ Can you provide a self-contained definition of terms? What is the "spherical setting"? What do you mean by "the lattice" -- which lattice? Can you define what is meant by $L$? What would the definition of a spherical setting or a sphere even be for finite fields? Finite fields don't have a distance metric; they're different from $\mathbb{R}$. So I suspect the answer will be no, but it'd help to see a self-contained question before I form a definite answer. $\endgroup$ – D.W. Jul 21 '16 at 17:51
  • $\begingroup$ Thank You for the corrections you suggested. I hope the question is self-contained now and any other requests for corrections are welcomed. Since I could not provide three links for the lack of enough reputation, the link for the second paper is here : eprint.iacr.org/2014/744 $\endgroup$ – sidhant Jul 21 '16 at 18:15
  • $\begingroup$ Thanks for the edits; that helps. Second question: Can you clarify what you're looking for? You say you want "a similar spherical setting", but can you clarify what you're looking for? Are you asking whether there is a definition of a sphere that is relevant to $\mathbb{Z}_2^n$? Are you asking for some way to formalize a variant of Definition 4, that will be suitable for $\mathbb{Z}_2^n$ (i.e., a problem definition)? Are you asking for a problem definition and an algorithm for it that comes with provable performance guarantees? $\endgroup$ – D.W. Jul 22 '16 at 1:53
  • 1
    $\begingroup$ I hope this question makes some semblance of sense now. Sorry for all the earlier problems. $\endgroup$ – sidhant Jul 27 '16 at 16:48
0
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.