@TechReport{Kybic-CAK-2010-40,
  IS = { zkontrolovano 02 Feb 2011 },
  UPDATE  = { 2011-01-14 },
 author =       {Jan Kybic and Ivan Vnu{\v c}ko},
 title =        {Approximate Best Bin First k-d Tree All Nearest Neighbor
                 Search with Incremental Updates},
 institution =  {Department of Cybernetics, Faculty of Electrical Engineering,
                 Czech Technical University},
 address =      {Prague, Czech Republic},
 year =         {2010},
 month =        {July},
 type =         {Research Report},
 number =       {K333--40/10, CTU--CMP--2010--10},
 issn =	        {1213-2365},
 pages =        {27},
 figures =      {4},
 authorship =   {80-20},
 psurl =        {[Kybic-TR-2010-10.pdf]},
 url =        {ftp://cmp.felk.cvut.cz/pub/cmp/articles/kybic/Kybic-TR-2010-10.pdf},
 project =      {1M0567},
 annote =       {We describe an approximate algorithm to find all
   nearest neighbors (NN) for a~set of points in moderate to
   high-dimensional spaces. Although the method is generally
   applicable, it is tailored to our main application, which is
   a~NN-based entropy estimation for an image similarity criterion for
   image registration. Our algorithm is unique for having
   simultaneously the following features: (i) It is usable for
   millions of data points in several tens of dimensions. (ii) It can
   deal with multiple points. (iii) It offers a~speedup of the all-NN
   search task with respect to repeating a~NN search for each query
   point. (iv) It allows exact as well as approximate search when
   reduced search time is needed. (v) The search tree can be updated
   incrementally when the change of values of the data points is
   small. The method is based on creating a~balanced k-d tree, which
   is then searched using the best-bin-first strategy. The tree nodes
   contain both tight and loose bounding boxes. The method is
   presented using NN defined in an l_infinity norm but can be applied
   to the $l_2$ norm, too.},
 keywords =     {nearest neighbor search, post-office problem, closest-point
                 queries, approximation algorithms, entropy estimation, k-d
                 tree, incremental update},
 comment =      {I need to shorten the manuscript to submit it as a journal
                 article and I want to keep this longer version with more
                 details available.},
}