subject:"\[jira\] \[Commented\] \(LUCENE\-8126\) Spatial prefix tree based on S2 geometry"

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-19 Thread Adrien Grand (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16405005#comment-16405005
 ] 

Adrien Grand commented on LUCENE-8126:
--

[~ivera] Can you set the "Fix Version/s" on this issue?

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 50m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-05 Thread ASF subversion and git services (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16386261#comment-16386261
 ] 

ASF subversion and git services commented on LUCENE-8126:
-

Commit c50a05becd62d620fcb2b39e8ac00eaee5e7f8f8 in lucene-solr's branch 
refs/heads/branch_7x from [~dsmiley]
[ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=c50a05b ]

LUCENE-8126: Add "s2" to SpatialPrefixTreeFactory lookup table

(cherry picked from commit e0d6465)


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 50m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-05 Thread ASF subversion and git services (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16386251#comment-16386251
 ] 

ASF subversion and git services commented on LUCENE-8126:
-

Commit e0d6465af94b6c6f7b8d570dee97c98de572c876 in lucene-solr's branch 
refs/heads/master from [~dsmiley]
[ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=e0d6465 ]

LUCENE-8126: Add "s2" to SpatialPrefixTreeFactory lookup table


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 50m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-05 Thread David Smiley (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16386196#comment-16386196
 ] 

David Smiley commented on LUCENE-8126:
--

I'll just do it; no point in asking you -- sorry

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 50m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-05 Thread David Smiley (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16386195#comment-16386195
 ] 

David Smiley commented on LUCENE-8126:
--

[~ivera] can you also please add a 2-line change to SpatialPrefixTreeFactory so 
that "s2" resolves to this new SPT Factory?

Perhaps in the future this class could be refactored to use the Java Service 
Provider framework like Lucene already uses it for codecs and various parts.

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 50m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-03 Thread David Smiley (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16384757#comment-16384757
 ] 

David Smiley commented on LUCENE-8126:
--

bq. Make prune code depend on this interface and not legacyCell. What do you 
think?

+1 -- lets get this simple change into 7.3; ehh?

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 50m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-03 Thread Ignacio Vera (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16384663#comment-16384663
 ] 

Ignacio Vera commented on LUCENE-8126:
--

I have come across this problem as well and it was in my next things to do.

S2 prefix tree has the same properties of the other trees : Cells at the same 
level are disjoint and a cell contains all child cells so it could be possible 
to prune bunchy leaves (and it will make the index lighter).

Unfortunately the current implementation only allows this for legacy cells. So 
my proposal is the following:

Create a new interface, that implements the Cell interface, and adds one method:

 
{code:java}
/**
 * Grid cells that share nothing with other cells when calling 
cell.getNextLevelCells() might
 * implement this interface. They will be eligible for prune bunchy leaves.
 */
public interface CellCanPrune extends Cell{

  /**
   * Return the number of children for the current cell.
   *
   * @return the number of children cell.
   */
  int getSubCellsSize();
}{code}
 

That is the only method required for prune bunchy leaves. Implementation for S2 
cells is trivial:

 
{code:java}
@Override
public int getSubCellsSize() {
if (cellId == null) { //root node
return 6;
}
return 4;
}{code}
 

Make prune code depend on this interface and not legacyCell. What do you think?

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 50m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-02 Thread David Smiley (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16384273#comment-16384273
 ] 

David Smiley commented on LUCENE-8126:
--

Nice to finally see this in!

I was trying to use this from Solr to try it out.  I went to one of our tests 
-- TestSolr4Spatial2 and ran it, after changing schema-spatial.xml so that the 
srtpgeom_geo3d field type looked as follows:
{code:xml}
  
{code}

But it doesn't work when given a non-point shape to index because of the 
default pruneLeafyBranches setting in RecursivePrefixTreeStrategy which only 
works with "LegacyPrefixTree" grids (the other 3 do).  Hmm.  Looking at the 
notes I put here long ago it seems that RPT Strategy should be modified to have 
it's constructor set {{this.pruneLeafyBranches = (grid instanceof 
LegacyPrefixTree)}}?

The actual exception thrown is here recursiveTraverseAndPrune:
{code:java}
  /** Returns true if cell was added as a leaf. If it wasn't it recursively 
descends. */
  private boolean recursiveTraverseAndPrune(Cell cell, Shape shape, int 
detailLevel, List result) {
// Important: this logic assumes Cells don't share anything with other 
cells when
// calling cell.getNextLevelCells(). This is only true for LegacyCell.
if (!(cell instanceof LegacyCell))
  throw new IllegalStateException("pruneLeafyBranches must be disabled for 
use with grid "+grid);
...
{code}
The comment about "This is only true for LegacyCell" should perhaps read "We 
know this is so for LegacyCell but don't know for other things."  Do you know 
if it's true for S2 [~ivera]?  Perhaps regardless better safe to not do this 
than do this pruning when it's not safe.

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 50m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-02 Thread ASF subversion and git services (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16383671#comment-16383671
 ] 

ASF subversion and git services commented on LUCENE-8126:
-

Commit fc51c1f2ef983ce4d8ba4894f822cc6f8fbc643d in lucene-solr's branch 
refs/heads/branch_7x from [~ivera]
[ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=fc51c1f ]

LUCENE-8126: fixed jar checksum


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 50m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-02 Thread ASF subversion and git services (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16383657#comment-16383657
 ] 

ASF subversion and git services commented on LUCENE-8126:
-

Commit ca2131573de4c8d127ea80fdb2bd37e00c87bbcc in lucene-solr's branch 
refs/heads/master from [~ivera]
[ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=ca21315 ]

LUCENE-8126: fixed jar checksum


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 50m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-02 Thread ASF subversion and git services (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16383422#comment-16383422
 ] 

ASF subversion and git services commented on LUCENE-8126:
-

Commit a281177f256fe4758b99306f74dc39c1bf82 in lucene-solr's branch 
refs/heads/master from [~ivera]
[ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=a281177 ]

LUCENE-8126: fix precommit


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 40m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-02 Thread ASF subversion and git services (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16383399#comment-16383399
 ] 

ASF subversion and git services commented on LUCENE-8126:
-

Commit e3032dd3fcc28570c5f9d2dab4961b5b07555912 in lucene-solr's branch 
refs/heads/master from [~ivera]
[ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=e3032dd ]

LUCENE-8126: New spatial prefix tree (SPT) based on google S2 geometry


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 40m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-03-02 Thread ASF subversion and git services (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16383398#comment-16383398
 ] 

ASF subversion and git services commented on LUCENE-8126:
-

Commit 1e86af061e41f1a7df1740f34ef58a1110626d96 in lucene-solr's branch 
refs/heads/branch_7x from [~ivera]
[ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=1e86af0 ]

LUCENE-8126: new spatial prefix tree (SPT) based on google S2 geometry


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 40m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-21 Thread David Smiley (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16371423#comment-16371423
 ] 

David Smiley commented on LUCENE-8126:
--

bq.  I am not sure that a different projection will help on this case, 
projection distorts the shapes as well as the cells so not sure how much much 
benefit we will get.

An experiment for another day I guess.  I'm more hopeful web-mercator will 
help.  Yes there is always distortion, but if the distortion is just overall 
size, then I think the cell-count shouldn't change.

bq. Healpix

Thanks for the reference; this looks cool!

RE benchmark; you said exactly this, which I can't track down but maybe I just 
don't know what to look for:

bq. I have added the performance test classes on the branch in case you want to 
have a look to check results are not bias.

bq. Anyway, it would be nice to have this SPT commited, so my question is which 
branches should I commit it? Not sure what is the policy here.

+1.  Do so to master & branch_7x.  This is standard practice for the vast 
majority of work.  If you _changed_ something that would break back-compat in 
unacceptable ways then such changes would belong only in master; but it's 
negotiable.

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 0.5h
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-20 Thread Ignacio Vera (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16369955#comment-16369955
 ] 

Ignacio Vera commented on LUCENE-8126:
--

They are in reality spherical polygons with 4 edges not "squares" (aka 
coordinate ranges which close to the poles are more like triangles). You can 
see in the diagram that at 60 degrees horizontal lines are big circles (they 
are slighltly curved on the equirectangular projection).  I am not sure that a 
different projection will help on this case, projection distorts the shapes as 
well as the cells so not sure how much much benefit we will get.

Heatmaps are fantastic to represent data but users needs to be careful as cells 
can represent different areas so results might be bias. In our case we do have 
heatmaps on the sphere but we are using Healpix 
([https://healpix.jpl.nasa.gov/)] to have equal area cells.

I am currently looking into a way to have a benchmark for STP similar to the 
geobenchmark for BKD trees. The difficult part here is all the different 
parameters you can set on a SPT.

{quote}

I'm having difficulty finding the benchmark; can you provide a link to the GH 
file?

{quote}

what are you looking for exactly?

 

Anyway, it would be nice to have this SPT commited, so my question is which 
branches should I commit it? Not sure what is the policy here.

 

 

 

 

 

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 0.5h
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-19 Thread David Smiley (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16369716#comment-16369716
 ] 

David Smiley commented on LUCENE-8126:
--

Thanks for investing the time into the illustrations [~ivera].  The diagram of 
the 3 prefix trees is very illustrative.  Usually when I think of people 
indexing "squares" I believe the square is aligned to lines of longitude and 
latitude... but this is not true for the so-called "squares" for your use-case? 
 Regardless of that, people index all kinds of shapes, e.g. circles, polygons 
and they will look differently at different latitudes.  I didn't know that it 
affects the cell count this much -- thanks for enlightening me.  I knew it 
_could_ in what I thought was some extreme cases but your diagram seems to show 
it's typical.  Hmm.  _I wonder if similar results could be achieved by 
internally using the web-mercator projection_?  Of course some scheme is needed 
to handle the polar caps which that projection doesn't even cover but whatever. 
 The web-mercator projection increases the overall size of the shape both 
latitudinally and longitudinally equally, and thus would probably yield roughly 
similar numbers of cells at all latitudes; wouldn't it?

RE index size -- you probably had difficulty benchmarking the differences 
because you used Lucene defaults.  Switch to a doc count based index writer 
flush (instead of memory based), and use SerialMergeScheduler to get 
predictable segments, albeit slower throughput that you wouldn't normally do in 
production.  This stuff can have a big impact on benchmark results, not just 
for index size but sometimes also benchmarking queries depending on how "lucky" 
one of the benchmark runs got if a big merge occurred to yield much fewer 
segments.

I'm having difficulty finding the benchmark; can you provide a link to the GH 
file?

At first I was unsure how S2 might improve point query performance but after 
some thought I figure that the cell count discussion for indexed shapes would 
apply as well for the cells a query shape might have to traverse.  Again; I 
wonder if a web-mercator projection would get similar improvements?  

Another nice thing about web-mercator based underlying coordinate system is 
that the index-time heatmap feature would produce a grid of numbers that are 
nice squares to be displayed in a web-mercator map client-side.  Today they 
tend to be horizontal rectangles that get flatter as you go to the poles.  It's 
not just about visual preference of squares; it's also about trying to ensure 
that any secondary processing of the raw heatmap data doesn't unintentionally 
skew/misrepresent data due to an assumption of a uniform grid when it's not 
actually uniform.  Sorry to get a little side-tracked but it's related.

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 0.5h
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-13 Thread Adrien Grand (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16363593#comment-16363593
 ] 

Adrien Grand commented on LUCENE-8126:
--

Thanks for the explanation [~ivera].

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 0.5h
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-13 Thread David Smiley (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16363013#comment-16363013
 ] 

David Smiley commented on LUCENE-8126:
--

BTW I’m on vacation with almost no Internet thru the 21st

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-cell.pdf, SPT-query.jpeg
>
>  Time Spent: 0.5h
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-13 Thread Ignacio Vera (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16362014#comment-16362014
 ] 

Ignacio Vera commented on LUCENE-8126:
--

[~jpountz], the important thing here is if the shape is close to the equator 
and close to the poles. When using bounding boxes, the further away you are 
from the equator, the more cells you need to describe a shape. S2 cells are 
more constant around the globe so it should use the similar number of cells 
regardless where you are on the sphere.

I put together an example (attached) where I index a square polygon on the 
equator and at a 60 degrees latitude with trees with same set-up. You can see 
that geohash tree is the more inneficient as it needs quite a lot of cells to 
describe the polygon, 260 at the equator and 390 at 60 degrees. S2 and Quad 
trees use the same number of cells to describe the polygon at the equator (108) 
but at 60 degrees, S2 uses a similar number of cells  and Quad tree almost 
double the number of cells required. Here is where the benefit comes.

I have attached as well a small graph showing query performance of my data 
depending on the SPT. The queries use composite strategy and are random cone 
searches (query shape is a random circle). Horizontal axis represents the 
number of hits of the query and the vertical axis the query execution time.

 

 

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
> Attachments: SPT-query.jpeg, STP-cell.pdf
>
>  Time Spent: 0.5h
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-12 Thread Adrien Grand (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16361161#comment-16361161
 ] 

Adrien Grand commented on LUCENE-8126:
--

These are significant speedups and reduction of the index size! Do we have any 
clue as to what with S2 triggers these improvements? The benchmark description 
says about the polygons that they are "all distributed mainly on the south 
hemisphere of the sphere", does it matter or would one get similar speedups for 
northern polygons?

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
>  Time Spent: 0.5h
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-12 Thread Ignacio Vera (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16360632#comment-16360632
 ] 

Ignacio Vera commented on LUCENE-8126:
--

[~dsmiley], indeed I have to iterate a few times with ant precommit but now it 
seems happy. Last two doubts:

1) In which branches should I commit this change? I pressume that it is needed 
in Master and 7.x. ([~kwri...@metacarta.com] changes in geo3d should be 
commited as well in 6.x?)

2) CHANGES.txt: I have added the reference under new features. I suppose this 
file needs to be updated in all committed braches.

Thanks in advance!

 

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
>  Time Spent: 0.5h
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-08 Thread David Smiley (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16357202#comment-16357202
 ] 

David Smiley commented on LUCENE-8126:
--

These are fantastic results [~ivera]!

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
>  Time Spent: 0.5h
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-08 Thread Ignacio Vera (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16356757#comment-16356757
 ] 

Ignacio Vera commented on LUCENE-8126:
--

I have added the performance test classes on the branch in case you want to 
have a look to check results are not bias.

I have done two test (They do not include index size as I have no found a 
reliable way of getting that info), I can only show you for now some tipical 
results.

1) Indexing 5k random polygons and executing 50 Random queries. Trees have 
precision set to 1e-4 and distErrPct to 5%:

load geohash : 132,15 indexed shapes per second
query geohash recursive : 10,88 queries per second
query geohash composite : 7,29 queries per second

load quad : 299,04 indexed shapes per second
query quad recursive : 15,13 queries per second
query quad composite : 10,89 queries per second

load s2 arity 4 : 623,67 indexed shapes per second
query s2 arity 4 recursive : 40,00 queries per second
query s2 arity 4 composite : 21,51 queries per second

load s2 arity 16 : 283,46 indexed shapes per second
query s2 arity 16 recursive : 12,22 queries per second
query s2 arity 16 composite : 9,99 queries per second

load s2 arity 64 : 159,05 indexed shapes per second
query s2 arity 64 recursive : 5,13 queries per second
query s2 arity 64 composite : 3,58 queries per second

 

1) Indexing 50k random points and executing 50 Random queries. Trees have 
precision set to 1e-6 and distErrPct to 0%:

load geohash : 14898,69 indexed shapes per second
query geohash recursive : 2,31 queries per second
query geohash composite : 2,29 queries per second

load quad : 5068,42 indexed shapes per second
query quad recursive : 5,10 queries per second
query quad composite : 5,11 queries per second

load s2 arity 4 : 9748,49 indexed shapes per second
query s2 arity 4 recursive : 11,34 queries per second
query s2 arity 4 composite : 11,38 queries per second

load s2 arity 16 : 15513,50 indexed shapes per second
query s2 arity 16 recursive : 3,86 queries per second
query s2 arity 16 composite : 3,83 queries per second

load s2 arity 64 : 16886,19 indexed shapes per second
query s2 arity 64 recursive : 1,56 queries per second
query s2 arity 64 composite : 1,56 queries per second

 

Some data of my use case: I need to index ~3M  documents. 2M are points, 0.5M 
polygons and 0.5M multi-polygons with an averge size of 20. They need to be 
indexed on the celestial sphere (unit sphere). All polygons are squared (4 
points) with different sizes, from 1 square degree to very tiny ones, all 
distributed mainly on the south hemisphere of the sphere. Moving from Geohash 
to S2 has provided the following benefits:

1) 20% reduccion of index size.

2) 75% reduccion on indexing time (yuhu!). 

3) 2.5 times faster queries.

 

Anyway what we need is a benchmark for SPT the same way that there is one for 
BKD tree. Probably my next mini-project.

Conclusion: If you use Geo3D, you probably want to use S2 :)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
>  Time Spent: 0.5h
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-07 Thread David Smiley (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16355620#comment-16355620
 ] 

David Smiley commented on LUCENE-8126:
--

Overall looks good [~ivera].  I think it's ready to be committed, 
notwithstanding some "ant precommit" stuff regarding the new dependency I'm 
sure you'll bump into.

The main question in my mind is how we communicate when someone should use this 
SPT.   For the other 3 I know when they are most appropriate.  But for this; I 
just don't know.  In the description you state:
{quote}Using this pixelization scheme reduces the size of the index, improves 
the performance of the queries and reduces the loading time for non-point 
shapes.
{quote}
Could you please share some numbers?

BTW GitHub-Jira integration now puts code review comments into the "Worklog" 
tab in Jira which doesn't flood the comments with noisy stuff or send redundant 
email notifications.  If someone interested wants to follow the activity and be 
notified, I believe they need to "subscribe" to the PR in GitHub.

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
>  Time Spent: 20m
>  Remaining Estimate: 0h
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-07 Thread Karl Wright (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16355494#comment-16355494
 ] 

Karl Wright commented on LUCENE-8126:
-

[~ivera], I think this is great, but I haven't been following the details.


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Assignee: Ignacio Vera
>Priority: Major
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-02-07 Thread Ignacio Vera (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16355439#comment-16355439
 ] 

Ignacio Vera commented on LUCENE-8126:
--

I would like to move these forward, any comment [~dsmiley], 
[~kwri...@metacarta.com] or it is ready to be merged?

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>Priority: Major
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-14 Thread Ignacio Vera (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16325523#comment-16325523
 ] 

Ignacio Vera commented on LUCENE-8126:
--

I committed a new version of the SPT with variable arity. First level is always 
divided by 6 (faces), and the following levels are divided either in 4 
sub-cells, 16 sub-cells or 64 sub-cells.

Performance of the tree can be checked using test classes. There are two 
conclusions:

 * For polygons you should always use 4-arity. 
 * For points only, users might want to use 16-arity. you loose a bit of query 
performance but decrease of loading time and index size.  

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread Ignacio Vera (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16321747#comment-16321747
 ] 

Ignacio Vera commented on LUCENE-8126:
--

Note that S2 geometry has 6-arity for the first level, after that divides every 
cell in 4 so it has in fact 4-arity.

[~daddywri] : I have added in the pull request a new Shape (GeoS2shape) which 
is a very fast implementation of a 4 points polygon. I do not perform any 
argument checking, is that ok? purpose of the shape is speed. In addition I 
have implemented it as a polygon and added a method in the polygon factory, is 
that approach ok?







> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread ASF GitHub Bot (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16321726#comment-16321726
 ] 

ASF GitHub Bot commented on LUCENE-8126:


Github user iverase commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/302#discussion_r160868387
  
--- Diff: 
lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java
 ---
@@ -0,0 +1,285 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import com.google.common.geometry.S2CellId;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.shape.Shape;
+import org.locationtech.spatial4j.shape.SpatialRelation;
+
+/**
+ * This class represents a S2 pixel in the RPT.
+ *
+ * @lucene.internal
+ */
+class S2PrefixTreeCell implements Cell {
+
+//Faces of S2 Geometry
+private static S2CellId[] FACES = new S2CellId[6];
+static {
+FACES[0] = S2CellId.fromFacePosLevel(0, 0, 0);
+FACES[1] = S2CellId.fromFacePosLevel(1, 0, 0);
+FACES[2] = S2CellId.fromFacePosLevel(2, 0, 0);
+FACES[3] = S2CellId.fromFacePosLevel(3, 0, 0);
+FACES[4] = S2CellId.fromFacePosLevel(4, 0, 0);
+FACES[5] = S2CellId.fromFacePosLevel(5, 0, 0);
+}
+
+/*Special character to define a cell leaf*/
+private static final byte LEAF = '+';
+
+/*Tokens are used to serialize cells*/
+private static final byte[] TOKENS;
+/*Map containing mapping between tokens and integer values*/
+private static final Map PIXELS;
+static {
+TOKENS = new byte[]{'0', '1', '2', '3', '4', '5'};
+PIXELS = new HashMap<>(6);
+PIXELS.put(TOKENS[0], 0);
+PIXELS.put(TOKENS[1], 1);
+PIXELS.put(TOKENS[2], 2);
+PIXELS.put(TOKENS[3], 3);
+PIXELS.put(TOKENS[4], 4);
+PIXELS.put(TOKENS[5], 5);
+}
+
+S2CellId cellId;
+int level; //cache level
+S2PrefixTree tree;
+
+SpatialRelation shapeRel= null;
+boolean isLeaf;
+Shape shape = null;
+
+S2PrefixTreeCell(S2PrefixTree tree, S2CellId cellId){
+this.cellId= cellId;
+this.tree = tree;
+setLevel();
+if (getLevel() == tree.getMaxLevels()) {
+setLeaf();
+}
+}
+
+void readCell(S2PrefixTree tree, BytesRef ref){
+isLeaf = false;
+shape = null;
+shapeRel = null;
+this.tree = tree;
+cellId = getS2CellIdFromBytesRef(ref);
+setLevel();
+if (isLeaf(ref) || getLevel() == tree.getMaxLevels()){
+setLeaf();
+}
+}
+
+@Override
+public SpatialRelation getShapeRel() {
+return shapeRel;
+}
+
+@Override
+public void setShapeRel(SpatialRelation rel) {
+shapeRel = rel;
+}
+
+@Override
+public boolean isLeaf() {
+return isLeaf;
+}
+
+@Override
+public void setLeaf() {
+isLeaf = true;
+}
+
+@Override
+public BytesRef getTokenBytesWithLeaf(BytesRef result) {
+result = getTokenBytesNoLeaf(result);
+//max levels do not have leaf
+if (isLeaf() && !(getLevel() == tree.getMaxLevels())){
+//Add leaf byte
+result.bytes[result.offset + result.length] = LEAF;
+result.length++;
+}
+return result;
+}
+
+@Override
+public BytesRef getTokenBytesNoLeaf(BytesRef result) {
+if (result == null){
+result =

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread David Smiley (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320976#comment-16320976
 ] 

David Smiley commented on LUCENE-8126:
--

_(an aside: I wish the JIRA GitHub integration didn't put so much code context 
around the feedback text!)_

It's nice to see a new RPT SpatialPrefixTree implementation :-)  The API is a 
little crusty; perhaps sometime we could kick around some ideas to make it 
nicer.

It'll be interesting to see how well this performs.  This appears to be a 6-ary 
tree, as opposed to 4-ary (quad) or 32-ary (geohash).  One could build a 
variable arity prefixTree by the way (i.e. first level has 256, next 128, 
etc.), and I recently tweaked one of ours to do that (not contributed back yet).

For point data, the higher the arity, the smaller the index but slower search 
as it must scan more.

For non-point data, it's not clear since distErrPct caps the resolution of a 
shape relative to its size, and I believe (though not 100% sure) that it yields 
a roughly normal distribution around a certain number of cells (given fixed 
distErrPct, random shape type & size, near equator, random tree arity).  It'd 
be neat to empirically validate my theory.  If I'm right, then the optimal 
arity is probably 4 for non-point shapes, and we have two of those 
implementations. RE "near equator" above, see LUCENE-5056 though it has an easy 
fix in my last comment.

Given the way S2 divides a world into 6 sides recursively, it seems it would 
place shapes at a balanced depth in the tree no matter where in the world the 
data is.  That's a nice benefit... making the cell depth for a shape a bit more 
shallow than the probable depth in the other tree implementations (assuming a 
target precision for a given shape).  That's a bonus.

CC [~nknize] you may find this issue interesting

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread ASF GitHub Bot (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320916#comment-16320916
 ] 

ASF GitHub Bot commented on LUCENE-8126:


Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/302#discussion_r160769685
  
--- Diff: 
lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java
 ---
@@ -0,0 +1,285 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import com.google.common.geometry.S2CellId;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.shape.Shape;
+import org.locationtech.spatial4j.shape.SpatialRelation;
+
+/**
+ * This class represents a S2 pixel in the RPT.
+ *
+ * @lucene.internal
+ */
+class S2PrefixTreeCell implements Cell {
+
+//Faces of S2 Geometry
+private static S2CellId[] FACES = new S2CellId[6];
+static {
+FACES[0] = S2CellId.fromFacePosLevel(0, 0, 0);
+FACES[1] = S2CellId.fromFacePosLevel(1, 0, 0);
+FACES[2] = S2CellId.fromFacePosLevel(2, 0, 0);
+FACES[3] = S2CellId.fromFacePosLevel(3, 0, 0);
+FACES[4] = S2CellId.fromFacePosLevel(4, 0, 0);
+FACES[5] = S2CellId.fromFacePosLevel(5, 0, 0);
+}
+
+/*Special character to define a cell leaf*/
+private static final byte LEAF = '+';
+
+/*Tokens are used to serialize cells*/
+private static final byte[] TOKENS;
+/*Map containing mapping between tokens and integer values*/
+private static final Map PIXELS;
+static {
+TOKENS = new byte[]{'0', '1', '2', '3', '4', '5'};
+PIXELS = new HashMap<>(6);
+PIXELS.put(TOKENS[0], 0);
+PIXELS.put(TOKENS[1], 1);
+PIXELS.put(TOKENS[2], 2);
+PIXELS.put(TOKENS[3], 3);
+PIXELS.put(TOKENS[4], 4);
+PIXELS.put(TOKENS[5], 5);
+}
+
+S2CellId cellId;
+int level; //cache level
+S2PrefixTree tree;
+
+SpatialRelation shapeRel= null;
+boolean isLeaf;
+Shape shape = null;
+
+S2PrefixTreeCell(S2PrefixTree tree, S2CellId cellId){
+this.cellId= cellId;
+this.tree = tree;
+setLevel();
+if (getLevel() == tree.getMaxLevels()) {
+setLeaf();
+}
+}
+
+void readCell(S2PrefixTree tree, BytesRef ref){
+isLeaf = false;
+shape = null;
+shapeRel = null;
+this.tree = tree;
+cellId = getS2CellIdFromBytesRef(ref);
+setLevel();
+if (isLeaf(ref) || getLevel() == tree.getMaxLevels()){
+setLeaf();
+}
+}
+
+@Override
+public SpatialRelation getShapeRel() {
+return shapeRel;
+}
+
+@Override
+public void setShapeRel(SpatialRelation rel) {
+shapeRel = rel;
+}
+
+@Override
+public boolean isLeaf() {
+return isLeaf;
+}
+
+@Override
+public void setLeaf() {
+isLeaf = true;
+}
+
+@Override
+public BytesRef getTokenBytesWithLeaf(BytesRef result) {
+result = getTokenBytesNoLeaf(result);
+//max levels do not have leaf
+if (isLeaf() && !(getLevel() == tree.getMaxLevels())){
+//Add leaf byte
+result.bytes[result.offset + result.length] = LEAF;
+result.length++;
+}
+return result;
+}
+
+@Override
+public BytesRef getTokenBytesNoLeaf(BytesRef result) {
+if (result == null){
+result =

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread ASF GitHub Bot (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320915#comment-16320915
 ] 

ASF GitHub Bot commented on LUCENE-8126:


Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/302#discussion_r160769274
  
--- Diff: 
lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java
 ---
@@ -0,0 +1,285 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import com.google.common.geometry.S2CellId;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.shape.Shape;
+import org.locationtech.spatial4j.shape.SpatialRelation;
+
+/**
+ * This class represents a S2 pixel in the RPT.
+ *
+ * @lucene.internal
+ */
+class S2PrefixTreeCell implements Cell {
+
+//Faces of S2 Geometry
+private static S2CellId[] FACES = new S2CellId[6];
+static {
+FACES[0] = S2CellId.fromFacePosLevel(0, 0, 0);
+FACES[1] = S2CellId.fromFacePosLevel(1, 0, 0);
+FACES[2] = S2CellId.fromFacePosLevel(2, 0, 0);
+FACES[3] = S2CellId.fromFacePosLevel(3, 0, 0);
+FACES[4] = S2CellId.fromFacePosLevel(4, 0, 0);
+FACES[5] = S2CellId.fromFacePosLevel(5, 0, 0);
+}
+
+/*Special character to define a cell leaf*/
+private static final byte LEAF = '+';
+
+/*Tokens are used to serialize cells*/
+private static final byte[] TOKENS;
+/*Map containing mapping between tokens and integer values*/
+private static final Map PIXELS;
+static {
+TOKENS = new byte[]{'0', '1', '2', '3', '4', '5'};
+PIXELS = new HashMap<>(6);
+PIXELS.put(TOKENS[0], 0);
+PIXELS.put(TOKENS[1], 1);
+PIXELS.put(TOKENS[2], 2);
+PIXELS.put(TOKENS[3], 3);
+PIXELS.put(TOKENS[4], 4);
+PIXELS.put(TOKENS[5], 5);
+}
+
+S2CellId cellId;
+int level; //cache level
+S2PrefixTree tree;
+
+SpatialRelation shapeRel= null;
+boolean isLeaf;
+Shape shape = null;
+
+S2PrefixTreeCell(S2PrefixTree tree, S2CellId cellId){
+this.cellId= cellId;
+this.tree = tree;
+setLevel();
+if (getLevel() == tree.getMaxLevels()) {
+setLeaf();
+}
+}
+
+void readCell(S2PrefixTree tree, BytesRef ref){
+isLeaf = false;
+shape = null;
+shapeRel = null;
+this.tree = tree;
+cellId = getS2CellIdFromBytesRef(ref);
+setLevel();
+if (isLeaf(ref) || getLevel() == tree.getMaxLevels()){
+setLeaf();
+}
+}
+
+@Override
+public SpatialRelation getShapeRel() {
+return shapeRel;
+}
+
+@Override
+public void setShapeRel(SpatialRelation rel) {
+shapeRel = rel;
+}
+
+@Override
+public boolean isLeaf() {
+return isLeaf;
+}
+
+@Override
+public void setLeaf() {
+isLeaf = true;
+}
+
+@Override
+public BytesRef getTokenBytesWithLeaf(BytesRef result) {
+result = getTokenBytesNoLeaf(result);
+//max levels do not have leaf
+if (isLeaf() && !(getLevel() == tree.getMaxLevels())){
+//Add leaf byte
+result.bytes[result.offset + result.length] = LEAF;
+result.length++;
+}
+return result;
+}
+
+@Override
+public BytesRef getTokenBytesNoLeaf(BytesRef result) {
+if (result == null){
+result =

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread ASF GitHub Bot (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320909#comment-16320909
 ] 

ASF GitHub Bot commented on LUCENE-8126:


Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/302#discussion_r160766117
  
--- Diff: 
lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java
 ---
@@ -0,0 +1,285 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import com.google.common.geometry.S2CellId;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.shape.Shape;
+import org.locationtech.spatial4j.shape.SpatialRelation;
+
+/**
+ * This class represents a S2 pixel in the RPT.
+ *
+ * @lucene.internal
+ */
+class S2PrefixTreeCell implements Cell {
+
+//Faces of S2 Geometry
+private static S2CellId[] FACES = new S2CellId[6];
+static {
+FACES[0] = S2CellId.fromFacePosLevel(0, 0, 0);
+FACES[1] = S2CellId.fromFacePosLevel(1, 0, 0);
+FACES[2] = S2CellId.fromFacePosLevel(2, 0, 0);
+FACES[3] = S2CellId.fromFacePosLevel(3, 0, 0);
+FACES[4] = S2CellId.fromFacePosLevel(4, 0, 0);
+FACES[5] = S2CellId.fromFacePosLevel(5, 0, 0);
+}
+
+/*Special character to define a cell leaf*/
+private static final byte LEAF = '+';
+
+/*Tokens are used to serialize cells*/
+private static final byte[] TOKENS;
+/*Map containing mapping between tokens and integer values*/
+private static final Map PIXELS;
+static {
+TOKENS = new byte[]{'0', '1', '2', '3', '4', '5'};
+PIXELS = new HashMap<>(6);
+PIXELS.put(TOKENS[0], 0);
+PIXELS.put(TOKENS[1], 1);
+PIXELS.put(TOKENS[2], 2);
+PIXELS.put(TOKENS[3], 3);
+PIXELS.put(TOKENS[4], 4);
+PIXELS.put(TOKENS[5], 5);
+}
+
+S2CellId cellId;
+int level; //cache level
+S2PrefixTree tree;
+
+SpatialRelation shapeRel= null;
+boolean isLeaf;
+Shape shape = null;
+
+S2PrefixTreeCell(S2PrefixTree tree, S2CellId cellId){
+this.cellId= cellId;
+this.tree = tree;
+setLevel();
+if (getLevel() == tree.getMaxLevels()) {
+setLeaf();
+}
+}
+
+void readCell(S2PrefixTree tree, BytesRef ref){
+isLeaf = false;
+shape = null;
+shapeRel = null;
+this.tree = tree;
+cellId = getS2CellIdFromBytesRef(ref);
+setLevel();
+if (isLeaf(ref) || getLevel() == tree.getMaxLevels()){
+setLeaf();
+}
+}
+
+@Override
+public SpatialRelation getShapeRel() {
+return shapeRel;
+}
+
+@Override
+public void setShapeRel(SpatialRelation rel) {
+shapeRel = rel;
+}
+
+@Override
+public boolean isLeaf() {
+return isLeaf;
+}
+
+@Override
+public void setLeaf() {
+isLeaf = true;
+}
+
+@Override
+public BytesRef getTokenBytesWithLeaf(BytesRef result) {
+result = getTokenBytesNoLeaf(result);
+//max levels do not have leaf
+if (isLeaf() && !(getLevel() == tree.getMaxLevels())){
+//Add leaf byte
+result.bytes[result.offset + result.length] = LEAF;
+result.length++;
+}
+return result;
+}
+
+@Override
+public BytesRef getTokenBytesNoLeaf(BytesRef result) {
+if (result == null){
+result =

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread ASF GitHub Bot (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320913#comment-16320913
 ] 

ASF GitHub Bot commented on LUCENE-8126:


Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/302#discussion_r160768405
  
--- Diff: 
lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java
 ---
@@ -0,0 +1,285 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import com.google.common.geometry.S2CellId;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.shape.Shape;
+import org.locationtech.spatial4j.shape.SpatialRelation;
+
+/**
+ * This class represents a S2 pixel in the RPT.
+ *
+ * @lucene.internal
+ */
+class S2PrefixTreeCell implements Cell {
+
+//Faces of S2 Geometry
+private static S2CellId[] FACES = new S2CellId[6];
+static {
+FACES[0] = S2CellId.fromFacePosLevel(0, 0, 0);
+FACES[1] = S2CellId.fromFacePosLevel(1, 0, 0);
+FACES[2] = S2CellId.fromFacePosLevel(2, 0, 0);
+FACES[3] = S2CellId.fromFacePosLevel(3, 0, 0);
+FACES[4] = S2CellId.fromFacePosLevel(4, 0, 0);
+FACES[5] = S2CellId.fromFacePosLevel(5, 0, 0);
+}
+
+/*Special character to define a cell leaf*/
+private static final byte LEAF = '+';
+
+/*Tokens are used to serialize cells*/
+private static final byte[] TOKENS;
+/*Map containing mapping between tokens and integer values*/
+private static final Map PIXELS;
+static {
+TOKENS = new byte[]{'0', '1', '2', '3', '4', '5'};
+PIXELS = new HashMap<>(6);
+PIXELS.put(TOKENS[0], 0);
+PIXELS.put(TOKENS[1], 1);
+PIXELS.put(TOKENS[2], 2);
+PIXELS.put(TOKENS[3], 3);
+PIXELS.put(TOKENS[4], 4);
+PIXELS.put(TOKENS[5], 5);
+}
+
+S2CellId cellId;
+int level; //cache level
+S2PrefixTree tree;
+
+SpatialRelation shapeRel= null;
+boolean isLeaf;
+Shape shape = null;
+
+S2PrefixTreeCell(S2PrefixTree tree, S2CellId cellId){
+this.cellId= cellId;
+this.tree = tree;
+setLevel();
+if (getLevel() == tree.getMaxLevels()) {
+setLeaf();
+}
+}
+
+void readCell(S2PrefixTree tree, BytesRef ref){
+isLeaf = false;
+shape = null;
+shapeRel = null;
+this.tree = tree;
+cellId = getS2CellIdFromBytesRef(ref);
+setLevel();
+if (isLeaf(ref) || getLevel() == tree.getMaxLevels()){
+setLeaf();
+}
+}
+
+@Override
+public SpatialRelation getShapeRel() {
+return shapeRel;
+}
+
+@Override
+public void setShapeRel(SpatialRelation rel) {
+shapeRel = rel;
+}
+
+@Override
+public boolean isLeaf() {
+return isLeaf;
+}
+
+@Override
+public void setLeaf() {
+isLeaf = true;
+}
+
+@Override
+public BytesRef getTokenBytesWithLeaf(BytesRef result) {
+result = getTokenBytesNoLeaf(result);
+//max levels do not have leaf
+if (isLeaf() && !(getLevel() == tree.getMaxLevels())){
+//Add leaf byte
+result.bytes[result.offset + result.length] = LEAF;
+result.length++;
+}
+return result;
+}
+
+@Override
+public BytesRef getTokenBytesNoLeaf(BytesRef result) {
+if (result == null){
+result =

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread ASF GitHub Bot (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320914#comment-16320914
 ] 

ASF GitHub Bot commented on LUCENE-8126:


Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/302#discussion_r160773175
  
--- Diff: 
lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTree.java
 ---
@@ -0,0 +1,111 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import com.google.common.geometry.S2CellId;
+import com.google.common.geometry.S2LatLng;
+import com.google.common.geometry.S2Projections;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.context.SpatialContext;
+import org.locationtech.spatial4j.distance.DistanceUtils;
+import org.locationtech.spatial4j.shape.Point;
+import org.locationtech.spatial4j.shape.Shape;
+
+/**
+ * Spatial prefix tree for S2 Geometry. Shape factories for the given 
{@link SpatialContext} must
+ * implement the interface {@link S2ShapeFactory}.
+ *
+ * @lucene.experimental
+ */
+public class S2PrefixTree extends SpatialPrefixTree {
+
+/**
+ * Factory for creating {@link S2PrefixTree} instances with useful 
defaults
+ */
+public static class Factory extends SpatialPrefixTreeFactory {
+
+@Override
+protected int getLevelForDistance(double degrees) {
+S2PrefixTree grid = new S2PrefixTree(ctx, 
S2PrefixTree.MAX_LEVELS);
+return grid.getLevelForDistance(degrees);
+}
+
+@Override
+protected SpatialPrefixTree newSPT() {
+return new S2PrefixTree(ctx,
+maxLevels != null ? maxLevels : S2PrefixTree.MAX_LEVELS);
+}
+}
+
+//factory to generate S2 cell shapes
+protected final S2ShapeFactory s2ShapeFactory;
+public static final int MAX_LEVELS = S2CellId.MAX_LEVEL + 1;
+
+public S2PrefixTree(SpatialContext ctx, int maxLevels) {
+super(ctx, maxLevels);
+if (!(ctx.getShapeFactory() instanceof S2ShapeFactory)) {
+throw new IllegalArgumentException("Spatial context does not 
support S2 spatial index.");
+}
+this.s2ShapeFactory = (S2ShapeFactory) ctx.getShapeFactory();
+}
+
+@Override
+public int getLevelForDistance(double dist) {
+if (dist ==0){
+return maxLevels;
+}
+return Math.min(maxLevels, 
S2Projections.MAX_WIDTH.getClosestLevel(dist * 
DistanceUtils.DEGREES_TO_RADIANS) +1);
+}
+
+@Override
+public double getDistanceForLevel(int level) {
+return S2Projections.MAX_WIDTH.getValue(level -1) * 
DistanceUtils.RADIANS_TO_DEGREES;
--- End diff --

nitpick: put space after that minus operator


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
>

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread ASF GitHub Bot (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320917#comment-16320917
 ] 

ASF GitHub Bot commented on LUCENE-8126:


Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/302#discussion_r160773587
  
--- Diff: 
lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTree.java
 ---
@@ -0,0 +1,111 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import com.google.common.geometry.S2CellId;
+import com.google.common.geometry.S2LatLng;
+import com.google.common.geometry.S2Projections;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.context.SpatialContext;
+import org.locationtech.spatial4j.distance.DistanceUtils;
+import org.locationtech.spatial4j.shape.Point;
+import org.locationtech.spatial4j.shape.Shape;
+
+/**
+ * Spatial prefix tree for S2 Geometry. Shape factories for the given 
{@link SpatialContext} must
+ * implement the interface {@link S2ShapeFactory}.
+ *
+ * @lucene.experimental
+ */
+public class S2PrefixTree extends SpatialPrefixTree {
+
+/**
+ * Factory for creating {@link S2PrefixTree} instances with useful 
defaults
+ */
+public static class Factory extends SpatialPrefixTreeFactory {
+
+@Override
+protected int getLevelForDistance(double degrees) {
+S2PrefixTree grid = new S2PrefixTree(ctx, 
S2PrefixTree.MAX_LEVELS);
+return grid.getLevelForDistance(degrees);
+}
+
+@Override
+protected SpatialPrefixTree newSPT() {
+return new S2PrefixTree(ctx,
+maxLevels != null ? maxLevels : S2PrefixTree.MAX_LEVELS);
+}
+}
+
+//factory to generate S2 cell shapes
+protected final S2ShapeFactory s2ShapeFactory;
+public static final int MAX_LEVELS = S2CellId.MAX_LEVEL + 1;
+
+public S2PrefixTree(SpatialContext ctx, int maxLevels) {
+super(ctx, maxLevels);
+if (!(ctx.getShapeFactory() instanceof S2ShapeFactory)) {
+throw new IllegalArgumentException("Spatial context does not 
support S2 spatial index.");
+}
+this.s2ShapeFactory = (S2ShapeFactory) ctx.getShapeFactory();
+}
+
+@Override
+public int getLevelForDistance(double dist) {
+if (dist ==0){
+return maxLevels;
+}
+return Math.min(maxLevels, 
S2Projections.MAX_WIDTH.getClosestLevel(dist * 
DistanceUtils.DEGREES_TO_RADIANS) +1);
+}
+
+@Override
+public double getDistanceForLevel(int level) {
+return S2Projections.MAX_WIDTH.getValue(level -1) * 
DistanceUtils.RADIANS_TO_DEGREES;
+}
+
+@Override
+public Cell getWorldCell() {
+return  new S2PrefixTreeCell(this, null);
+}
+
+@Override
+public Cell readCell(BytesRef term, Cell scratch) {
+S2PrefixTreeCell cell = (S2PrefixTreeCell) scratch;
+if (cell == null)
+cell = (S2PrefixTreeCell) getWorldCell();
+cell.readCell(this, term);
+return cell;
+}
+
+@Override
+public CellIterator getTreeCellIterator(Shape shape, int detailLevel) {
+if (!(shape instanceof Point)) {
+return  super.getTreeCellIterator(shape, detailLevel);
+}
+Point p = (Point) shape;
+S2CellId id = S2CellId.fromLatLng(S2LatLng.fromDegrees(p.getY(), 
p.getX())).parent(detailLevel-1);
+List cells = new ArrayList<>(detailLevel);
+for (int i=0; i < detailLevel -1; i++) {
--- End diff --

nitpick: put a space after that minus operator


> Spatial

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread ASF GitHub Bot (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320912#comment-16320912
 ] 

ASF GitHub Bot commented on LUCENE-8126:


Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/302#discussion_r160768053
  
--- Diff: 
lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java
 ---
@@ -0,0 +1,285 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import com.google.common.geometry.S2CellId;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.shape.Shape;
+import org.locationtech.spatial4j.shape.SpatialRelation;
+
+/**
+ * This class represents a S2 pixel in the RPT.
+ *
+ * @lucene.internal
+ */
+class S2PrefixTreeCell implements Cell {
+
+//Faces of S2 Geometry
+private static S2CellId[] FACES = new S2CellId[6];
+static {
+FACES[0] = S2CellId.fromFacePosLevel(0, 0, 0);
+FACES[1] = S2CellId.fromFacePosLevel(1, 0, 0);
+FACES[2] = S2CellId.fromFacePosLevel(2, 0, 0);
+FACES[3] = S2CellId.fromFacePosLevel(3, 0, 0);
+FACES[4] = S2CellId.fromFacePosLevel(4, 0, 0);
+FACES[5] = S2CellId.fromFacePosLevel(5, 0, 0);
+}
+
+/*Special character to define a cell leaf*/
+private static final byte LEAF = '+';
+
+/*Tokens are used to serialize cells*/
+private static final byte[] TOKENS;
+/*Map containing mapping between tokens and integer values*/
+private static final Map PIXELS;
--- End diff --

Since this map has a small set of fixed values that have numeric 
equivalents, perhaps we can do direct addressing into an array?


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread ASF GitHub Bot (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320910#comment-16320910
 ] 

ASF GitHub Bot commented on LUCENE-8126:


Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/302#discussion_r160768230
  
--- Diff: 
lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTree.java
 ---
@@ -0,0 +1,111 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import com.google.common.geometry.S2CellId;
+import com.google.common.geometry.S2LatLng;
+import com.google.common.geometry.S2Projections;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.context.SpatialContext;
+import org.locationtech.spatial4j.distance.DistanceUtils;
+import org.locationtech.spatial4j.shape.Point;
+import org.locationtech.spatial4j.shape.Shape;
+
+/**
+ * Spatial prefix tree for S2 Geometry. Shape factories for the given 
{@link SpatialContext} must
+ * implement the interface {@link S2ShapeFactory}.
+ *
+ * @lucene.experimental
+ */
+public class S2PrefixTree extends SpatialPrefixTree {
+
+/**
+ * Factory for creating {@link S2PrefixTree} instances with useful 
defaults
+ */
+public static class Factory extends SpatialPrefixTreeFactory {
+
+@Override
+protected int getLevelForDistance(double degrees) {
+S2PrefixTree grid = new S2PrefixTree(ctx, 
S2PrefixTree.MAX_LEVELS);
+return grid.getLevelForDistance(degrees);
+}
+
+@Override
+protected SpatialPrefixTree newSPT() {
+return new S2PrefixTree(ctx,
+maxLevels != null ? maxLevels : S2PrefixTree.MAX_LEVELS);
+}
+}
+
+//factory to generate S2 cell shapes
+protected final S2ShapeFactory s2ShapeFactory;
+public static final int MAX_LEVELS = S2CellId.MAX_LEVEL + 1;
+
+public S2PrefixTree(SpatialContext ctx, int maxLevels) {
+super(ctx, maxLevels);
+if (!(ctx.getShapeFactory() instanceof S2ShapeFactory)) {
+throw new IllegalArgumentException("Spatial context does not 
support S2 spatial index.");
+}
+this.s2ShapeFactory = (S2ShapeFactory) ctx.getShapeFactory();
+}
+
+@Override
+public int getLevelForDistance(double dist) {
+if (dist ==0){
+return maxLevels;
+}
+return Math.min(maxLevels, 
S2Projections.MAX_WIDTH.getClosestLevel(dist * 
DistanceUtils.DEGREES_TO_RADIANS) +1);
+}
+
+@Override
+public double getDistanceForLevel(int level) {
+return S2Projections.MAX_WIDTH.getValue(level -1) * 
DistanceUtils.RADIANS_TO_DEGREES;
+}
+
+@Override
+public Cell getWorldCell() {
+return  new S2PrefixTreeCell(this, null);
+}
+
+@Override
+public Cell readCell(BytesRef term, Cell scratch) {
+S2PrefixTreeCell cell = (S2PrefixTreeCell) scratch;
+if (cell == null)
+cell = (S2PrefixTreeCell) getWorldCell();
--- End diff --

nitpick: our code style in Lucene/Solr is to always use braces


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread ASF GitHub Bot (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320911#comment-16320911
 ] 

ASF GitHub Bot commented on LUCENE-8126:


Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/302#discussion_r160766597
  
--- Diff: 
lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/S2PrefixTreeCell.java
 ---
@@ -0,0 +1,285 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.prefix.tree;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import com.google.common.geometry.S2CellId;
+import org.apache.lucene.util.BytesRef;
+import org.locationtech.spatial4j.shape.Shape;
+import org.locationtech.spatial4j.shape.SpatialRelation;
+
+/**
+ * This class represents a S2 pixel in the RPT.
+ *
+ * @lucene.internal
+ */
+class S2PrefixTreeCell implements Cell {
+
+//Faces of S2 Geometry
+private static S2CellId[] FACES = new S2CellId[6];
+static {
+FACES[0] = S2CellId.fromFacePosLevel(0, 0, 0);
+FACES[1] = S2CellId.fromFacePosLevel(1, 0, 0);
+FACES[2] = S2CellId.fromFacePosLevel(2, 0, 0);
+FACES[3] = S2CellId.fromFacePosLevel(3, 0, 0);
+FACES[4] = S2CellId.fromFacePosLevel(4, 0, 0);
+FACES[5] = S2CellId.fromFacePosLevel(5, 0, 0);
+}
+
+/*Special character to define a cell leaf*/
+private static final byte LEAF = '+';
+
+/*Tokens are used to serialize cells*/
+private static final byte[] TOKENS;
+/*Map containing mapping between tokens and integer values*/
+private static final Map PIXELS;
+static {
+TOKENS = new byte[]{'0', '1', '2', '3', '4', '5'};
+PIXELS = new HashMap<>(6);
+PIXELS.put(TOKENS[0], 0);
+PIXELS.put(TOKENS[1], 1);
+PIXELS.put(TOKENS[2], 2);
+PIXELS.put(TOKENS[3], 3);
+PIXELS.put(TOKENS[4], 4);
+PIXELS.put(TOKENS[5], 5);
+}
+
+S2CellId cellId;
+int level; //cache level
+S2PrefixTree tree;
+
+SpatialRelation shapeRel= null;
+boolean isLeaf;
+Shape shape = null;
+
+S2PrefixTreeCell(S2PrefixTree tree, S2CellId cellId){
+this.cellId= cellId;
+this.tree = tree;
+setLevel();
+if (getLevel() == tree.getMaxLevels()) {
+setLeaf();
+}
+}
+
+void readCell(S2PrefixTree tree, BytesRef ref){
+isLeaf = false;
+shape = null;
+shapeRel = null;
+this.tree = tree;
+cellId = getS2CellIdFromBytesRef(ref);
+setLevel();
+if (isLeaf(ref) || getLevel() == tree.getMaxLevels()){
+setLeaf();
+}
+}
+
+@Override
+public SpatialRelation getShapeRel() {
+return shapeRel;
+}
+
+@Override
+public void setShapeRel(SpatialRelation rel) {
+shapeRel = rel;
+}
+
+@Override
+public boolean isLeaf() {
+return isLeaf;
+}
+
+@Override
+public void setLeaf() {
+isLeaf = true;
+}
+
+@Override
+public BytesRef getTokenBytesWithLeaf(BytesRef result) {
+result = getTokenBytesNoLeaf(result);
+//max levels do not have leaf
+if (isLeaf() && !(getLevel() == tree.getMaxLevels())){
+//Add leaf byte
+result.bytes[result.offset + result.length] = LEAF;
+result.length++;
+}
+return result;
+}
+
+@Override
+public BytesRef getTokenBytesNoLeaf(BytesRef result) {
+if (result == null){
+result =

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread Ignacio Vera (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320485#comment-16320485
 ] 

Ignacio Vera commented on LUCENE-8126:
--

Hi [~dsmiley],

I created a pull request that hopefully clarifies most of your questions. I am 
interested in how S2 geometry pixelates the sphere, using polygons instead of 
coordinate ranges. 


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-10 Thread ASF GitHub Bot (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16320448#comment-16320448
 ] 

ASF GitHub Bot commented on LUCENE-8126:


GitHub user iverase opened a pull request:

https://github.com/apache/lucene-solr/pull/302

LUCENE-8126:  Spatial prefix tree based on S2 geometry



You can merge this pull request into a Git repository by running:

$ git pull https://github.com/iverase/lucene-solr master

Alternatively you can review and apply these changes as the patch at:

https://github.com/apache/lucene-solr/pull/302.patch

To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

This closes #302


commit ed57d35c3896c61b8e7af31bce66650800225a34
Author: ivera 
Date:   2018-01-10T15:29:40Z

LUCENE-8126: first commit of S2 RPT

commit 9d00f003a0c980ca9eccaff8d4b2e9eebf1e77e2
Author: ivera 
Date:   2018-01-10T15:31:39Z

LUCENE-8126: first commit of S2 RPT

commit 6aa0199f07f7c8e23be8ff550fc3fd0aefc5554a
Author: ivera 
Date:   2018-01-10T15:33:36Z

LUCENE-8126: Performance test classes. They are included to show the 
increae of performance using the new RPT.




> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-09 Thread David Smiley (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16319669#comment-16319669
 ] 

David Smiley commented on LUCENE-8126:
--

This sounds very interesting Ignacio!  In spatial-extras, you can add a 
dependency on s2.  Start that way and we can change our minds if it seems we're 
using a super small piece of s2.

I don't completely understand what you are proposing though.  My understanding 
of s2 is that it's sort of a competitor/alternative to Lucene Geo3d.  But come 
to think of it, I do recall there was some indexing primitives in there that 
was apart from the surface-of-sphere shape implementations.  Ultimately, I 
assume we're talking about indexing interesting shapes such as polygons (and 
surface-of-sphere ones at that); right?  And I figure that this index technique 
you have in mind wouldn't replace the need to store the vector/raw 
implementation to check for a precise match as we're doing now with Geo3d + 
RPT, right?  So we're talking about a faster RPT of sorts using some techniques 
in s2, using it's code in fact, and of course using Lucene's terms dictionary 
(or do you have in mind the Points API) ?

BTW have you seen this benchmark?: 
http://home.apache.org/~mikemccand/geobench.html  It's just point data so it's 
not completely apt here but thought I'd share anyway.

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-09 Thread Karl Wright (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16318453#comment-16318453
 ] 

Karl Wright commented on LUCENE-8126:
-

Sounds reasonable.


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-09 Thread Ignacio Vera (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16318449#comment-16318449
 ] 

Ignacio Vera commented on LUCENE-8126:
--

Still I might want to add a new GeoShape that represents a S2 cell. It is 
basically a convex polygon with 4 sides and a footprint/performance similar to 
GeoRectangle. 

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-09 Thread Ignacio Vera (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16318444#comment-16318444
 ] 

Ignacio Vera commented on LUCENE-8126:
--

module spatial-extras. I do not plan/want to add any dependency in spatial3d.

> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry

2018-01-09 Thread Karl Wright (JIRA)


[ 
https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16318439#comment-16318439
 ] 

Karl Wright commented on LUCENE-8126:
-

[~ivera], which Lucene module would have this dependency?


> Spatial prefix tree based on S2 geometry
> 
>
> Key: LUCENE-8126
> URL: https://issues.apache.org/jira/browse/LUCENE-8126
> Project: Lucene - Core
>  Issue Type: New Feature
>  Components: modules/spatial-extras
>Reporter: Ignacio Vera
>
> Hi [~dsmiley],
> I have been working on a prefix tree based on goggle S2 geometry 
> (https://s2geometry.io/) to be used mainly with Geo3d shapes with very 
> promising results, in particular for complex shapes (e.g polygons). Using 
> this pixelization scheme reduces the size of the index, improves the 
> performance of the queries and reduces the loading time for non-point shapes. 
> If you are ok with this contribution and before providing any code I would 
> like to understand what is the correct/prefered approach:
> 1) Add new depency to the S2 library 
> (https://mvnrepository.com/artifact/io.sgr/s2-geometry-library-java). It has 
> Apache 2.0 license so it should be ok.
> 2) Create a utility class with all methods necessary to navigate the S2 tree 
> and create shapes from S2 cells (basically port what we need from the library 
> into Lucene).
> What do you think?



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org

46 matches

Mail list logo