[
https://issues.apache.org/jira/browse/LUCENE-10628?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17565882#comment-17565882
]
Ignacio Vera commented on LUCENE-10628:
---------------------------------------
I have mainly worked with two type of trees in Lucene.
*
[KD-tree|https://github.com/apache/lucene/blob/35ca2d79f73c6dfaf5e648fe241f7e0b37084a90/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java#L79]:
It is complex to build so probably not suitable for building them on the fly
but best structure for an index.
* [Interval
tree|https://github.com/apache/lucene/blob/2d6ad2fee6dfd96388594f4de9b37c037efe8017/lucene/core/src/java/org/apache/lucene/geo/ComponentTree.java#L28]
(I think originally introduced by Robert Muir): Not as efficient as a kd-tree
but much cheaper to build and suitable for small data.
>From a quick look I think you would be looking for an interval tree but mind
>you that I have only worked with that tree for very low dimension. I guess
>this kind of tree will quickly degenerate due to the [curse of
>dimensionality|https://en.wikipedia.org/wiki/Curse_of_dimensionality]. How may
>dimensions are you expecting to support?
> Enable MatchingFacetSetCounts to use space partitioning data structures
> -----------------------------------------------------------------------
>
> Key: LUCENE-10628
> URL: https://issues.apache.org/jira/browse/LUCENE-10628
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Marc D'Mello
> Priority: Minor
>
> Currently, {{MatchingFacetSetCounts}} iterates over {{FacetSetMatcher}}
> instances passed into it linearly. While this is fine in some cases, if we
> have a large amount of {{FacetSetMatcher}}'s, this can be inefficient. We
> should provide the option to users to enable the use of space partitioning
> data structures (namely R trees and KD trees) so we can potentially scan over
> these {{FacetSetMatcher}}'s in sub-linear time.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
