22:
192:
3015:
appearing in "cake"s subtree having distance less than 2 to "cool" would violate the triangle inequality: the triangle inequality requires that for this set of three numbers (as sides of a triangle), no two can sum to less than the third, but here the distance from "cool" to "book" (which is 2) plus
3624:
R. Baeza-Yates, W. Cunto, U. Manber, and S. Wu. Proximity matching using fixed queries trees. In M. Crochemore and D. Gusfield, editors, 5th
Combinatorial Pattern Matching, LNCS 807, pages 198–212, Asilomar, CA, June
2123:
2403:
2995:. Therefore, the subtree rooted at "cake" will be pruned from the search, as the word closest to "cool" cannot appear in that subtree. To see why this pruning is correct, notice that a candidate word
3505:
to distance 1, then the node containing "boon" is popped last, which has distance 2 from "cool" and therefore does not improve the best result. Finally, "cook" is returned as the answer
2522:
2252:
1216:
621:
3340:
380:
3424:
1503:
3139:
2787:
as this is the best (i.e. smallest) distance found thus far. Next each outgoing arc from the root is considered in turn: the arc from "book" to "books" has weight 1, and since
2305:
1432:
1074:
2153:
40:
1556:
3632:
3581:
3270:
2973:
2869:
2785:
277:
3036:(which is less than 2) cannot reach or exceed the distance from "book" to "cake" (which is 4). Therefore, it is safe to disregard the entire subtree rooted at "cake".
3539:
3503:
3175:
2612:
1825:
1780:
1351:
177:
3228:
3090:
2931:
2827:
2743:
1737:
541:
496:
1962:
1905:
744:
124:
2710:
2442:
1466:
805:
776:
407:
315:
1628:
to nodes that can only improve the best candidate found so far by taking advantage of the BK-tree organization and of the triangle inequality (cut-off criterion).
1246:
2643:
3467:
3444:
3360:
3195:
3057:
3034:
3013:
2993:
2889:
2683:
2663:
2565:
2545:
2196:
2176:
2026:
2006:
1986:
1937:
1885:
1865:
1845:
1757:
1702:
1676:
1654:
1626:
1606:
1586:
1527:
1398:
1375:
1315:
1295:
1271:
1166:
1142:
1122:
1098:
1040:
1020:
997:
965:
945:
915:
895:
869:
849:
825:
712:
684:
664:
561:
516:
455:
427:
244:
217:
3948:
3177:
remains set at 2 and the single outgoing arc from the node containing "books" is considered. Next, the node containing "boo" is popped from
4155:
3699:
2033:
629:
Consider the arc from "book" to "books". The distance between "book" and any word in {"books", "boo", "boon", "cook"} is equal to 1;
58:
3598:
4211:
2312:
3815:
3657:
635:
Consider the arc from "books" to "boo". The distance between "books" and any word in {"boo", "boon", "cook"} is equal to 2.
3670:
180:
3780:
3662:
4165:
2452:
2202:
3721:
1173:
3275:
320:
3692:
3633:
Ricardo Baeza-Yates and
Gonzalo Navarro. Fast Approximate String Matching in a Dictionary. Proc. SPIRE'98
3365:
3859:
3708:
3272:. Each outgoing arc from "boo" is now considered; the arc from "boo" to "boon" has weight 1, and since
1472:
219:
of words {"book", "books", "cake", "boo", "boon", "cook", "cake", "cape", "cart"} obtained by using the
3095:
2261:
1404:
1046:
566:
2132:
80:
3849:
3804:
3652:
3592:
1679:
872:
220:
3963:
3739:
2665:
is initialized to contain the root of the tree, which is subsequently popped as the first value of
1535:
3819:
4130:
4089:
3915:
3905:
3784:
3469:
are considered in arbitrary order: suppose the node containing "cook" is popped first, improving
3544:
3233:
2936:
2832:
2748:
249:
4024:
3725:
3685:
3508:
3472:
3144:
2581:
1794:
1762:
1320:
141:
3200:
3062:
2894:
2790:
2715:
1709:
463:
4115:
1947:
1890:
719:
94:
2688:
2415:
1439:
783:
749:
385:
288:
4059:
3809:
1225:
2625:
521:
4012:
4007:
3890:
3824:
3452:
3429:
3345:
3180:
3042:
3019:
2998:
2978:
2874:
2668:
2648:
2550:
2530:
2181:
2161:
2011:
1991:
1971:
1922:
1870:
1850:
1830:
1742:
1687:
1661:
1639:
1611:
1591:
1571:
1512:
1383:
1360:
1300:
1280:
1256:
1151:
1127:
1107:
1083:
1025:
1005:
982:
950:
930:
900:
880:
854:
834:
810:
697:
669:
649:
546:
501:
440:
412:
283:
229:
202:
2891:
for further processing. The next arc, from "book" to "cake," has weight 4, and since
4205:
4160:
4140:
3983:
3872:
3799:
3734:
4120:
4084:
3900:
3895:
3877:
3789:
3616:
W. Burkhard and R. Keller. Some approaches to best-match file searching, CACM, 1973
84:
76:
4170:
4135:
4125:
4039:
3973:
3968:
3958:
3867:
3716:
4180:
4150:
4110:
3953:
3882:
3829:
3749:
130:
is selected as root node. The root node may have zero or more subtrees. The
4185:
4145:
3992:
3920:
3910:
1588:, the lookup primitive traverses the BK-tree to find the closest element of
3615:
4074:
3764:
4190:
4064:
4044:
4017:
4002:
3754:
3665:
4175:
4079:
4054:
3844:
3774:
3769:
3744:
3677:
3230:, the distance from "cool" to "boo." This again does not improve upon
3673:
126:. Then, BK-tree is defined in the following way. An arbitrary element
4094:
4069:
4049:
4034:
3943:
3834:
3759:
3601:– a modified form of Levenshtein distance that allows transpositions
457:
of the BK-tree, the weight assigned to its egress arcs are distinct;
3651:
An explanation of BK-Trees and their relationship to metric spaces
191:
3938:
3839:
3794:
190:
3930:
3645:
3681:
2118:{\displaystyle (w_{best},d_{best})\leftarrow (\perp ,d_{max})}
15:
3595:– the distance metric commonly used when building a BK-tree
2398:{\displaystyle (w_{best},d_{best})\leftarrow (w_{u},d_{u})}
1739:: the maximum distance allowed between the best match and
2622:
Consider the example 8-node B-K Tree shown above and set
3656:
An explanation of BK-Trees with an implementation in C#
36:
646:
The insertion primitive is used to populate a BK-tree
3547:
3511:
3475:
3455:
3432:
3368:
3348:
3278:
3236:
3203:
3183:
3147:
3098:
3065:
3045:
3022:
3001:
2981:
2939:
2897:
2877:
2835:
2793:
2751:
2718:
2691:
2671:
2651:
2628:
2584:
2553:
2533:
2455:
2418:
2315:
2264:
2205:
2184:
2164:
2135:
2036:
2014:
1994:
1974:
1950:
1925:
1893:
1873:
1853:
1833:
1797:
1765:
1745:
1712:
1690:
1664:
1642:
1614:
1594:
1574:
1538:
1515:
1475:
1442:
1407:
1386:
1363:
1323:
1303:
1283:
1259:
1228:
1176:
1154:
1130:
1110:
1086:
1049:
1028:
1008:
985:
953:
933:
903:
883:
857:
837:
813:
786:
752:
722:
700:
672:
652:
569:
549:
524:
504:
466:
443:
415:
388:
323:
291:
252:
232:
205:
144:
97:
4103:
3982:
3929:
3858:
3715:
2745:since the distance from "book" to "cool" is 2, and
31:
may be too technical for most readers to understand
3575:
3533:
3497:
3461:
3438:
3418:
3354:
3334:
3264:
3222:
3189:
3169:
3133:
3084:
3051:
3028:
3007:
2987:
2975:, the node containing "cake" is not inserted into
2967:
2925:
2883:
2863:
2821:
2779:
2737:
2704:
2677:
2657:
2637:
2606:
2559:
2539:
2516:
2436:
2397:
2299:
2246:
2190:
2170:
2147:
2117:
2020:
2000:
1988:a set of nodes to process, and insert the root of
1980:
1956:
1931:
1899:
1879:
1859:
1839:
1819:
1774:
1751:
1731:
1696:
1670:
1648:
1620:
1600:
1580:
1550:
1521:
1497:
1460:
1426:
1392:
1369:
1345:
1309:
1289:
1265:
1240:
1210:
1160:
1136:
1116:
1092:
1068:
1034:
1014:
991:
959:
939:
909:
889:
863:
843:
819:
799:
770:
738:
706:
678:
658:
615:
555:
535:
510:
490:
449:
421:
401:
374:
309:
271:
238:
211:
171:
118:
1608:. The key idea is to restrict the exploration of
3039:Next the node containing "books" is popped from
2871:, the node containing "books" is inserted into
1678:: the corresponding discrete metric (e.g. the
3693:
199:This picture depicts the BK-tree for the set
134:subtree is recursively built of all elements
8:
3092:, the distance from "cool" to "books." As
3700:
3686:
3678:
2517:{\displaystyle |d_{uv}-d_{u}|<d_{best}}
2247:{\displaystyle d_{u}\leftarrow d(w,w_{u})}
3648:with test results and performance graphs.
3552:
3546:
3516:
3510:
3480:
3474:
3454:
3449:Finally each of the two last elements in
3431:
3401:
3383:
3369:
3367:
3347:
3311:
3293:
3279:
3277:
3241:
3235:
3208:
3202:
3182:
3152:
3146:
3116:
3103:
3097:
3070:
3064:
3044:
3021:
3000:
2980:
2944:
2938:
2912:
2898:
2896:
2876:
2840:
2834:
2808:
2794:
2792:
2756:
2750:
2723:
2717:
2696:
2690:
2670:
2650:
2627:
2589:
2583:
2552:
2532:
2499:
2487:
2481:
2465:
2456:
2454:
2417:
2386:
2373:
2345:
2323:
2314:
2282:
2269:
2263:
2235:
2210:
2204:
2183:
2163:
2134:
2100:
2066:
2044:
2035:
2013:
1993:
1973:
1949:
1924:
1892:
1872:
1852:
1832:
1802:
1796:
1764:
1744:
1717:
1711:
1689:
1663:
1641:
1613:
1593:
1573:
1537:
1514:
1480:
1474:
1441:
1412:
1406:
1385:
1362:
1328:
1322:
1302:
1282:
1258:
1227:
1193:
1175:
1153:
1129:
1109:
1085:
1054:
1048:
1027:
1007:
984:
952:
932:
902:
882:
856:
836:
812:
791:
785:
751:
727:
721:
699:
671:
651:
593:
580:
568:
548:
523:
503:
465:
442:
414:
393:
387:
363:
350:
328:
322:
290:
257:
251:
231:
204:
143:
96:
59:Learn how and when to remove this message
43:, without removing the technical details.
79:suggested by Walter Austin Burkhard and
1211:{\displaystyle k\leftarrow d(w_{u},w)}
746:denotes the weight assigned to an arc
3335:{\displaystyle |2-1|=1<d_{best}=2}
375:{\displaystyle d_{uv}=d(w_{u},w_{v})}
41:make it understandable to non-experts
7:
3419:{\displaystyle |2-2|=0<d_{best}}
2142:
1769:
1498:{\displaystyle d_{uv}\leftarrow k}
897:: the element to be inserted into
563:satisfies the following equation:
14:
3134:{\displaystyle d_{u}>d_{best}}
2300:{\displaystyle d_{u}<d_{best}}
1427:{\displaystyle w_{v}\leftarrow w}
1069:{\displaystyle w_{r}\leftarrow w}
616:{\displaystyle d(w_{u},w_{v'})=k}
83:specifically adapted to discrete
2148:{\displaystyle S\neq \emptyset }
807:denotes word assigned to a node
20:
2618:Example of the lookup algorithm
666:according to a discrete metric
3384:
3370:
3294:
3280:
2913:
2899:
2809:
2795:
2488:
2457:
2431:
2419:
2392:
2366:
2363:
2360:
2316:
2241:
2222:
2216:
2112:
2087:
2084:
2081:
2037:
1542:
1489:
1455:
1443:
1418:
1205:
1186:
1180:
1060:
851:: the discrete metric used by
765:
753:
604:
573:
485:
473:
433:The BK-tree is built so that:
369:
343:
304:
292:
160:
148:
113:
101:
1:
1551:{\displaystyle u\leftarrow v}
409:denotes the word assigned to
3669:A BK-tree implementation in
3661:A BK-tree implementation in
3644:A BK-tree implementation in
3599:Damerau–Levenshtein distance
3016:the distance from "cool" to
181:approximate string matching
179:. BK-trees can be used for
87:. For simplicity, consider
4228:
3576:{\displaystyle d_{best}=1}
3426:, "cook" is also added to
3265:{\displaystyle d_{best}=2}
2968:{\displaystyle d_{best}=2}
2864:{\displaystyle d_{best}=2}
2780:{\displaystyle d_{best}=2}
272:{\displaystyle w_{u}\in W}
246:is labeled by a string of
1827:: the closest element to
1568:Given a searched element
4156:Left-child right-sibling
3534:{\displaystyle w_{best}}
3498:{\displaystyle d_{best}}
3170:{\displaystyle d_{best}}
2607:{\displaystyle w_{best}}
1820:{\displaystyle w_{best}}
1775:{\displaystyle +\infty }
1346:{\displaystyle d_{uv}=k}
172:{\displaystyle d(a,b)=k}
4212:Trees (data structures)
3986:data partitioning trees
3944:C-trie (compressed ADT)
3223:{\displaystyle d_{u}=2}
3085:{\displaystyle d_{u}=3}
2926:{\displaystyle |4-2|=2}
2822:{\displaystyle |1-2|=1}
2738:{\displaystyle d_{u}=2}
1732:{\displaystyle d_{max}}
1704:: the searched element;
491:{\displaystyle e=(u,v)}
3577:
3535:
3499:
3463:
3440:
3420:
3356:
3336:
3266:
3224:
3191:
3171:
3135:
3086:
3053:
3030:
3009:
2989:
2969:
2927:
2885:
2865:
2823:
2781:
2739:
2706:
2679:
2659:
2639:
2608:
2561:
2541:
2524:: (cut-off criterion)
2518:
2438:
2399:
2301:
2248:
2192:
2172:
2158:Pop an arbitrary node
2149:
2119:
2022:
2002:
1982:
1958:
1957:{\displaystyle \perp }
1933:
1901:
1900:{\displaystyle \perp }
1881:
1861:
1841:
1821:
1776:
1753:
1733:
1698:
1672:
1650:
1622:
1602:
1582:
1552:
1523:
1499:
1462:
1428:
1394:
1371:
1347:
1311:
1291:
1267:
1242:
1212:
1162:
1138:
1118:
1094:
1070:
1036:
1016:
993:
961:
941:
911:
891:
865:
845:
821:
801:
772:
740:
739:{\displaystyle d_{uv}}
708:
680:
660:
617:
557:
537:
512:
492:
451:
423:
403:
376:
311:
273:
240:
213:
196:
173:
120:
119:{\displaystyle d(x,y)}
3578:
3536:
3500:
3464:
3441:
3421:
3357:
3342:, "boon" is added to
3337:
3267:
3225:
3192:
3172:
3136:
3087:
3054:
3031:
3010:
2990:
2970:
2928:
2886:
2866:
2824:
2782:
2740:
2707:
2705:{\displaystyle w_{u}}
2680:
2660:
2640:
2609:
2562:
2542:
2519:
2439:
2437:{\displaystyle (u,v)}
2400:
2302:
2249:
2193:
2173:
2150:
2120:
2023:
2003:
1983:
1959:
1934:
1902:
1882:
1862:
1842:
1822:
1777:
1754:
1734:
1699:
1673:
1651:
1623:
1603:
1583:
1553:
1524:
1500:
1463:
1461:{\displaystyle (u,v)}
1429:
1395:
1372:
1348:
1312:
1292:
1268:
1243:
1213:
1163:
1139:
1119:
1095:
1071:
1037:
1017:
994:
962:
942:
912:
892:
866:
846:
822:
802:
800:{\displaystyle w_{u}}
773:
771:{\displaystyle (u,v)}
741:
709:
681:
661:
618:
558:
538:
513:
493:
452:
424:
404:
402:{\displaystyle w_{u}}
377:
312:
310:{\displaystyle (u,v)}
274:
241:
214:
195:An example of BK-tree
194:
174:
121:
4166:Log-structured merge
3709:Tree data structures
3593:Levenshtein distance
3545:
3509:
3473:
3453:
3430:
3366:
3362:. Similarly, since
3346:
3276:
3234:
3201:
3181:
3145:
3096:
3063:
3043:
3020:
2999:
2979:
2937:
2895:
2875:
2833:
2791:
2749:
2716:
2689:
2669:
2649:
2626:
2582:
2551:
2531:
2453:
2416:
2313:
2262:
2203:
2182:
2162:
2133:
2034:
2012:
1992:
1972:
1948:
1923:
1891:
1871:
1851:
1831:
1795:
1763:
1743:
1710:
1688:
1680:Levenshtein distance
1662:
1640:
1612:
1592:
1572:
1536:
1513:
1473:
1440:
1405:
1384:
1361:
1321:
1301:
1281:
1257:
1226:
1174:
1152:
1128:
1108:
1084:
1047:
1026:
1006:
983:
951:
931:
901:
881:
873:Levenshtein distance
855:
835:
811:
784:
750:
720:
698:
670:
650:
567:
547:
522:
502:
464:
441:
413:
386:
321:
289:
250:
230:
221:Levenshtein distance
203:
142:
95:
1241:{\displaystyle k=0}
1002:Create a root node
4131:Fractal tree index
3726:associative arrays
3573:
3531:
3495:
3459:
3436:
3416:
3352:
3332:
3262:
3220:
3187:
3167:
3131:
3082:
3049:
3026:
3005:
2985:
2965:
2923:
2881:
2861:
2819:
2777:
2735:
2702:
2675:
2655:
2638:{\displaystyle w=}
2635:
2604:
2557:
2537:
2514:
2434:
2395:
2297:
2244:
2188:
2168:
2145:
2115:
2018:
1998:
1978:
1954:
1929:
1897:
1877:
1857:
1837:
1817:
1772:
1749:
1729:
1694:
1668:
1646:
1618:
1598:
1578:
1548:
1519:
1495:
1458:
1424:
1390:
1367:
1343:
1307:
1287:
1263:
1238:
1208:
1158:
1134:
1114:
1090:
1066:
1032:
1012:
989:
957:
937:
907:
887:
861:
841:
817:
797:
768:
736:
704:
676:
656:
613:
553:
536:{\displaystyle v'}
533:
518:, each descendant
508:
488:
447:
419:
399:
372:
307:
269:
236:
209:
197:
169:
116:
4199:
4198:
3462:{\displaystyle S}
3439:{\displaystyle S}
3355:{\displaystyle S}
3190:{\displaystyle S}
3052:{\displaystyle S}
3029:{\displaystyle c}
3008:{\displaystyle c}
2988:{\displaystyle S}
2933:is not less than
2884:{\displaystyle S}
2712:="book". Further
2678:{\displaystyle u}
2658:{\displaystyle S}
2560:{\displaystyle S}
2540:{\displaystyle v}
2191:{\displaystyle S}
2171:{\displaystyle u}
2021:{\displaystyle S}
2001:{\displaystyle t}
1981:{\displaystyle S}
1932:{\displaystyle t}
1880:{\displaystyle d}
1867:and according to
1860:{\displaystyle t}
1840:{\displaystyle w}
1752:{\displaystyle w}
1697:{\displaystyle w}
1671:{\displaystyle d}
1649:{\displaystyle t}
1621:{\displaystyle t}
1601:{\displaystyle w}
1581:{\displaystyle w}
1522:{\displaystyle v}
1393:{\displaystyle v}
1370:{\displaystyle v}
1310:{\displaystyle u}
1290:{\displaystyle v}
1266:{\displaystyle u}
1161:{\displaystyle u}
1137:{\displaystyle t}
1117:{\displaystyle u}
1093:{\displaystyle r}
1035:{\displaystyle t}
1015:{\displaystyle r}
992:{\displaystyle t}
960:{\displaystyle w}
947:corresponding to
940:{\displaystyle t}
910:{\displaystyle t}
890:{\displaystyle w}
864:{\displaystyle t}
844:{\displaystyle d}
820:{\displaystyle u}
707:{\displaystyle t}
679:{\displaystyle d}
659:{\displaystyle t}
556:{\displaystyle v}
511:{\displaystyle k}
450:{\displaystyle u}
422:{\displaystyle u}
239:{\displaystyle u}
212:{\displaystyle W}
183:in a dictionary.
69:
68:
61:
4219:
3702:
3695:
3688:
3679:
3631:
3623:
3614:
3582:
3580:
3579:
3574:
3566:
3565:
3540:
3538:
3537:
3532:
3530:
3529:
3504:
3502:
3501:
3496:
3494:
3493:
3468:
3466:
3465:
3460:
3445:
3443:
3442:
3437:
3425:
3423:
3422:
3417:
3415:
3414:
3387:
3373:
3361:
3359:
3358:
3353:
3341:
3339:
3338:
3333:
3325:
3324:
3297:
3283:
3271:
3269:
3268:
3263:
3255:
3254:
3229:
3227:
3226:
3221:
3213:
3212:
3196:
3194:
3193:
3188:
3176:
3174:
3173:
3168:
3166:
3165:
3140:
3138:
3137:
3132:
3130:
3129:
3108:
3107:
3091:
3089:
3088:
3083:
3075:
3074:
3058:
3056:
3055:
3050:
3035:
3033:
3032:
3027:
3014:
3012:
3011:
3006:
2994:
2992:
2991:
2986:
2974:
2972:
2971:
2966:
2958:
2957:
2932:
2930:
2929:
2924:
2916:
2902:
2890:
2888:
2887:
2882:
2870:
2868:
2867:
2862:
2854:
2853:
2828:
2826:
2825:
2820:
2812:
2798:
2786:
2784:
2783:
2778:
2770:
2769:
2744:
2742:
2741:
2736:
2728:
2727:
2711:
2709:
2708:
2703:
2701:
2700:
2684:
2682:
2681:
2676:
2664:
2662:
2661:
2656:
2644:
2642:
2641:
2636:
2613:
2611:
2610:
2605:
2603:
2602:
2566:
2564:
2563:
2558:
2546:
2544:
2543:
2538:
2523:
2521:
2520:
2515:
2513:
2512:
2491:
2486:
2485:
2473:
2472:
2460:
2443:
2441:
2440:
2435:
2404:
2402:
2401:
2396:
2391:
2390:
2378:
2377:
2359:
2358:
2337:
2336:
2306:
2304:
2303:
2298:
2296:
2295:
2274:
2273:
2253:
2251:
2250:
2245:
2240:
2239:
2215:
2214:
2197:
2195:
2194:
2189:
2177:
2175:
2174:
2169:
2154:
2152:
2151:
2146:
2124:
2122:
2121:
2116:
2111:
2110:
2080:
2079:
2058:
2057:
2027:
2025:
2024:
2019:
2007:
2005:
2004:
1999:
1987:
1985:
1984:
1979:
1963:
1961:
1960:
1955:
1938:
1936:
1935:
1930:
1906:
1904:
1903:
1898:
1886:
1884:
1883:
1878:
1866:
1864:
1863:
1858:
1846:
1844:
1843:
1838:
1826:
1824:
1823:
1818:
1816:
1815:
1781:
1779:
1778:
1773:
1758:
1756:
1755:
1750:
1738:
1736:
1735:
1730:
1728:
1727:
1703:
1701:
1700:
1695:
1677:
1675:
1674:
1669:
1655:
1653:
1652:
1647:
1627:
1625:
1624:
1619:
1607:
1605:
1604:
1599:
1587:
1585:
1584:
1579:
1557:
1555:
1554:
1549:
1528:
1526:
1525:
1520:
1504:
1502:
1501:
1496:
1488:
1487:
1467:
1465:
1464:
1459:
1433:
1431:
1430:
1425:
1417:
1416:
1399:
1397:
1396:
1391:
1380:Create the node
1376:
1374:
1373:
1368:
1352:
1350:
1349:
1344:
1336:
1335:
1316:
1314:
1313:
1308:
1296:
1294:
1293:
1288:
1272:
1270:
1269:
1264:
1247:
1245:
1244:
1239:
1217:
1215:
1214:
1209:
1198:
1197:
1167:
1165:
1164:
1159:
1143:
1141:
1140:
1135:
1123:
1121:
1120:
1115:
1099:
1097:
1096:
1091:
1075:
1073:
1072:
1067:
1059:
1058:
1041:
1039:
1038:
1033:
1021:
1019:
1018:
1013:
998:
996:
995:
990:
966:
964:
963:
958:
946:
944:
943:
938:
916:
914:
913:
908:
896:
894:
893:
888:
870:
868:
867:
862:
850:
848:
847:
842:
826:
824:
823:
818:
806:
804:
803:
798:
796:
795:
777:
775:
774:
769:
745:
743:
742:
737:
735:
734:
713:
711:
710:
705:
685:
683:
682:
677:
665:
663:
662:
657:
622:
620:
619:
614:
603:
602:
601:
585:
584:
562:
560:
559:
554:
542:
540:
539:
534:
532:
517:
515:
514:
509:
497:
495:
494:
489:
456:
454:
453:
448:
428:
426:
425:
420:
408:
406:
405:
400:
398:
397:
381:
379:
378:
373:
368:
367:
355:
354:
336:
335:
316:
314:
313:
308:
278:
276:
275:
270:
262:
261:
245:
243:
242:
237:
218:
216:
215:
210:
178:
176:
175:
170:
125:
123:
122:
117:
91:discrete metric
81:Robert M. Keller
64:
57:
53:
50:
44:
24:
23:
16:
4227:
4226:
4222:
4221:
4220:
4218:
4217:
4216:
4202:
4201:
4200:
4195:
4099:
3978:
3925:
3854:
3850:Weight-balanced
3805:Order statistic
3719:
3711:
3706:
3641:
3628:
3620:
3611:
3608:
3589:
3548:
3543:
3542:
3512:
3507:
3506:
3476:
3471:
3470:
3451:
3450:
3428:
3427:
3397:
3364:
3363:
3344:
3343:
3307:
3274:
3273:
3237:
3232:
3231:
3204:
3199:
3198:
3179:
3178:
3148:
3143:
3142:
3112:
3099:
3094:
3093:
3066:
3061:
3060:
3041:
3040:
3018:
3017:
2997:
2996:
2977:
2976:
2940:
2935:
2934:
2893:
2892:
2873:
2872:
2836:
2831:
2830:
2789:
2788:
2752:
2747:
2746:
2719:
2714:
2713:
2692:
2687:
2686:
2667:
2666:
2647:
2646:
2624:
2623:
2620:
2585:
2580:
2579:
2549:
2548:
2529:
2528:
2495:
2477:
2461:
2451:
2450:
2414:
2413:
2382:
2369:
2341:
2319:
2311:
2310:
2278:
2265:
2260:
2259:
2231:
2206:
2201:
2200:
2180:
2179:
2160:
2159:
2131:
2130:
2096:
2062:
2040:
2032:
2031:
2010:
2009:
1990:
1989:
1970:
1969:
1946:
1945:
1921:
1920:
1889:
1888:
1869:
1868:
1849:
1848:
1829:
1828:
1798:
1793:
1792:
1761:
1760:
1741:
1740:
1713:
1708:
1707:
1686:
1685:
1660:
1659:
1638:
1637:
1610:
1609:
1590:
1589:
1570:
1569:
1566:
1534:
1533:
1511:
1510:
1476:
1471:
1470:
1438:
1437:
1436:Create the arc
1408:
1403:
1402:
1382:
1381:
1359:
1358:
1324:
1319:
1318:
1299:
1298:
1279:
1278:
1255:
1254:
1224:
1223:
1189:
1172:
1171:
1150:
1149:
1126:
1125:
1124:to the root of
1106:
1105:
1082:
1081:
1050:
1045:
1044:
1024:
1023:
1004:
1003:
981:
980:
949:
948:
929:
928:
899:
898:
879:
878:
853:
852:
833:
832:
809:
808:
787:
782:
781:
748:
747:
723:
718:
717:
714:: the BK-tree;
696:
695:
668:
667:
648:
647:
644:
594:
589:
576:
565:
564:
545:
544:
525:
520:
519:
500:
499:
462:
461:
439:
438:
411:
410:
389:
384:
383:
359:
346:
324:
319:
318:
287:
286:
253:
248:
247:
228:
227:
201:
200:
189:
140:
139:
93:
92:
65:
54:
48:
45:
37:help improve it
34:
25:
21:
12:
11:
5:
4225:
4223:
4215:
4214:
4204:
4203:
4197:
4196:
4194:
4193:
4188:
4183:
4178:
4173:
4168:
4163:
4158:
4153:
4148:
4143:
4138:
4133:
4128:
4123:
4118:
4113:
4107:
4105:
4101:
4100:
4098:
4097:
4092:
4087:
4082:
4077:
4072:
4067:
4062:
4057:
4052:
4047:
4042:
4037:
4032:
4015:
4010:
4005:
4000:
3995:
3989:
3987:
3980:
3979:
3977:
3976:
3971:
3966:
3964:Ternary search
3961:
3956:
3951:
3946:
3941:
3935:
3933:
3927:
3926:
3924:
3923:
3918:
3913:
3908:
3903:
3898:
3893:
3888:
3880:
3875:
3870:
3864:
3862:
3856:
3855:
3853:
3852:
3847:
3842:
3837:
3832:
3827:
3822:
3812:
3807:
3802:
3797:
3792:
3787:
3777:
3772:
3767:
3762:
3757:
3752:
3747:
3742:
3737:
3731:
3729:
3713:
3712:
3707:
3705:
3704:
3697:
3690:
3682:
3676:
3675:
3667:
3659:
3654:
3649:
3640:
3639:External links
3637:
3636:
3635:
3626:
3618:
3607:
3604:
3603:
3602:
3596:
3588:
3585:
3572:
3569:
3564:
3561:
3558:
3555:
3551:
3528:
3525:
3522:
3519:
3515:
3492:
3489:
3486:
3483:
3479:
3458:
3435:
3413:
3410:
3407:
3404:
3400:
3396:
3393:
3390:
3386:
3382:
3379:
3376:
3372:
3351:
3331:
3328:
3323:
3320:
3317:
3314:
3310:
3306:
3303:
3300:
3296:
3292:
3289:
3286:
3282:
3261:
3258:
3253:
3250:
3247:
3244:
3240:
3219:
3216:
3211:
3207:
3186:
3164:
3161:
3158:
3155:
3151:
3128:
3125:
3122:
3119:
3115:
3111:
3106:
3102:
3081:
3078:
3073:
3069:
3048:
3025:
3004:
2984:
2964:
2961:
2956:
2953:
2950:
2947:
2943:
2922:
2919:
2915:
2911:
2908:
2905:
2901:
2880:
2860:
2857:
2852:
2849:
2846:
2843:
2839:
2818:
2815:
2811:
2807:
2804:
2801:
2797:
2776:
2773:
2768:
2765:
2762:
2759:
2755:
2734:
2731:
2726:
2722:
2699:
2695:
2674:
2654:
2634:
2631:
2619:
2616:
2615:
2614:
2601:
2598:
2595:
2592:
2588:
2574:
2573:
2572:
2571:
2570:
2569:
2568:
2556:
2536:
2511:
2508:
2505:
2502:
2498:
2494:
2490:
2484:
2480:
2476:
2471:
2468:
2464:
2459:
2433:
2430:
2427:
2424:
2421:
2407:
2406:
2405:
2394:
2389:
2385:
2381:
2376:
2372:
2368:
2365:
2362:
2357:
2354:
2351:
2348:
2344:
2340:
2335:
2332:
2329:
2326:
2322:
2318:
2294:
2291:
2288:
2285:
2281:
2277:
2272:
2268:
2254:
2243:
2238:
2234:
2230:
2227:
2224:
2221:
2218:
2213:
2209:
2198:
2187:
2167:
2144:
2141:
2138:
2125:
2114:
2109:
2106:
2103:
2099:
2095:
2092:
2089:
2086:
2083:
2078:
2075:
2072:
2069:
2065:
2061:
2056:
2053:
2050:
2047:
2043:
2039:
2029:
2017:
1997:
1977:
1966:
1965:
1964:
1953:
1928:
1909:
1908:
1896:
1876:
1856:
1836:
1814:
1811:
1808:
1805:
1801:
1784:
1783:
1771:
1768:
1759:, defaults to
1748:
1726:
1723:
1720:
1716:
1705:
1693:
1683:
1667:
1657:
1656:: the BK-tree;
1645:
1617:
1597:
1577:
1565:
1562:
1561:
1560:
1559:
1558:
1547:
1544:
1541:
1531:
1530:
1529:
1518:
1505:
1494:
1491:
1486:
1483:
1479:
1468:
1457:
1454:
1451:
1448:
1445:
1434:
1423:
1420:
1415:
1411:
1400:
1389:
1377:is not found:
1366:
1353:
1342:
1339:
1334:
1331:
1327:
1306:
1286:
1275:
1274:
1273:
1262:
1237:
1234:
1231:
1218:
1207:
1204:
1201:
1196:
1192:
1188:
1185:
1182:
1179:
1157:
1144:
1133:
1113:
1102:
1101:
1100:
1089:
1076:
1065:
1062:
1057:
1053:
1042:
1031:
1011:
988:
968:
967:
956:
936:
919:
918:
906:
886:
876:
860:
840:
830:
829:
828:
816:
794:
790:
779:
767:
764:
761:
758:
755:
733:
730:
726:
703:
675:
655:
643:
640:
639:
638:
637:
636:
630:
612:
609:
606:
600:
597:
592:
588:
583:
579:
575:
572:
552:
531:
528:
507:
487:
484:
481:
478:
475:
472:
469:
458:
446:
431:
430:
418:
396:
392:
371:
366:
362:
358:
353:
349:
345:
342:
339:
334:
331:
327:
317:is labeled by
306:
303:
300:
297:
294:
280:
268:
265:
260:
256:
235:
208:
188:
185:
168:
165:
162:
159:
156:
153:
150:
147:
115:
112:
109:
106:
103:
100:
67:
66:
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
4224:
4213:
4210:
4209:
4207:
4192:
4189:
4187:
4184:
4182:
4179:
4177:
4174:
4172:
4169:
4167:
4164:
4162:
4159:
4157:
4154:
4152:
4149:
4147:
4144:
4142:
4141:Hash calendar
4139:
4137:
4134:
4132:
4129:
4127:
4124:
4122:
4119:
4117:
4114:
4112:
4109:
4108:
4106:
4102:
4096:
4093:
4091:
4088:
4086:
4083:
4081:
4078:
4076:
4073:
4071:
4068:
4066:
4063:
4061:
4058:
4056:
4053:
4051:
4048:
4046:
4043:
4041:
4038:
4036:
4033:
4030:
4028:
4022:
4020:
4016:
4014:
4011:
4009:
4006:
4004:
4001:
3999:
3996:
3994:
3991:
3990:
3988:
3985:
3981:
3975:
3972:
3970:
3967:
3965:
3962:
3960:
3957:
3955:
3952:
3950:
3947:
3945:
3942:
3940:
3937:
3936:
3934:
3932:
3928:
3922:
3919:
3917:
3916:van Emde Boas
3914:
3912:
3909:
3907:
3906:Skew binomial
3904:
3902:
3899:
3897:
3894:
3892:
3889:
3887:
3885:
3881:
3879:
3876:
3874:
3871:
3869:
3866:
3865:
3863:
3861:
3857:
3851:
3848:
3846:
3843:
3841:
3838:
3836:
3833:
3831:
3828:
3826:
3823:
3821:
3817:
3813:
3811:
3808:
3806:
3803:
3801:
3798:
3796:
3793:
3791:
3788:
3786:
3785:Binary search
3782:
3778:
3776:
3773:
3771:
3768:
3766:
3763:
3761:
3758:
3756:
3753:
3751:
3748:
3746:
3743:
3741:
3738:
3736:
3733:
3732:
3730:
3727:
3723:
3718:
3714:
3710:
3703:
3698:
3696:
3691:
3689:
3684:
3683:
3680:
3674:
3672:
3668:
3666:
3664:
3660:
3658:
3655:
3653:
3650:
3647:
3643:
3642:
3638:
3634:
3630:
3627:
3622:
3619:
3617:
3613:
3610:
3609:
3605:
3600:
3597:
3594:
3591:
3590:
3586:
3584:
3570:
3567:
3562:
3559:
3556:
3553:
3549:
3526:
3523:
3520:
3517:
3513:
3490:
3487:
3484:
3481:
3477:
3456:
3447:
3433:
3411:
3408:
3405:
3402:
3398:
3394:
3391:
3388:
3380:
3377:
3374:
3349:
3329:
3326:
3321:
3318:
3315:
3312:
3308:
3304:
3301:
3298:
3290:
3287:
3284:
3259:
3256:
3251:
3248:
3245:
3242:
3238:
3217:
3214:
3209:
3205:
3184:
3162:
3159:
3156:
3153:
3149:
3126:
3123:
3120:
3117:
3113:
3109:
3104:
3100:
3079:
3076:
3071:
3067:
3046:
3037:
3023:
3002:
2982:
2962:
2959:
2954:
2951:
2948:
2945:
2941:
2920:
2917:
2909:
2906:
2903:
2878:
2858:
2855:
2850:
2847:
2844:
2841:
2837:
2829:is less than
2816:
2813:
2805:
2802:
2799:
2774:
2771:
2766:
2763:
2760:
2757:
2753:
2732:
2729:
2724:
2720:
2697:
2693:
2672:
2652:
2632:
2629:
2617:
2599:
2596:
2593:
2590:
2586:
2578:
2575:
2554:
2534:
2526:
2525:
2509:
2506:
2503:
2500:
2496:
2492:
2482:
2478:
2474:
2469:
2466:
2462:
2449:
2446:
2445:
2428:
2425:
2422:
2411:
2408:
2387:
2383:
2379:
2374:
2370:
2355:
2352:
2349:
2346:
2342:
2338:
2333:
2330:
2327:
2324:
2320:
2309:
2308:
2292:
2289:
2286:
2283:
2279:
2275:
2270:
2266:
2258:
2255:
2236:
2232:
2228:
2225:
2219:
2211:
2207:
2199:
2185:
2165:
2157:
2156:
2139:
2136:
2129:
2126:
2107:
2104:
2101:
2097:
2093:
2090:
2076:
2073:
2070:
2067:
2063:
2059:
2054:
2051:
2048:
2045:
2041:
2030:
2015:
1995:
1975:
1967:
1951:
1944:
1941:
1940:
1926:
1919:
1916:
1915:
1914:
1913:
1907:if not found;
1894:
1874:
1854:
1834:
1812:
1809:
1806:
1803:
1799:
1791:
1790:
1789:
1788:
1766:
1746:
1724:
1721:
1718:
1714:
1706:
1691:
1684:
1681:
1665:
1658:
1643:
1636:
1635:
1634:
1633:
1629:
1615:
1595:
1575:
1563:
1545:
1539:
1532:
1516:
1509:
1506:
1492:
1484:
1481:
1477:
1469:
1452:
1449:
1446:
1435:
1421:
1413:
1409:
1401:
1387:
1379:
1378:
1364:
1357:
1354:
1340:
1337:
1332:
1329:
1325:
1304:
1297:the child of
1284:
1276:
1260:
1253:
1250:
1249:
1235:
1232:
1229:
1222:
1219:
1202:
1199:
1194:
1190:
1183:
1177:
1170:
1169:
1155:
1148:
1145:
1131:
1111:
1103:
1087:
1080:
1077:
1063:
1055:
1051:
1043:
1029:
1009:
1001:
1000:
986:
978:
975:
974:
973:
972:
954:
934:
926:
925:
924:
923:
904:
884:
877:
874:
858:
838:
831:
814:
792:
788:
780:
762:
759:
756:
731:
728:
724:
716:
715:
701:
694:
693:
692:
691:
687:
673:
653:
641:
634:
631:
628:
625:
624:
610:
607:
598:
595:
590:
586:
581:
577:
570:
550:
529:
526:
505:
482:
479:
476:
470:
467:
459:
444:
437:for all node
436:
435:
434:
416:
394:
390:
364:
360:
356:
351:
347:
340:
337:
332:
329:
325:
301:
298:
295:
285:
281:
266:
263:
258:
254:
233:
225:
224:
223:
222:
206:
193:
186:
184:
182:
166:
163:
157:
154:
151:
145:
137:
133:
129:
110:
107:
104:
98:
90:
86:
85:metric spaces
82:
78:
74:
63:
60:
52:
42:
38:
32:
29:This article
27:
18:
17:
4026:
4018:
3997:
3883:
3816:Left-leaning
3722:dynamic sets
3717:Search trees
3629:
3621:
3612:
3448:
3038:
2621:
2576:
2447:
2409:
2256:
2127:
1942:
1917:
1911:
1910:
1786:
1785:
1631:
1630:
1567:
1507:
1355:
1251:
1220:
1146:
1078:
976:
970:
969:
927:The node of
921:
920:
689:
688:
645:
632:
626:
460:for all arc
432:
198:
135:
131:
127:
88:
72:
70:
55:
46:
30:
4116:Exponential
4104:Other trees
3646:Common Lisp
2412:egress-arc
498:labeled by
77:metric tree
4060:Priority R
3810:Palindrome
3606:References
1939:is empty:
1912:Algorithm:
1847:stored in
1317:such that
999:is empty:
971:Algorithm:
871:(e.g. the
633:Example 2:
627:Example 1:
226:each node
138:such that
49:March 2019
4146:iDistance
4025:implicit
4013:Hilbert R
4008:Cartesian
3891:Fibonacci
3825:Scapegoat
3820:Red–black
3378:−
3288:−
2907:−
2803:−
2475:−
2364:←
2217:←
2143:∅
2140:≠
2091:⊥
2085:←
1952:⊥
1895:⊥
1770:∞
1543:←
1490:←
1419:←
1181:←
1061:←
642:Insertion
264:∈
4206:Category
4161:Link/cut
3873:Binomial
3800:Interval
3587:See also
3059:and now
2645:"cool".
2410:For each
1168:exists:
599:′
530:′
4121:Fenwick
4085:Segment
3984:Spatial
3901:Pairing
3896:Leftist
3818:)
3790:Dancing
3783:)
3781:Optimal
2527:Insert
1968:Create
1787:Output:
922:Output:
187:Example
89:integer
73:BK-tree
35:Please
4171:Merkle
4136:Fusion
4126:Finger
4050:Octree
4040:Metric
3974:Y-fast
3969:X-fast
3959:Suffix
3878:Brodal
3868:Binary
3671:Python
2577:Return
1943:Return
1632:Input:
1564:Lookup
1508:Return
1252:Return
1079:Return
690:Input:
382:where
4181:Range
4151:K-ary
4111:Cover
3954:Radix
3939:Ctrie
3931:Tries
3860:Heaps
3840:Treap
3830:Splay
3795:HTree
3750:(a,b)
3740:2–3–4
3625:1994.
3541:with
2685:with
2547:into
2178:from
2128:While
2008:into
1277:Find
1147:While
282:each
75:is a
4186:SPQR
4065:Quad
3993:Ball
3949:Hash
3921:Weak
3911:Skew
3886:-ary
3395:<
3305:<
3197:and
3110:>
2493:<
2276:<
1104:Set
979:the
132:k-th
4191:Top
4045:MVP
4003:BSP
3755:AVL
3735:2–3
3663:Lua
1887:or
1356:If
1022:in
543:of
284:arc
39:to
4208::
4176:PQ
4090:VP
4080:R*
4075:R+
4055:PH
4029:-d
4021:-d
3998:BK
3845:UB
3770:B*
3765:B+
3745:AA
3583:.
3446:.
3141:,
2448:If
2444::
2307::
2257:If
2155::
1918:If
1682:);
1248::
1221:If
977:If
875:);
686:.
623::
71:A
4095:X
4070:R
4035:M
4031:)
4027:k
4023:(
4019:k
3884:d
3835:T
3814:(
3779:(
3775:B
3760:B
3728:)
3724:/
3720:(
3701:e
3694:t
3687:v
3571:1
3568:=
3563:t
3560:s
3557:e
3554:b
3550:d
3527:t
3524:s
3521:e
3518:b
3514:w
3491:t
3488:s
3485:e
3482:b
3478:d
3457:S
3434:S
3412:t
3409:s
3406:e
3403:b
3399:d
3392:0
3389:=
3385:|
3381:2
3375:2
3371:|
3350:S
3330:2
3327:=
3322:t
3319:s
3316:e
3313:b
3309:d
3302:1
3299:=
3295:|
3291:1
3285:2
3281:|
3260:2
3257:=
3252:t
3249:s
3246:e
3243:b
3239:d
3218:2
3215:=
3210:u
3206:d
3185:S
3163:t
3160:s
3157:e
3154:b
3150:d
3127:t
3124:s
3121:e
3118:b
3114:d
3105:u
3101:d
3080:3
3077:=
3072:u
3068:d
3047:S
3024:c
3003:c
2983:S
2963:2
2960:=
2955:t
2952:s
2949:e
2946:b
2942:d
2921:2
2918:=
2914:|
2910:2
2904:4
2900:|
2879:S
2859:2
2856:=
2851:t
2848:s
2845:e
2842:b
2838:d
2817:1
2814:=
2810:|
2806:2
2800:1
2796:|
2775:2
2772:=
2767:t
2764:s
2761:e
2758:b
2754:d
2733:2
2730:=
2725:u
2721:d
2698:u
2694:w
2673:u
2653:S
2633:=
2630:w
2600:t
2597:s
2594:e
2591:b
2587:w
2567:.
2555:S
2535:v
2510:t
2507:s
2504:e
2501:b
2497:d
2489:|
2483:u
2479:d
2470:v
2467:u
2463:d
2458:|
2432:)
2429:v
2426:,
2423:u
2420:(
2393:)
2388:u
2384:d
2380:,
2375:u
2371:w
2367:(
2361:)
2356:t
2353:s
2350:e
2347:b
2343:d
2339:,
2334:t
2331:s
2328:e
2325:b
2321:w
2317:(
2293:t
2290:s
2287:e
2284:b
2280:d
2271:u
2267:d
2242:)
2237:u
2233:w
2229:,
2226:w
2223:(
2220:d
2212:u
2208:d
2186:S
2166:u
2137:S
2113:)
2108:x
2105:a
2102:m
2098:d
2094:,
2088:(
2082:)
2077:t
2074:s
2071:e
2068:b
2064:d
2060:,
2055:t
2052:s
2049:e
2046:b
2042:w
2038:(
2028:.
2016:S
1996:t
1976:S
1927:t
1875:d
1855:t
1835:w
1813:t
1810:s
1807:e
1804:b
1800:w
1782:;
1767:+
1747:w
1725:x
1722:a
1719:m
1715:d
1692:w
1666:d
1644:t
1616:t
1596:w
1576:w
1546:v
1540:u
1517:v
1493:k
1485:v
1482:u
1478:d
1456:)
1453:v
1450:,
1447:u
1444:(
1422:w
1414:v
1410:w
1388:v
1365:v
1341:k
1338:=
1333:v
1330:u
1326:d
1305:u
1285:v
1261:u
1236:0
1233:=
1230:k
1206:)
1203:w
1200:,
1195:u
1191:w
1187:(
1184:d
1178:k
1156:u
1132:t
1112:u
1088:r
1064:w
1056:r
1052:w
1030:t
1010:r
987:t
955:w
935:t
917:;
905:t
885:w
859:t
839:d
827:;
815:u
793:u
789:w
778:;
766:)
763:v
760:,
757:u
754:(
732:v
729:u
725:d
702:t
674:d
654:t
611:k
608:=
605:)
596:v
591:w
587:,
582:u
578:w
574:(
571:d
551:v
527:v
506:k
486:)
483:v
480:,
477:u
474:(
471:=
468:e
445:u
429:.
417:u
395:u
391:w
370:)
365:v
361:w
357:,
352:u
348:w
344:(
341:d
338:=
333:v
330:u
326:d
305:)
302:v
299:,
296:u
293:(
279:;
267:W
259:u
255:w
234:u
207:W
167:k
164:=
161:)
158:b
155:,
152:a
149:(
146:d
136:b
128:a
114:)
111:y
108:,
105:x
102:(
99:d
62:)
56:(
51:)
47:(
33:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
