title: pyflann returns negative indices for nearest neighbours on ubuntu when passed 'kmeans' parameter
body: <p><strong>Goal</strong></p>
  
  <p>I'm trying to get: </p>
  
  <ol>
  <li>The approximate nearest neighbours library FLANN, and </li>
  <li>The python binding pyflann</li>
  </ol>
  
  <p>working correctly on an AWS ec2 instance, which is running Ubuntu. My aim is to compare FLANN with other ANN implementations, like ANNOY and the scikit-learn ANN implementation, to see which one works best for the the company I work for. We are working with millions of vectors of dimension ~ 500. </p>
  
  <p>For this reason, it's important to me to get FLANN itself working, rather than receiving suggestions for alternative ANN implementations. I'm aware of the nice <a href="http://radimrehurek.com/2013/12/performance-shootout-of-nearest-neighbours-contestants/" rel="nofollow">blogpost</a>, of Radim Rehurek, but we have a concrete data set on which we'd like to check performance of various ANN algorithms, so his blog doesn't remove the need for us to benchmark on our own data.</p>
  
  <p><strong>Problem</strong></p>
  
  <p>I've succeeded in installing versions of both flann and pyflann, but pyflann returns nonsense results when asked to create an ANN index using the 'kmeans' parameter. For example, consider the following python code and its output:</p>
  
  <pre><code>&gt;&gt;&gt; from pyflann import *
  &gt;&gt;&gt; from numpy import *
  &gt;&gt;&gt; from numpy.random import *
  &gt;&gt;&gt; dataset = rand(1000, 100)
  &gt;&gt;&gt; testset = rand(10, 100)
  &gt;&gt;&gt; flann = FLANN()
  &gt;&gt;&gt; result,dists = flann.nn(dataset,testset, 5, algorithm="kmeans")
  &gt;&gt;&gt; print result
  [[ -278697864       32687  -278697864       32687  1677721700]
   [   40632322           6    16778074  1677721700           9]
   [     285184  1509950821          12       25600  1811940196]
   [         15   426661632   140837888          18    16801138]
   [   16779610          21    23986182   107304960          24]
   [-2080373660   190447616          27  1694501978   224002059]
   [         30  1694502490   257556491          33 -2080373404]
   [  207224832          36  1509949572          49           0]
   [   43668848           0  -278698024       32687     8650760]
   [    1006080  1392509796  1397948499         208           0]]
  &gt;&gt;&gt;
  </code></pre>
  
  <p>Since the line: </p>
  
  <pre><code>result,dists = flann.nn(dataset,testset, 5, algorithm="kmeans")
  </code></pre>
  
  <p>is asking for five neighbours for each of the ten 100-dimensional vectors in "testset", the outputted array has the correct dimension: the ten rows correspond to the ten vectors in "testset", and each row has length five, reflecting the fact that I asked for five neighbours. However, the values of the entries cannot be correct, because some are negative, and many are outside the range 0 -- 999, the range of indices of possible nearest neighbours. For comparison, here is the output of my terminal using almost the same code as above, changing only "kmeans" to "kdtree":</p>
  
  <pre><code>&gt;&gt;&gt; from pyflann import *
  &gt;&gt;&gt; from numpy import *
  &gt;&gt;&gt; from numpy.random import *
  &gt;&gt;&gt; dataset = rand(1000, 100)
  &gt;&gt;&gt; testset = rand(10, 100)
  &gt;&gt;&gt; flann = FLANN()
  &gt;&gt;&gt; result,dists = flann.nn(dataset,testset, 5, algorithm="kdtree")
  &gt;&gt;&gt; print result
  [[189 363 397 723 685]
   [400 952 892 332 477]
   [560 959 295 591 394]
   [596 652 250  43 448]
   [498 706 543 761 323]
   [334 974 591 620 766]
   [435 386  58 962 421]
   [234 301 189 355 191]
   [857 133 420 544 612]
   [978 995 439 648 627]]
  &gt;&gt;&gt;
  </code></pre>
  
  <p>This time, all entries are nonnegative integers between 0 and 999, as expected. Of course, the data is generated randomly, so results will vary, but using the "kmeans" argument produces consistently silly results, whereas "kdtree" produces consistently sensible ones. </p>
  
  <p><strong>Software and OS details</strong></p>
  
  <p><strong>(0)</strong> Ubuntu distro: </p>
  
  <p>Ubuntu 14.04 LTS</p>
  
  <p><strong>(1)</strong> libflann-dev:</p>
  
  <p>Typing: </p>
  
  <p>sudo aptitude show libflann-dev</p>
  
  <p>Produces: </p>
  
  <pre><code>Package: libflann-dev
  State: installed
  Automatically installed: no
  Version: 1.8.4-3
  Priority: optional
  Section: universe/libdevel
  Maintainer: Ubuntu Developers &lt;ubuntu-devel-discuss@lists.ubuntu.com&gt;
  Architecture: amd64
  Uncompressed Size: 11.2 M
  Depends: libflann1.8 (= 1.8.4-3)
  Description: Fast Library for Approximate Nearest Neighbors - development
   FLANN is a library for performing fast approximate nearest neighbor searches in high dimensional spaces. It contains a collection of algorithms found to work best for
   nearest neighbor search and a system for automatically choosing the best algorithm and optimum parameters depending on the dataset.
  
   This package contains development files needed to build FLANN applications.
  Homepage: http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN
  </code></pre>
  
  <p><strong>(2)</strong> Typing:</p>
  
  <p>sudo aptitude show python</p>
  
  <p>produces:</p>
  
  <pre><code>Package: python
  State: installed
  Automatically installed: no
  Multi-Arch: allowed
  Version: 2.7.5-5ubuntu3
  Priority: optional
  Section: python
  Maintainer: Ubuntu Developers &lt;ubuntu-devel-discuss@lists.ubuntu.com&gt;
  Architecture: amd64
  Uncompressed Size: 687 k
  Depends: python2.7 (&gt;= 2.7.5-1~), python-minimal (= 2.7.5-5ubuntu3), libpython-stdlib (= 2.7.5-5ubuntu3)
  Suggests: python-doc (= 2.7.5-5ubuntu3), python-tk (&gt;= 2.7.5-1~)
  Conflicts: python-central (&lt; 0.5.5)
  Breaks: python-bz2 (&lt; 1.1-8), python-csv (&lt; 1.0-4), python-email (&lt; 2.5.5-3), update-manager-core (&lt; 0.200.5-2)
  Replaces: python-dev (&lt; 2.6.5-2)
  Provides: python-ctypes, python-email, python-importlib, python-profiler, python-wsgiref, python:any
  Description: interactive high-level object-oriented language (default version)
   Python, the high-level, interactive object oriented language, includes an extensive class library with lots of goodies for network programming, system administration,
   sounds and graphics.
  
   This package is a dependency package, which depends on Debian's default Python version (currently v2.7).
  Homepage: http://www.python.org/
  </code></pre>
  
  <p><strong>Method of installation</strong></p>
  
  <p>I first attempted to install FLANN with the command:</p>
  
  <pre><code>sudo apt-get install libflann1.8
  </code></pre>
  
  <p>after installing pyflann with:</p>
  
  <pre><code>sudo pip install -e git+git://github.com/Captricity/pyflann.git#egg=pyflann,
  </code></pre>
  
  <p>I typed: </p>
  
  <pre><code>python -c 'import pyflann'
  </code></pre>
  
  <p>and received the error message:</p>
  
  <pre><code>Traceback (most recent call last):
    File "&lt;string&gt;", line 1, in &lt;module&gt;
    File "/mnt/working/src/pyflann/pyflann/__init__.py", line 27, in &lt;module&gt;
      from index import *
    File "/mnt/working/src/pyflann/pyflann/index.py", line 27, in &lt;module&gt;
      from bindings.flann_ctypes import *
    File "/mnt/working/src/pyflann/pyflann/bindings/__init__.py", line 30, in &lt;module&gt;
      from flann_ctypes import *
    File "/mnt/working/src/pyflann/pyflann/bindings/flann_ctypes.py", line 169, in &lt;module&gt;
      raise ImportError('Cannot load dynamic library. Did you compile FLANN?')
  ImportError: Cannot load dynamic library. Did you compile FLANN?
  </code></pre>
  
  <p>Then, on a fresh ec2 instance, I typed: </p>
  
  <pre><code>sudo apt-get install libflann-dev
  sudo pip install -e git+git://github.com/Captricity/pyflann.git#egg=pyflann
  </code></pre>
  
  <p>and ran</p>
  
  <pre><code>python -c 'import pyflann'
  </code></pre>
  
  <p>without complaint. However, I have the "kmeans" problem described above.</p>
  
  <p><strong>Note</strong></p>
  
  <p>I've succeded in installing FLANN and pyflann on my MacBookPro, and everything works fine -- even using "kmeans" as a nearest neighbours query argument produces sensible results. </p>