Re: high-dimensional knn-GIST tests (was Re: Cube extension kNN support)

On Thu, Oct 24, 2013 at 3:50 AM, Gordon Mohr <gojomo-pgsql(at)xavvy(dot)com> wrote:

> On 9/22/13 4:38 PM, Stas Kelvich wrote:
>
>> Hello, hackers.
>>
>> Here is the patch that introduces kNN search for cubes with
>> euclidean, taxicab and chebyshev distances.
>>
>
> Thanks for this! I decided to give the patch a try at the bleeding edge
> with some high-dimensional vectors, specifically the 1.4 million
> 1000-dimensional Freebase entity vectors from the Google 'word2vec' project:
>

I believe the curse of dimensionality is affecting you here. I think it is
impossible to get an improvement over sequential scan for 1000 dimensional
vectors. Read here:

http://en.wikipedia.org/wiki/Curse_of_dimensionality#k-nearest_neighbor_classification

Regards
Marcin Mańk