Lucene - Core
  1. Lucene - Core
  2. LUCENE-6519

BKD polygon queries should avoid per-hit filtering when cell is fully enclosed

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 5.3, 6.0
    • Component/s: modules/sandbox
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      In LUCENE-6481, Nicholas Knize added methods to test for the relationship between an axis-aligned rect vs the query polygon, e.g. is the rect fully contained by the polygon, overlaps its boundaries, or fully outside the polygon.

      I think we should also use those methods to speed up BKDPointInPolygonQuery, to decide on recursively visiting the tree, how to handle the leaf blocks under internal nodes.

      1. LUCENE-6519.patch
        10 kB
        Michael McCandless
      2. LUCENE-6519.patch
        18 kB
        Michael McCandless

        Activity

        Hide
        Michael McCandless added a comment -

        Patch, just pulling over code from LUCENE-6481 ... once that issue is done I'll refactor to share in GeoUtils.

        Show
        Michael McCandless added a comment - Patch, just pulling over code from LUCENE-6481 ... once that issue is done I'll refactor to share in GeoUtils.
        Hide
        Michael McCandless added a comment -

        I haven't tested performance improvement from this but I expect it's sizable, since it means all ancestors from a tree node can now skip filtering per-hit.

        Show
        Michael McCandless added a comment - I haven't tested performance improvement from this but I expect it's sizable, since it means all ancestors from a tree node can now skip filtering per-hit.
        Hide
        Michael McCandless added a comment -

        I made a 3rd "BKD tree in Lucene" video to visualize the improvement from this change: https://plus.google.com/+MichaelMcCandless/posts/GB843diupeT

        Show
        Michael McCandless added a comment - I made a 3rd "BKD tree in Lucene" video to visualize the improvement from this change: https://plus.google.com/+MichaelMcCandless/posts/GB843diupeT
        Hide
        Michael McCandless added a comment -

        New patch, refactored to use the methods in GeoUtils from LUCENE-6481, I think it's ready.

        This should make polygon query with BKD much faster, since it now only does the full poly check for those points in leaf cells that cross the polygon boundary.

        Show
        Michael McCandless added a comment - New patch, refactored to use the methods in GeoUtils from LUCENE-6481 , I think it's ready. This should make polygon query with BKD much faster, since it now only does the full poly check for those points in leaf cells that cross the polygon boundary.
        Hide
        ASF subversion and git services added a comment -

        Commit 1684719 from Michael McCandless in branch 'dev/trunk'
        [ https://svn.apache.org/r1684719 ]

        LUCENE-6519: make BKDPointInPolygonQueries much faster: avoid the per-hit polygon check when a leaf cell is fully contained by the polygon

        Show
        ASF subversion and git services added a comment - Commit 1684719 from Michael McCandless in branch 'dev/trunk' [ https://svn.apache.org/r1684719 ] LUCENE-6519 : make BKDPointInPolygonQueries much faster: avoid the per-hit polygon check when a leaf cell is fully contained by the polygon
        Hide
        ASF subversion and git services added a comment -

        Commit 1684724 from Michael McCandless in branch 'dev/branches/branch_5x'
        [ https://svn.apache.org/r1684724 ]

        LUCENE-6519: make BKDPointInPolygonQueries much faster: avoid the per-hit polygon check when a leaf cell is fully contained by the polygon

        Show
        ASF subversion and git services added a comment - Commit 1684724 from Michael McCandless in branch 'dev/branches/branch_5x' [ https://svn.apache.org/r1684724 ] LUCENE-6519 : make BKDPointInPolygonQueries much faster: avoid the per-hit polygon check when a leaf cell is fully contained by the polygon
        Hide
        Shalin Shekhar Mangar added a comment -

        Bulk close for 5.3.0 release

        Show
        Shalin Shekhar Mangar added a comment - Bulk close for 5.3.0 release

          People

          • Assignee:
            Michael McCandless
            Reporter:
            Michael McCandless
          • Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development