You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by Karl Wright <da...@gmail.com> on 2015/01/22 21:08:23 UTC
Potential contribution: Geo 3d package
I would like to explore contributing a geo3d package to Lucene. This can
be used in conjunction with Lucene search, both for generating geohashes
(via spatial4j) for complex geographic shapes, as well as limiting results
resulting from those queries to those results within the exact shape in
highly performant ways.
The package uses 3d planar geometry to do its magic, which basically limits
computation necessary to determine membership (once a shape has been
initialized, of course) to only multiplications and additions, which makes
it feasible to construct a performant BoostSource-based filter for
geographic shapes. The math is somewhat more involved when generating
geohashes, but is still more than fast enough to do a good job.
For reasons that are not really technical, the only open-source project
that I can contribute this to initially is Lucene. If people believe it
would be a valuable addition, and would like me to create a ticket and
attach a patch, please respond.
Thanks,
Karl Wright
Re: Potential contribution: Geo 3d package
Posted by "david.w.smiley@gmail.com" <da...@gmail.com>.
Ok; I get it. Please go right ahead and create an issue with the source
attached.
p.s. I was half-expecting you to mention you had some sort of quadrangle
thing…. (memories from 5 years ago when you worked at MetaCarta) :-)
~ David Smiley
Freelance Apache Lucene/Solr Search Consultant/Developer
http://www.linkedin.com/in/davidwsmiley
On Thu, Jan 22, 2015 at 4:46 PM, Karl Wright <da...@gmail.com> wrote:
> Hi David,
>
> What I'm open-sourcing is the computational geometry package which
> provides the _underpinnings_ of both geo hash generation and shape
> filtering in our system. What I would expect a user to index are geohashes
> generated by Lucene's spatial4j integration, using a spatial4j Shape which
> is trivial and which I can contribute separately only (because it has other
> ties in our world that I am *not* contributing). The user will also need
> to index DocValues fields for each document that contain the X, Y, and Z
> values of the items in question, which can be generated by the package I'm
> contributing as well. For filtering to the shape, there are a number of
> approaches possible; we have a BoostSource implementation that does this
> but which requires a FunctionQuery to be part of the search query.
>
> If you are in favor, I'll create a ticket and attach the library.
>
> Karl
>
>
> On Thu, Jan 22, 2015 at 4:01 PM, david.w.smiley@gmail.com <
> david.w.smiley@gmail.com> wrote:
>
>> Okay. Since this is not _already_ implementing a Spatial4j shape, I can
>> only presume this isn't using SpatialPrefixTree &
>> RecursivePrefixTreeStrategy etc. So how is index & search done? Or is
>> that simply not a part of what you are open-sourcing here — this
>> open-source release is just the computational geometry work you’ve done?
>> If I’m right can you reveal how that’s working in your system or is that
>> not for public release?
>>
>> Any way, to make it abundantly clear I’m a strong +1 to this based on
>> what you’ve had to say so far.
>>
>> ~ David Smiley
>> Freelance Apache Lucene/Solr Search Consultant/Developer
>> http://www.linkedin.com/in/davidwsmiley
>>
>> On Thu, Jan 22, 2015 at 3:42 PM, Karl Wright <da...@gmail.com> wrote:
>>
>>> I should make it clear: geo3d does not do geo hashing by itself -- it
>>> simply provides support for determining relationships between shapes and
>>> traditional bounding boxes, which is what Spatial4J needs to support Lucene
>>> geo hashing.
>>>
>>> Karl
>>>
>>> On Thu, Jan 22, 2015 at 3:36 PM, Karl Wright <da...@gmail.com> wrote:
>>>
>>>> Hi David,
>>>>
>>>> The package itself is independent of spatial4j, but a GeoShape
>>>> implementation of spatial4j Shape is trivial; I can contribute that
>>>> separately.
>>>>
>>>> Karl
>>>>
>>>>
>>>> On Thu, Jan 22, 2015 at 3:27 PM, david.w.smiley@gmail.com <
>>>> david.w.smiley@gmail.com> wrote:
>>>>
>>>>> Nice Karl! I’d love to learn more about this. Does the shapes here
>>>>> implement a Spatial4j Shape and thus would work with SpatialPrefixTree &
>>>>> friends for index & search? If not, what is the search side of the
>>>>> equation here?
>>>>>
>>>>> ~ David Smiley
>>>>> Freelance Apache Lucene/Solr Search Consultant/Developer
>>>>> http://www.linkedin.com/in/davidwsmiley
>>>>>
>>>>> On Thu, Jan 22, 2015 at 3:08 PM, Karl Wright <da...@gmail.com>
>>>>> wrote:
>>>>>
>>>>>> I would like to explore contributing a geo3d package to Lucene. This
>>>>>> can be used in conjunction with Lucene search, both for generating
>>>>>> geohashes (via spatial4j) for complex geographic shapes, as well as
>>>>>> limiting results resulting from those queries to those results within the
>>>>>> exact shape in highly performant ways.
>>>>>>
>>>>>> The package uses 3d planar geometry to do its magic, which basically
>>>>>> limits computation necessary to determine membership (once a shape has been
>>>>>> initialized, of course) to only multiplications and additions, which makes
>>>>>> it feasible to construct a performant BoostSource-based filter for
>>>>>> geographic shapes. The math is somewhat more involved when generating
>>>>>> geohashes, but is still more than fast enough to do a good job.
>>>>>>
>>>>>> For reasons that are not really technical, the only open-source
>>>>>> project that I can contribute this to initially is Lucene. If people
>>>>>> believe it would be a valuable addition, and would like me to create a
>>>>>> ticket and attach a patch, please respond.
>>>>>>
>>>>>> Thanks,
>>>>>> Karl Wright
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>
Re: Potential contribution: Geo 3d package
Posted by Karl Wright <da...@gmail.com>.
Hi David,
I think you may be thinking of QTM. This package does not use QTM because
spatial4j's geo hash generation uses lat/lon bounding boxes. ;-)
See LUCENE-6196.
Karl
On Thu, Jan 22, 2015 at 4:46 PM, Karl Wright <da...@gmail.com> wrote:
> Hi David,
>
> What I'm open-sourcing is the computational geometry package which
> provides the _underpinnings_ of both geo hash generation and shape
> filtering in our system. What I would expect a user to index are geohashes
> generated by Lucene's spatial4j integration, using a spatial4j Shape which
> is trivial and which I can contribute separately only (because it has other
> ties in our world that I am *not* contributing). The user will also need
> to index DocValues fields for each document that contain the X, Y, and Z
> values of the items in question, which can be generated by the package I'm
> contributing as well. For filtering to the shape, there are a number of
> approaches possible; we have a BoostSource implementation that does this
> but which requires a FunctionQuery to be part of the search query.
>
> If you are in favor, I'll create a ticket and attach the library.
>
> Karl
>
>
> On Thu, Jan 22, 2015 at 4:01 PM, david.w.smiley@gmail.com <
> david.w.smiley@gmail.com> wrote:
>
>> Okay. Since this is not _already_ implementing a Spatial4j shape, I can
>> only presume this isn't using SpatialPrefixTree &
>> RecursivePrefixTreeStrategy etc. So how is index & search done? Or is
>> that simply not a part of what you are open-sourcing here — this
>> open-source release is just the computational geometry work you’ve done?
>> If I’m right can you reveal how that’s working in your system or is that
>> not for public release?
>>
>> Any way, to make it abundantly clear I’m a strong +1 to this based on
>> what you’ve had to say so far.
>>
>> ~ David Smiley
>> Freelance Apache Lucene/Solr Search Consultant/Developer
>> http://www.linkedin.com/in/davidwsmiley
>>
>> On Thu, Jan 22, 2015 at 3:42 PM, Karl Wright <da...@gmail.com> wrote:
>>
>>> I should make it clear: geo3d does not do geo hashing by itself -- it
>>> simply provides support for determining relationships between shapes and
>>> traditional bounding boxes, which is what Spatial4J needs to support Lucene
>>> geo hashing.
>>>
>>> Karl
>>>
>>> On Thu, Jan 22, 2015 at 3:36 PM, Karl Wright <da...@gmail.com> wrote:
>>>
>>>> Hi David,
>>>>
>>>> The package itself is independent of spatial4j, but a GeoShape
>>>> implementation of spatial4j Shape is trivial; I can contribute that
>>>> separately.
>>>>
>>>> Karl
>>>>
>>>>
>>>> On Thu, Jan 22, 2015 at 3:27 PM, david.w.smiley@gmail.com <
>>>> david.w.smiley@gmail.com> wrote:
>>>>
>>>>> Nice Karl! I’d love to learn more about this. Does the shapes here
>>>>> implement a Spatial4j Shape and thus would work with SpatialPrefixTree &
>>>>> friends for index & search? If not, what is the search side of the
>>>>> equation here?
>>>>>
>>>>> ~ David Smiley
>>>>> Freelance Apache Lucene/Solr Search Consultant/Developer
>>>>> http://www.linkedin.com/in/davidwsmiley
>>>>>
>>>>> On Thu, Jan 22, 2015 at 3:08 PM, Karl Wright <da...@gmail.com>
>>>>> wrote:
>>>>>
>>>>>> I would like to explore contributing a geo3d package to Lucene. This
>>>>>> can be used in conjunction with Lucene search, both for generating
>>>>>> geohashes (via spatial4j) for complex geographic shapes, as well as
>>>>>> limiting results resulting from those queries to those results within the
>>>>>> exact shape in highly performant ways.
>>>>>>
>>>>>> The package uses 3d planar geometry to do its magic, which basically
>>>>>> limits computation necessary to determine membership (once a shape has been
>>>>>> initialized, of course) to only multiplications and additions, which makes
>>>>>> it feasible to construct a performant BoostSource-based filter for
>>>>>> geographic shapes. The math is somewhat more involved when generating
>>>>>> geohashes, but is still more than fast enough to do a good job.
>>>>>>
>>>>>> For reasons that are not really technical, the only open-source
>>>>>> project that I can contribute this to initially is Lucene. If people
>>>>>> believe it would be a valuable addition, and would like me to create a
>>>>>> ticket and attach a patch, please respond.
>>>>>>
>>>>>> Thanks,
>>>>>> Karl Wright
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>
Re: Potential contribution: Geo 3d package
Posted by Karl Wright <da...@gmail.com>.
Hi David,
What I'm open-sourcing is the computational geometry package which provides
the _underpinnings_ of both geo hash generation and shape filtering in our
system. What I would expect a user to index are geohashes generated by
Lucene's spatial4j integration, using a spatial4j Shape which is trivial
and which I can contribute separately only (because it has other ties in
our world that I am *not* contributing). The user will also need to index
DocValues fields for each document that contain the X, Y, and Z values of
the items in question, which can be generated by the package I'm
contributing as well. For filtering to the shape, there are a number of
approaches possible; we have a BoostSource implementation that does this
but which requires a FunctionQuery to be part of the search query.
If you are in favor, I'll create a ticket and attach the library.
Karl
On Thu, Jan 22, 2015 at 4:01 PM, david.w.smiley@gmail.com <
david.w.smiley@gmail.com> wrote:
> Okay. Since this is not _already_ implementing a Spatial4j shape, I can
> only presume this isn't using SpatialPrefixTree &
> RecursivePrefixTreeStrategy etc. So how is index & search done? Or is
> that simply not a part of what you are open-sourcing here — this
> open-source release is just the computational geometry work you’ve done?
> If I’m right can you reveal how that’s working in your system or is that
> not for public release?
>
> Any way, to make it abundantly clear I’m a strong +1 to this based on what
> you’ve had to say so far.
>
> ~ David Smiley
> Freelance Apache Lucene/Solr Search Consultant/Developer
> http://www.linkedin.com/in/davidwsmiley
>
> On Thu, Jan 22, 2015 at 3:42 PM, Karl Wright <da...@gmail.com> wrote:
>
>> I should make it clear: geo3d does not do geo hashing by itself -- it
>> simply provides support for determining relationships between shapes and
>> traditional bounding boxes, which is what Spatial4J needs to support Lucene
>> geo hashing.
>>
>> Karl
>>
>> On Thu, Jan 22, 2015 at 3:36 PM, Karl Wright <da...@gmail.com> wrote:
>>
>>> Hi David,
>>>
>>> The package itself is independent of spatial4j, but a GeoShape
>>> implementation of spatial4j Shape is trivial; I can contribute that
>>> separately.
>>>
>>> Karl
>>>
>>>
>>> On Thu, Jan 22, 2015 at 3:27 PM, david.w.smiley@gmail.com <
>>> david.w.smiley@gmail.com> wrote:
>>>
>>>> Nice Karl! I’d love to learn more about this. Does the shapes here
>>>> implement a Spatial4j Shape and thus would work with SpatialPrefixTree &
>>>> friends for index & search? If not, what is the search side of the
>>>> equation here?
>>>>
>>>> ~ David Smiley
>>>> Freelance Apache Lucene/Solr Search Consultant/Developer
>>>> http://www.linkedin.com/in/davidwsmiley
>>>>
>>>> On Thu, Jan 22, 2015 at 3:08 PM, Karl Wright <da...@gmail.com>
>>>> wrote:
>>>>
>>>>> I would like to explore contributing a geo3d package to Lucene. This
>>>>> can be used in conjunction with Lucene search, both for generating
>>>>> geohashes (via spatial4j) for complex geographic shapes, as well as
>>>>> limiting results resulting from those queries to those results within the
>>>>> exact shape in highly performant ways.
>>>>>
>>>>> The package uses 3d planar geometry to do its magic, which basically
>>>>> limits computation necessary to determine membership (once a shape has been
>>>>> initialized, of course) to only multiplications and additions, which makes
>>>>> it feasible to construct a performant BoostSource-based filter for
>>>>> geographic shapes. The math is somewhat more involved when generating
>>>>> geohashes, but is still more than fast enough to do a good job.
>>>>>
>>>>> For reasons that are not really technical, the only open-source
>>>>> project that I can contribute this to initially is Lucene. If people
>>>>> believe it would be a valuable addition, and would like me to create a
>>>>> ticket and attach a patch, please respond.
>>>>>
>>>>> Thanks,
>>>>> Karl Wright
>>>>>
>>>>>
>>>>
>>>
>>
>
Re: Potential contribution: Geo 3d package
Posted by "david.w.smiley@gmail.com" <da...@gmail.com>.
Okay. Since this is not _already_ implementing a Spatial4j shape, I can
only presume this isn't using SpatialPrefixTree &
RecursivePrefixTreeStrategy etc. So how is index & search done? Or is
that simply not a part of what you are open-sourcing here — this
open-source release is just the computational geometry work you’ve done?
If I’m right can you reveal how that’s working in your system or is that
not for public release?
Any way, to make it abundantly clear I’m a strong +1 to this based on what
you’ve had to say so far.
~ David Smiley
Freelance Apache Lucene/Solr Search Consultant/Developer
http://www.linkedin.com/in/davidwsmiley
On Thu, Jan 22, 2015 at 3:42 PM, Karl Wright <da...@gmail.com> wrote:
> I should make it clear: geo3d does not do geo hashing by itself -- it
> simply provides support for determining relationships between shapes and
> traditional bounding boxes, which is what Spatial4J needs to support Lucene
> geo hashing.
>
> Karl
>
> On Thu, Jan 22, 2015 at 3:36 PM, Karl Wright <da...@gmail.com> wrote:
>
>> Hi David,
>>
>> The package itself is independent of spatial4j, but a GeoShape
>> implementation of spatial4j Shape is trivial; I can contribute that
>> separately.
>>
>> Karl
>>
>>
>> On Thu, Jan 22, 2015 at 3:27 PM, david.w.smiley@gmail.com <
>> david.w.smiley@gmail.com> wrote:
>>
>>> Nice Karl! I’d love to learn more about this. Does the shapes here
>>> implement a Spatial4j Shape and thus would work with SpatialPrefixTree &
>>> friends for index & search? If not, what is the search side of the
>>> equation here?
>>>
>>> ~ David Smiley
>>> Freelance Apache Lucene/Solr Search Consultant/Developer
>>> http://www.linkedin.com/in/davidwsmiley
>>>
>>> On Thu, Jan 22, 2015 at 3:08 PM, Karl Wright <da...@gmail.com> wrote:
>>>
>>>> I would like to explore contributing a geo3d package to Lucene. This
>>>> can be used in conjunction with Lucene search, both for generating
>>>> geohashes (via spatial4j) for complex geographic shapes, as well as
>>>> limiting results resulting from those queries to those results within the
>>>> exact shape in highly performant ways.
>>>>
>>>> The package uses 3d planar geometry to do its magic, which basically
>>>> limits computation necessary to determine membership (once a shape has been
>>>> initialized, of course) to only multiplications and additions, which makes
>>>> it feasible to construct a performant BoostSource-based filter for
>>>> geographic shapes. The math is somewhat more involved when generating
>>>> geohashes, but is still more than fast enough to do a good job.
>>>>
>>>> For reasons that are not really technical, the only open-source project
>>>> that I can contribute this to initially is Lucene. If people believe it
>>>> would be a valuable addition, and would like me to create a ticket and
>>>> attach a patch, please respond.
>>>>
>>>> Thanks,
>>>> Karl Wright
>>>>
>>>>
>>>
>>
>
Re: Potential contribution: Geo 3d package
Posted by Karl Wright <da...@gmail.com>.
I should make it clear: geo3d does not do geo hashing by itself -- it
simply provides support for determining relationships between shapes and
traditional bounding boxes, which is what Spatial4J needs to support Lucene
geo hashing.
Karl
On Thu, Jan 22, 2015 at 3:36 PM, Karl Wright <da...@gmail.com> wrote:
> Hi David,
>
> The package itself is independent of spatial4j, but a GeoShape
> implementation of spatial4j Shape is trivial; I can contribute that
> separately.
>
> Karl
>
>
> On Thu, Jan 22, 2015 at 3:27 PM, david.w.smiley@gmail.com <
> david.w.smiley@gmail.com> wrote:
>
>> Nice Karl! I’d love to learn more about this. Does the shapes here
>> implement a Spatial4j Shape and thus would work with SpatialPrefixTree &
>> friends for index & search? If not, what is the search side of the
>> equation here?
>>
>> ~ David Smiley
>> Freelance Apache Lucene/Solr Search Consultant/Developer
>> http://www.linkedin.com/in/davidwsmiley
>>
>> On Thu, Jan 22, 2015 at 3:08 PM, Karl Wright <da...@gmail.com> wrote:
>>
>>> I would like to explore contributing a geo3d package to Lucene. This
>>> can be used in conjunction with Lucene search, both for generating
>>> geohashes (via spatial4j) for complex geographic shapes, as well as
>>> limiting results resulting from those queries to those results within the
>>> exact shape in highly performant ways.
>>>
>>> The package uses 3d planar geometry to do its magic, which basically
>>> limits computation necessary to determine membership (once a shape has been
>>> initialized, of course) to only multiplications and additions, which makes
>>> it feasible to construct a performant BoostSource-based filter for
>>> geographic shapes. The math is somewhat more involved when generating
>>> geohashes, but is still more than fast enough to do a good job.
>>>
>>> For reasons that are not really technical, the only open-source project
>>> that I can contribute this to initially is Lucene. If people believe it
>>> would be a valuable addition, and would like me to create a ticket and
>>> attach a patch, please respond.
>>>
>>> Thanks,
>>> Karl Wright
>>>
>>>
>>
>
Re: Potential contribution: Geo 3d package
Posted by Karl Wright <da...@gmail.com>.
Hi David,
The package itself is independent of spatial4j, but a GeoShape
implementation of spatial4j Shape is trivial; I can contribute that
separately.
Karl
On Thu, Jan 22, 2015 at 3:27 PM, david.w.smiley@gmail.com <
david.w.smiley@gmail.com> wrote:
> Nice Karl! I’d love to learn more about this. Does the shapes here
> implement a Spatial4j Shape and thus would work with SpatialPrefixTree &
> friends for index & search? If not, what is the search side of the
> equation here?
>
> ~ David Smiley
> Freelance Apache Lucene/Solr Search Consultant/Developer
> http://www.linkedin.com/in/davidwsmiley
>
> On Thu, Jan 22, 2015 at 3:08 PM, Karl Wright <da...@gmail.com> wrote:
>
>> I would like to explore contributing a geo3d package to Lucene. This can
>> be used in conjunction with Lucene search, both for generating geohashes
>> (via spatial4j) for complex geographic shapes, as well as limiting results
>> resulting from those queries to those results within the exact shape in
>> highly performant ways.
>>
>> The package uses 3d planar geometry to do its magic, which basically
>> limits computation necessary to determine membership (once a shape has been
>> initialized, of course) to only multiplications and additions, which makes
>> it feasible to construct a performant BoostSource-based filter for
>> geographic shapes. The math is somewhat more involved when generating
>> geohashes, but is still more than fast enough to do a good job.
>>
>> For reasons that are not really technical, the only open-source project
>> that I can contribute this to initially is Lucene. If people believe it
>> would be a valuable addition, and would like me to create a ticket and
>> attach a patch, please respond.
>>
>> Thanks,
>> Karl Wright
>>
>>
>
Re: Potential contribution: Geo 3d package
Posted by "david.w.smiley@gmail.com" <da...@gmail.com>.
Nice Karl! I’d love to learn more about this. Does the shapes here
implement a Spatial4j Shape and thus would work with SpatialPrefixTree &
friends for index & search? If not, what is the search side of the
equation here?
~ David Smiley
Freelance Apache Lucene/Solr Search Consultant/Developer
http://www.linkedin.com/in/davidwsmiley
On Thu, Jan 22, 2015 at 3:08 PM, Karl Wright <da...@gmail.com> wrote:
> I would like to explore contributing a geo3d package to Lucene. This can
> be used in conjunction with Lucene search, both for generating geohashes
> (via spatial4j) for complex geographic shapes, as well as limiting results
> resulting from those queries to those results within the exact shape in
> highly performant ways.
>
> The package uses 3d planar geometry to do its magic, which basically
> limits computation necessary to determine membership (once a shape has been
> initialized, of course) to only multiplications and additions, which makes
> it feasible to construct a performant BoostSource-based filter for
> geographic shapes. The math is somewhat more involved when generating
> geohashes, but is still more than fast enough to do a good job.
>
> For reasons that are not really technical, the only open-source project
> that I can contribute this to initially is Lucene. If people believe it
> would be a valuable addition, and would like me to create a ticket and
> attach a patch, please respond.
>
> Thanks,
> Karl Wright
>
>
Re: Potential contribution: Geo 3d package
Posted by Michael McCandless <lu...@mikemccandless.com>.
+1, this sounds like a nice addition to Lucene's spatial module.
Even if it overlaps with what we have today, we can merge the two
approaches with time.
Mike McCandless
http://blog.mikemccandless.com
On Thu, Jan 22, 2015 at 3:08 PM, Karl Wright <da...@gmail.com> wrote:
> I would like to explore contributing a geo3d package to Lucene. This can be
> used in conjunction with Lucene search, both for generating geohashes (via
> spatial4j) for complex geographic shapes, as well as limiting results
> resulting from those queries to those results within the exact shape in
> highly performant ways.
>
> The package uses 3d planar geometry to do its magic, which basically limits
> computation necessary to determine membership (once a shape has been
> initialized, of course) to only multiplications and additions, which makes
> it feasible to construct a performant BoostSource-based filter for
> geographic shapes. The math is somewhat more involved when generating
> geohashes, but is still more than fast enough to do a good job.
>
> For reasons that are not really technical, the only open-source project that
> I can contribute this to initially is Lucene. If people believe it would be
> a valuable addition, and would like me to create a ticket and attach a
> patch, please respond.
>
> Thanks,
> Karl Wright
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org