Author here. You almost have it completely right. The features are not stored in a tree. They are an ARRAY of trees. So we hold face1 and face2 constant, load

Author here. You almost have it completely right. The features are not stored in a tree. They are an ARRAY of trees. So we hold face1 and face2 constant, load up the tree for feature 1, descend it, record the value. Then we load up the tree for feature 2, descend it, record the value. Etc. If we have 1000 of faceA, faceB, and 5000 features, that means we'd do 5000 descensions of -different- trees, then iterate to the next face, a million times. You are absolutely correct about the data sizes mattering in that the reason this fails is because you cannot, over the course of a million matches, cache all 5000 trees (given their size). The new algorithm, however, held the tree for feature 1 fixed, and iterated over the faces, which, in this case are simple vectors. This results in using the -same- tree for 1 million consecutive comparisons, then switching trees for feature 2, and so on. In spite of this correction, pretty much everything you've said is accurate. The primary difference is this scenario is much, much worse on cache than the one you've described.