lucene-java-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Mike Hansen <>
Subject Re: Spatial Search with Nested Polygons
Date Fri, 27 Mar 2015 04:27:27 GMT
On Thu, Mar 26, 2015 at 9:06 PM,
<> 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.


To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message