Spatial Search with Nested Polygons

[Mike Hansen <mh...@gmail.com>]

I was wondering about the feasibility / difficultly of implementing a
solution to the following problem with Lucene.

For each document, I have a series of nested polygons each associated
with a numerical value.  My search query gives a point, and I want to
return all of the documents whose largest polygon contains the point
(that part is easy).  Additionally, I'd like to have access to the
numerical value of the smallest polygon which contains the point
(something like makeDistanceValueSource).

Thanks,
--Mike

---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org

Re: Spatial Search with Nested Polygons

["david.w.smiley@gmail.com" <da...@gmail.com>]

On Fri, Mar 27, 2015 at 12:27 AM, Mike Hansen <mh...@gmail.com> wrote:

> There are a few things which could probably help with performance.
> Each document has only around say 30 polygons. You could do a binary
> search which would help reduce the cost. Additionally, I have a
> distinguished point contained inside of all the nested polygons so I
> can pre-compute the minimum and maximum distances from that point to
> the edge of the polygon and use that to also reduce the number of
> containment checks to do.  I expect that there will be on the order to
> 500-1000 documents considered for each search.
>

Oh right, they are *nested*; I overlooked that.  I like your binary-search
plan — makes sense.

~ David Smiley
Freelance Apache Lucene/Solr Search Consultant/Developer
http://www.linkedin.com/in/davidwsmiley

Re: Spatial Search with Nested Polygons

[Mike Hansen <mh...@gmail.com>]

On Thu, Mar 26, 2015 at 9:06 PM, david.w.smiley@gmail.com
<da...@gmail.com> wrote:
> The second, (non-easy) part seems like it could be pretty slow:
>
> To determine “the smallest polygon which contains the point” for the
> current matching document, you’d have to iterate over them in
> smallest-to-largest-1 order and check containment, so that you know which
> corresponding value to return.  There will be a performance hit for sure.

There are a few things which could probably help with performance.
Each document has only around say 30 polygons. You could do a binary
search which would help reduce the cost. Additionally, I have a
distinguished point contained inside of all the nested polygons so I
can pre-compute the minimum and maximum distances from that point to
the edge of the polygon and use that to also reduce the number of
containment checks to do.  I expect that there will be on the order to
500-1000 documents considered for each search.

> This sounds like a custom ValueSource/FunctionValues that does that logic…
> perhaps by grabbing the shapes from SerializedDVStrategy’s shape providing
> ValueSource.  If you provide the shapes using a Spatial4j ShapeCollection
> with the order from biggest to smallest, you can know the index of which
> shape matches, and then pull the i-th numeric value you need from a list of
> numbers in BinaryDocValues.  The largest shape could be kept out of here
> since you don’t need it.

Thanks -- this is very helpful.

--Mike

---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org

Re: Spatial Search with Nested Polygons

["david.w.smiley@gmail.com" <da...@gmail.com>]

Hi Mike,

The second, (non-easy) part seems like it could be pretty slow:

Additionally, I'd like to have access to the
> numerical value of the smallest polygon which contains the point
> (something like makeDistanceValueSource).


To determine “the smallest polygon which contains the point” for the
current matching document, you’d have to iterate over them in
smallest-to-largest-1 order and check containment, so that you know which
corresponding value to return.  There will be a performance hit for sure.
This sounds like a custom ValueSource/FunctionValues that does that logic…
perhaps by grabbing the shapes from SerializedDVStrategy’s shape providing
ValueSource.  If you provide the shapes using a Spatial4j ShapeCollection
with the order from biggest to smallest, you can know the index of which
shape matches, and then pull the i-th numeric value you need from a list of
numbers in BinaryDocValues.  The largest shape could be kept out of here
since you don’t need it.

~ David Smiley
Freelance Apache Lucene/Solr Search Consultant/Developer
http://www.linkedin.com/in/davidwsmiley

On Thu, Mar 26, 2015 at 11:47 PM, Mike Hansen <mh...@gmail.com> wrote:

> I was wondering about the feasibility / difficultly of implementing a
> solution to the following problem with Lucene.
>
> For each document, I have a series of nested polygons each associated
> with a numerical value.  My search query gives a point, and I want to
> return all of the documents whose largest polygon contains the point
> (that part is easy).  Additionally, I'd like to have access to the
> numerical value of the smallest polygon which contains the point
> (something like makeDistanceValueSource).
>
> Thanks,
> --Mike
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>
>