Improve GeoPointDistanceQuery performance [LUCENE-7663]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
GeoPoint queries currently use only the bounding box for filtering.
But the query circle is only roughly 80% of the bounding box, so we could be roughly 20% faster. Furthermore, the current approach requires splitting the box if it crosses the date line.
> Schubert, E., Zimek, A., & Kriegel, H. P. (2013, August). Geodetic distance queries on r-trees for indexing geographic data. In International Symposium on Spatial and Temporal Databases (pp. 146-164).
The minimum spherical distance of a point to a rectangle is given ("Algorithm 2: Optimized Minimum Distance Point to MBR"). Rectangles whose minimum distance is larger than the query radius can be skipped. The authors used the R-tree, but it will work with any bounding box, so it can be used in CellComparator#relate.
It's not very complex - a few case distinctions, and then either Haversine distance, or cross-track-distance. So the cost ist comparable to Haversine.
This could be added as GeoRelationUtils.pointToRectMinimumDistance, for example.
This approach can also be used to priorize rectangles, for top-k search.
---
Migrated from [LUCENE-7663](https://issues.apache.org/jira/browse/LUCENE-7663) by Erich Schubert, updated Jan 28 2017
Contributor guide
Research direction
Start with GeoPointDistanceQuery and inspect CellComparator#relate, where bounding-box filtering is performed. Read the cited minimum-distance algorithm and consider GeoRelationUtils.pointToRectMinimumDistance; done means distance-aware rectangle filtering avoids unnecessary date-line splitting while preserving query results and performance.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- performance, search
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100