xapian-core/docs/geospatial.rst

   1 .. Copyright (C) 2008 Lemur Consulting Ltd
   2
   3 ================================
   4 Geospatial searching with Xapian
   5 ================================
   6
   7 .. contents:: Table of contents
   8
   9 Introduction
  10 ============
  11
  12 This document describes a set of features present in Xapian which are designed
  13 to allow geospatial searches to be supported.  Currently, the geospatial
  14 support allows sets of locations to be stored associated with each document, as
  15 latitude/longitude coordinates, and allows searches to be restricted or
  16 reordered on the basis of distance from a second set of locations.
  17
  18 Three types of geospatial searches are supported:
  19
  20  - Returning a list of documents in order of distance from a query location.
  21    This may be used in conjunction with any Xapian query.
  22
  23  - Returning a list of documents within a given distance of a query location.
  24    This may be used in conjunction with any other Xapian query, and with any
  25    Xapian sort order.
  26
  27  - Returning a set of documents in a combined order based on distance from a
  28    query location, and relevance.
  29
  30 Locations are stored in value slots, allowing multiple independent locations to
  31 be used for a single document.  It is also possible to store multiple
  32 coordinates in a single value slot, in which case the closest coordinate will
  33 be used for distance calculations.
  34
  35 Metrics
  36 =======
  37
  38 A metric is a function which calculates the distance between two points.
  39
  40 Calculating the exact distance between two geographical points is an involved
  41 subject.  In fact, even defining the meaning of a geographical point is very
  42 hard to do precisely - not only do you need to define a mathematical projection
  43 used to calculate the coordinates, you also need to choose a model of the shape
  44 of the Earth, and identify a few sample points to identify the coordinates of
  45 particular locations.  Since the Earth is constantly changing shape, these
  46 coordinates also need to be defined at a particular date.
  47
  48 There are a few standard datums which define all these - a very common datum is
  49 the WGS84 datum, which is the datum used by the GPS system.  Unless you have a
  50 good reason not to, we recommend using the WGS84 datum, since this will ensure
  51 that preset parameters of the functions built in to Xapian will have the
  52 correct values (currently, the only such parameter is the Earth radius used by
  53 the GreatCircleMetric, but more may be added in future).
  54
  55 Since there are lots of ways of calculating distances between two points, using
  56 different assumptions about the approximations which are valid, Xapian allows
  57 user-implemented metrics.  These are subclasses of the Xapian::LatLongMetric
  58 class; see the API documentation for details on how to implement the various
  59 required methods.
  60
  61 There is currently only one built-in metric - the GreatCircleMetric.  As the
  62 name suggests, this calculates the distance between a latitude and longitude
  63 based on the assumption that the world is a perfect sphere.  The radius of the
  64 world can be specified as a constructor parameter, but defaults to a reasonable
  65 approximation of the radius of the Earth.  The calculation uses the haversine
  66 formula, which is accurate for points which are close together, but can have
  67 significant error for coordinates which are on opposite sides of the sphere: on
  68 the other hand, such points are likely to be at the end of a ranked list of
  69 search results, so this probably doesn't matter.
  70
  71 Indexing
  72 ========
  73
  74 To index a set of documents with location, you need to store serialised
  75 latitude-longitude coordinates in a value slot in your documents.  To do this,
  76 use the LatLongCoord class.  For example, this is how you might store a
  77 latitude and longitude corresponding to "London" in value slot 0::
  78
  79   Xapian::Document doc;
  80   doc.add_value(0, Xapian::LatLongCoord(51.53, 0.08).serialise());
  81
  82 Of course, often a location is a bit more complicated than a single point - for
  83 example, postcode regions in the UK can cover a fairly wide area.  If a search
  84 were to treat such a location as a single point, the distances returned could
  85 be incorrect by as much as a couple of miles.  Xapian therefore allows you to
  86 store a set of points in a single slot - the distance calculation will return
  87 the distance to the closest of these points.  This is often a good enough work
  88 around for this problem - if you require greater accuracy, you will need to
  89 filter the results after they are returned from Xapian.
  90
  91 To store multiple coordinates in a single slot, use the LatLongCoords class::
  92
  93   Xapian::Document doc;
  94   Xapian::LatLongCoords coords;
  95   coords.append(Xapian::LatLongCoord(51.53, 0.08));
  96   coords.append(Xapian::LatLongCoord(51.51, 0.07));
  97   coords.append(Xapian::LatLongCoord(51.52, 0.09));
  98   doc.add_value(0, coords.serialise());
  99
 100 (Note that the serialised form of a LatLongCoords object containing a single
 101 coordinate is exactly the same as the serialised form of the corresponding
 102 LatLongCoord object.)
 103
 104 Searching
 105 =========
 106
 107 Sorting results by distance
 108 ---------------------------
 109
 110 If you simply want your results to be returned in order of distance, you can
 111 use the LatLongDistanceKeyMaker class to calculate sort keys.  For example, to
 112 return results in order of distance from the coordinate (51.00, 0.50), based on
 113 the values stored in slot 0, and using the great-circle distance::
 114
 115   Xapian::Database db("my_database");
 116   Xapian::Enquire enq(db);
 117   enq.set_query(Xapian::Query("my_query"));
 118   GreatCircleMetric metric;
 119   LatLongCoord centre(51.00, 0.50);
 120   Xapian::LatLongDistanceKeyMaker keymaker(0, centre, metric);
 121   enq.set_sort_by_key(keymaker, False);
 122
 123 Filtering results by distance
 124 -----------------------------
 125
 126 To return only those results within a given distance, you can use the
 127 LatLongDistancePostingSource.  For example, to return only those results within
 128 5 miles of coordinate (51.00, 0.50), based on the values stored in slot 0, and
 129 using the great-circle distance::
 130
 131   Xapian::Database db("my_database");
 132   Xapian::Enquire enq(db);
 133   Xapian::Query q("my_query");
 134   GreatCircleMetric metric;
 135   LatLongCoord centre(51.00, 0.50);
 136   double max_range = Xapian::miles_to_metres(5);
 137   Xapian::LatLongDistancePostingSource ps(0, centre, metric, max_range)
 138   q = Xapian::Query(Xapian::Query::OP_FILTER, q, Xapian::Query(ps));
 139   enq.set_query(q);
 140
 141 Ranking results on a combination of distance and relevance
 142 ----------------------------------------------------------
 143
 144 To return results ranked by a combination of their relevance and their
 145 distance, you can also use the LatLongDistancePostingSource.  Beware that
 146 getting the right balance of weights is tricky: there is little solid
 147 theoretical basis for this, so the best approach is often to try various
 148 different parameters, evaluate the results, and settle on the best.  The
 149 LatLongDistancePostingSource returns a weight of 1.0 for a document which is at
 150 the specified location, and a lower, but always positive, weight for points
 151 further away. It has two parameters, k1 and k2, which control how fast the
 152 weight decays, which can be specified to the constructor (but aren't in this
 153 example) - see the API documentation for details of these parameters.::
 154
 155   Xapian::Database db("my_database");
 156   Xapian::Enquire enq(db);
 157   Xapian::Query q("my_query");
 158   GreatCircleMetric metric;
 159   LatLongCoord centre(51.00, 0.50);
 160   double max_range = Xapian::miles_to_metres(5);
 161   Xapian::LatLongDistancePostingSource ps(0, centre, metric, max_range)
 162   q = Xapian::Query(Xapian::Query::AND, q, Xapian::Query(ps));
 163   enq.set_query(q);
 164
 165
 166 Performance
 167 ===========
 168
 169 The location information associated with each document is stored in a document
 170 value.  This allows it to be looked up quickly at search time, so that the
 171 exact distance from the query location can be calculated.  However, this method
 172 requires that the distance of each potential match is checked, which can be
 173 expensive.
 174
 175 To gain a performance boost, it is possible to store additional terms in
 176 documents to identify regions at various scales.  There are various ways to
 177 generate such terms (for example, the O-QTM algorithm referenced below).
 178 However, the encoding for coordinates that Xapian uses has some nice properties
 179 which help here.  Specifically, the standard encoded form for a coordinate used
 180 is a 6 byte representation, which identifies a point on the surface of the
 181 earth to an accuracy of 1/16 of a second (ie, at worst slightly less than 2
 182 metre accuracy).  However, this representation can be truncated to 2 bytes to
 183 represent a bounding box 1 degree on a side, or to 3, 4 or 5 bytes to get
 184 successively more accurate bounding boxes.
 185
 186 It would therefore be possible to gain considerable efficiency for range
 187 restricted searches by storing terms holding each of these successively more
 188 accurate representations, and to construct a query combining an appropriate set
 189 of these terms to ensure that only documents which are potentially in a range
 190 of interest are considered.
 191
 192 It is entirely possible that a more efficient implementation could be performed
 193 using "R trees" or "KD trees" (or one of the many other tree structures used
 194 for geospatial indexing - see https://en.wikipedia.org/wiki/Spatial_index for a
 195 list of some of these).  However, using the QTM approach will require minimal
 196 effort and make use of the existing, and well tested, Xapian database.
 197 Additionally, by simply generating special terms to restrict the search, the
 198 existing optimisations of the Xapian query parser are taken advantage of.
 199
 200 References
 201 ==========
 202
 203 The following may be of interest.
 204
 205 The O-QTM algorithm is described in "Dutton, G. (1996). Encoding and handling
 206 geospatial data with hierarchical triangular meshes. In Kraak, M.J. and
 207 Molenaar, M. (eds.)  Advances in GIS Research II. London: Taylor & Francis,
 208 505-518." , a copy of which is available from
 209 http://www.spatial-effects.com/papers/conf/GDutton_SDH96.pdf
 210
 211 Some of the geometry needed to calculate the correct set of QTM IDs to cover a
 212 particular region is detailed in
 213 ftp://ftp.research.microsoft.com/pub/tr/tr-2005-123.pdf
 214
 215 Also, see:
 216 http://www.sdss.jhu.edu/htm/doc/c++/htmInterface.html