<p>Before I get to answers, I would like to point out that when you have a program that uses a large set of numbers you should always use <code>numpy.array</code> from <a href="https://numpy.org/" rel="noreferrer">numpy library</a> to store that kind of data. I don't know what version of Python, <a href="https://scikit-learn.org" rel="noreferrer">scikit-learn</a>, and <a href="https://www.scipy.org/" rel="noreferrer">SciPy</a> are you using, but I am using Python 3.7.3, scikit-learn 0.21.3, and SciPy 1.3.0. When I ran your code to compare build-times, I got <code>AttributeError: 'list' object has no attribute 'size'</code>. This error is saying that list <code>listOfRandom2DPoints</code> has no attribute <code>size</code>. The problem is that <code>sklearn.neighbors.KDTree</code> expects <code>numpy.array</code> which has attribute <code>size</code>. Class <code>scipy.spatial.KDTree</code> works with Python lists but as you can see in the <a href="https://github.com/scipy/scipy/blob/v1.4.1/scipy/spatial/kdtree.py#L241-L942" rel="noreferrer">source code of <code>__init__</code> method of class <code>scipy.spatial.KDTree</code></a>, first line is <code>self.data = np.asarray(data)</code>, which means that data will be converted to <code>numpy.array</code>.</p>

<p>Because of this, I cahanged your lines:</p>

<pre><code>from random import randint
listOfRandom2DPoints = [ [randint(0,dim),randint(0,dim)] for x in range(length)]
</code></pre>

<p>to:</p>

<pre><code>import numpy as np
ListOfRandom2DPoints = np.random.randint(0, dim, size=(length, 2))
</code></pre>

<p>(This change doesn't affect speed comparisons because change is made in setup code.)</p>

<p>Now answers on your questions:</p>

<ol>
<li><p>Like you said scikit-learn seems to beet SciPy for the build time. The reason why this happens isn't that scikit-learn has a faster algorithm, but <code>sklearn.neighbors.KDTree</code> is implemented in <a href="https://cython.org/" rel="noreferrer">Cython</a> (<a href="https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/neighbors/_kd_tree.pyx" rel="noreferrer">link to source code</a>), and <code>scipy.spatial.KDTree</code> is written in pure Python code (<a href="https://github.com/scipy/scipy/blob/v1.4.1/scipy/spatial/kdtree.py#L185-L942" rel="noreferrer">link to source code</a>).</p>

<p>(If you don't know what is Cython, an oversimplified explanation would
be that Cython makes possible writing C code in Python and main
reason for doing that is that C is much faster than Python)</p>

<p>SciPy library also has implementation in Cython <code>scipy.spatial.cKDTree</code> (<a href="https://github.com/scipy/scipy/blob/v1.4.1/scipy/spatial/ckdtree.pyx#L401-L1525" rel="noreferrer">link to source code</a>), it works the same as <code>scipy.spatial.KDTree</code> and if you compare build times of <code>sklearn.neighbors.KDTree</code> and <code>scipy.spatial.cKDTree</code>:</p>

<pre><code>timeit.timeit('scipy.spatial.cKDTree(npListOfRandom2DPoints, leafsize=20)', setup=setup, number=nTimes)
timeit.timeit('sklearn.neighbors.KDTree(npListOfRandom2DPoints, leaf_size=20)', setup=setup, number=nTimes)
</code></pre>

<p>Build times are very similar, and when I ran the code, <code>scipy.spatial.cKDTree</code> was a little bit (around 20%) faster.</p>

<p>With query times situation is very similar, <code>scipy.spatial.KDTree</code> (pure Python implementation) is about ten times slower than <code>sklearn.neighbors.KDTree</code> (Cython implementation) and <code>scipy.spatial.cKDTree</code> (Cython implementation) is aproximatly as fast as <code>sklearn.neighbors.KDTree</code>. I have tested query times up to N = 10000000, and got the same result as you. Query times stay the same regardless of N (meaning query time for <code>scipy.spatial.KDTree</code> is same for N = 1000 and N = 1000000, and the same thing for query times for<code>sklearn.neighbors.KDTree</code> and <code>scipy.spatial.cKDTree</code>). That is because query (search) time complexity is O(logN) and even for N = 1000000, logN is very small so the difference is too small to measure.</p></li>
<li><p>Build algorithm of <code>sklearn.neighbors.KDTree</code> (<code>__init__</code> method of class) has time complexity of O(KNlogN) (<a href="https://scikit-learn.org/stable/modules/neighbors.html#nearest-neighbor-algorithms" rel="noreferrer">about scikit-learn Nearest Neighbor Algorithms</a>) so in your case it would be O(2NlogN) which is practically O(NlogN). Based on very similar build times of <code>sklearn.neighbors.KDTree</code> and <code>scipy.spatial.cKDTree</code> I assume that the build algorithm of <code>scipy.spatial.cKDTree</code> also has time complexity of O(NlogN). I am no expert on nearest neighbor search algorithms, but based on some online search, I would say that for low-dimensional nearest neighbor search algorithms this as fast as it can be. If you go to  <a href="https://en.wikipedia.org/wiki/Nearest_neighbor_search" rel="noreferrer">nearest neighbor search Wikipedia page</a> you will see that there are <a href="https://en.wikipedia.org/wiki/Nearest_neighbor_search#Exact_methods" rel="noreferrer">exact methods</a> and <a href="https://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximation_methods" rel="noreferrer">approximation methods</a>. <a href="https://en.wikipedia.org/wiki/K-d_tree" rel="noreferrer">k-d tree</a> is exact method, it is subtype of <a href="https://en.wikipedia.org/wiki/Nearest_neighbor_search#Space_partitioning" rel="noreferrer">space partitioning methods</a>. Of all space partitioning methods (only fast exact methods for nearest neighbor search based on Wikipedia page), k-d tree is the best method in the case of low-dimensional Euclidean space for nearest neighbor search in static context (there isn't a lot of insertions and deletions). Also if you look at approximation methods under <a href="https://en.wikipedia.org/wiki/Nearest_neighbor_search#Greedy_search_in_proximity_neighborhood_graphs" rel="noreferrer">greedy search in proximity neighborhood graphs</a> you will see "Proximity graph methods are considered the current state-of-the-art for the approximate nearest neighbors search." When you look at the research article that is cited for this method (<a href="https://arxiv.org/abs/1603.09320" rel="noreferrer">Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs</a>) you can see that this method has time complexity of O(NlogN). This means that for low-dimensional spaces k-d tree (exact method) is as fast as approximation methods. For now, we have compared build (construction) time complexity of structures that are used for nearest neighbor searches. All these algorithms have search (query) time complexity of O(logN). So best that we can get is build complexity of O(NlogN) and query complexity of O(logN) which is what we have in k-d tree method. So based on my research I would say that k-d tree is the best structure for low-dimensional nearest neighbor searches. </p>

<p>(I think if there was a better (faster) method to do nearest neighbor search, than scikit-learn and SciPy would have implemented that method. Also from a theoretical standpoint, knowing that fastest sorting algorithms have time complexity of O(NlogN), it would be quite surprising to have nearest neighbor search build algorithm with time complexity less than O(NlogN).)</p></li>
<li><p>Like I said you are comparing <code>sklearn.neighbors.KDTree</code> with Cython implementation and <code>scipy.spatial.KDTree</code> with pure Python implementation. In theory <code>sklearn.neighbors.KDTree</code> should be faster than <code>scipy.spatial.KDTree</code>, I compared these up to 1000000 and they seem to get closer at large N. For N = 100, <code>scipy.spatial.KDTree</code> is about 10 times slower than <code>sklearn.neighbors.KDTree</code> and for N = 1000000, <code>scipy.spatial.KDTree</code> is about twice as slow as <code>sklearn.neighbors.KDTree</code>. I am not sure why is this happening, but I suspect that for big N, memory becomes a bigger problem than the number of operations.</p>

<p>I checked re-build time also up to 1000000 and it does increase linearly and that is because the duration of function <code>pickle.loads</code> is linearly proportional to the size of the loading object.</p></li>
<li><p>For me, pickling of <code>sklearn.neighbors.KDTree</code>, <code>scipy.spatial.KDTree</code>, and <code>scipy.spatial.cKDTree</code> works so I can't reproduce your error. I am guessing that the problem is that you have an older version of SciPy so updating SciPy to the newest version should fix this problem.</p>

<p>(If you need more help on this problem you should add some more info to your question. What are your Python and SciPy versions, exact code to reproduce this error, and full error message?)</p></li>
</ol>
Speed of K-Nearest-Neighbour build/search with SciKit-learn and SciPy
<p>I have a large set of 2-dimensional points and want to be able to rapidly query the set for the k-Nearest-Neighbours of any point in the 2-d space. Since it's low-dimensional, a KD-Tree seems like a good way to go about it. My initial data set will only be updated very rarely, so the time to query a point should be more important to me than the build-time. However, each time I run the program I will need to re-load the object, so I also need a structure that can be saved and reloaded swiftly.</p>

<p>The two choices readily available are the KDTree structures in SciPy and in SciKit-learn. Below I profile the two of these for build-speed and query-speed across a large range of list lengths. I also pickle the SciKit-learn structure and show the time to re-load the object from the pickle. These are compared in a graph, and the code used to generate the timings is included below.</p>

<p>As I show in the graph, loading from a pickle is faster than building it from scratch by half an order of magnitude for large N, showing that the KDTree is suitable for my use case (ie. frequent re-loads but infrequent re-builds).</p>

<p><img src="https://i.stack.imgur.com/YFDJj.png" alt="Comparing build-, reload- and query-time of two KD-Tree structures"></p>

<p>Code to compare build-times:</p>

<pre><code># Profiling the building time for the two KD-tree structures and re-loading from a pickle
import math, timeit, pickle, sklearn.neighbors

the_lengths = [100, 1000, 10000, 100000, 1000000]

theSciPyBuildTime = []
theSklBuildTime = []
theRebuildTime = []

for length in the_lengths:
    dim = 5*int(math.sqrt(length))
    nTimes = 50
    from random import randint
    listOfRandom2DPoints = [ [randint(0,dim),randint(0,dim)] for x in range(length)]

    setup = """import scipy.spatial
import sklearn.neighbors
length = """ + str(length) + """
dim = """ + str(dim) + """
from random import randint
listOfRandom2DPoints = [ [randint(0,dim),randint(0,dim)] for x in range(length)]"""

    theSciPyBuildTime.append( timeit.timeit('scipy.spatial.KDTree(listOfRandom2DPoints, leafsize=20)', setup=setup, number=nTimes)/nTimes )
    theSklBuildTime.append( timeit.timeit('sklearn.neighbors.KDTree(listOfRandom2DPoints, leaf_size=20)', setup=setup, number=nTimes)/nTimes )

    theTreeSkl = sklearn.neighbors.KDTree(listOfRandom2DPoints, leaf_size=20, metric='euclidean')
    f = open('temp.pkl','w')
    temp = pickle.dumps(theTreeSkl)

    theRebuildTime.append( timeit.timeit('pickle.loads(temp)', 'from __main__ import pickle,temp', number=nTimes)/nTimes )
</code></pre>

<p>Code to compare query-times:</p>

<pre><code># Profiling the query time for the two KD-tree structures
import scipy.spatial, sklearn.neighbors

the_lengths = [100, 1000, 10000, 100000, 1000000, 10000000]

theSciPyQueryTime = []
theSklQueryTime = []

for length in the_lengths:
    dim = 5*int(math.sqrt(length))
    nTimes = 50
    listOfRandom2DPoints = [ [randint(0,dim),randint(0,dim)] for x in range(length)]

    setup = """from __main__ import sciPiTree,sklTree
from random import randint
length = """ + str(length) + """
randPoint = [randint(0,""" + str(dim) + """),randint(0,""" + str(dim) + """)]""" 

    sciPiTree = scipy.spatial.KDTree(listOfRandom2DPoints, leafsize=20)
    sklTree = sklearn.neighbors.KDTree(listOfRandom2DPoints, leaf_size=20)

    theSciPyQueryTime.append( timeit.timeit('sciPiTree.query(randPoint,10)', setup=setup, number=nTimes)/nTimes )
    theSklQueryTime.append( timeit.timeit('sklTree.query(randPoint,10)', setup=setup, number=nTimes)/nTimes )
</code></pre>

<p>&nbsp;</p>

<p>Questions:</p>

<ol>
<li><p><strong>The Result</strong>: Although they're getting closer for very large N,
SciKit-learn seems to beat SciPy for both build time and query time.
Have other people found this?</p></li>
<li><p><strong>The Maths</strong>: Are there any better structures available for this?
I'm only working in a 2D space (although the data will be quite
dense so brute force is out), is there a better structure for
low-dimensional kNN searches?</p></li>
<li><p><strong>The Speed</strong>: It looks like the build-time for the two approaches is
getting closer at large N but my computer gave up on me - can anyone
verify this for me for larger N?! Thanks!! Does re-build time
continue to increase roughly linearly as well?</p></li>
<li><p><strong>Practicalities</strong>: The SciPy KDTree won't pickle. As reported in
<a href="https://stackoverflow.com/questions/5773216/saving-kdtree-object-in-python">this post</a>, I'm given the following error "PicklingError: Can't
pickle : it's not found as
scipy.spatial.kdtree.innernode" - I think this is due to it being a
nested structure. According to an answer reported in <a href="https://stackoverflow.com/questions/1947904/how-can-i-pickle-a-nested-class-in-python">this post</a>,
nested structures can be pickled with dill. However, dill gives me
the same error - why is this?</p></li>
</ol>