2
$\begingroup$

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: enter image description here

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

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.