Dear theorists and experimenters,
I find that kd-tree search looks at many more leaves in $L_1$ than in
$L_{max}$ ($L_\infty$).
Does anyone else see this ? If so,
why ? (An $L_1$ simplex of volume 1 is much wider than a unit cube — the back of my envelope says ~ dim/$e$ — but that doesn't get me very far.)
is there some way of using fast $L_{max}$ search to speed up slow $L_1$ ?
Some numbers for dim=16, on data uniform$^3$ to model some clumping:
L1: 0.72 sec p=1 dim=16 N=10000 nask=100 nnear=2 eps=0 leafsize=10
100 queries looked at av 64 % of the 10000 points, 80 % of 1909 boxes
L2: 0.36 sec p=2 dim=16 N=10000 nask=100 nnear=2 eps=0 leafsize=10
100 queries looked at av 25 % of the 10000 points, 37 % of 1909 boxes
Lmax: 0.06 sec p=inf dim=16 N=10000 nask=100 nnear=2 eps=0 leafsize=10
100 queries looked at av 6.2 % of the 10000 points, 10 % of 1909 boxes
A plot of 5 queries:
One sees here that the distances to box edges (blue) increase slowly in $L_1$
—
for this limited data.
(Can someone please add tag "kd-tree", thanks.)
