[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17467761#comment-17467761
]
Matt Juntunen commented on GEOMETRY-142:
----------------------------------------
I've added another implementation named {{BucketKDTree}} that stores single
entries in splitting nodes as well as in leaf nodes as lists. However, the
performance is worse than the other implementations. The best implementation
for {{get}} and {{put}} performance is {{varoctree}}, although it does terribly
with {{remove}}. I think the next step is to explore {{varoctree}} a bit more
and see if this can be improved.
||Benchmark||(impl)||(pointDist)||(randomSeed)||(randomized)||Mode||Cnt||Score||Error||Units||
|PointMapDataStructurePerformance.get|treemap|block|1|true|avgt|5|2535086.177|±
196957.459|ns/op|
|PointMapDataStructurePerformance.get|varoctree|block|1|true|avgt|5|3835217.249|±
106874.863|ns/op|
|PointMapDataStructurePerformance.get|kdtree|block|1|true|avgt|5|5918314.090|±
433275.740|ns/op|
|PointMapDataStructurePerformance.get|rebuilding-kdtree|block|1|true|avgt|5|5046805.168|±
397529.992|ns/op|
|PointMapDataStructurePerformance.get|bucket-kdtree|block|1|true|avgt|5|6028908.768|±
598811.980|ns/op|
|PointMapDataStructurePerformance.put|treemap|block|1|true|avgt|5|1543477.168|±
59915.220|ns/op|
|PointMapDataStructurePerformance.put|varoctree|block|1|true|avgt|5|1721624.355|±
31012.494|ns/op|
|PointMapDataStructurePerformance.put|kdtree|block|1|true|avgt|5|7977304.891|±
122840.849|ns/op|
|PointMapDataStructurePerformance.put|rebuilding-kdtree|block|1|true|avgt|5|5687657.624|±
132680.481|ns/op|
|PointMapDataStructurePerformance.put|bucket-kdtree|block|1|true|avgt|5|76366216.557|±
964906.841|ns/op|
|PointMapDataStructurePerformance.remove|treemap|block|1|true|avgt|5|54016.786|±
22942.461|ns/op|
|PointMapDataStructurePerformance.remove|varoctree|block|1|true|avgt|5|1513340.914|±
40069.462|ns/op|
|PointMapDataStructurePerformance.remove|kdtree|block|1|true|avgt|5|61120.730|±
11036.797|ns/op|
|PointMapDataStructurePerformance.remove|rebuilding-kdtree|block|1|true|avgt|5|79552.232|±
10029.806|ns/op|
|PointMapDataStructurePerformance.remove|bucket-kdtree|block|1|true|avgt|5|91491.103|±
14820.207|ns/op|
> Point Set/Map
> -------------
>
> Key: GEOMETRY-142
> URL: https://issues.apache.org/jira/browse/GEOMETRY-142
> Project: Apache Commons Geometry
> Issue Type: New Feature
> Reporter: Matt Juntunen
> Priority: Major
>
> It would be very useful to have set and map implementations that accepts
> points and vectors as keys and use "fuzzy" look up logic, where values are
> compared using a precision context. This would have uses in a number of
> situations, including the implementation of GEOMETRY-110.
> Options for the implementation of such classes include
> * BSP trees (as already implemented)
> * k-d trees
> * quadtrees/octrees
> * r-trees
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
