Lucene - Core
  1. Lucene - Core
  2. LUCENE-4550

For extremely wide shapes (> 180 degrees) distErrPct is not used correctly

    Details

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

      Description

      When a shape is given to a PrefixTreeStrategy (index or query time), it needs to know how many levels down the prefix tree to go for a target precision (distErrPct). distErrPct is basically a fraction of the radius of the shape, defaulting to 2.5% (0.0025).

      If the shape presented is extremely wide, > 180 degrees, then the internal calculations in SpatialArgs.calcDistanceFromErrPct(...) will wrongly measure the shape's size as having width < 180 degrees, yielding more accuracy than intended. Given that this happens for unrealistic shape sizes and results in more accuracy, I am flagging this as "minor", but a bug nonetheless. Indeed, this was discovered as a result of someone using lucene-spatial incorrectly, not for an actual shape they have. But in the extreme [erroneous] case they had, they had 566k terms generated, when it should have been ~1k tops.

        Activity

        Hide
        David Smiley added a comment -

        A solution is to calculate the distance from a bbox corner to its center, instead of the current algorithm which takes half of the distance from opposite corners. The only small issue to consider is that the distance from a bbox corner to its center will vary up to ~4x (worse case) depending on wether you take a top corner or bottom corner, so I could do both and take the shorter (resulting in a little more accuracy than taking the longer).

        Show
        David Smiley added a comment - A solution is to calculate the distance from a bbox corner to its center, instead of the current algorithm which takes half of the distance from opposite corners. The only small issue to consider is that the distance from a bbox corner to its center will vary up to ~4x (worse case) depending on wether you take a top corner or bottom corner, so I could do both and take the shorter (resulting in a little more accuracy than taking the longer).
        Hide
        David Smiley added a comment -

        Bug fixed. I'll commit today.

        Show
        David Smiley added a comment - Bug fixed. I'll commit today.
        Hide
        David Smiley added a comment -

        CHANGES.txt entry will be as follows:

        • LUCENE-4550: Shapes wider than 180 degrees would use too much accuracy for the PrefixTree based SpatialStrategy. For a pathological case of nearly 360 degrees and barely any height, it would generate so many indexed terms (> 500k) that it could even cause an OutOfMemoryError. Fixed. (David Smiley)
        Show
        David Smiley added a comment - CHANGES.txt entry will be as follows: LUCENE-4550 : Shapes wider than 180 degrees would use too much accuracy for the PrefixTree based SpatialStrategy. For a pathological case of nearly 360 degrees and barely any height, it would generate so many indexed terms (> 500k) that it could even cause an OutOfMemoryError. Fixed. (David Smiley)
        Hide
        Commit Tag Bot added a comment -

        [trunk commit] David Wayne Smiley
        http://svn.apache.org/viewvc?view=revision&revision=1437182

        LUCENE-4550: fix SpatialArgs.calcDistanceFromErrPct

        Show
        Commit Tag Bot added a comment - [trunk commit] David Wayne Smiley http://svn.apache.org/viewvc?view=revision&revision=1437182 LUCENE-4550 : fix SpatialArgs.calcDistanceFromErrPct
        Hide
        Commit Tag Bot added a comment -

        [branch_4x commit] David Wayne Smiley
        http://svn.apache.org/viewvc?view=revision&revision=1437185

        LUCENE-4550: fix SpatialArgs.calcDistanceFromErrPct

        Show
        Commit Tag Bot added a comment - [branch_4x commit] David Wayne Smiley http://svn.apache.org/viewvc?view=revision&revision=1437185 LUCENE-4550 : fix SpatialArgs.calcDistanceFromErrPct
        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:
            1 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development