msfroh commented on PR #14352: URL: https://github.com/apache/lucene/pull/14352#issuecomment-2722703844
> Another new thought is that I believe SinglePointVisitor is unnecessary, as processing each point separately will traverse the bkd tree multiple times. MergePointVisitor will only traverse the bkd tree once. Therefore, in most cases, SinglePointVisitor will result in slower performance. As long as MergePointVisitor supports both single and multiple dimensions, reverse collection optimization can be used. Right now, `MergePointVisitor` only supports 1-dimension, since it relies on the fact that it can traverse the tree from left to right at the same time as it's traversing the points from left to right (like a merge sort). I think it might be possible to do an N-dimensional approach like a quick sort, though. Suppose you have a list of N-dimensional points. At the root of the tree, (I think) you always have two children. If you take the upper bound of the right child / lower bound of the left child as your pivot, you can do an O(n) reordering of the list into points that potentially match on the left and right. (If there's a common value shared between right and left, you would have to push those values both ways.) As you go down the tree, you're focused on a sublist of the original list and can reorder that sublist based on the next level's pivot. The values shared between left and right might mess things up, though, since you can't safely reorder them on the left without potentially messing up the right. Hmm... might still be doable, though. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
