Lucene - Core
  1. Lucene - Core
  2. LUCENE-4916

Spatial WithinPrefixTreeFilter can too eagerly find false-positive

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 4.3, Trunk
    • Component/s: modules/spatial
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      The recently committed WithinPrefixTreeFilter can sometimes match a false-positive due to the grid approximation technique. Some of this is normal. But if an indexed shape has any of its leaf detail levels "simplified" (removed) up to a higher level, then a false-positive match can occur that is a little too eager when one of those cells that were simplified-away don't intersect the query shape, and thus shouldn't be considered a match for this predicate.

      Marking as "Minor" because it should be quite rare, and when it does occur, the answer (a match) will usually appear close-enough due to the grid approximation that it's not a totally inaccurate answer. I found this problem via extensive randomized testing. I want to fix it because it should make my new tests pass

        Activity

        Transition Time In Source Status Execution Times Last Executer Last Execution Date
        Open Open Resolved Resolved
        11h 16m 1 David Smiley 08/Apr/13 17:50
        Resolved Resolved Closed Closed
        31d 17h 43m 1 Uwe Schindler 10/May/13 11:34
        Uwe Schindler made changes -
        Status Resolved [ 5 ] Closed [ 6 ]
        Hide
        Uwe Schindler added a comment -

        Closed after release.

        Show
        Uwe Schindler added a comment - Closed after release.
        David Smiley made changes -
        Status Open [ 1 ] Resolved [ 5 ]
        Fix Version/s 5.0 [ 12321663 ]
        Fix Version/s 4.3 [ 12324143 ]
        Resolution Fixed [ 1 ]
        David Smiley made changes -
        Field Original Value New Value
        Attachment LUCENE-4916__Spatial_Within_RPT_and_shape_simplification.patch [ 12577544 ]
        Hide
        David Smiley added a comment -

        The attached patch fixes this issue, and includes a testcase. The approach has room for further optimization.

        Although unrelated, I found it possible for AbstractVisitingPrefixTreeFilter to have a minimum configurable scan level of 0 (formerly 1). I made this change too; it enabled the aforementioned test to be a little more thorough.

        Show
        David Smiley added a comment - The attached patch fixes this issue, and includes a testcase. The approach has room for further optimization. Although unrelated, I found it possible for AbstractVisitingPrefixTreeFilter to have a minimum configurable scan level of 0 (formerly 1). I made this change too; it enabled the aforementioned test to be a little more thorough.
        David Smiley created issue -

          People

          • Assignee:
            David Smiley
            Reporter:
            David Smiley
          • Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development