[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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 > (https://mvnrepository.com/artifact/
[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[jira] [Commented] (LUCENE-8126) Spatial prefix tree based on S2 geometry
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[ https://issues.apache.org/jira/browse/LUCENE-8126?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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