apache / apache/lucene

Improve GeoPointDistanceQuery performance [LUCENE-7663]

Open
#8,714 3 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Minor type:enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.