Can you guys help me understand BK-tree?

Revision ru10, by imaonemanarmy, 2018-09-13 12:52:51

I understand how it works. But the question is why it works. This data structure is based on string metrics, it can use the Levenstein distance metric, for example. Here's the article talking about this: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees

My question is this. The author of the article says: "Call the resultant distance d. Because we know the triangle inequality holds, all our results must have at most distance d+n and at least distance d-n from test."

I don't understand why the search segment is [d-n, d+n].

I'd really appreciate if someone explained.

I know that from the triangle inequality we have:

a + b ≥ c
a + c ≥ b → c ≥ b - a
b + c ≥ a → c ≥ a - b

Combining the last 2, we get

c ≥ |a + b|

But I don't understand what to associate a,b,c with. And why does the author say that we need to search in the segment [d-N,d-N] instead of [|d-N|,d+N].

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru16 Russian imaonemanarmy 2018-09-13 12:59:10 4
ru15 Russian imaonemanarmy 2018-09-13 12:57:34 2 Мелкая правка: 'leqslantc\geqslant a+' -> 'leqslantc\leqslant a+'
ru14 Russian imaonemanarmy 2018-09-13 12:57:19 58
ru13 Russian imaonemanarmy 2018-09-13 12:55:06 2 Мелкая правка: 'nt $[d-N,d-N]$ instea' -> 'nt $[d-N,d+N]$ instea'
ru12 Russian imaonemanarmy 2018-09-13 12:54:28 10
ru11 Russian imaonemanarmy 2018-09-13 12:53:09 2 Мелкая правка: 'geqslant|a+b|$$\n\nBu' -> 'geqslant|a-b|$$\n\nBu'
ru10 Russian imaonemanarmy 2018-09-13 12:52:51 5 Мелкая правка: '2, we get c\geqslant|a+b|.\n\nBut I ' -> '2, we get $$c\geqslant|a+b|$$\n\nBut I '
ru9 Russian imaonemanarmy 2018-09-13 12:52:06 20
ru8 Russian imaonemanarmy 2018-09-13 12:50:06 32
ru7 Russian imaonemanarmy 2018-09-13 12:49:38 30
ru6 Russian imaonemanarmy 2018-09-13 12:49:02 20
ru5 Russian imaonemanarmy 2018-09-13 12:48:16 55
ru4 Russian imaonemanarmy 2018-09-13 12:47:42 11 Мелкая правка: 'a$$\n$$b+c>=a -> c>=a-' -> 'a$$\n$$b+c\geqslanta -> c>=a-'
ru3 Russian imaonemanarmy 2018-09-13 12:47:03 6
ru2 Russian imaonemanarmy 2018-09-13 12:46:39 6
ru1 Russian imaonemanarmy 2018-09-13 12:46:01 935 Первая редакция (опубликовано)