[MRG] Locality Sensitive Hashing for approximate nearest neighbor search(GSoC)

Please do not go (back!) to the string representation route.

We need the test suite you refer to anyway; given that, maintaining an int
based representation is reasonable despite the ambiguities and platform
differences. The space (and less so, time) efficiencies of using int-based
representations are significant (~4x for the index, which matters in the
not-too-high-dimension regime). A variable hash length is not practically a
benefit: 32bits is quite a lot for in-memory applications, and still very
compact. A byte array approach might be reasonable as it is compact, the
speed cost is less a concern.

On Wed, Oct 22, 2014 at 12:11 PM, jnothman <notifications@github.com> wrote:

> In sklearn/neighbors/approximate.py:
>
> > +__all__ = ["LSHForest"]
> > +
> > +
> > +def _find_matching_indices(sorted_array, item, left_mask, right_mask):
> > +    """Finds indices in sorted array of integers.
> > +
> > +    Most significant h bits in the binary representations of the
> > +    integers are matched with the items' most significant h bits.
> > +    """
> > +    left_index = np.searchsorted(sorted_array, item & left_mask)
> > +    right_index = np.searchsorted(sorted_array, item | right_mask,
> > +                                  side='right')
> > +    return np.arange(left_index, right_index)
> > +
> > +
> > +def _find_longest_prefix_match(bit_string_array, query, hash_size,
>
> For the sake of minimising the work necessary to merge this, I have
> changed my mind; we can leave a rewrite of this code till later, as
> currently there are no operations that should be *broken* by this quirky
> behaviour, although I still think it's a bad idea to leave it in the code
> in the long term.
>
> Where I found it problematic was in trying to rewrite the function to use
> only two lookups in bit_string_array. In doing so you have to have a
> function that just calculates the shared prefix length of two ints, which
> is of course byte-order dependent. I ran into trouble.
>
> So I think what we need are:
>
>    - tests of this private method that confirm it does what it is meant
>    to, whether the arrays passed in are of dtype '>u4' or of '<u4'.
>    - a comment pointing to the numpy issue
>
> (If you'd rather go down the string representation path, which again
> benefits from allowing a variable hash size and discarding the masks
> arrays, this is still an option, and I'm happy to submit a patch for the
> code, but tests are still needed.)
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/scikit-learn/scikit-learn/pull/3304/files#r19204157>.
>



-- 
Daniel Vainsencher