lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From rm...@apache.org
Subject lucene-solr git commit: LUCENE-7103: further optimize LatLonPoint.newDistanceSort
Date Mon, 14 Mar 2016 20:27:36 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/branch_6x a6fe1c0b1 -> 3163b9895


LUCENE-7103: further optimize LatLonPoint.newDistanceSort


Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/3163b989
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/3163b989
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/3163b989

Branch: refs/heads/branch_6x
Commit: 3163b98959ae834b27a0ee8479344b61460d8851
Parents: a6fe1c0
Author: Robert Muir <rmuir@apache.org>
Authored: Mon Mar 14 16:25:31 2016 -0400
Committer: Robert Muir <rmuir@apache.org>
Committed: Mon Mar 14 16:26:39 2016 -0400

----------------------------------------------------------------------
 .../document/LatLonPointDistanceComparator.java | 41 ++++++++++++++++----
 .../lucene/document/TestBigIntegerPoint.java    |  4 +-
 .../lucene/document/TestInetAddressPoint.java   |  4 +-
 .../apache/lucene/document/TestLatLonPoint.java |  2 +-
 .../document/TestLatLonPointDistanceQuery.java  |  4 +-
 .../document/TestLatLonPointDistanceSort.java   | 28 +++++++++++--
 6 files changed, 64 insertions(+), 19 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3163b989/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java
b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java
index 86c9134..ef4c3f3 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonPointDistanceComparator.java
@@ -26,9 +26,10 @@ import org.apache.lucene.index.SortedNumericDocValues;
 import org.apache.lucene.search.FieldComparator;
 import org.apache.lucene.search.LeafFieldComparator;
 import org.apache.lucene.search.Scorer;
-import org.apache.lucene.spatial.util.GeoDistanceUtils;
+import org.apache.lucene.spatial.util.GeoProjectionUtils;
 import org.apache.lucene.spatial.util.GeoRect;
 import org.apache.lucene.spatial.util.GeoUtils;
+import org.apache.lucene.util.SloppyMath;
 
 /**
  * Compares documents by distance from an origin point
@@ -96,7 +97,7 @@ class LatLonPointDistanceComparator extends FieldComparator<Double>
implements L
         crossesDateLine = false;
       } else {
         assert Double.isFinite(bottom);
-        GeoRect box = GeoUtils.circleToBBox(longitude, latitude, bottom);
+        GeoRect box = GeoUtils.circleToBBox(longitude, latitude, haversin2(bottom));
         // pre-encode our box to our integer encoding, so we don't have to decode 
         // to double values for uncompetitive hits. This has some cost!
         int minLatEncoded = LatLonPoint.encodeLatitude(box.minLat);
@@ -166,7 +167,7 @@ class LatLonPointDistanceComparator extends FieldComparator<Double>
implements L
       if (outsideBox == false) {
         double docLatitude = LatLonPoint.decodeLatitude(latitudeBits);
         double docLongitude = LatLonPoint.decodeLongitude(longitudeBits);
-        minValue = Math.min(minValue, GeoDistanceUtils.haversin(latitude, longitude, docLatitude,
docLongitude));
+        minValue = Math.min(minValue, haversin1(latitude, longitude, docLatitude, docLongitude));
       }
     }
     return Double.compare(bottom, minValue);
@@ -174,7 +175,7 @@ class LatLonPointDistanceComparator extends FieldComparator<Double>
implements L
   
   @Override
   public void copy(int slot, int doc) throws IOException {
-    values[slot] = distance(doc);
+    values[slot] = sortKey(doc);
   }
   
   @Override
@@ -190,17 +191,17 @@ class LatLonPointDistanceComparator extends FieldComparator<Double>
implements L
   
   @Override
   public Double value(int slot) {
-    return Double.valueOf(values[slot]);
+    return Double.valueOf(haversin2(values[slot]));
   }
   
   @Override
   public int compareTop(int doc) throws IOException {
-    return Double.compare(topValue, distance(doc));
+    return Double.compare(topValue, haversin2(sortKey(doc)));
   }
   
   // TODO: optimize for single-valued case?
   // TODO: do all kinds of other optimizations!
-  double distance(int doc) {
+  double sortKey(int doc) {
     currentDocs.setDocument(doc);
 
     int numValues = currentDocs.count();
@@ -213,8 +214,32 @@ class LatLonPointDistanceComparator extends FieldComparator<Double>
implements L
       long encoded = currentDocs.valueAt(i);
       double docLatitude = LatLonPoint.decodeLatitude((int)(encoded >> 32));
       double docLongitude = LatLonPoint.decodeLongitude((int)(encoded & 0xFFFFFFFF));
-      minValue = Math.min(minValue, GeoDistanceUtils.haversin(latitude, longitude, docLatitude,
docLongitude));
+      minValue = Math.min(minValue, haversin1(latitude, longitude, docLatitude, docLongitude));
     }
     return minValue;
   }
+
+  // sort by first part of the haversin computation. note that this value is meaningless
to the user.
+  // invoke haversin2() to "complete" the calculation and get a distance in meters.
+  static double haversin1(double lat1, double lon1, double lat2, double lon2) {
+    double dLat = SloppyMath.TO_RADIANS * (lat2 - lat1);
+    double dLon = SloppyMath.TO_RADIANS * (lon2 - lon1);
+    lat1 = SloppyMath.TO_RADIANS * (lat1);
+    lat2 = SloppyMath.TO_RADIANS * (lat2);
+
+    final double sinDLatO2 = SloppyMath.sin(dLat / 2);
+    final double sinDLonO2 = SloppyMath.sin(dLon / 2);
+
+    return sinDLatO2*sinDLatO2 + sinDLonO2 * sinDLonO2 * SloppyMath.cos(lat1) * SloppyMath.cos(lat2);
+  }
+
+  // second half of the haversin calculation, used to convert results from haversin1 (used
internally
+  // for sorting) for display purposes.
+  static double haversin2(double partial) {
+    if (Double.isInfinite(partial)) {
+      return partial;
+    }
+    double c = 2 * SloppyMath.asin(Math.sqrt(partial));
+    return (GeoProjectionUtils.SEMIMAJOR_AXIS * c);
+  }
 }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3163b989/lucene/sandbox/src/test/org/apache/lucene/document/TestBigIntegerPoint.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestBigIntegerPoint.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestBigIntegerPoint.java
index 8f38bcd..a7a1295 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestBigIntegerPoint.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestBigIntegerPoint.java
@@ -41,7 +41,7 @@ public class TestBigIntegerPoint extends LuceneTestCase {
     
     // search and verify we found our doc
     IndexReader reader = writer.getReader();
-    IndexSearcher searcher = newSearcher(reader, false);
+    IndexSearcher searcher = newSearcher(reader);
     assertEquals(1, searcher.count(BigIntegerPoint.newExactQuery("field", large)));
     assertEquals(1, searcher.count(BigIntegerPoint.newRangeQuery("field", large.subtract(BigInteger.ONE),
large.add(BigInteger.ONE))));
     assertEquals(1, searcher.count(BigIntegerPoint.newSetQuery("field", large)));
@@ -66,7 +66,7 @@ public class TestBigIntegerPoint extends LuceneTestCase {
     
     // search and verify we found our doc
     IndexReader reader = writer.getReader();
-    IndexSearcher searcher = newSearcher(reader, false);
+    IndexSearcher searcher = newSearcher(reader);
     assertEquals(1, searcher.count(BigIntegerPoint.newExactQuery("field", negative)));
     assertEquals(1, searcher.count(BigIntegerPoint.newRangeQuery("field", negative.subtract(BigInteger.ONE),
negative.add(BigInteger.ONE))));
 

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3163b989/lucene/sandbox/src/test/org/apache/lucene/document/TestInetAddressPoint.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestInetAddressPoint.java
b/lucene/sandbox/src/test/org/apache/lucene/document/TestInetAddressPoint.java
index c91b52b..b0e7107 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestInetAddressPoint.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestInetAddressPoint.java
@@ -41,7 +41,7 @@ public class TestInetAddressPoint extends LuceneTestCase {
     
     // search and verify we found our doc
     IndexReader reader = writer.getReader();
-    IndexSearcher searcher = newSearcher(reader, false);
+    IndexSearcher searcher = newSearcher(reader);
     assertEquals(1, searcher.count(InetAddressPoint.newExactQuery("field", address)));
     assertEquals(1, searcher.count(InetAddressPoint.newPrefixQuery("field", address, 24)));
     assertEquals(1, searcher.count(InetAddressPoint.newRangeQuery("field", InetAddress.getByName("1.2.3.3"),
InetAddress.getByName("1.2.3.5"))));
@@ -68,7 +68,7 @@ public class TestInetAddressPoint extends LuceneTestCase {
     
     // search and verify we found our doc
     IndexReader reader = writer.getReader();
-    IndexSearcher searcher = newSearcher(reader, false);
+    IndexSearcher searcher = newSearcher(reader);
     assertEquals(1, searcher.count(InetAddressPoint.newExactQuery("field", address)));
     assertEquals(1, searcher.count(InetAddressPoint.newPrefixQuery("field", address, 64)));
     assertEquals(1, searcher.count(InetAddressPoint.newRangeQuery("field", InetAddress.getByName("fec0::f66c"),
InetAddress.getByName("fec0::f66e"))));

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3163b989/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPoint.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPoint.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPoint.java
index d180d58..ff4af12 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPoint.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPoint.java
@@ -39,7 +39,7 @@ public class TestLatLonPoint extends LuceneTestCase {
     
     // search and verify we found our doc
     IndexReader reader = writer.getReader();
-    IndexSearcher searcher = newSearcher(reader, false);
+    IndexSearcher searcher = newSearcher(reader);
     assertEquals(1, searcher.count(LatLonPoint.newBoxQuery("field", 18, 19, -66, -65)));
 
     reader.close();

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3163b989/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java
b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java
index fa95710..c69791c 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceQuery.java
@@ -55,7 +55,7 @@ public class TestLatLonPointDistanceQuery extends LuceneTestCase {
     
     // search within 50km and verify we found our doc
     IndexReader reader = writer.getReader();
-    IndexSearcher searcher = newSearcher(reader, false);
+    IndexSearcher searcher = newSearcher(reader);
     assertEquals(1, searcher.count(LatLonPoint.newDistanceQuery("field", 18, -65, 50_000)));
 
     reader.close();
@@ -148,7 +148,7 @@ public class TestLatLonPointDistanceQuery extends LuceneTestCase {
       writer.addDocument(doc);
     }
     IndexReader reader = writer.getReader();
-    IndexSearcher searcher = new IndexSearcher(reader);
+    IndexSearcher searcher = newSearcher(reader);
 
     for (int i = 0; i < numQueries; i++) {
       double lat = -90 + 180.0 * random().nextDouble();

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3163b989/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
index a776b3f..7df956f 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
@@ -54,7 +54,7 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase {
     iw.addDocument(doc);
     
     IndexReader reader = iw.getReader();
-    IndexSearcher searcher = new IndexSearcher(reader);
+    IndexSearcher searcher = newSearcher(reader);
     iw.close();
 
     Sort sort = new Sort(LatLonPoint.newDistanceSort("location", 40.7143528, -74.0059731));
@@ -91,7 +91,7 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase {
     iw.addDocument(doc);
     
     IndexReader reader = iw.getReader();
-    IndexSearcher searcher = new IndexSearcher(reader);
+    IndexSearcher searcher = newSearcher(reader);
     iw.close();
 
     Sort sort = new Sort(LatLonPoint.newDistanceSort("location", 40.7143528, -74.0059731));
@@ -128,7 +128,7 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase {
     iw.addDocument(doc);
     
     IndexReader reader = iw.getReader();
-    IndexSearcher searcher = new IndexSearcher(reader);
+    IndexSearcher searcher = newSearcher(reader);
     iw.close();
 
     SortField sortField = LatLonPoint.newDistanceSort("location", 40.7143528, -74.0059731);
@@ -234,7 +234,7 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase {
       writer.addDocument(doc);
     }
     IndexReader reader = writer.getReader();
-    IndexSearcher searcher = new IndexSearcher(reader);
+    IndexSearcher searcher = newSearcher(reader);
 
     for (int i = 0; i < numQueries; i++) {
       double lat = -90 + 180.0 * random().nextDouble();
@@ -289,4 +289,24 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase {
     writer.close();
     dir.close();
   }
+
+  /** Test this method sorts the same way as real haversin */
+  public void testPartialHaversin() {
+    for (int i = 0; i < 100000; i++) {
+      double centerLat = -90 + 180.0 * random().nextDouble();
+      double centerLon = -180 + 360.0 * random().nextDouble();
+
+      double lat1 = -90 + 180.0 * random().nextDouble();
+      double lon1 = -180 + 360.0 * random().nextDouble();
+
+      double lat2 = -90 + 180.0 * random().nextDouble();
+      double lon2 = -180 + 360.0 * random().nextDouble();
+
+      int expected = Integer.signum(Double.compare(GeoDistanceUtils.haversin(centerLat, centerLon,
lat1, lon1),
+                                                   GeoDistanceUtils.haversin(centerLat, centerLon,
lat2, lon2)));
+      int actual = Integer.signum(Double.compare(LatLonPointDistanceComparator.haversin1(centerLat,
centerLon, lat1, lon1),
+                                                 LatLonPointDistanceComparator.haversin1(centerLat,
centerLon, lat2, lon2)));
+      assertEquals(expected, actual);
+    }
+  }
 }


Mime
View raw message