[SEDONA-453] Performance degrade when indexing points using Quadtree

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.5.1
• Labels: pull-request-available
• Assignee: Unassigned
• Reporter: Kristin Cowalcijk
• Created: 21/Dec/23 13:18
• Updated: 13/Jan/24 23:56
• Resolved: 13/Jan/24 23:56

Description

We found that the index efficiency of Quadtree drastically degrades when indexing datasets made up of points. The index returns way more candidates than expected when querying the Quadtree using envelopes. The reason is that JTS Quadtree automatically expands indexed envelopes by 0.5 if the envelope has zero width and height (see Quadtree.java#L61-L96), this makes the indexed envelopes of points are way larger than necessary, especially when indexed points are WGS84 coordinates.

Suppose that we are indexing the following dataset using Quadtree:

The envelopes indexed by Quadtree happens to be something like this:

One possible workaround for this problem is to manually extend envelopes with 0 width or height by 1e-3. This will prevent JTS Quadtree from extending the envelopes by 0.5, and 1e-3 is small enough to cope with the most common use cases while not increasing the size of the Quadtree too much.

Maybe we should change the default index type sedona.global.index from quadtree to rtree, since STRtree has better performance in most cases and does not have such pitfalls.

Issue Links

• links to: GitHub Pull Request #1158