[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17457773#comment-17457773
]
Matt Juntunen commented on GEOMETRY-142:
----------------------------------------
I've implemented a standard {{KDTree}} and a subclass named
{{RebuildingKDTree}} that rebuilds the tree every time the tree size changes by
a multiple of 2. The rebuilding algorithm is a very simple, brute-force
algorithm so there is still a lot of work to do there. Note that these trees do
_not_ split on all 3 dimensions like I was mentioning before. The algorithms
are much simpler when only a single dimension is split at a time.
Below are the results from one of the performance tests.
||Benchmark||(impl)||(pointDist)||(randomSeed)||(randomized)||Mode||Cnt||Score||Error||Units||
|PointMapDataStructurePerformance.get|treemap|block|1|true|avgt|5|1901011.695|±
267736.431|ns/op|
|PointMapDataStructurePerformance.get|varoctree|block|1|true|avgt|5|2216097.740|±
30461.346|ns/op|
|PointMapDataStructurePerformance.get|kdtree|block|1|true|avgt|5|9498722.093|±
648666.885|ns/op|
|PointMapDataStructurePerformance.get|rebuilding-kdtree|block|1|true|avgt|5|6910157.540|±
649841.106|ns/op|
|PointMapDataStructurePerformance.put|treemap|block|1|true|avgt|5|1918716.941|±
51856.642|ns/op|
|PointMapDataStructurePerformance.put|varoctree|block|1|true|avgt|5|2228210.059|±
48411.970|ns/op|
|PointMapDataStructurePerformance.put|kdtree|block|1|true|avgt|5|10285677.435|±
213900.413|ns/op|
|PointMapDataStructurePerformance.put|rebuilding-kdtree|block|1|true|avgt|5|7505692.915|±
340146.696|ns/op|
|PointMapDataStructurePerformance.remove|treemap|block|1|true|avgt|5|73542.543|±
15082.714|ns/op|
|PointMapDataStructurePerformance.remove|varoctree|block|1|true|avgt|5|2037858.976|±
430068.967|ns/op|
|PointMapDataStructurePerformance.remove|kdtree|block|1|true|avgt|5|88291.325|±
15735.485|ns/op|
|PointMapDataStructurePerformance.remove|rebuilding-kdtree|block|1|true|avgt|5|111478.176|±
14909.521|ns/op|
*Observations*
- Varoctree is actually not that bad for get and put. I thought it would be
much worse compared to the other ones.
- Rebuilding the tree periodically improved the KD tree performance except on
remove.
*Next steps*
- Work on improving the performance of the rebuild algorithm.
- Continue researching alternative algorithms.
> 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)
