search

tzaeschke / tinspin-indexes

Spatial index library with R*Tree, STR-Tree, Quadtree, CritBit, KD-Tree, CoverTree and PH-Tree
http://www.tinspin.org
Apache License 2.0
111 stars 24 forks source link

CritbitKD returning wrong results #7

Closed tzaeschke closed 7 years ago

tzaeschke commented 7 years ago

CritBitKD may rarely return wrong results of data is dense, i.e. if two data points differ exactly at a depth of 64 bit. CritBit would then store unnecessarily the first identical 64bit a infix, which would confuse the query iterator when rebuilding the keys during traversal.

See TestCritBitKD.test64_3_10000_queries.

tzaeschke commented 7 years ago

Fixed in f3c5b67bf4654d7bee64f38bbd424c94d1eacdda