Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-7663

Improve GeoPointDistanceQuery performance

    Details

    • Type: Improvement
    • Status: Open
    • Priority: Minor
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: None
    • Labels:
      None
    • Lucene Fields:
      New

      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.

        Attachments

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              erich.schubert Erich Schubert
            • Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

              • Created:
                Updated: