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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.