Why Trees Don't Work (for d > 10)
[Weber and Blott]
derive some results on average performance of kNN search:
- (degeneration)
the complexity of searching via a partitioning scheme tends
to O(N) for sufficiently large d
- (complexity)
for every partitioning scheme, there exists some d
such that all blocks are accessed if dimensionality exceeds d
- (performance)
most data- and space-partitioning schemes perform worse than
sequential scan by the time d=10
|
![[prev]](icon/prev.gif){kind=icon}
![[index]](icon/up.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}