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, 5.0
    • 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

        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.
        Hide
        Uwe Schindler added a comment -

        Closed after release.

        Show
        Uwe Schindler added a comment - Closed after release.

          People

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

            Dates

            • Created:
              Updated:
              Resolved:

              Development