asfimport
commented
6 years ago Karl Wright (@DaddyWri) (migrated from JIRA)
@iverase, which Lucene module would have this dependency?
Closed asfimport closed 6 years ago
asfimport
commented
6 years ago Karl Wright (@DaddyWri) (migrated from JIRA)
@iverase, which Lucene module would have this dependency?
asfimport
commented
6 years ago Ignacio Vera (@iverase) (migrated from JIRA)
module spatial-extras. I do not plan/want to add any dependency in spatial3d.
asfimport
commented
6 years ago Ignacio Vera (@iverase) (migrated from JIRA)
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.
asfimport
commented
6 years ago Karl Wright (@DaddyWri) (migrated from JIRA)
Sounds reasonable.
asfimport
commented
6 years ago David Smiley (@dsmiley) (migrated from JIRA)
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.
asfimport
commented
6 years ago ASF GitHub Bot (migrated from JIRA)
GitHub user iverase opened a pull request:
https://github.com/apache/lucene-solr/pull/302
LUCENE-8126: Spatial prefix tree based on S2 geometryYou can merge this pull request into a Git repository by running:
$ git pull https://github.com/iverase/lucene-solr masterAlternatively you can review and apply these changes as the patch at:
https://github.com/apache/lucene-solr/pull/302.patchTo 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 <ivera@...> Date: 2018-01-10T15:29:40Z
LUCENE-8126: first commit of S2 RPTcommit 9d00f003a0c980ca9eccaff8d4b2e9eebf1e77e2 Author: ivera <ivera@...> Date: 2018-01-10T15:31:39Z
LUCENE-8126: first commit of S2 RPTcommit 6aa0199f07f7c8e23be8ff550fc3fd0aefc5554a Author: ivera <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.Ignacio Vera (@iverase) (migrated from JIRA)
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.
asfimport
commented
6 years ago ASF GitHub Bot (migrated from JIRA)
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<Byte,Integer> 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 = new BytesRef();
+ }
+ getBytesRefFromS2CellId(cellId, result);
+ return result;
+ }
+
+ `@Override`
+ public int getLevel() {
+ return this.level;
+ }
+
+ /\*\*
+ \* Cache level of cell.
+ \*/
+ private void setLevel() {
+ if (this.cellId == null) {
+ this.level = 0;
+ }
+ else {
+ this.level = this.cellId.level() + 1;
+ }
+ }
+
+ `@Override`
+ public CellIterator getNextLevelCells(Shape shapeFilter) {
+ S2CellId[] children;
+ if (cellId == null){ // this is the world cell
+ children = FACES;
+ }
+ else {
+ children = new S2CellId[4];
+ children[0] = cellId.childBegin();
+ children[1] = children[0].next();
+ children[2] = children[1].next();
+ children[3] = children[2].next();
+ }
+ List<Cell> cells = new ArrayList<>(children.length);
+ for (S2CellId pixel : children) {
+ cells.add(new S2PrefixTreeCell(tree, pixel));
+ }
+ return new FilterCellIterator(cells.iterator(), shapeFilter);
+ }
+
+ `@Override`
+ public Shape getShape(){
+ if (shape==null){
+ if (cellId == null) { //World cell
+ return tree.getSpatialContext().getWorldBounds();
+ }
+ return tree.s2ShapeFactory.getS2CellShape(cellId);
— End diff –
I think you meant to cache to this.shape instead?ASF GitHub Bot (migrated from JIRA)
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 bracesASF GitHub Bot (migrated from JIRA)
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<Byte,Integer> 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 = new BytesRef();
+ }
+ getBytesRefFromS2CellId(cellId, result);
+ return result;
+ }
+
+ `@Override`
+ public int getLevel() {
+ return this.level;
+ }
+
+ /\*\*
+ \* Cache level of cell.
+ \*/
+ private void setLevel() {
— End diff –
it'd be simpler of getLevel had this logic.... is the s2's cellId.level() not trivially fast and so you want to effectively cache it?ASF GitHub Bot (migrated from JIRA)
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<Byte,Integer> 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?ASF GitHub Bot (migrated from JIRA)
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<Byte,Integer> 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 = new BytesRef();
+ }
+ getBytesRefFromS2CellId(cellId, result);
+ return result;
+ }
+
+ `@Override`
+ public int getLevel() {
+ return this.level;
+ }
+
+ /\*\*
+ \* Cache level of cell.
+ \*/
+ private void setLevel() {
+ if (this.cellId == null) {
+ this.level = 0;
+ }
+ else {
+ this.level = this.cellId.level() + 1;
+ }
+ }
+
+ `@Override`
+ public CellIterator getNextLevelCells(Shape shapeFilter) {
+ S2CellId[] children;
+ if (cellId == null){ // this is the world cell
+ children = FACES;
+ }
+ else {
— End diff –
nitpick: our code style in Lucene/Solr is for an else statement to be on the same line as the previous closing braceASF GitHub Bot (migrated from JIRA)
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 operatorASF GitHub Bot (migrated from JIRA)
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<Byte,Integer> 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 = new BytesRef();
+ }
+ getBytesRefFromS2CellId(cellId, result);
+ return result;
+ }
+
+ `@Override`
+ public int getLevel() {
+ return this.level;
+ }
+
+ /\*\*
+ \* Cache level of cell.
+ \*/
+ private void setLevel() {
+ if (this.cellId == null) {
+ this.level = 0;
+ }
+ else {
+ this.level = this.cellId.level() + 1;
+ }
+ }
+
+ `@Override`
+ public CellIterator getNextLevelCells(Shape shapeFilter) {
+ S2CellId[] children;
+ if (cellId == null){ // this is the world cell
+ children = FACES;
+ }
+ else {
+ children = new S2CellId[4];
+ children[0] = cellId.childBegin();
+ children[1] = children[0].next();
+ children[2] = children[1].next();
+ children[3] = children[2].next();
+ }
+ List<Cell> cells = new ArrayList<>(children.length);
+ for (S2CellId pixel : children) {
+ cells.add(new S2PrefixTreeCell(tree, pixel));
+ }
+ return new FilterCellIterator(cells.iterator(), shapeFilter);
+ }
+
+ `@Override`
+ public Shape getShape(){
+ if (shape==null){
+ if (cellId == null) { //World cell
+ return tree.getSpatialContext().getWorldBounds();
+ }
+ return tree.s2ShapeFactory.getS2CellShape(cellId);
+ }
+ return shape;
+ }
+
+ `@Override`
+ public boolean isPrefixOf(Cell c) {
+ if (cellId == null) {
+ return true;
+ }
+ S2PrefixTreeCell cell =(S2PrefixTreeCell)c;
+ return cellId.contains(cell.cellId);
+ }
+
+ `@Override`
+ public int compareToNoLeaf(Cell fromCell) {
+ if (cellId == null) {
+ return 1;
+ }
+ S2PrefixTreeCell cell = (S2PrefixTreeCell)fromCell;
+ return cellId.compareTo(cell.cellId);
+ }
+
+ /\*\*
+ \* Check if a cell is a leaf.
+ \*
+ \* `@param` ref The Byteref of the leaf
+ \* `@return` true if it is a leaf, e.g last byte is the special Character.
+ \*/
+ private boolean isLeaf(BytesRef ref){
+ return (ref.bytes[ref.offset + ref.length - 1] == LEAF);
+ }
+
+ /\*\*
+ \* Get the {`@link` S2CellId} from the {`@link` BytesRef} representation.
+ \*
+ \* `@param` ref The bytes.
+ \* `@return` the corresponding S2 cell.
+ \*/
+ private S2CellId getS2CellIdFromBytesRef(BytesRef ref){
+ int length = ref.length;
+ if (isLeaf(ref)){
+ length--;
+ }
+ if (length == 0) {
+ return null; //world cell
+ }
+ int face = PIXELS.get(ref.bytes[ref.offset]);
+ S2CellId cellId = FACES[face];
+ //we will do it directly with cell ids for performance
+ long id = cellId.id();
+ for (int i=ref.offset+1; i<ref.offset + length; i++){
+ int pos = PIXELS.get(ref.bytes[i]);
+ long oldLsb = id & -id;
+ id = id - oldLsb + (oldLsb >>> 2);
+ id = id + pos \* ((id & -id) << 1);
+ }
+ return new S2CellId(id);
+ }
+
+ /\*\*
+ \* Codify a {`@link` S2CellId} into its {`@link` BytesRef} representation.
+ \*
+ \* `@param` cellId The S2 Cell id to codify.
+ \* `@param` bref The byteref representation.
+ \*/
+ private void getBytesRefFromS2CellId(S2CellId cellId, BytesRef bref){
+ if (cellId == null) {//world cell
+ bref.length=0;
+ return;
+ }
+ int length = getLevel() + 1;
+ byte[] b = new byte[length];
— End diff –
the bref parameter may already have bytes that is of this length. If it is, reuse it thus avoiding object allocation. BytesRef exists to avoid object allocation and copying.ASF GitHub Bot (migrated from JIRA)
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<Byte,Integer> 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 = new BytesRef();
+ }
+ getBytesRefFromS2CellId(cellId, result);
+ return result;
+ }
+
+ `@Override`
+ public int getLevel() {
+ return this.level;
+ }
+
+ /\*\*
+ \* Cache level of cell.
+ \*/
+ private void setLevel() {
+ if (this.cellId == null) {
+ this.level = 0;
+ }
+ else {
+ this.level = this.cellId.level() + 1;
+ }
+ }
+
+ `@Override`
+ public CellIterator getNextLevelCells(Shape shapeFilter) {
+ S2CellId[] children;
+ if (cellId == null){ // this is the world cell
+ children = FACES;
+ }
+ else {
+ children = new S2CellId[4];
+ children[0] = cellId.childBegin();
+ children[1] = children[0].next();
+ children[2] = children[1].next();
+ children[3] = children[2].next();
+ }
+ List<Cell> cells = new ArrayList<>(children.length);
+ for (S2CellId pixel : children) {
+ cells.add(new S2PrefixTreeCell(tree, pixel));
+ }
+ return new FilterCellIterator(cells.iterator(), shapeFilter);
+ }
+
+ `@Override`
+ public Shape getShape(){
+ if (shape==null){
+ if (cellId == null) { //World cell
+ return tree.getSpatialContext().getWorldBounds();
+ }
+ return tree.s2ShapeFactory.getS2CellShape(cellId);
+ }
+ return shape;
+ }
+
+ `@Override`
+ public boolean isPrefixOf(Cell c) {
+ if (cellId == null) {
+ return true;
+ }
+ S2PrefixTreeCell cell =(S2PrefixTreeCell)c;
+ return cellId.contains(cell.cellId);
+ }
+
+ `@Override`
+ public int compareToNoLeaf(Cell fromCell) {
+ if (cellId == null) {
+ return 1;
+ }
+ S2PrefixTreeCell cell = (S2PrefixTreeCell)fromCell;
+ return cellId.compareTo(cell.cellId);
+ }
+
+ /\*\*
+ \* Check if a cell is a leaf.
+ \*
+ \* `@param` ref The Byteref of the leaf
+ \* `@return` true if it is a leaf, e.g last byte is the special Character.
+ \*/
+ private boolean isLeaf(BytesRef ref){
+ return (ref.bytes[ref.offset + ref.length - 1] == LEAF);
+ }
+
+ /\*\*
+ \* Get the {`@link` S2CellId} from the {`@link` BytesRef} representation.
+ \*
+ \* `@param` ref The bytes.
+ \* `@return` the corresponding S2 cell.
+ \*/
+ private S2CellId getS2CellIdFromBytesRef(BytesRef ref){
+ int length = ref.length;
+ if (isLeaf(ref)){
+ length--;
+ }
+ if (length == 0) {
+ return null; //world cell
+ }
+ int face = PIXELS.get(ref.bytes[ref.offset]);
+ S2CellId cellId = FACES[face];
+ //we will do it directly with cell ids for performance
+ long id = cellId.id();
+ for (int i=ref.offset+1; i<ref.offset + length; i++){
+ int pos = PIXELS.get(ref.bytes[i]);
+ long oldLsb = id & -id;
+ id = id - oldLsb + (oldLsb >>> 2);
+ id = id + pos \* ((id & -id) << 1);
+ }
+ return new S2CellId(id);
+ }
+
+ /\*\*
+ \* Codify a {`@link` S2CellId} into its {`@link` BytesRef} representation.
+ \*
+ \* `@param` cellId The S2 Cell id to codify.
+ \* `@param` bref The byteref representation.
+ \*/
+ private void getBytesRefFromS2CellId(S2CellId cellId, BytesRef bref){
+ if (cellId == null) {//world cell
+ bref.length=0;
+ return;
+ }
+ int length = getLevel() + 1;
+ byte[] b = new byte[length];
+ b[0] = TOKENS[cellId.face()];
+ for (int i =1; i < getLevel(); i++) {
+ b[i] = TOKENS[cellId.childPosition(i)];
+ }
+ bref.bytes = b;
+ bref.length = getLevel();
+ bref.offset = 0;
+ }
+
+ `@Override`
+ public int hashCode() {
+ if (cellId == null) {
+ return super.hashCode();
+ }
+ return this.cellId.hashCode();
+ }
+
+ `@Override`
+ public boolean equals(Object o) {
+ S2PrefixTreeCell cell = (S2PrefixTreeCell)o;
+ if (cellId == null) {
— End diff –
see Objects.equals(...)ASF GitHub Bot (migrated from JIRA)
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<Cell> cells = new ArrayList<>(detailLevel);
+ for (int i=0; i < detailLevel -1; i++) {
— End diff –
nitpick: put a space after that minus operatorDavid Smiley (@dsmiley) (migrated from JIRA)
(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 #6120 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
asfimport
commented
6 years ago ASF GitHub Bot (migrated from JIRA)
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<Byte,Integer> 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 = new BytesRef();
+ }
+ getBytesRefFromS2CellId(cellId, result);
+ return result;
+ }
+
+ `@Override`
+ public int getLevel() {
+ return this.level;
+ }
+
+ /\*\*
+ \* Cache level of cell.
+ \*/
+ private void setLevel() {
— End diff –
The method cellId.level() is probably efficient but because it can be called several times I think we are saving some ticks on the clock by caching it. Ignacio Vera (@iverase) (migrated from JIRA)
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?
asfimport
commented
6 years ago Ignacio Vera (@iverase) (migrated from JIRA)
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:
asfimport
commented
6 years ago Ignacio Vera (@iverase) (migrated from JIRA)
I would like to move these forward, any comment @dsmiley, @DaddyWri or it is ready to be merged?
asfimport
commented
6 years ago Karl Wright (@DaddyWri) (migrated from JIRA)
@iverase, I think this is great, but I haven't been following the details.
asfimport
commented
6 years ago David Smiley (@dsmiley) (migrated from JIRA)
Overall looks good @iverase. 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:
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.
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.
asfimport
commented
6 years ago Ignacio Vera (@iverase) (migrated from JIRA)
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 :)
asfimport
commented
6 years ago David Smiley (@dsmiley) (migrated from JIRA)
These are fantastic results @iverase!
asfimport
commented
6 years ago Ignacio Vera (@iverase) (migrated from JIRA)
@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. (@DaddyWri 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!
asfimport
commented
6 years ago Adrien Grand (@jpountz) (migrated from JIRA)
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?
asfimport
commented
6 years ago Ignacio Vera (@iverase) (migrated from JIRA)
@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.
asfimport
commented
6 years ago David Smiley (@dsmiley) (migrated from JIRA)
BTW I’m on vacation with almost no Internet thru the 21st
asfimport
commented
6 years ago Adrien Grand (@jpountz) (migrated from JIRA)
Thanks for the explanation @iverase.
asfimport
commented
6 years ago David Smiley (@dsmiley) (migrated from JIRA)
Thanks for investing the time into the illustrations @iverase. 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.
asfimport
commented
6 years ago Ignacio Vera (@iverase) (migrated from JIRA)
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.
I'm having difficulty finding the benchmark; can you provide a link to the GH file?
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.
asfimport
commented
6 years ago David Smiley (@dsmiley) (migrated from JIRA)
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.
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:
I have added the performance test classes on the branch in case you want to have a look to check results are not bias.
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.
asfimport
commented
6 years ago ASF subversion and git services (migrated from JIRA)
Commit 1e86af061e41f1a7df1740f34ef58a1110626d96 in lucene-solr's branch refs/heads/branch_7x from @iverase 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
asfimport
commented
6 years ago ASF subversion and git services (migrated from JIRA)
Commit e3032dd3fcc28570c5f9d2dab4961b5b07555912 in lucene-solr's branch refs/heads/master from @iverase 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
asfimport
commented
6 years ago ASF subversion and git services (migrated from JIRA)
Commit a281177f256fedddd4758b99306f74dc39c1bf82 in lucene-solr's branch refs/heads/master from @iverase https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=a281177
LUCENE-8126: fix precommit
asfimport
commented
6 years ago Ignacio Vera (@iverase) (migrated from JIRA)
I see this on the automatic tests:
BUILD FAILED
/home/jenkins/workspace/Lucene-Solr-master-Linux/build.xml:618: The following error occurred while executing this line:
/home/jenkins/workspace/Lucene-Solr-master-Linux/build.xml:491: The following error occurred while executing this line:
/home/jenkins/workspace/Lucene-Solr-master-Linux/build.xml:479: Source checkout is modified!!! Offending files:
asfimport
commented
6 years ago ASF subversion and git services (migrated from JIRA)
Commit ca2131573de4c8d127ea80fdb2bd37e00c87bbcc in lucene-solr's branch refs/heads/master from @iverase https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=ca21315
LUCENE-8126: fixed jar checksum
asfimport
commented
6 years ago ASF subversion and git services (migrated from JIRA)
Commit fc51c1f2ef983ce4d8ba4894f822cc6f8fbc643d in lucene-solr's branch refs/heads/branch_7x from @iverase https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=fc51c1f
LUCENE-8126: fixed jar checksum
asfimport
commented
6 years ago David Smiley (@dsmiley) (migrated from JIRA)
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:
<fieldType name="srptgeom_geo3d" class="solr.RptWithGeometrySpatialField"
spatialContextFactory="Geo3D" planetModel="wgs84"
prefixTree="org.apache.lucene.spatial.prefix.tree.S2PrefixTree$Factory"
/>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:
/** 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<Cell> 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);
...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 @iverase? Perhaps regardless better safe to not do this than do this pruning when it's not safe.
asfimport
commented
6 years ago Ignacio Vera (@iverase) (migrated from JIRA)
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:
/**
* Grid cells that share nothing with other cells when calling cell.getNextLevelCells() might
* implement this interface. They will be eligible for prune bunchy leaves.
*
* `@lucene`.experimental
*/
public interface CellCanPrune extends Cell{
/**
* Return the number of children for the current cell.
*
* `@return` the number of children cell.
*/
int getSubCellsSize();
}
That is the only method required for prune bunchy leaves. Implementation for S2 cells is trivial:
`@Override`
public int getSubCellsSize() {
if (cellId == null) { //root node
return 6;
}
return (int) Math.pow(4, tree.arity);
}
Make prune code depend on this interface and not legacyCell. What do you think?
asfimport
commented
6 years ago David Smiley (@dsmiley) (migrated from JIRA)
Make prune code depend on this interface and not legacyCell. What do you think?
+1 – lets get this simple change into 7.3; ehh?
asfimport
commented
6 years ago Ignacio Vera (@iverase) (migrated from JIRA)
@dsmiley, I have opened #9238 for tracking the change we were discussing.
asfimport
commented
6 years ago David Smiley (@dsmiley) (migrated from JIRA)
@iverase 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.
asfimport
commented
6 years ago David Smiley (@dsmiley) (migrated from JIRA)
I'll just do it; no point in asking you – sorry
asfimport
commented
6 years ago ASF subversion and git services (migrated from JIRA)
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
asfimport
commented
6 years ago ASF subversion and git services (migrated from JIRA)
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)
asfimport
commented
6 years ago Adrien Grand (@jpountz) (migrated from JIRA)
@iverase Can you set the "Fix Version/s" on this issue?
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?
Migrated from LUCENE-8126 by Ignacio Vera (@iverase), 1 vote, resolved Mar 04 2018 Attachments: SPT-cell.pdf, SPT-query.jpeg