You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2015/06/03 16:16:39 UTC
svn commit: r1683340 [1/2] - in /lucene/dev/trunk/lucene: ./
sandbox/src/java/org/apache/lucene/bkdtree/
sandbox/src/resources/META-INF/services/
sandbox/src/test/org/apache/lucene/bkdtree/
Author: mikemccand
Date: Wed Jun 3 14:16:39 2015
New Revision: 1683340
URL: http://svn.apache.org/r1683340
Log:
LUCENE-6477: add experimental but very fast BKD tree for geo-spatial 'bbox/poly contains indexed lat/lon points' queries
Added:
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointField.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInBBoxQuery.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInPolygonQuery.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesConsumer.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesFormat.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesProducer.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeReader.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeSortedNumericDocValues.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeWriter.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/GrowingHeapLatLonWriter.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/HeapLatLonReader.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/HeapLatLonWriter.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/LatLonReader.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/LatLonWriter.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/OfflineLatLonReader.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/OfflineLatLonWriter.java (with props)
lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/package.html (with props)
lucene/dev/trunk/lucene/sandbox/src/resources/META-INF/services/org.apache.lucene.codecs.DocValuesFormat (with props)
lucene/dev/trunk/lucene/sandbox/src/test/org/apache/lucene/bkdtree/
lucene/dev/trunk/lucene/sandbox/src/test/org/apache/lucene/bkdtree/TestBKDTree.java (with props)
Modified:
lucene/dev/trunk/lucene/CHANGES.txt
Modified: lucene/dev/trunk/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/CHANGES.txt?rev=1683340&r1=1683339&r2=1683340&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/CHANGES.txt (original)
+++ lucene/dev/trunk/lucene/CHANGES.txt Wed Jun 3 14:16:39 2015
@@ -50,6 +50,10 @@ New Features
* LUCENE-6487: Spatial Geo3D API now has a WGS84 ellipsoid world model option.
(Karl Wright via David Smiley)
+* LUCENE-6477: Add experimental BKD geospatial tree doc values format
+ and queries, for fast "bbox/polygon contains lat/lon points" (Mike
+ McCandless)
+
Bug fixes
* LUCENE-6500: ParallelCompositeReader did not always call
Added: lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointField.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointField.java?rev=1683340&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointField.java (added)
+++ lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointField.java Wed Jun 3 14:16:39 2015
@@ -0,0 +1,50 @@
+package org.apache.lucene.bkdtree;
+
+/*
+ * 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.
+ */
+
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.FieldType;
+import org.apache.lucene.index.DocValuesType;
+
+/** Add this to a document to index lat/lon point, but be sure to use {@link BKDTreeDocValuesFormat} for the field. */
+public final class BKDPointField extends Field {
+
+ public static final FieldType TYPE = new FieldType();
+ static {
+ TYPE.setDocValuesType(DocValuesType.SORTED_NUMERIC);
+ TYPE.freeze();
+ }
+
+ /**
+ * Creates a new BKDPointField field with the specified lat and lon
+ * @param name field name
+ * @param lat double latitude
+ * @param lon double longitude
+ * @throws IllegalArgumentException if the field name is null or lat or lon are out of bounds
+ */
+ public BKDPointField(String name, double lat, double lon) {
+ super(name, TYPE);
+ if (BKDTreeWriter.validLat(lat) == false) {
+ throw new IllegalArgumentException("invalid lat (" + lat + "): must be -90 to 90");
+ }
+ if (BKDTreeWriter.validLon(lon) == false) {
+ throw new IllegalArgumentException("invalid lon (" + lon + "): must be -180 to 180");
+ }
+ fieldsData = Long.valueOf(((long) BKDTreeWriter.encodeLat(lat) << 32) | (BKDTreeWriter.encodeLon(lon) & 0xffffffffL));
+ }
+}
Added: lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInBBoxQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInBBoxQuery.java?rev=1683340&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInBBoxQuery.java (added)
+++ lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInBBoxQuery.java Wed Jun 3 14:16:39 2015
@@ -0,0 +1,214 @@
+package org.apache.lucene.bkdtree;
+
+/*
+ * 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.
+ */
+
+import java.io.IOException;
+import java.util.Set;
+
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedNumericDocValues;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.Explanation;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.ToStringUtils;
+
+/** Finds all previously indexed points that fall within the specified boundings box.
+ *
+ * <p>The field must be indexed with {@link BKDTreeDocValuesFormat}, and {@link BKDPointField} added per document.
+ *
+ * <p><b>NOTE</b>: for fastest performance, this allocates FixedBitSet(maxDoc) for each segment. The score of each hit is the query boost.
+ *
+ * @lucene.experimental */
+
+public class BKDPointInBBoxQuery extends Query {
+ final String field;
+ final double minLat;
+ final double maxLat;
+ final double minLon;
+ final double maxLon;
+
+ /** Matches all points >= minLon, minLat (inclusive) and < maxLon, maxLat (exclusive). */
+ public BKDPointInBBoxQuery(String field, double minLat, double maxLat, double minLon, double maxLon) {
+ this.field = field;
+ if (BKDTreeWriter.validLat(minLat) == false) {
+ throw new IllegalArgumentException("minLat=" + minLat + " is not a valid latitude");
+ }
+ if (BKDTreeWriter.validLat(maxLat) == false) {
+ throw new IllegalArgumentException("maxLat=" + maxLat + " is not a valid latitude");
+ }
+ if (BKDTreeWriter.validLon(minLon) == false) {
+ throw new IllegalArgumentException("minLon=" + minLon + " is not a valid longitude");
+ }
+ if (BKDTreeWriter.validLon(maxLon) == false) {
+ throw new IllegalArgumentException("maxLon=" + maxLon + " is not a valid longitude");
+ }
+ this.minLon = minLon;
+ this.maxLon = maxLon;
+ this.minLat = minLat;
+ this.maxLat = maxLat;
+ }
+
+ @Override
+ public Weight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
+
+ // I don't use RandomAccessWeight here: it's no good to approximate with "match all docs"; this is an inverted structure and should be
+ // used in the first pass:
+
+ return new Weight(this) {
+ private float queryNorm;
+ private float queryWeight;
+
+ @Override
+ public void extractTerms(Set<Term> terms) {
+ }
+
+ @Override
+ public float getValueForNormalization() throws IOException {
+ queryWeight = getBoost();
+ return queryWeight * queryWeight;
+ }
+
+ @Override
+ public void normalize(float norm, float topLevelBoost) {
+ queryNorm = norm * topLevelBoost;
+ queryWeight *= queryNorm;
+ }
+
+ @Override
+ public Explanation explain(LeafReaderContext context, int doc) throws IOException {
+ final Scorer s = scorer(context, context.reader().getLiveDocs());
+ final boolean exists = s != null && s.advance(doc) == doc;
+
+ if (exists) {
+ return Explanation.match(queryWeight, BKDPointInBBoxQuery.this.toString() + ", product of:",
+ Explanation.match(getBoost(), "boost"), Explanation.match(queryNorm, "queryNorm"));
+ } else {
+ return Explanation.noMatch(BKDPointInBBoxQuery.this.toString() + " doesn't match id " + doc);
+ }
+ }
+
+ @Override
+ public Scorer scorer(LeafReaderContext context, Bits acceptDocs) throws IOException {
+ LeafReader reader = context.reader();
+ SortedNumericDocValues sdv = reader.getSortedNumericDocValues(field);
+ if (sdv == null) {
+ // No docs in this segment had this field
+ return null;
+ }
+
+ if (sdv instanceof BKDTreeSortedNumericDocValues == false) {
+ throw new IllegalStateException("field \"" + field + "\" was not indexed with BKDTreeDocValuesFormat: got: " + sdv);
+ }
+ BKDTreeSortedNumericDocValues treeDV = (BKDTreeSortedNumericDocValues) sdv;
+ BKDTreeReader tree = treeDV.getBKDTreeReader();
+
+ DocIdSet result = tree.intersect(acceptDocs, minLat, maxLat, minLon, maxLon, treeDV.delegate);
+
+ final DocIdSetIterator disi = result.iterator();
+
+ return new Scorer(this) {
+
+ @Override
+ public float score() throws IOException {
+ return queryWeight;
+ }
+
+ @Override
+ public int freq() throws IOException {
+ return 1;
+ }
+
+ @Override
+ public int docID() {
+ return disi.docID();
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ return disi.nextDoc();
+ }
+
+ @Override
+ public int advance(int target) throws IOException {
+ return disi.advance(target);
+ }
+
+ @Override
+ public long cost() {
+ return disi.cost();
+ }
+ };
+ }
+ };
+ }
+ @Override
+ public int hashCode() {
+ int hash = super.hashCode();
+ hash += Double.hashCode(minLat)^0x14fa55fb;
+ hash += Double.hashCode(maxLat)^0x733fa5fe;
+ hash += Double.hashCode(minLon)^0x14fa55fb;
+ hash += Double.hashCode(maxLon)^0x733fa5fe;
+ return hash;
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (super.equals(other) && other instanceof BKDPointInBBoxQuery) {
+ final BKDPointInBBoxQuery q = (BKDPointInBBoxQuery) other;
+ return field.equals(q.field) &&
+ minLat == q.minLat &&
+ maxLat == q.maxLat &&
+ minLon == q.minLon &&
+ maxLon == q.maxLon;
+ }
+
+ return false;
+ }
+
+ @Override
+ public String toString(String field) {
+ final StringBuilder sb = new StringBuilder();
+ sb.append(getClass().getSimpleName());
+ sb.append(':');
+ if (this.field.equals(field) == false) {
+ sb.append("field=");
+ sb.append(this.field);
+ sb.append(':');
+ }
+
+ return sb.append(" Lower Left: [")
+ .append(minLon)
+ .append(',')
+ .append(minLat)
+ .append(']')
+ .append(" Upper Right: [")
+ .append(maxLon)
+ .append(',')
+ .append(maxLat)
+ .append("]")
+ .append(ToStringUtils.boost(getBoost()))
+ .toString();
+ }
+}
Added: lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInPolygonQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInPolygonQuery.java?rev=1683340&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInPolygonQuery.java (added)
+++ lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDPointInPolygonQuery.java Wed Jun 3 14:16:39 2015
@@ -0,0 +1,284 @@
+package org.apache.lucene.bkdtree;
+
+/*
+ * 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.
+ */
+
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.Set;
+
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedNumericDocValues;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.Explanation;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.ToStringUtils;
+
+/** Finds all previously indexed points that fall within the specified polygon.
+ *
+ * <p>The field must be indexed with {@link BKDTreeDocValuesFormat}, and {@link BKDPointField} added per document.
+ *
+ * <p>Because this implementation cannot intersect each cell with the polygon, it will be costly especially for large polygons, as every
+ * possible point must be checked.
+ *
+ * <p><b>NOTE</b>: for fastest performance, this allocates FixedBitSet(maxDoc) for each segment. The score of each hit is the query boost.
+ *
+ * @lucene.experimental */
+
+public class BKDPointInPolygonQuery extends Query {
+ final String field;
+ final double minLat;
+ final double maxLat;
+ final double minLon;
+ final double maxLon;
+ final double[] polyLats;
+ final double[] polyLons;
+
+ /** The lats/lons must be clockwise or counter-clockwise. */
+ public BKDPointInPolygonQuery(String field, double[] polyLats, double[] polyLons) {
+ this.field = field;
+ if (polyLats.length != polyLons.length) {
+ throw new IllegalArgumentException("polyLats and polyLons must be equal length");
+ }
+ if (polyLats.length < 4) {
+ throw new IllegalArgumentException("at least 4 polygon points required");
+ }
+ if (polyLats[0] != polyLats[polyLats.length-1]) {
+ throw new IllegalArgumentException("first and last points of the polygon must be the same (it must close itself): polyLats[0]=" + polyLats[0] + " polyLats[" + (polyLats.length-1) + "]=" + polyLats[polyLats.length-1]);
+ }
+ if (polyLons[0] != polyLons[polyLons.length-1]) {
+ throw new IllegalArgumentException("first and last points of the polygon must be the same (it must close itself): polyLons[0]=" + polyLons[0] + " polyLons[" + (polyLons.length-1) + "]=" + polyLons[polyLons.length-1]);
+ }
+
+ this.polyLats = polyLats;
+ this.polyLons = polyLons;
+
+ double minLon = Double.POSITIVE_INFINITY;
+ double minLat = Double.POSITIVE_INFINITY;
+ double maxLon = Double.NEGATIVE_INFINITY;
+ double maxLat = Double.NEGATIVE_INFINITY;
+ for(int i=0;i<polyLats.length;i++) {
+ double lat = polyLats[i];
+ if (BKDTreeWriter.validLat(lat) == false) {
+ throw new IllegalArgumentException("polyLats[" + i + "]=" + lat + " is not a valid latitude");
+ }
+ minLat = Math.min(minLat, lat);
+ maxLat = Math.max(maxLat, lat);
+ double lon = polyLons[i];
+ if (BKDTreeWriter.validLon(lon) == false) {
+ throw new IllegalArgumentException("polyLons[" + i + "]=" + lat + " is not a valid longitude");
+ }
+ minLon = Math.min(minLon, lon);
+ maxLon = Math.max(maxLon, lon);
+ }
+ this.minLon = minLon;
+ this.maxLon = maxLon;
+ this.minLat = minLat;
+ this.maxLat = maxLat;
+ }
+
+ @Override
+ public Weight createWeight(IndexSearcher searcher, boolean needsScores) throws IOException {
+
+ // I don't use RandomAccessWeight here: it's no good to approximate with "match all docs"; this is an inverted structure and should be
+ // used in the first pass:
+
+ // TODO: except that the polygon verify is costly! The approximation should be all docs in all overlapping cells, and matches() should
+ // then check the polygon
+
+ return new Weight(this) {
+ private float queryNorm;
+ private float queryWeight;
+
+ @Override
+ public void extractTerms(Set<Term> terms) {
+ }
+
+ @Override
+ public float getValueForNormalization() throws IOException {
+ queryWeight = getBoost();
+ return queryWeight * queryWeight;
+ }
+
+ @Override
+ public void normalize(float norm, float topLevelBoost) {
+ queryNorm = norm * topLevelBoost;
+ queryWeight *= queryNorm;
+ }
+
+ @Override
+ public Explanation explain(LeafReaderContext context, int doc) throws IOException {
+ final Scorer s = scorer(context, context.reader().getLiveDocs());
+ final boolean exists = s != null && s.advance(doc) == doc;
+
+ if (exists) {
+ return Explanation.match(queryWeight, BKDPointInPolygonQuery.this.toString() + ", product of:",
+ Explanation.match(getBoost(), "boost"), Explanation.match(queryNorm, "queryNorm"));
+ } else {
+ return Explanation.noMatch(BKDPointInPolygonQuery.this.toString() + " doesn't match id " + doc);
+ }
+ }
+
+ @Override
+ public Scorer scorer(LeafReaderContext context, Bits acceptDocs) throws IOException {
+ LeafReader reader = context.reader();
+ SortedNumericDocValues sdv = reader.getSortedNumericDocValues(field);
+ if (sdv == null) {
+ // No docs in this segment had this field
+ return null;
+ }
+
+ if (sdv instanceof BKDTreeSortedNumericDocValues == false) {
+ throw new IllegalStateException("field \"" + field + "\" was not indexed with BKDTreeDocValuesFormat: got: " + sdv);
+ }
+ BKDTreeSortedNumericDocValues treeDV = (BKDTreeSortedNumericDocValues) sdv;
+ BKDTreeReader tree = treeDV.getBKDTreeReader();
+
+ // TODO: make this more efficient: as we recurse the BKD tree we should check whether the
+ // bbox we are recursing into intersects our shape; Apache SIS may have (non-GPL!) code to do this?
+ DocIdSet result = tree.intersect(acceptDocs, minLat, maxLat, minLon, maxLon,
+ new BKDTreeReader.LatLonFilter() {
+ @Override
+ public boolean accept(double lat, double lon) {
+ return pointInPolygon(lat, lon);
+ }
+ }, treeDV.delegate);
+
+ final DocIdSetIterator disi = result.iterator();
+
+ return new Scorer(this) {
+
+ @Override
+ public float score() throws IOException {
+ return queryWeight;
+ }
+
+ @Override
+ public int freq() throws IOException {
+ return 1;
+ }
+
+ @Override
+ public int docID() {
+ return disi.docID();
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ return disi.nextDoc();
+ }
+
+ @Override
+ public int advance(int target) throws IOException {
+ return disi.advance(target);
+ }
+
+ @Override
+ public long cost() {
+ return disi.cost();
+ }
+ };
+ }
+ };
+ }
+
+ // TODO: share w/ GeoUtils:
+
+ /**
+ * simple even-odd point in polygon computation
+ * 1. Determine if point is contained in the longitudinal range
+ * 2. Determine whether point crosses the edge by computing the latitudinal delta
+ * between the end-point of a parallel vector (originating at the point) and the
+ * y-component of the edge sink
+ *
+ * NOTE: Requires polygon point (x,y) order either clockwise or counter-clockwise
+ */
+ boolean pointInPolygon(double lat, double lon) {
+ /**
+ * Note: This is using a euclidean coordinate system which could result in
+ * upwards of 110KM error at the equator.
+ * TODO convert coordinates to cylindrical projection (e.g. mercator)
+ */
+
+ // TODO: this quantizes a bit differently ... boundary cases will fail here:
+ boolean inPoly = false;
+ for (int i = 1; i < polyLons.length; i++) {
+ if (polyLons[i] <= lon && polyLons[i-1] > lon || polyLons[i-1] <= lon && polyLons[i] > lon) {
+ if (polyLats[i] + (lon - polyLons[i]) / (polyLons[i-1] - polyLons[i]) * (polyLats[i-1] - polyLats[i]) <= lat) {
+ inPoly = !inPoly;
+ }
+ }
+ }
+ return inPoly;
+ }
+
+ @Override
+ @SuppressWarnings({"unchecked","rawtypes"})
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (o == null || getClass() != o.getClass()) return false;
+ if (!super.equals(o)) return false;
+
+ BKDPointInPolygonQuery that = (BKDPointInPolygonQuery) o;
+
+ if (Arrays.equals(polyLons, that.polyLons) == false) {
+ return false;
+ }
+ if (Arrays.equals(polyLats, that.polyLats) == false) {
+ return false;
+ }
+
+ return true;
+ }
+
+ @Override
+ public final int hashCode() {
+ int result = super.hashCode();
+ result = 31 * result + Arrays.hashCode(polyLons);
+ result = 31 * result + Arrays.hashCode(polyLats);
+ return result;
+ }
+
+ @Override
+ public String toString(String field) {
+ final StringBuilder sb = new StringBuilder();
+ sb.append(getClass().getSimpleName());
+ sb.append(':');
+ if (this.field.equals(field) == false) {
+ sb.append(" field=");
+ sb.append(this.field);
+ sb.append(':');
+ }
+ sb.append(" Points: ");
+ for (int i=0; i<polyLons.length; ++i) {
+ sb.append("[")
+ .append(polyLons[i])
+ .append(", ")
+ .append(polyLats[i])
+ .append("] ");
+ }
+ sb.append(ToStringUtils.boost(getBoost()));
+ return sb.toString();
+ }
+}
Added: lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesConsumer.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesConsumer.java?rev=1683340&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesConsumer.java (added)
+++ lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesConsumer.java Wed Jun 3 14:16:39 2015
@@ -0,0 +1,133 @@
+package org.apache.lucene.bkdtree;
+
+/*
+ * 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.
+ */
+
+import java.io.Closeable;
+import java.io.IOException;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+
+import org.apache.lucene.codecs.CodecUtil;
+import org.apache.lucene.codecs.DocValuesConsumer;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.IndexFileNames;
+import org.apache.lucene.index.SegmentWriteState;
+import org.apache.lucene.store.IndexOutput;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.IOUtils;
+
+class BKDTreeDocValuesConsumer extends DocValuesConsumer implements Closeable {
+ final DocValuesConsumer delegate;
+ final int maxPointsInLeafNode;
+ final int maxPointsSortInHeap;
+ final IndexOutput out;
+ final Map<Integer,Long> fieldIndexFPs = new HashMap<>();
+ final SegmentWriteState state;
+
+ public BKDTreeDocValuesConsumer(DocValuesConsumer delegate, SegmentWriteState state, int maxPointsInLeafNode, int maxPointsSortInHeap) throws IOException {
+ BKDTreeWriter.verifyParams(maxPointsInLeafNode, maxPointsSortInHeap);
+ this.delegate = delegate;
+ this.maxPointsInLeafNode = maxPointsInLeafNode;
+ this.maxPointsSortInHeap = maxPointsSortInHeap;
+ this.state = state;
+ String datFileName = IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, BKDTreeDocValuesFormat.DATA_EXTENSION);
+ out = state.directory.createOutput(datFileName, state.context);
+ CodecUtil.writeIndexHeader(out, BKDTreeDocValuesFormat.DATA_CODEC_NAME, BKDTreeDocValuesFormat.DATA_VERSION_CURRENT,
+ state.segmentInfo.getId(), state.segmentSuffix);
+ }
+
+ @Override
+ public void close() throws IOException {
+ boolean success = false;
+ try {
+ CodecUtil.writeFooter(out);
+ success = true;
+ } finally {
+ if (success) {
+ IOUtils.close(delegate, out);
+ } else {
+ IOUtils.closeWhileHandlingException(delegate, out);
+ }
+ }
+
+ String metaFileName = IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, BKDTreeDocValuesFormat.META_EXTENSION);
+ IndexOutput metaOut = state.directory.createOutput(metaFileName, state.context);
+ success = false;
+ try {
+ CodecUtil.writeIndexHeader(metaOut, BKDTreeDocValuesFormat.META_CODEC_NAME, BKDTreeDocValuesFormat.META_VERSION_CURRENT,
+ state.segmentInfo.getId(), state.segmentSuffix);
+ metaOut.writeVInt(fieldIndexFPs.size());
+ for(Map.Entry<Integer,Long> ent : fieldIndexFPs.entrySet()) {
+ metaOut.writeVInt(ent.getKey());
+ metaOut.writeVLong(ent.getValue());
+ }
+ CodecUtil.writeFooter(metaOut);
+ success = true;
+ } finally {
+ if (success) {
+ IOUtils.close(metaOut);
+ } else {
+ IOUtils.closeWhileHandlingException(metaOut);
+ }
+ }
+ }
+
+ @Override
+ public void addSortedNumericField(FieldInfo field, Iterable<Number> docToValueCount, Iterable<Number> values) throws IOException {
+ delegate.addSortedNumericField(field, docToValueCount, values);
+ BKDTreeWriter writer = new BKDTreeWriter(maxPointsInLeafNode, maxPointsSortInHeap);
+ Iterator<Number> valueIt = values.iterator();
+ Iterator<Number> valueCountIt = docToValueCount.iterator();
+ for (int docID=0;docID<state.segmentInfo.maxDoc();docID++) {
+ assert valueCountIt.hasNext();
+ int count = valueCountIt.next().intValue();
+ for(int i=0;i<count;i++) {
+ assert valueIt.hasNext();
+ long value = valueIt.next().longValue();
+ int latEnc = (int) (value >> 32);
+ int lonEnc = (int) (value & 0xffffffff);
+ writer.add(latEnc, lonEnc, docID);
+ }
+ }
+
+ long indexStartFP = writer.finish(out);
+
+ fieldIndexFPs.put(field.number, indexStartFP);
+ }
+
+ @Override
+ public void addNumericField(FieldInfo field, Iterable<Number> values) throws IOException {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void addBinaryField(FieldInfo field, Iterable<BytesRef> values) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void addSortedField(FieldInfo field, Iterable<BytesRef> values, Iterable<Number> docToOrd) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void addSortedSetField(FieldInfo field, Iterable<BytesRef> values, Iterable<Number> docToOrdCount, Iterable<Number> ords) {
+ throw new UnsupportedOperationException();
+ }
+}
Added: lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesFormat.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesFormat.java?rev=1683340&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesFormat.java (added)
+++ lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesFormat.java Wed Jun 3 14:16:39 2015
@@ -0,0 +1,109 @@
+package org.apache.lucene.bkdtree;
+
+/*
+ * 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.
+ */
+
+import java.io.IOException;
+
+import org.apache.lucene.codecs.DocValuesConsumer;
+import org.apache.lucene.codecs.DocValuesFormat;
+import org.apache.lucene.codecs.DocValuesProducer;
+import org.apache.lucene.codecs.lucene50.Lucene50DocValuesFormat;
+import org.apache.lucene.index.SegmentReadState;
+import org.apache.lucene.index.SegmentWriteState;
+
+/**
+ * A {@link DocValuesFormat} to efficiently index geo-spatial lat/lon points
+ * from {@link BKDPointField} for fast bounding-box ({@link BKDPointInBBoxQuery})
+ * and polygon ({@link BKDPointInPolygonQuery}) queries.
+ *
+ * <p>This wraps {@link Lucene50DocValuesFormat}, but saves its own BKD tree
+ * structures to disk for fast query-time intersection. See <a
+ * href="https://www.cs.duke.edu/~pankaj/publications/papers/bkd-sstd.pdf">this paper</a>
+ * for details.
+ *
+ * <p>The BKD tree slices up 2D (lat/lon) space into smaller and
+ * smaller rectangles, until the smallest rectangles have approximately
+ * between X/2 and X (X default is 1024) points in them, at which point
+ * such leaf cells are written as a block to disk, while the index tree
+ * structure recording how space was sub-divided is loaded into HEAP
+ * at search time. At search time, the tree is recursed based on whether
+ * each of left or right child overlap with the query shape, and once
+ * a leaf block is reached, all documents in that leaf block are collected
+ * if the cell is fully enclosed by the query shape, or filtered and then
+ * collected, if not.
+ *
+ * <p>The index is also quite compact, because docs only appear once in
+ * the tree (no "prefix terms").
+ *
+ * <p>In addition to the files written by {@link Lucene50DocValuesFormat}, this format writes:
+ * <ol>
+ * <li><tt>.kdd</tt>: BKD leaf data and index</li>
+ * <li><tt>.kdm</tt>: BKD metadata</li>
+ * </ol>
+ *
+ * <p>The disk format is experimental and free to change suddenly, and this code likely has new and exciting bugs!
+ *
+ * @lucene.experimental */
+
+public class BKDTreeDocValuesFormat extends DocValuesFormat {
+
+ static final String DATA_CODEC_NAME = "BKDData";
+ static final int DATA_VERSION_START = 0;
+ static final int DATA_VERSION_CURRENT = DATA_VERSION_START;
+ static final String DATA_EXTENSION = "kdd";
+
+ static final String META_CODEC_NAME = "BKDMeta";
+ static final int META_VERSION_START = 0;
+ static final int META_VERSION_CURRENT = META_VERSION_START;
+ static final String META_EXTENSION = "kdm";
+
+ private final int maxPointsInLeafNode;
+ private final int maxPointsSortInHeap;
+
+ private final DocValuesFormat delegate = new Lucene50DocValuesFormat();
+
+ /** Default constructor */
+ public BKDTreeDocValuesFormat() {
+ this(BKDTreeWriter.DEFAULT_MAX_POINTS_IN_LEAF_NODE, BKDTreeWriter.DEFAULT_MAX_POINTS_SORT_IN_HEAP);
+ }
+
+ /** Creates this with custom configuration.
+ *
+ * @param maxPointsInLeafNode Maximum number of points in each leaf cell. Smaller values create a deeper tree with larger in-heap index and possibly
+ * faster searching. The default is 1024.
+ * @param maxPointsSortInHeap Maximum number of points where in-heap sort can be used. When the number of points exceeds this, a (slower)
+ * offline sort is used. The default is 128 * 1024.
+ *
+ * @lucene.experimental */
+ public BKDTreeDocValuesFormat(int maxPointsInLeafNode, int maxPointsSortInHeap) {
+ super("BKDTree");
+ BKDTreeWriter.verifyParams(maxPointsInLeafNode, maxPointsSortInHeap);
+ this.maxPointsInLeafNode = maxPointsInLeafNode;
+ this.maxPointsSortInHeap = maxPointsSortInHeap;
+ }
+
+ @Override
+ public DocValuesConsumer fieldsConsumer(final SegmentWriteState state) throws IOException {
+ return new BKDTreeDocValuesConsumer(delegate.fieldsConsumer(state), state, maxPointsInLeafNode, maxPointsSortInHeap);
+ }
+
+ @Override
+ public DocValuesProducer fieldsProducer(SegmentReadState state) throws IOException {
+ return new BKDTreeDocValuesProducer(delegate.fieldsProducer(state), state);
+ }
+}
Added: lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesProducer.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesProducer.java?rev=1683340&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesProducer.java (added)
+++ lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeDocValuesProducer.java Wed Jun 3 14:16:39 2015
@@ -0,0 +1,169 @@
+package org.apache.lucene.bkdtree;
+
+/*
+ * 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.
+ */
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.atomic.AtomicLong;
+
+import org.apache.lucene.codecs.CodecUtil;
+import org.apache.lucene.codecs.DocValuesProducer;
+import org.apache.lucene.index.BinaryDocValues;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.IndexFileNames;
+import org.apache.lucene.index.NumericDocValues;
+import org.apache.lucene.index.SegmentReadState;
+import org.apache.lucene.index.SortedDocValues;
+import org.apache.lucene.index.SortedNumericDocValues;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.store.ChecksumIndexInput;
+import org.apache.lucene.store.IndexInput;
+import org.apache.lucene.util.Accountable;
+import org.apache.lucene.util.Accountables;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.IOUtils;
+import org.apache.lucene.util.RamUsageEstimator;
+
+class BKDTreeDocValuesProducer extends DocValuesProducer {
+
+ private final Map<String,BKDTreeReader> treeReaders = new HashMap<>();
+ private final Map<Integer,Long> fieldToIndexFPs = new HashMap<>();
+
+ private final IndexInput datIn;
+ private final AtomicLong ramBytesUsed;
+ private final int maxDoc;
+ private final DocValuesProducer delegate;
+ private final boolean merging;
+
+ public BKDTreeDocValuesProducer(DocValuesProducer delegate, SegmentReadState state) throws IOException {
+ String metaFileName = IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, BKDTreeDocValuesFormat.META_EXTENSION);
+ ChecksumIndexInput metaIn = state.directory.openChecksumInput(metaFileName, state.context);
+ CodecUtil.checkIndexHeader(metaIn, BKDTreeDocValuesFormat.META_CODEC_NAME, BKDTreeDocValuesFormat.META_VERSION_START, BKDTreeDocValuesFormat.META_VERSION_CURRENT,
+ state.segmentInfo.getId(), state.segmentSuffix);
+ int fieldCount = metaIn.readVInt();
+ for(int i=0;i<fieldCount;i++) {
+ int fieldNumber = metaIn.readVInt();
+ long indexFP = metaIn.readVLong();
+ fieldToIndexFPs.put(fieldNumber, indexFP);
+ }
+ CodecUtil.checkFooter(metaIn);
+ metaIn.close();
+
+ String datFileName = IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, BKDTreeDocValuesFormat.DATA_EXTENSION);
+ datIn = state.directory.openInput(datFileName, state.context);
+ CodecUtil.checkIndexHeader(datIn, BKDTreeDocValuesFormat.DATA_CODEC_NAME, BKDTreeDocValuesFormat.DATA_VERSION_START, BKDTreeDocValuesFormat.DATA_VERSION_CURRENT,
+ state.segmentInfo.getId(), state.segmentSuffix);
+ ramBytesUsed = new AtomicLong(RamUsageEstimator.shallowSizeOfInstance(getClass()));
+ maxDoc = state.segmentInfo.maxDoc();
+ this.delegate = delegate;
+ merging = false;
+ }
+
+ // clone for merge: we don't hang onto the BKDTrees we load
+ BKDTreeDocValuesProducer(BKDTreeDocValuesProducer orig) throws IOException {
+ assert Thread.holdsLock(orig);
+ datIn = orig.datIn.clone();
+ ramBytesUsed = new AtomicLong(orig.ramBytesUsed.get());
+ delegate = orig.delegate.getMergeInstance();
+ fieldToIndexFPs.putAll(orig.fieldToIndexFPs);
+ treeReaders.putAll(orig.treeReaders);
+ merging = true;
+ maxDoc = orig.maxDoc;
+ }
+
+ @Override
+ public synchronized SortedNumericDocValues getSortedNumeric(FieldInfo field) throws IOException {
+ BKDTreeReader treeReader = treeReaders.get(field.name);
+ if (treeReader == null) {
+ // Lazy load
+ Long fp = fieldToIndexFPs.get(field.number);
+ if (fp == null) {
+ throw new IllegalArgumentException("this field was not indexed as a BKDPointField");
+ }
+ datIn.seek(fp);
+ treeReader = new BKDTreeReader(datIn, maxDoc);
+
+ // Only hang onto the reader when we are not merging:
+ if (merging == false) {
+ treeReaders.put(field.name, treeReader);
+ ramBytesUsed.addAndGet(treeReader.ramBytesUsed());
+ }
+ }
+
+ return new BKDTreeSortedNumericDocValues(treeReader, delegate.getSortedNumeric(field));
+ }
+
+ @Override
+ public void close() throws IOException {
+ IOUtils.close(datIn, delegate);
+ }
+
+ @Override
+ public void checkIntegrity() throws IOException {
+ CodecUtil.checksumEntireFile(datIn);
+ }
+
+ @Override
+ public NumericDocValues getNumeric(FieldInfo field) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public BinaryDocValues getBinary(FieldInfo field) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public SortedDocValues getSorted(FieldInfo field) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public SortedSetDocValues getSortedSet(FieldInfo field) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public Bits getDocsWithField(FieldInfo field) throws IOException {
+ return delegate.getDocsWithField(field);
+ }
+
+ @Override
+ public synchronized Collection<Accountable> getChildResources() {
+ List<Accountable> resources = new ArrayList<>();
+ for(Map.Entry<String,BKDTreeReader> ent : treeReaders.entrySet()) {
+ resources.add(Accountables.namedAccountable("field " + ent.getKey(), ent.getValue()));
+ }
+
+ return resources;
+ }
+
+ @Override
+ public synchronized DocValuesProducer getMergeInstance() throws IOException {
+ return new BKDTreeDocValuesProducer(this);
+ }
+
+ @Override
+ public long ramBytesUsed() {
+ return ramBytesUsed.get();
+ }
+}
Added: lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeReader.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeReader.java?rev=1683340&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeReader.java (added)
+++ lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeReader.java Wed Jun 3 14:16:39 2015
@@ -0,0 +1,385 @@
+package org.apache.lucene.bkdtree;
+
+/*
+ * 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.
+ */
+
+import java.io.IOException;
+
+import org.apache.lucene.index.SortedNumericDocValues;
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.store.ByteArrayDataInput;
+import org.apache.lucene.store.IndexInput;
+import org.apache.lucene.util.Accountable;
+import org.apache.lucene.util.BitDocIdSet;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.RamUsageEstimator;
+
+/** Handles intersection of a shape with a BKD tree previously written with {@link BKDTreeWriter}.
+ *
+ * @lucene.experimental */
+
+final class BKDTreeReader implements Accountable {
+ final private int[] splitValues;
+ final private int leafNodeOffset;
+ final private long[] leafBlockFPs;
+ final int maxDoc;
+ final IndexInput in;
+
+ interface LatLonFilter {
+ boolean accept(double lat, double lon);
+ }
+
+ public BKDTreeReader(IndexInput in, int maxDoc) throws IOException {
+
+ // Read index:
+ int numLeaves = in.readVInt();
+ leafNodeOffset = numLeaves;
+
+ // Tree is fully balanced binary tree, so number of nodes = numLeaves-1, except our nodeIDs are 1-based (splitValues[0] is unused):
+ splitValues = new int[numLeaves];
+ for(int i=0;i<numLeaves;i++) {
+ splitValues[i] = in.readInt();
+ }
+ leafBlockFPs = new long[numLeaves];
+ for(int i=0;i<numLeaves;i++) {
+ leafBlockFPs[i] = in.readVLong();
+ }
+
+ this.maxDoc = maxDoc;
+ this.in = in;
+ }
+
+ private static final class QueryState {
+ final IndexInput in;
+ byte[] scratch = new byte[16];
+ final ByteArrayDataInput scratchReader = new ByteArrayDataInput(scratch);
+ final FixedBitSet bits;
+ final int latMinEnc;
+ final int latMaxEnc;
+ final int lonMinEnc;
+ final int lonMaxEnc;
+ final LatLonFilter latLonFilter;
+ final SortedNumericDocValues sndv;
+
+ public QueryState(IndexInput in, int maxDoc,
+ int latMinEnc, int latMaxEnc,
+ int lonMinEnc, int lonMaxEnc,
+ LatLonFilter latLonFilter,
+ SortedNumericDocValues sndv) {
+ this.in = in;
+ this.bits = new FixedBitSet(maxDoc);
+ this.latMinEnc = latMinEnc;
+ this.latMaxEnc = latMaxEnc;
+ this.lonMinEnc = lonMinEnc;
+ this.lonMaxEnc = lonMaxEnc;
+ this.latLonFilter = latLonFilter;
+ this.sndv = sndv;
+ }
+ }
+
+ public DocIdSet intersect(Bits acceptDocs, double latMin, double latMax, double lonMin, double lonMax, SortedNumericDocValues sndv) throws IOException {
+ return intersect(acceptDocs, latMin, latMax, lonMin, lonMax, null, sndv);
+ }
+
+ public DocIdSet intersect(Bits acceptDocs, double latMin, double latMax, double lonMin, double lonMax, LatLonFilter filter, SortedNumericDocValues sndv) throws IOException {
+ if (BKDTreeWriter.validLat(latMin) == false) {
+ throw new IllegalArgumentException("invalid latMin: " + latMin);
+ }
+ if (BKDTreeWriter.validLat(latMax) == false) {
+ throw new IllegalArgumentException("invalid latMax: " + latMax);
+ }
+ if (BKDTreeWriter.validLon(lonMin) == false) {
+ throw new IllegalArgumentException("invalid lonMin: " + lonMin);
+ }
+ if (BKDTreeWriter.validLon(lonMax) == false) {
+ throw new IllegalArgumentException("invalid lonMax: " + lonMax);
+ }
+
+ int latMinEnc = BKDTreeWriter.encodeLat(latMin);
+ int latMaxEnc = BKDTreeWriter.encodeLat(latMax);
+ int lonMinEnc = BKDTreeWriter.encodeLon(lonMin);
+ int lonMaxEnc = BKDTreeWriter.encodeLon(lonMax);
+
+ // TODO: we should use a sparse bit collector here, but BitDocIdSet.Builder is 2.4X slower than straight FixedBitSet.
+ // Maybe we should use simple int[] (not de-duping) up until size X, then cutover. Or maybe SentinelIntSet when it's
+ // small.
+
+ QueryState state = new QueryState(in.clone(), maxDoc,
+ latMinEnc, latMaxEnc,
+ lonMinEnc, lonMaxEnc,
+ filter,
+ sndv);
+
+ int hitCount = intersect(acceptDocs, state, 1,
+ BKDTreeWriter.encodeLat(-90.0),
+ BKDTreeWriter.encodeLat(Math.nextAfter(90.0, Double.POSITIVE_INFINITY)),
+ BKDTreeWriter.encodeLon(-180.0),
+ BKDTreeWriter.encodeLon(Math.nextAfter(180.0, Double.POSITIVE_INFINITY)));
+
+ // NOTE: hitCount is an over-estimate in the multi-valued case:
+ return new BitDocIdSet(state.bits, hitCount);
+ }
+
+ /** Fast path: this is called when the query rect fully encompasses all cells under this node. */
+ private int addAll(Bits acceptDocs, QueryState state, int nodeID) throws IOException {
+ if (nodeID >= leafNodeOffset) {
+ // Leaf node
+ long fp = leafBlockFPs[nodeID-leafNodeOffset];
+ //System.out.println(" leaf nodeID=" + nodeID + " vs leafNodeOffset=" + leafNodeOffset + " fp=" + fp);
+ if (fp == 0) {
+ // Dead end node (adversary case):
+ return 0;
+ }
+ //IndexInput in = leafDISI.in;
+ state.in.seek(fp);
+ //allLeafDISI.reset(fp);
+
+ //System.out.println(" seek to leafFP=" + fp);
+ // How many points are stored in this leaf cell:
+ int count = state.in.readVInt();
+ if (state.latLonFilter != null) {
+ // Handle this differently since we must also look up lat/lon:
+
+ int hitCount = 0;
+ for(int i=0;i<count;i++) {
+
+ int docID = state.in.readInt();
+
+ if (acceptDocs == null || acceptDocs.get(docID)) {
+
+ state.sndv.setDocument(docID);
+
+ // How many values this doc has:
+ int docValueCount = state.sndv.count();
+ for(int j=0;j<docValueCount;j++) {
+ long enc = state.sndv.valueAt(j);
+ int latEnc = (int) ((enc>>32) & 0xffffffffL);
+ int lonEnc = (int) (enc & 0xffffffffL);
+
+ // TODO: maybe we can fix LatLonFilter to operate on encoded forms?
+ if (state.latLonFilter.accept(BKDTreeWriter.decodeLat(latEnc), BKDTreeWriter.decodeLon(lonEnc))) {
+ state.bits.set(docID);
+ hitCount++;
+
+ // Stop processing values for this doc since it's now accepted:
+ break;
+ }
+ }
+ }
+ }
+
+ return hitCount;
+
+ } else if (acceptDocs != null) {
+ for(int i=0;i<count;i++) {
+ int docID = state.in.readInt();
+ if (acceptDocs.get(docID)) {
+ state.bits.set(docID);
+ }
+ }
+ } else {
+ for(int i=0;i<count;i++) {
+ int docID = state.in.readInt();
+ state.bits.set(docID);
+ }
+ }
+
+ //bits.or(allLeafDISI);
+ //return allLeafDISI.getHitCount();
+ return count;
+ } else {
+ int splitValue = splitValues[nodeID];
+
+ if (splitValue == Integer.MAX_VALUE) {
+ // Dead end node (adversary case):
+ return 0;
+ }
+
+ //System.out.println(" splitValue=" + splitValue);
+
+ //System.out.println(" addAll: inner");
+ int count = 0;
+ count += addAll(acceptDocs, state, 2*nodeID);
+ count += addAll(acceptDocs, state, 2*nodeID+1);
+ //System.out.println(" addAll: return count=" + count);
+ return count;
+ }
+ }
+
+ private int intersect(Bits acceptDocs, QueryState state,
+ int nodeID,
+ int cellLatMinEnc, int cellLatMaxEnc, int cellLonMinEnc, int cellLonMaxEnc)
+ throws IOException {
+
+ // 2.06 sec -> 1.52 sec for 225 OSM London queries:
+ if (state.latMinEnc <= cellLatMinEnc && state.latMaxEnc >= cellLatMaxEnc && state.lonMinEnc <= cellLonMinEnc && state.lonMaxEnc >= cellLonMaxEnc) {
+ // Optimize the case when the query fully contains this cell: we can
+ // recursively add all points without checking if they match the query:
+
+ /*
+ System.out.println("A: " + BKDTreeWriter.decodeLat(cellLatMinEnc)
+ + " " + BKDTreeWriter.decodeLat(cellLatMaxEnc)
+ + " " + BKDTreeWriter.decodeLon(cellLonMinEnc)
+ + " " + BKDTreeWriter.decodeLon(cellLonMaxEnc));
+ */
+
+ return addAll(acceptDocs, state, nodeID);
+ }
+
+ long latRange = (long) cellLatMaxEnc - (long) cellLatMinEnc;
+ long lonRange = (long) cellLonMaxEnc - (long) cellLonMinEnc;
+
+ int dim;
+ if (latRange >= lonRange) {
+ dim = 0;
+ } else {
+ dim = 1;
+ }
+
+ //System.out.println("\nintersect node=" + nodeID + " vs " + leafNodeOffset);
+
+ if (nodeID >= leafNodeOffset) {
+ // Leaf node; scan and filter all points in this block:
+ //System.out.println(" intersect leaf nodeID=" + nodeID + " vs leafNodeOffset=" + leafNodeOffset + " fp=" + leafBlockFPs[nodeID-leafNodeOffset]);
+ int hitCount = 0;
+
+ //IndexInput in = leafDISI.in;
+ long fp = leafBlockFPs[nodeID-leafNodeOffset];
+ if (fp == 0) {
+ // Dead end node (adversary case):
+ //System.out.println(" dead-end leaf");
+ return 0;
+ }
+
+ /*
+ System.out.println("I: " + BKDTreeWriter.decodeLat(cellLatMinEnc)
+ + " " + BKDTreeWriter.decodeLat(cellLatMaxEnc)
+ + " " + BKDTreeWriter.decodeLon(cellLonMinEnc)
+ + " " + BKDTreeWriter.decodeLon(cellLonMaxEnc));
+ */
+
+ state.in.seek(fp);
+
+ // How many points are stored in this leaf cell:
+ int count = state.in.readVInt();
+
+ for(int i=0;i<count;i++) {
+ int docID = state.in.readInt();
+ if (acceptDocs == null || acceptDocs.get(docID)) {
+ state.sndv.setDocument(docID);
+ // How many values this doc has:
+ int docValueCount = state.sndv.count();
+ for(int j=0;j<docValueCount;j++) {
+ long enc = state.sndv.valueAt(j);
+
+ int latEnc = (int) ((enc>>32) & 0xffffffffL);
+ int lonEnc = (int) (enc & 0xffffffffL);
+
+ if (latEnc >= state.latMinEnc &&
+ latEnc < state.latMaxEnc &&
+ lonEnc >= state.lonMinEnc &&
+ lonEnc < state.lonMaxEnc &&
+ (state.latLonFilter == null ||
+ state.latLonFilter.accept(BKDTreeWriter.decodeLat(latEnc), BKDTreeWriter.decodeLon(lonEnc)))) {
+ state.bits.set(docID);
+ hitCount++;
+
+ // Stop processing values for this doc:
+ break;
+ }
+ }
+ }
+ }
+
+ return hitCount;
+
+ // this (using BitDocIdSet.Builder) is 3.4X slower!
+ /*
+ //bits.or(leafDISI);
+ //return leafDISI.getHitCount();
+ */
+
+ } else {
+
+ int splitValue = splitValues[nodeID];
+
+ if (splitValue == Integer.MAX_VALUE) {
+ // Dead end node (adversary case):
+ //System.out.println(" dead-end sub-tree");
+ return 0;
+ }
+
+ //System.out.println(" splitValue=" + splitValue);
+
+ int count = 0;
+
+ if (dim == 0) {
+
+ //System.out.println(" split on lat=" + splitValue);
+
+ // Inner node split on lat:
+
+ // Left node:
+ if (state.latMinEnc < splitValue) {
+ //System.out.println(" recurse left");
+ count += intersect(acceptDocs, state,
+ 2*nodeID,
+ cellLatMinEnc, splitValue, cellLonMinEnc, cellLonMaxEnc);
+ }
+
+ // Right node:
+ if (state.latMaxEnc >= splitValue) {
+ //System.out.println(" recurse right");
+ count += intersect(acceptDocs, state,
+ 2*nodeID+1,
+ splitValue, cellLatMaxEnc, cellLonMinEnc, cellLonMaxEnc);
+ }
+
+ } else {
+ // Inner node split on lon:
+ assert dim == 1;
+
+ // System.out.println(" split on lon=" + splitValue);
+
+ // Left node:
+ if (state.lonMinEnc < splitValue) {
+ // System.out.println(" recurse left");
+ count += intersect(acceptDocs, state,
+ 2*nodeID,
+ cellLatMinEnc, cellLatMaxEnc, cellLonMinEnc, splitValue);
+ }
+
+ // Right node:
+ if (state.lonMaxEnc >= splitValue) {
+ // System.out.println(" recurse right");
+ count += intersect(acceptDocs, state,
+ 2*nodeID+1,
+ cellLatMinEnc, cellLatMaxEnc, splitValue, cellLonMaxEnc);
+ }
+ }
+
+ return count;
+ }
+ }
+
+ @Override
+ public long ramBytesUsed() {
+ return splitValues.length * RamUsageEstimator.NUM_BYTES_INT +
+ leafBlockFPs.length * RamUsageEstimator.NUM_BYTES_LONG;
+ }
+}
Added: lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeSortedNumericDocValues.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeSortedNumericDocValues.java?rev=1683340&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeSortedNumericDocValues.java (added)
+++ lucene/dev/trunk/lucene/sandbox/src/java/org/apache/lucene/bkdtree/BKDTreeSortedNumericDocValues.java Wed Jun 3 14:16:39 2015
@@ -0,0 +1,49 @@
+package org.apache.lucene.bkdtree;
+
+/*
+ * 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.
+ */
+
+import org.apache.lucene.index.SortedNumericDocValues;
+
+class BKDTreeSortedNumericDocValues extends SortedNumericDocValues {
+ final BKDTreeReader bkdTreeReader;
+ final SortedNumericDocValues delegate;
+
+ public BKDTreeSortedNumericDocValues(BKDTreeReader bkdTreeReader, SortedNumericDocValues delegate) {
+ this.bkdTreeReader = bkdTreeReader;
+ this.delegate = delegate;
+ }
+
+ public BKDTreeReader getBKDTreeReader() {
+ return bkdTreeReader;
+ }
+
+ @Override
+ public void setDocument(int doc) {
+ delegate.setDocument(doc);
+ }
+
+ @Override
+ public long valueAt(int index) {
+ return delegate.valueAt(index);
+ }
+
+ @Override
+ public int count() {
+ return delegate.count();
+ }
+}