# Does kd-tree search look at more leaves in L1 than in Lmax ?

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.)