Can you guys help me understand BK-tree?

Правка ru8, от imaonemanarmy, 2018-09-13 12:50:06

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 impliesc ≥ b - a
b + c ≥ a impliesc ≥ a - b

Combining the last 2, we get c\geqslant|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].

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru16 Русский imaonemanarmy 2018-09-13 12:59:10 4
ru15 Русский imaonemanarmy 2018-09-13 12:57:34 2 Мелкая правка: 'leqslantc\geqslant a+' -> 'leqslantc\leqslant a+'
ru14 Русский imaonemanarmy 2018-09-13 12:57:19 58
ru13 Русский imaonemanarmy 2018-09-13 12:55:06 2 Мелкая правка: 'nt $[d-N,d-N]$ instea' -> 'nt $[d-N,d+N]$ instea'
ru12 Русский imaonemanarmy 2018-09-13 12:54:28 10
ru11 Русский imaonemanarmy 2018-09-13 12:53:09 2 Мелкая правка: 'geqslant|a+b|$$\n\nBu' -> 'geqslant|a-b|$$\n\nBu'
ru10 Русский 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 Русский imaonemanarmy 2018-09-13 12:52:06 20
ru8 Русский imaonemanarmy 2018-09-13 12:50:06 32
ru7 Русский imaonemanarmy 2018-09-13 12:49:38 30
ru6 Русский imaonemanarmy 2018-09-13 12:49:02 20
ru5 Русский imaonemanarmy 2018-09-13 12:48:16 55
ru4 Русский imaonemanarmy 2018-09-13 12:47:42 11 Мелкая правка: 'a$$\n$$b+c>=a -> c>=a-' -> 'a$$\n$$b+c\geqslanta -> c>=a-'
ru3 Русский imaonemanarmy 2018-09-13 12:47:03 6
ru2 Русский imaonemanarmy 2018-09-13 12:46:39 6
ru1 Русский imaonemanarmy 2018-09-13 12:46:01 935 Первая редакция (опубликовано)