File: geospatial.html

package info (click to toggle)
xapian-core 1.4.11-1
links: PTS, VCS
area: main
in suites: buster
size: 21,876 kB
sloc: cpp: 120,318; ansic: 9,802; sh: 4,664; perl: 851; makefile: 567; tcl: 319; python: 40
file content (576 lines) | stat: -rw-r--r-- 20,325 bytes
<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.14: http://docutils.sourceforge.net/" />
<title>Geospatial searching with Xapian</title>
<style type="text/css">

/*
:Author: David Goodger (goodger@python.org)
:Id: $Id: html4css1.css 7952 2016-07-26 18:15:59Z milde $
:Copyright: This stylesheet has been placed in the public domain.

Default cascading style sheet for the HTML output of Docutils.

See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/

/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
  border: 0 }

table.borderless td, table.borderless th {
  /* Override padding for "table.docutils td" with "! important".
     The right padding separates the table cells. */
  padding: 0 0.5em 0 0 ! important }

.first {
  /* Override more specific margin styles with "! important". */
  margin-top: 0 ! important }

.last, .with-subtitle {
  margin-bottom: 0 ! important }

.hidden {
  display: none }

.subscript {
  vertical-align: sub;
  font-size: smaller }

.superscript {
  vertical-align: super;
  font-size: smaller }

a.toc-backref {
  text-decoration: none ;
  color: black }

blockquote.epigraph {
  margin: 2em 5em ; }

dl.docutils dd {
  margin-bottom: 0.5em }

object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
  overflow: hidden;
}

/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
  font-weight: bold }
*/

div.abstract {
  margin: 2em 5em }

div.abstract p.topic-title {
  font-weight: bold ;
  text-align: center }

div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
  margin: 2em ;
  border: medium outset ;
  padding: 1em }

div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
  font-weight: bold ;
  font-family: sans-serif }

div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title, .code .error {
  color: red ;
  font-weight: bold ;
  font-family: sans-serif }

/* Uncomment (and remove this text!) to get reduced vertical space in
   compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
  margin-bottom: 0.5em }

div.compound .compound-last, div.compound .compound-middle {
  margin-top: 0.5em }
*/

div.dedication {
  margin: 2em 5em ;
  text-align: center ;
  font-style: italic }

div.dedication p.topic-title {
  font-weight: bold ;
  font-style: normal }

div.figure {
  margin-left: 2em ;
  margin-right: 2em }

div.footer, div.header {
  clear: both;
  font-size: smaller }

div.line-block {
  display: block ;
  margin-top: 1em ;
  margin-bottom: 1em }

div.line-block div.line-block {
  margin-top: 0 ;
  margin-bottom: 0 ;
  margin-left: 1.5em }

div.sidebar {
  margin: 0 0 0.5em 1em ;
  border: medium outset ;
  padding: 1em ;
  background-color: #ffffee ;
  width: 40% ;
  float: right ;
  clear: right }

div.sidebar p.rubric {
  font-family: sans-serif ;
  font-size: medium }

div.system-messages {
  margin: 5em }

div.system-messages h1 {
  color: red }

div.system-message {
  border: medium outset ;
  padding: 1em }

div.system-message p.system-message-title {
  color: red ;
  font-weight: bold }

div.topic {
  margin: 2em }

h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
  margin-top: 0.4em }

h1.title {
  text-align: center }

h2.subtitle {
  text-align: center }

hr.docutils {
  width: 75% }

img.align-left, .figure.align-left, object.align-left, table.align-left {
  clear: left ;
  float: left ;
  margin-right: 1em }

img.align-right, .figure.align-right, object.align-right, table.align-right {
  clear: right ;
  float: right ;
  margin-left: 1em }

img.align-center, .figure.align-center, object.align-center {
  display: block;
  margin-left: auto;
  margin-right: auto;
}

table.align-center {
  margin-left: auto;
  margin-right: auto;
}

.align-left {
  text-align: left }

.align-center {
  clear: both ;
  text-align: center }

.align-right {
  text-align: right }

/* reset inner alignment in figures */
div.align-right {
  text-align: inherit }

/* div.align-center * { */
/*   text-align: left } */

.align-top    {
  vertical-align: top }

.align-middle {
  vertical-align: middle }

.align-bottom {
  vertical-align: bottom }

ol.simple, ul.simple {
  margin-bottom: 1em }

ol.arabic {
  list-style: decimal }

ol.loweralpha {
  list-style: lower-alpha }

ol.upperalpha {
  list-style: upper-alpha }

ol.lowerroman {
  list-style: lower-roman }

ol.upperroman {
  list-style: upper-roman }

p.attribution {
  text-align: right ;
  margin-left: 50% }

p.caption {
  font-style: italic }

p.credits {
  font-style: italic ;
  font-size: smaller }

p.label {
  white-space: nowrap }

p.rubric {
  font-weight: bold ;
  font-size: larger ;
  color: maroon ;
  text-align: center }

p.sidebar-title {
  font-family: sans-serif ;
  font-weight: bold ;
  font-size: larger }

p.sidebar-subtitle {
  font-family: sans-serif ;
  font-weight: bold }

p.topic-title {
  font-weight: bold }

pre.address {
  margin-bottom: 0 ;
  margin-top: 0 ;
  font: inherit }

pre.literal-block, pre.doctest-block, pre.math, pre.code {
  margin-left: 2em ;
  margin-right: 2em }

pre.code .ln { color: grey; } /* line numbers */
pre.code, code { background-color: #eeeeee }
pre.code .comment, code .comment { color: #5C6576 }
pre.code .keyword, code .keyword { color: #3B0D06; font-weight: bold }
pre.code .literal.string, code .literal.string { color: #0C5404 }
pre.code .name.builtin, code .name.builtin { color: #352B84 }
pre.code .deleted, code .deleted { background-color: #DEB0A1}
pre.code .inserted, code .inserted { background-color: #A3D289}

span.classifier {
  font-family: sans-serif ;
  font-style: oblique }

span.classifier-delimiter {
  font-family: sans-serif ;
  font-weight: bold }

span.interpreted {
  font-family: sans-serif }

span.option {
  white-space: nowrap }

span.pre {
  white-space: pre }

span.problematic {
  color: red }

span.section-subtitle {
  /* font-size relative to parent (h1..h6 element) */
  font-size: 80% }

table.citation {
  border-left: solid 1px gray;
  margin-left: 1px }

table.docinfo {
  margin: 2em 4em }

table.docutils {
  margin-top: 0.5em ;
  margin-bottom: 0.5em }

table.footnote {
  border-left: solid 1px black;
  margin-left: 1px }

table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
  padding-left: 0.5em ;
  padding-right: 0.5em ;
  vertical-align: top }

table.docutils th.field-name, table.docinfo th.docinfo-name {
  font-weight: bold ;
  text-align: left ;
  white-space: nowrap ;
  padding-left: 0 }

/* "booktabs" style (no vertical lines) */
table.docutils.booktabs {
  border: 0px;
  border-top: 2px solid;
  border-bottom: 2px solid;
  border-collapse: collapse;
}
table.docutils.booktabs * {
  border: 0px;
}
table.docutils.booktabs th {
  border-bottom: thin solid;
  text-align: left;
}

h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
  font-size: 100% }

ul.auto-toc {
  list-style-type: none }

</style>
</head>
<body>
<div class="document" id="geospatial-searching-with-xapian">
<h1 class="title">Geospatial searching with Xapian</h1>

<!-- Copyright (C) 2008 Lemur Consulting Ltd -->
<div class="contents topic" id="table-of-contents">
<p class="topic-title first">Table of contents</p>
<ul class="simple">
<li><a class="reference internal" href="#introduction" id="id1">Introduction</a></li>
<li><a class="reference internal" href="#metrics" id="id2">Metrics</a></li>
<li><a class="reference internal" href="#indexing" id="id3">Indexing</a></li>
<li><a class="reference internal" href="#searching" id="id4">Searching</a><ul>
<li><a class="reference internal" href="#sorting-results-by-distance" id="id5">Sorting results by distance</a></li>
<li><a class="reference internal" href="#filtering-results-by-distance" id="id6">Filtering results by distance</a></li>
<li><a class="reference internal" href="#ranking-results-on-a-combination-of-distance-and-relevance" id="id7">Ranking results on a combination of distance and relevance</a></li>
</ul>
</li>
<li><a class="reference internal" href="#performance" id="id8">Performance</a></li>
<li><a class="reference internal" href="#references" id="id9">References</a></li>
</ul>
</div>
<div class="section" id="introduction">
<h1><a class="toc-backref" href="#id1">Introduction</a></h1>
<p>This document describes a set of features present in Xapian which are designed
to allow geospatial searches to be supported.  Currently, the geospatial
support allows sets of locations to be stored associated with each document, as
latitude/longitude coordinates, and allows searches to be restricted or
reordered on the basis of distance from a second set of locations.</p>
<p>Three types of geospatial searches are supported:</p>
<blockquote>
<ul class="simple">
<li>Returning a list of documents in order of distance from a query location.
This may be used in conjunction with any Xapian query.</li>
<li>Returning a list of documents within a given distance of a query location.
This may be used in conjunction with any other Xapian query, and with any
Xapian sort order.</li>
<li>Returning a set of documents in a combined order based on distance from a
query location, and relevance.</li>
</ul>
</blockquote>
<p>Locations are stored in value slots, allowing multiple independent locations to
be used for a single document.  It is also possible to store multiple
coordinates in a single value slot, in which case the closest coordinate will
be used for distance calculations.</p>
</div>
<div class="section" id="metrics">
<h1><a class="toc-backref" href="#id2">Metrics</a></h1>
<p>A metric is a function which calculates the distance between two points.</p>
<p>Calculating the exact distance between two geographical points is an involved
subject.  In fact, even defining the meaning of a geographical point is very
hard to do precisely - not only do you need to define a mathematical projection
used to calculate the coordinates, you also need to choose a model of the shape
of the Earth, and identify a few sample points to identify the coordinates of
particular locations.  Since the Earth is constantly changing shape, these
coordinates also need to be defined at a particular date.</p>
<p>There are a few standard datums which define all these - a very common datum is
the WGS84 datum, which is the datum used by the GPS system.  Unless you have a
good reason not to, we recommend using the WGS84 datum, since this will ensure
that preset parameters of the functions built in to Xapian will have the
correct values (currently, the only such parameter is the Earth radius used by
the GreatCircleMetric, but more may be added in future).</p>
<p>Since there are lots of ways of calculating distances between two points, using
different assumptions about the approximations which are valid, Xapian allows
user-implemented metrics.  These are subclasses of the Xapian::LatLongMetric
class; see the API documentation for details on how to implement the various
required methods.</p>
<p>There is currently only one built-in metric - the GreatCircleMetric.  As the
name suggests, this calculates the distance between a latitude and longitude
based on the assumption that the world is a perfect sphere.  The radius of the
world can be specified as a constructor parameter, but defaults to a reasonable
approximation of the radius of the Earth.  The calculation uses the haversine
formula, which is accurate for points which are close together, but can have
significant error for coordinates which are on opposite sides of the sphere: on
the other hand, such points are likely to be at the end of a ranked list of
search results, so this probably doesn't matter.</p>
</div>
<div class="section" id="indexing">
<h1><a class="toc-backref" href="#id3">Indexing</a></h1>
<p>To index a set of documents with location, you need to store serialised
latitude-longitude coordinates in a value slot in your documents.  To do this,
use the LatLongCoord class.  For example, this is how you might store a
latitude and longitude corresponding to &quot;London&quot; in value slot 0:</p>
<pre class="literal-block">
Xapian::Document doc;
doc.add_value(0, Xapian::LatLongCoord(51.53, 0.08).serialise());
</pre>
<p>Of course, often a location is a bit more complicated than a single point - for
example, postcode regions in the UK can cover a fairly wide area.  If a search
were to treat such a location as a single point, the distances returned could
be incorrect by as much as a couple of miles.  Xapian therefore allows you to
store a set of points in a single slot - the distance calculation will return
the distance to the closest of these points.  This is often a good enough work
around for this problem - if you require greater accuracy, you will need to
filter the results after they are returned from Xapian.</p>
<p>To store multiple coordinates in a single slot, use the LatLongCoords class:</p>
<pre class="literal-block">
Xapian::Document doc;
Xapian::LatLongCoords coords;
coords.append(Xapian::LatLongCoord(51.53, 0.08));
coords.append(Xapian::LatLongCoord(51.51, 0.07));
coords.append(Xapian::LatLongCoord(51.52, 0.09));
doc.add_value(0, coords.serialise());
</pre>
<p>(Note that the serialised form of a LatLongCoords object containing a single
coordinate is exactly the same as the serialised form of the corresponding
LatLongCoord object.)</p>
</div>
<div class="section" id="searching">
<h1><a class="toc-backref" href="#id4">Searching</a></h1>
<div class="section" id="sorting-results-by-distance">
<h2><a class="toc-backref" href="#id5">Sorting results by distance</a></h2>
<p>If you simply want your results to be returned in order of distance, you can
use the LatLongDistanceKeyMaker class to calculate sort keys.  For example, to
return results in order of distance from the coordinate (51.00, 0.50), based on
the values stored in slot 0, and using the great-circle distance:</p>
<pre class="literal-block">
Xapian::Database db(&quot;my_database&quot;);
Xapian::Enquire enq(db);
enq.set_query(Xapian::Query(&quot;my_query&quot;));
GreatCircleMetric metric;
LatLongCoord centre(51.00, 0.50);
Xapian::LatLongDistanceKeyMaker keymaker(0, centre, metric);
enq.set_sort_by_key(keymaker, False);
</pre>
</div>
<div class="section" id="filtering-results-by-distance">
<h2><a class="toc-backref" href="#id6">Filtering results by distance</a></h2>
<p>To return only those results within a given distance, you can use the
LatLongDistancePostingSource.  For example, to return only those results within
5 miles of coordinate (51.00, 0.50), based on the values stored in slot 0, and
using the great-circle distance:</p>
<pre class="literal-block">
Xapian::Database db(&quot;my_database&quot;);
Xapian::Enquire enq(db);
Xapian::Query q(&quot;my_query&quot;);
GreatCircleMetric metric;
LatLongCoord centre(51.00, 0.50);
double max_range = Xapian::miles_to_metres(5);
Xapian::LatLongDistancePostingSource ps(0, centre, metric, max_range)
q = Xapian::Query(Xapian::Query::OP_FILTER, q, Xapian::Query(ps));
enq.set_query(q);
</pre>
</div>
<div class="section" id="ranking-results-on-a-combination-of-distance-and-relevance">
<h2><a class="toc-backref" href="#id7">Ranking results on a combination of distance and relevance</a></h2>
<p>To return results ranked by a combination of their relevance and their
distance, you can also use the LatLongDistancePostingSource.  Beware that
getting the right balance of weights is tricky: there is little solid
theoretical basis for this, so the best approach is often to try various
different parameters, evaluate the results, and settle on the best.  The
LatLongDistancePostingSource returns a weight of 1.0 for a document which is at
the specified location, and a lower, but always positive, weight for points
further away. It has two parameters, k1 and k2, which control how fast the
weight decays, which can be specified to the constructor (but aren't in this
example) - see the API documentation for details of these parameters.:</p>
<pre class="literal-block">
Xapian::Database db(&quot;my_database&quot;);
Xapian::Enquire enq(db);
Xapian::Query q(&quot;my_query&quot;);
GreatCircleMetric metric;
LatLongCoord centre(51.00, 0.50);
double max_range = Xapian::miles_to_metres(5);
Xapian::LatLongDistancePostingSource ps(0, centre, metric, max_range)
q = Xapian::Query(Xapian::Query::AND, q, Xapian::Query(ps));
enq.set_query(q);
</pre>
</div>
</div>
<div class="section" id="performance">
<h1><a class="toc-backref" href="#id8">Performance</a></h1>
<p>The location information associated with each document is stored in a document
value.  This allows it to be looked up quickly at search time, so that the
exact distance from the query location can be calculated.  However, this method
requires that the distance of each potential match is checked, which can be
expensive.</p>
<p>To gain a performance boost, it is possible to store additional terms in
documents to identify regions at various scales.  There are various ways to
generate such terms (for example, the O-QTM algorithm referenced below).
However, the encoding for coordinates that Xapian uses has some nice properties
which help here.  Specifically, the standard encoded form for a coordinate used
is a 6 byte representation, which identifies a point on the surface of the
earth to an accuracy of 1/16 of a second (ie, at worst slightly less than 2
metre accuracy).  However, this representation can be truncated to 2 bytes to
represent a bounding box 1 degree on a side, or to 3, 4 or 5 bytes to get
successively more accurate bounding boxes.</p>
<p>It would therefore be possible to gain considerable efficiency for range
restricted searches by storing terms holding each of these successively more
accurate representations, and to construct a query combining an appropriate set
of these terms to ensure that only documents which are potentially in a range
of interest are considered.</p>
<p>It is entirely possible that a more efficient implementation could be performed
using &quot;R trees&quot; or &quot;KD trees&quot; (or one of the many other tree structures used
for geospatial indexing - see <a class="reference external" href="https://en.wikipedia.org/wiki/Spatial_index">https://en.wikipedia.org/wiki/Spatial_index</a> for a
list of some of these).  However, using the QTM approach will require minimal
effort and make use of the existing, and well tested, Xapian database.
Additionally, by simply generating special terms to restrict the search, the
existing optimisations of the Xapian query parser are taken advantage of.</p>
</div>
<div class="section" id="references">
<h1><a class="toc-backref" href="#id9">References</a></h1>
<p>The following may be of interest.</p>
<p>The O-QTM algorithm is described in &quot;Dutton, G. (1996). Encoding and handling
geospatial data with hierarchical triangular meshes. In Kraak, M.J. and
Molenaar, M. (eds.)  Advances in GIS Research II. London: Taylor &amp; Francis,
505-518.&quot; , a copy of which is available from
<a class="reference external" href="http://www.spatial-effects.com/papers/conf/GDutton_SDH96.pdf">http://www.spatial-effects.com/papers/conf/GDutton_SDH96.pdf</a></p>
<p>Some of the geometry needed to calculate the correct set of QTM IDs to cover a
particular region is detailed in
<a class="reference external" href="ftp://ftp.research.microsoft.com/pub/tr/tr-2005-123.pdf">ftp://ftp.research.microsoft.com/pub/tr/tr-2005-123.pdf</a></p>
<p>Also, see:
<a class="reference external" href="http://www.sdss.jhu.edu/htm/doc/c++/htmInterface.html">http://www.sdss.jhu.edu/htm/doc/c++/htmInterface.html</a></p>
</div>
</div>
</body>
</html>