Geo_shape fields created in the Elastic Stack 7.0+ guarantee 1cm accuracy while providing faster searching and indexing. Learn more in this post.

With the addition of <a href="/blog/elasticsearch-5-0-0-released#data-structures">new data structures</a> in <a href="https://mail-archives.apache.org/mod_mbox/www-announce/201604.mbox/%3cCABM+u9LWQhLxSyg=vfQ4=_gcLOPLe6FJrejH0jjjFwFhBRivBQ@mail.gmail.com%3e">Lucene 6.0</a>, the <a href="/blog/elasticsearch-5-0-0-released">Elasticsearch 5.0 release</a> delivered massive indexing and search <a href="/blog/elasticsearch-5-0-0-released#indexing">performance improvements</a> for one-dimension <a href="/guide/en/elasticsearch/reference/7.5/number.html">numeric</a>, <a href="/guide/en/elasticsearch/reference/7.5/date.html">date</a>, and <a href="/guide/en/elasticsearch/reference/7.5/ip.html">IP</a> fields, and two-dimension (lat, lon) <a href="/guide/en/elasticsearch/reference/7.4/geo-point.html">geo_point</a> fields. Building on this work, the <a href="/blog/elasticsearch-6-0-0-released">Elasticsearch 6.0 release</a> further improved usability and simplicity of the <a href="/guide/en/elasticsearch/reference/7.5/geo-point.html#geo-point-params">geo_point API</a> by setting the default indexing structure to the new <a href="/blog/lucene-points-6.0">block k-d tree</a> (BKD) and removing all support for legacy <a href="/blog/supercharging-geopoint">prefix tree encoding</a>. Starting with <a href="/blog/elasticsearch-7-0-0-released">Elasticsearch 7.0</a>, we are excited to present the details of the <a href="https://issues.apache.org/jira/browse/LUCENE-8396">new default indexing technique</a> for <a href="/guide/en/elasticsearch/reference/7.5/geo-shape.html">geo_shape</a> field types that, once again, delivers an immense <a href="https://home.apache.org/~ivera/geoshapebench.html">performance improvement</a> over the legacy <a href="https://opensourceconnections.com/blog/2014/04/11/indexing-polygons-in-lucene-with-accuracy/">prefix tree indexing approach</a> for geospatial geometries. With the improvements described here, geo_shape fields created in 7.0 and later guarantee 1 cm accuracy while, on average, providing faster searching and several times faster indexing compared to 6.x geo shapes
 <h2>The need for a new approach</h2>For the past several years the <a href="/guide/en/elasticsearch/reference/0.90/mapping-geo-shape-type.html#_mapping_options_2">geo_shape mapping parameters</a> have been a source of <a href="https://github.com/elastic/elasticsearch/issues/25833">confusion and frustration</a> for many users. Finding the right configuration parameters to strike a balance between spatial accuracy and index / search performance often demanded an unreasonable amount of effort and understanding of the inner data structures from our users. <a href="https://github.com/elastic/elasticsearch/issues/25844">In some cases</a> users either gave up or were unable to find an acceptable configuration and were stuck with <a href="https://github.com/elastic/elasticsearch/issues/22087">poor performance</a>. For a company that strives for simplicity for our users and demands a high level of performance from our products, we wanted to do better. Building on past efforts, we set out to provide a similar level of performance improvement with geo_shape that we achieved with geo_point.
<img src="https://images.contentstack.io/v3/assets/bltefdd0b53724fa2ce/blt9c0997aec446b908/5df17fc261829a38dad2d891/bkd-backed-geo-simple-things-blog.jpg" data-sys-asset-uid="blt9c0997aec446b908" alt="Simple things should be simple" style="display: block; margin: auto;">
Until the release of the BKD tree, the <a href="https://en.wikipedia.org/wiki/Inverted_index">inverted index</a> was the only data structure available for providing search capabilities. This structure, originally intended for searching text documents, relied on converting unstructured text into a <a href="http://blog.mikemccandless.com/2012/04/lucenes-tokenstreams-are-actually.html">stream of tokens</a>. This can be thought of as splitting sentences into a stream of words. To use this structure for spatial indexing, Lucene needed a way to convert the spatial geometries into a stream of tokens representing the coverage area. This was achieved through a technique known as <a href="https://en.wikipedia.org/wiki/Rasterisation">rasterization</a>; a process that converts line graphics into a stream of cells. For images and graphics displays, each cell is the equivalent of a pixel which has a fixed size. Search applications, on the other hand, strive to store the most amount of data with the smallest index possible, so fixed size spatial cells are not required. In fact, storing all cells at a fixed size causes an unnecessarily large index. For geospatial geometries, the size of the cell translates to a square size on the earth’s surface; this is known as <a href="https://www.sciencedirect.com/topics/earth-and-planetary-sciences/spatial-resolution">spatial resolution</a> (represented as <code>tree_levels</code> or <code>precision</code> in the mappings). The following image (source: ESRI) illustrates the <a href="https://desktop.arcgis.com/en/arcmap/latest/manage-data/raster-and-images/cell-size-of-raster-data.htm">trade-offs</a> that need to be considered when selecting an appropriate spatial resolution.
<img src="https://images.contentstack.io/v3/assets/bltefdd0b53724fa2ce/blte945872467d36edf/5df1717a8c8da537d52c441b/bkd-backed-geo-rasterization-blog.png" data-sys-asset-uid="blte945872467d36edf" alt="Trade-offs when selecting an appropriate spatial resolution" style="display: block; margin: auto;">
To achieve organized structure with an efficient storage footprint the spatial index employed the use of <a href="https://en.wikipedia.org/wiki/Quadtree">quadtrees</a>; a hierarchical organization of cells where each cell is recursively partitioned into quadrants. This eliminates the need to store all cells by only recursing to the highest resolution for cells that fall on the boundary of the geometry. The following image illustrates a point radius circle decomposed into a hierarchical set of cells using Lucene’s quadtree implementation (note the highest resolution and sheer number of cells on the boundary of the circle). Each cell is then encoded into a <a href="https://en.wikipedia.org/wiki/Z-order_curve">morton code</a> (binary representation) so it can be inserted into the inverted index. In addition to the spatial resolution issues (including the search accuracy problem where all points and geometries inside the smallest cell need to be linearly scanned at query time) converting a single vector geometry into a stream of raster cells introduces an index size overhead proportional to the size of the shape; the larger the shape the larger the index.
<img src="https://images.contentstack.io/v3/assets/bltefdd0b53724fa2ce/blt9b4611d46c2e6170/5df174c87fa7913850f30e4d/bkd-backed-geo-quad-trees-blog.jpg" data-sys-asset-uid="blt9b4611d46c2e6170" alt="Point radius circle using Lucene's quadtree implementation" style="display: block; margin: auto;">
It’s clear that while this approach works, it carries a number of drawbacks that quickly become realized with even the simplest of shapes. The following image illustrates an eight vertex polygon covering a 1 degree by 1 degree square latitude, longitude area. Using the quadtree approach, with spatial resolution set to 3 meters, results in 1,105,889 terms in the inverted index; and that’s just for one shape! From this example It’s clear the cost of using a rasterized index necessitated a new, more efficient, approach to indexing and searching spatial geometries at massive scale.
<img src="https://images.contentstack.io/v3/assets/bltefdd0b53724fa2ce/blt5dc6ec9f303bd93f/5df18031aecae93859556c8f/bkd-backed-geo-8-vertex-polygon-blog.png" data-sys-asset-uid="blt5dc6ec9f303bd93f" alt="Eight-vertex image " style="display: block; margin: auto;">
<h2>Inspired by computer graphics...</h2>Dealing with high resolution geometries, level of detail, and limitations in graphics computing performance is <a href="https://dl.acm.org/citation.cfm?id=360329">not a unique or novel problem</a>. Remaining in vector space and avoiding the conversion of vector geometries to cell based rasters was the first realization to overhauling and improving the shape indexing in Lucene. By remaining in vector space we avoid many of the spatial resolution issues encountered when indexing in raster space. To efficiently store and display high resolution geometries, most computer graphics and game engines decompose these geometries into primitives, such as <a href="https://steemit.com/computer-graphics/@jrkirby/the-fundamentals-of-computer-graphics-i-triangles-and-rendering">triangles</a>. Triangles are largely efficient because, “<a href="https://web.archive.org/web/20110818125503/http://www.devmaster.net/articles/software-rendering/part3.php">every object can be split into triangles but a triangle cannot be split into anything else than triangles</a>”. The <a href="https://developer.arm.com/solutions/graphics/developer-guides/best-practices-for-mobile-game-art-assets-1/geometry-best-practices/single-page">following image</a>&nbsp;(source: Arm® Technologies) illustrates two different geometry resolutions displayed as a collection of triangles.
<img src="https://images.contentstack.io/v3/assets/bltefdd0b53724fa2ce/bltb6541b85f88bbda4/5df172611202185d397ad293/bkd-backed-geo-triangle-count-blog.jpg" data-sys-asset-uid="bltb6541b85f88bbda4" alt="Two different geometry resolutions displayed as a collection of triangles" "="" width="600" style="display: block; margin: auto;">
To achieve this, we needed an efficient triangular <a href="https://en.wikipedia.org/wiki/Tessellation">tessellation</a> algorithm that converts input vector geometry into a stream of triangles that remain in vector space. We turned to David Eberly’s <a href="https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf">2002 paper</a>, “Triangulation by Ear Clipping” and quickly found that our friends at <a href="https://www.mapbox.com/">Mapbox</a> had adapted the same algorithm to their WebGL rendering layer in an implementation they call <a href="https://github.com/mapbox/earcut">earcut</a>. This reputability was encouraging and we quickly adapted a similar approach and benchmarked its performance against the original quadtree implementation. The following image illustrates one of those benchmarks. Using the same simple eight vertex polygon as demonstrated above, covering a 1 degree by 1 degree square latitude, longitude area the triangular tessellation approach was applied. After a 7 ms computation performance (in a development environment, so your mileage may vary) the polygon was decomposed into a total of eight triangle terms versus 1,105,889 quad terms using the rasterization approach used in prefix tree indexing. This represents a 138,236 to 1 compression ratio! Keeping the geometry in vector space also means we no longer have to worry about the spatial resolution issues associated with the quad cells; so geometries nearly remain in the same resolution as provided by the user. More on this below.
 <img src="https://images.contentstack.io/v3/assets/bltefdd0b53724fa2ce/bltc9097d9763b89fda/5df180496ac09b386d565bbb/bkd-backed-geo-ear-clipping-blog.png" data-sys-asset-uid="bltc9097d9763b89fda" alt="bkd-backed-geo-ear-clipping-blog.png" style="display: block; margin: auto;">
<h2>Encoding and indexing…</h2>With triangular tessellation, the number of terms have been significantly reduced and the original accuracy of the geometry has been maintained, but geometries are now represented as a collection of triangles instead of their original vertex form. With this change the shape indexing and search problem is reduced to a process of organizing the triangles into the BKD data structure such that search is efficient. Achieving this required two additional improvements.
First, the BKD data structure needed a way to optimally organize the triangular geometries. This was achieved through a modification of the BKD implementation referred to as <a href="https://issues.apache.org/jira/browse/LUCENE-8496">selective indexing</a>. The objective with selective indexing is to allow N-dimensional fields to designate the first k dimensions (index dimensions) for driving the construction of the BKD tree with the remaining d dimensions (data dimensions) as stored ancillary data for use at the leaf nodes. For the collection of 2D triangles, the first four dimensions were chosen as index dimensions representing the bounding box of the triangle. By doing this, the general BKD tree is converted into an <a href="https://en.wikipedia.org/wiki/R-tree">R-tree</a> where the internal nodes of the tree are a collection of bounding boxes, and the leaves contain data required to reconstruct the original triangles.
The second improvement needed was a <a href="https://issues.apache.org/jira/browse/LUCENE-8521">compact dimensional encoding</a> of the individual tessellated triangles such that they could be stored efficiently at the leaves of the tree without requiring an unnecessarily large amount of space. This was accomplished using three data dimensions (seven total dimensions) that enable the encoding to reconstruct the three 2D vertices of the triangle from the first four bounding box dimensions. However, in order to support all spatial relations (e.g., CONTAINS queries when the original indexed geometries are no longer maintained) the following requirements are needed:
<ul>
	<li>Triangle vertices must be encoded in counter-clockwise orientation.</li>
	<li>Triangle vertex order can start at any point; e.g., triangle ABC satisfies the following relationship: ABC == CAB == BCA</li>
</ul>These two assumptions enable an efficient encoding where original triangles can be reconstructed in such a way that orientation is preserved while being able to mark which triangle edge belongs to the original geometry. The following image illustrates the eight possible encodings for tessellated triangles.
<img src="https://images.contentstack.io/v3/assets/bltefdd0b53724fa2ce/bltbf4ec28f5831f68d/5df1730be56e3c38566131c8/bkd-backed-geo-tesselated-triangles-blog.jpg" data-sys-asset-uid="bltbf4ec28f5831f68d" alt="Illustrating the eight possible encodings for tessellated triangles" style="display: block; margin: auto;">
In the chart above, the “code” dimension indicates which vertex(es) are shared with the original bounding box and how to reconstruct the remaining vertex(es) from the min/max bounding box index dimensions and y, x data dimensions. In the first row, for example, the code dimension ‘0’ indicates the triangle shares the (Ymin, Xmin), and (Ymax, Xmax) vertices with the bounding box index dimensions. The third triangle vertex can then be reconstructed using the Y and X data dimensions directly. With this encoding, the tessellated triangles are efficiently indexed using a total of seven dimensions such that the BKD data structure is organized as an R Tree that is optimal for spatial search while being able to reconstruct the original vertices of the triangle from a small amount of ancillary data.
Finally, to keep the index size as small as possible, each dimensional value is passed through a <a href="https://issues.apache.org/jira/browse/LUCENE-8581">quantization function</a> that converts from 64-bit double precision floating point to a 32-bit integer space. This process enables better compression of the stored triangles and bounding boxes resulting in an index that is more than half the size of storing the original values. It is important to note, however, that the quantization function is slightly lossy and introduces a spatial error of 1 cm. This means precision of the original geometry is no longer maintained but will be guaranteed within 1 cm accuracy.
 <h2>Performance benchmarks and more resources</h2>While we plan to cover other performance improvements, BKD optimizations, benchmarks, new features, and changes in future blog posts, Mike McCandless maintains a series of limited <a href="https://home.apache.org/~mikemccand/geobench.html">nightly Lucene benchmarks</a> that can be followed while more optimizations are made to the internal data structures. Keep in mind that all benchmark configurations vary and no one single benchmark is perfect so, as always, your mileage may vary. Of course the Lucene community <a href="mailto:java-user@lucene.apache.org">would love to hear any feedback you may have</a> and if you run into any issues with the Elastic stack feel free to reach out on the <a href="https://discuss.elastic.co/">Elastic Discuss forums</a>. Thank you and we look forward to further improving and enhancing your spatial search experience!

bkd-backed-geo-blog-banner.jpg

bkd-backed-geo-blog-thumb.jpg

BKD-backed geo_shapes in Elasticsearch: precision + efficiency + speed

elasticsearch-weekly-blog-banner.png

elasticsearch-weekly-blog-thumb.png

This Week in Elasticsearch and Apache Lucene - 2019-10-21

Want to know what life at Elastic is like? You've come to the right place. Hear from our Elasticians first hand as we highlight their stories and photos from around the world. In this Spotlight, Nick Knize shares his journey with Elastic, from the start to the recent release of the <a href="https://github.com/elastic/elasticsearch/pull/44980">new ShapeFieldMapper.</a>My name is Nick Knize, and I’m the Geospatial Technical Lead at Elastic. I work on <a href="https://www.elastic.co/blog/elasticsearch-7-4-0-released">Elasticsearch</a> together with the <a href="https://www.elastic.co/products/maps">Elastic Maps</a> team. Elastic Maps is a really exciting product for users of the Elastic Stack. With it, users can analyze their geospatial data, visualize with interactive layers, and search through multiple sources of data in real time — and so much more. Users can experience <a href="https://www.elastic.co/elastic-maps-service">Elastic Maps</a> in Kibana today and open up new ways to visually explore their location data. They can also try it out <a href="https://www.elastic.co/products/elasticsearch/service">on the Elasticsearch Service</a>.<img src="https://images.contentstack.io/v3/assets/bltefdd0b53724fa2ce/bltd7cf2a6b4e48e127/5d9bbdb95c13780eebeb44f9/Nick_Knize.jpg" data-sys-asset-uid="bltd7cf2a6b4e48e127" alt="Nick" style="display: block; margin: auto;">Over the last few years I’ve watched my team grow and with it the technical capabilities of what we can do with geo in Elasticsearch, Kibana, and machine learning. I want to share a bit about how I ended up at Elastic, why I think it’s a great place for engineers to work, and a few of the major accomplishments we’ve made as a team over the last few years.<h2>A geospatial roadmap</h2>My journey into geospatial development was a long one, and not exactly straightforward. I initially studied meteorology in college — I had and still have a fascination with weather patterns, astronomy, and terrestrial analysis. But after a short time studying meteorology, I realized I was doing better in my programming classes and enjoyed programming and mathematics way more than coloring and manually creating maps. I decided I wanted to go deeper and design and develop programming models capable of analyzing the earth and its behaviors.As I did more and more modeling and visualization, I converted into being a software engineer but again found other interests, specifically in computer graphics. After taking an internship in the medical school’s image guided surgery lab, I had the notion that I would become a character animator at a movie studio. Those dreams were quickly dashed — I learned I’m not much of an artist — and I ended up doing more image processing and analysis, computer vision, facial recognition, and biometrics than real character animation.That was when it hit me: images in combination with location attributes are extremely powerful. And once I started playing around with image analysis, I was hooked. After several years of study, and a lot of research, my professors suggested that I complete a dissertation for a PhD. So I did, knowing that it would open doors for me later in life.<h2>Coming to Elastic</h2>Following my university studies, I worked as a government contractor. After several years of contracting work, I had grown a bit restless in the government space and wanted to work on an open technology found at the core of many other companies’ products. I also wanted to get into open source, because being able to push code out there and let people see it, use it, and collaborate with it was something I found incredibly exciting.After doing some research I came across Elasticsearch and was excited by the possibilities I saw in the product. I interviewed with Elastic (which was just called Elasticsearch at the time), and after the interview I felt that the technical freedom to explore new things and eventually have them turn into a feature release was a great opportunity that I couldn’t pass up.I was brought in to completely overhaul the geospatial code inside of <a href="https://www.elastic.co/products/elasticsearch">Elasticsearch</a> and <a href="https://lucene.apache.org/">Lucene</a>. I'm a longtime Lucene committer, so I worked closely with the Lucene team to introduce a new spatial and numeric data structure that now indexes anything that's numeric in Elasticsearch. So, anytime you index scientific data, for example an integer, float, IP, date, timestamp, or latitude/longitude, it indexes in a new data structure that I and a few other people developed and improved from the Lucene side.<h2>Building success with the team</h2>I started with Elastic in 2014. We were still a small company then — around 120 or 130 employees. I remember a few months after I joined we had the first <a href="https://www.elastic.co/elasticon/">Elastic{ON}</a>. In those days we all fit into <a href="https://www.pier39.com/">Pier 39</a> on a single stage.I needed a good team to bring our geospatial vision to life. At first the engineers who worked on the project had a broad focus in their career — they weren’t exactly specialized in geo but they were extremely talented developers nonetheless. I began hiring additional developers that were passionate and fully dedicated to the geospatial tech space, which is where the project really took off.<img src="https://images.contentstack.io/v3/assets/bltefdd0b53724fa2ce/blt85a44a307401702f/5d9bbda173942313e3c43495/zoom_meeting.jpg" data-sys-asset-uid="blt85a44a307401702f" alt="Meet the team" style="display: block; margin: auto;">From the beginning, my ultimate goal with the geo capabilities in the Elastic Stack has been to do everything we can with arbitrary geospatial geometries and shapes. Doing that makes it possible for users to index terrestrial shapes in Elasticsearch, and run geospatial object searches and analysis for a wide range of traditional and non-traditional GIS use cases.With a team in place, and focusing on the above goal, we had a big win with Elasticsearch 6.0 with the release of the <a href="https://www.elastic.co/blog/lucene-points-6.0">BKD data structure</a> for all numerics, including latitude and longitude geo_point types. Then we expanded what we accomplished in 6.0 to geo shapes, for more performant indexing and searching of geospatial geometries for the <a href="https://www.elastic.co/blog/elastic-stack-6-6-0-released">Elastic Stack 6.6 release</a>.Then the focus shifted to achieve the same performance success for arbitrary geometries. If users want to index shapes inside Elasticsearch and perform all sorts of spatial analysis on geometric objects, they should be able to — and at lightning speed. The optimized geo_shape fields in Elasticsearch 6.6 were a big step forward toward that goal. We were able to create the <a href="https://github.com/elastic/elasticsearch/pull/44980">first pull request</a> for a new Elasticsearch shape field type for indexing and searching arbitrary Cartesian geometries. This was a really exciting development.<h2>Engineering culture at Elastic</h2>There’s a lot more to working at Elastic than the really exciting leaps and bounds we’ve made technologically (which is already enough of an incentive for most). What some engineers might not know when starting at Elastic is that you’re joining forces with a company that's ready to stand by you. You have a lot of freedom to explore and do things, which is a far cry from what you might experience working on proprietary software somewhere else. I think most engineers enjoy that freedom, because if those other engineers are anything like me, they get bored doing the same thing over and over again.Another big bonus of working with Elastic is that, at least with my team, you have the opportunity to be a Lucene committer. This is a pretty big feather in the cap for any software developer. It's a good resume builder, opens doors, and genuinely — I think — makes you feel pretty good about what you do.<h2>Staying power</h2>Elastic is a company with a lot of longevity. That’s because we evolve and grow. And as the company has evolved, so have the reasons that I’ve stayed on with Elastic over the years.At first, I stuck with Elastic because of the technology. I told myself that as long as Elastic stays true to the original idea of building a pluggable framework that allows people to apply the Elastic Stack in different ways, I will follow — and we have.But what has also kept me here is the culture. I've now got two&nbsp;kids at home, and being with a company that has <a href="https://www.elastic.co/about/our-source-code">the flexibility of Elastic</a>, supported by the trust from my managers and staff that we can get the work done, is a priceless incentive to keep working with my amazing team well into the future.Interested in joining a company with a Source Code to live by? We’re hiring. Check out <a href="https://www.elastic.co/about/teams">our teams</a> and <a href="https://www.elastic.co/about/careers/">find your fit!</a> Want to read more about life at Elastic? Read more <a href="https://www.elastic.co/blog/category/culture">on our blog</a>!

geospatial_map.jpg

Nick_Knize.jpg

Life@ Elastic | Geospatial mapping with Nick Knize

Numeric and Date Range indexing has finally come to Elasticsearch! Come find out how you can index and search your entire calendar using Elasticsearch 5.2.

<html><head></head><body>
	Like this post? Love numbers and Elasticsearch? I&#x2019;ll be at Elastic{ON} to meet with attendees face to face and answer your questions. Consider <a href="https://www.elastic.co/elasticon/conf/2017/sf">attending the event</a>. Hope to see you there.


	Imagine being able index your calendar to quickly find all events whose time range conflicts with a proposed event. Or creating a global television guide to find all shows, movies, sports, or broadcasts that are aired during certain time periods. Looking for something even more futuristic? Imagine creating a catalog of <a href="http://www.headwallphotonics.com/blog/press-releases/press-releases-blog/hyperspectral-imaging-successfully-screens-cancer-tissue">spectral signatures for all known cancer cells</a> in order to more rapidly identify, classify, and diagnose potential malignant activity.

<h2>From discrete to continuous</h2>

	Until recently, these use cases have been extremely difficult, or next to impossible, to solve at scale using Elasticsearch&apos;s discrete <a href="https://www.elastic.co/guide/en/elasticsearch/reference/5.1/number.html">numeric</a> and <a href="https://www.elastic.co/guide/en/elasticsearch/reference/5.1/date.html">date</a> fields. While running <a href="https://www.elastic.co/guide/en/elasticsearch/reference/5.1/query-dsl-range-query.html" target="_blank">range</a> queries over discrete points are the most typical and widely used capability, it quickly became clear that having the ability to index and search over continuous ranges would be a tremendously useful feature to support. Thanks to recent advancements in Apache <a href="https://issues.apache.org/jira/browse/LUCENE-7381">Lucene</a> this desire has become a reality in <a href="https://github.com/elastic/elasticsearch/pull/21002">Elasticsearch</a>.

<h2>Elasticsearch welcomes&#xA0;Numeric and Date Range field types</h2>
We are proud to announce the following new Range field types are included in the Elasticsearch 5.2 release:

<ul>
	<li><code>integer_range</code></li>
	<li><code>float_range</code></li>
	<li><code>long_range</code></li>
	<li><code>double_range</code></li>
	<li><code>date_range</code></li>
</ul>

	The mapping definition for these new range data types work the same way as their discrete Numeric and Date counterparts. The following provides an example mapping definition for a document type (called &quot;conference&quot;) that contains both an integer and date range:

<pre class="prettyprint">PUT events/
{
 &quot;mappings&quot; : {
 &quot;conference&quot; : {
 &quot;properties&quot; : {
 &quot;expected_attendees&quot; : {
 &quot;type&quot; : &quot;integer_range&quot;
 },
 &quot;time&quot; : {
 &quot;type&quot; : &quot;date_range&quot;,
 &quot;format&quot; : &quot;yyyy-MM-dd HH:mm:ss||yyyy-MM-dd||epoch_millis&quot; 
 }
 }
 }
 }
}
</pre>

	Indexing a document using the above mapping is as simple as defining the range fields the same way you would in a <a href="https://www.elastic.co/guide/en/elasticsearch/reference/5.1/query-dsl-range-query.html">Numeric</a> or <a href="https://www.elastic.co/guide/en/elasticsearch/reference/5.1/date.html">Date</a> Range Query. Like Date Range queries, indexing a Date Range field also uses the same Date Math format definition. The following example demonstrates indexing a document with an integer_range and date_range field type:

<pre class="prettyprint">PUT events/conference/1
{
 &quot;title&quot; : &quot;Pink Floyd / Wizard of Oz Halloween Trip&quot;,
 &quot;expected_attendees&quot; : {
 &quot;gte&quot; : 100000,
 &quot;lt&quot; : 200001
 },
 &quot;time&quot; : {
 &quot;gte&quot; : &quot;2015-10-31 12:00&quot;,
 &quot;lt&quot; : &quot;2015-11-01&quot;
 }
}
</pre>

	Querying Numeric and Date Range fields use the same&#xA0;<a href="https://www.elastic.co/guide/en/elasticsearch/reference/5.1/query-dsl-range-query.html">Range Query</a>&#xA0;domain specific language&#xA0;(DSL) definition as before with the addition of a new optional relation parameter. This parameter enables the user to define the type of Range query desired. This is defined as one of: <code>INTERSECTS</code> (default), <code>CONTAINS</code>, or <code>WITHIN</code> and can be combined with other Boolean queries to achieve different desired results (e.g., <code>DISJOINT</code>). The following example demonstrates a <code>WITHIN</code> query over the events index:

<pre class="prettyprint">GET events/_search
{
 &quot;query&quot; : {
 &quot;range&quot; : {
 &quot;time&quot; : {
 &quot;gte&quot; : &quot;2015-10-01&quot;,
 &quot;lte&quot; : &quot;2015-12-31&quot;,
 &quot;relation&quot; : &quot;within&quot;
 }
 }
 }
}
</pre>

	Like discrete numeric and date fields their new range counterparts are restricted to a single dimension only. In the future we plan to lift this restriction and expand them to handle 8 and 4 dimensions, respectively.

<h2>Lucene implementation</h2>
On October 18th, we published a blog post describing <a href="https://www.elastic.co/blog/apache-lucene-numeric-filters">The Evolution of Numeric Range Filters in Apache Lucene</a>. This historical account of Lucene&#x2019;s maturation as a numeric search engine details the technical advancements of numeric indexing and search culminating in the <a href="https://www.cs.duke.edu/~pankaj/publications/papers/bkd-sstd.pdf">Bkd-Tree Data Structure</a>. Instead of continuing to represent numeric data using a structure specifically designed and tuned for text, the Bkd implementation introduced the first flexible tree structure designed specifically for indexing discrete numeric points. These discrete points can now be searched in Elasticsearch using the <a href="https://www.elastic.co/guide/en/elasticsearch/reference/5.0/query-dsl-range-query.html">numeric range query</a>&#xA0;DSL&#xA0;definition. Built around the theory and concepts of a <a href="https://en.wikipedia.org/wiki/K-d_tree">k-dimensional tree</a> (k-d tree), the new <a href="https://www.elastic.co/blog/lucene-points-6.0">Points</a> codec format also paved the way for providing <a href="https://en.wikipedia.org/wiki/Multidimensional_panel_data">multi-dimensional</a> support for more advanced scientific or data analysis use cases and provide the foundation classes needed to bring the range field feature to Lucene and ultimately to Elasticsearch.

<h3>Indexing</h3>

	The solution was fairly trivial: for each dimension, represent the dimensional numeric range as a 2 dimensional point where the encoding is stored as an array of minimum values, d, (for each dimension) followed by an array of maximum values, D. This means for the Bkd restriction of 8 dimensions the numeric range fields provided by Lucene only support indexing up to 4 dimensional ranges. The image below provides a simple illustration of Lucene&#x2019;s dimensional range encoding.
<center><img src="https://api.contentstack.io/v2/uploads/586db46105ac83231cd5cddb/download?uid=blta3ab8babd36d9ccb" data-sys-asset-uid="blta3ab8babd36d9ccb" alt="Lucene&apos;s Dimensional Range Encoding"></center>

	Essentially, to Lucene a 1-dimension range simply looks like a 2-dimension point. This encoding is then passed to the Bkd indexer which proceeds to build a hierarchical tree of d*2-dimensional points; where d is the dimension of the range, or 4 in the above illustration.

<h3>Searching</h3>

	Implementing search for dimensional ranges boiled down to one critical step - defining and computing the spatial relation between the user provided search range (the target) and the indexed ranges (or minimum bounding ranges at each level of the tree). This was accomplished by implementing a dimensional range comparator that evaluates the range relation at each dimension. The spatial relations implemented in the comparator, and thus by Lucene numeric range queries, include: INTERSECTS, CONTAINS, and WITHIN. DISJOINT queries are then accomplished using an INTERSECTS query contained in a boolean query with a MUST_NOT clause. For multi-value fields a document is only considered DISJOINT if all values are disjoint. CROSSES relations are currently in-work and planned as a future enhancement. The following image illustrates the computed relations between two simple 1 dimensional ranges.
<center><img src="https://api.contentstack.io/v2/uploads/586db5b864fc892e6362907b/download?uid=blt221a660e65c1b27b" data-sys-asset-uid="blt221a660e65c1b27b" alt="Range Relations"></center>

	This example follows the convention that an open dot represents a range that does not include that specified value. The pink range represents the target (query) and the turquoise represents an indexed range.

<h2>Give it a try...</h2>

	We are extremely excited to see the many unique and creative ways that Numeric and Date range indexing and searching is applied to solve your particular use case. As always we encourage feedback, suggestions, and contributions on our Elasticsearch <a href="https://github.com/elastic/elasticsearch">github page</a> and we hope these new field types come in handy for you!


	And with that, the time is gone, the song is over&#x2026; Enjoy!
</body></html>

dark_side_of_the_numeric_ranges.png

brick_in_the_wall_ranges.jpg

Numeric and Date Ranges in Elasticsearch: Just Another Brick in the Wall

Interested in making your Elasticsearch application location aware? Read how we have supercharged GeoPoint fields in 2.2.

<html><head></head><body>&#x201C;I want to location enable my application but where do I start? Elasticsearch has had geo support for some time but how does it work? What are all of those <a href="https://www.elastic.co/guide/en/elasticsearch/reference/2.3/geo-point.html#geo-point-params">parameters</a> for? What kind of performance can I expect?&#x201D; The explosive growth of geospatial and spatiotemporal data for so many diverse <a href="http://www.datanami.com/2015/05/21/5-ways-big-geospatial-data-is-driving-analytics-in-the-real-world/">use-cases</a> emphasizes the need for efficient geospatial data structures and analysis tools. With many Geospatial specialty applications and libraries already available, few offer the scalability and flexibility of combined full text search and aggregations with location based information. Enter Elasticsearch. We hope this post answers some of those nagging questions regarding how geospatial field types work and how you can begin location enabling your Elasticsearch-driven applications. 

<h1>So what&apos;s new?
</h1>
Elasticsearch has supported <a href="https://www.elastic.co/guide/en/elasticsearch/guide/current/geoloc.html">geospatial fields</a> for some time; and a short while ago we provided a demo and overview of the <a href="https://www.elastic.co/webinars/elasticsearch-2-0-overview">new features and performance improvements</a> available in <a href="https://www.elastic.co/blog/elasticsearch-2-0-0-released">2.0</a>. While the existing <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/mapping-types.html#_geo_dataypes">geospatial field types</a> benefit from some of the low level improvements in 2.0 (specifically doc_values), the 2.2 release supercharges geo_point fields by improving the underlying data structure and query approach.

<h2>Indexed by default</h2>
Prior to 2.2, geo_point fields used no default indexing structure (aside from a not_analyzed &#x201C;lat,lon&#x201D; <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/string.html">string field</a>). This is because, until Lucene 5.3, a core Geo data structure based on the internal <a href="https://www.elastic.co/guide/en/elasticsearch/guide/current/inverted-index.html">inverted index</a> (that did not require a third-party library associated with a <a href="http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html">restrictive software license</a>) did not exist. In order to circumvent this limitation, so the <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/geo-queries.html">geo Query DSL</a> could be used, the <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/mapping-types.html#_geo_dataypes">geo_point field mapping</a> required specifying at least one of: <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/lat-lon.html">lat_lon</a> : true, <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/geohash.html">geohash</a> : true. At the implementation level the lat_lon option stored latitude and longitude data as two separate <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/number.html">numeric</a> fields, while the geohash option encoded all geo_point fields&#xA0;as an <a href="http://www.movable-type.co.uk/scripts/geohash.html">alphanumeric string based geohash</a>. Since both structures are based on the <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/number.html">number</a>, and <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/string.html">string</a> core types, respectively, supporting 2D geo data indexing required no additional indexing code. 
With the release of Lucene 5.3, a new specialized <a href="https://issues.apache.org/jira/browse/LUCENE-6450">GeoPointField</a> type is now available. This field type is built on the internal inverted index structure and all of the amazing work accomplished by the <a href="https://issues.apache.org/jira/browse/LUCENE/">Lucene Community</a> to make this structure as <a href="https://issues.apache.org/jira/browse/LUCENE-3030">efficient and performant</a> as possible. While an inverted index is not a <a href="http://www.cs.umd.edu/~hjs/pubs/kim.pdf">typical structure</a> used for geospatial data, it can be remarkably fast when applied correctly; and since the structure reuses all of the same <a href="https://www.elastic.co/blog/what-is-an-apache-lucene-codec">codec</a> logic implemented by Lucene, all of the dangerous corruption issues related to introducing new file types for new data structures are less of a concern. In order to work with the inverted index, the GeoPointField type uses a <a href="https://en.wikipedia.org/wiki/Quadtree">quad-tree</a> <a href="https://en.wikipedia.org/wiki/Raster_graphics">raster graphics</a> based approach by encoding latitude and longitude values as a single 64 bit integer and using variable length <a href="https://en.wikipedia.org/wiki/Prefix_code">prefix codes</a> for the terms in the term dictionary. The following graphic illustrates this technique for geo_point data.
<img src="https://api.contentstack.io/v2/assets/575e4d139e7a83165490d758/download?uid=bltbdb2021b350dbd50?uid=bltbdb2021b350dbd50" data-sys-asset-uid="blted966f3c63515921" style="max-width:100%;">&#xA0;

Graphic above is based on a graphic from <a href="https://karussell.wordpress.com/2012/05/23/spatial-keys-memory-efficient-geohashes/" target="_blank">Spatial Keys - Memory Efficient Geohashes by Karussell</a>.

Further encoding <a href="https://issues.apache.org/jira/browse/LUCENE-6712">improvements</a> were then applied to minimize the size of the terms dictionary, thus minimizing the overall size of the index. With the performance improvements to <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/doc-values.html">doc values</a> there is no need to store every prefix term up to the full resolution. Each point can be approximated using the prefix as a precision step of the top 32 most significant bits. Points along the search boundary can then be further scrutinized using full precision obtained from doc_values. This two-phase approach strikes a balance between index size and processing time. 

<h2>Rasterized queries</h2>
The new GeoPointField approach brings improved efficiency for all <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/geo-queries.html">geo query capabilities</a> available in Elasticsearch. Prior to 2.2, geo_point field queries were accomplished using a two-phase approach (<a href="https://www.elastic.co/blog/better-query-execution-coming-elasticsearch-2-0">two-phase iterator</a> in the 2.0 release). The first phase used either a prefix stemmer for <a href="https://www.elastic.co/guide/en/elasticsearch/reference/2.3/geohash.html">geohash</a> indexed points, or lat/lon <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-range-query.html">numeric range queries</a> for <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/lat-lon.html">lat_lon</a> indexed points to query based on the bounding box of the search area. The full precision results were then checked against the search criteria (e.g., <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-geo-polygon-query.html">polygon</a>, <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-geo-distance-query.html">distance</a>, <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-geo-distance-range-query.html">distance range</a>). While the improvements to the two-phase iterator improved query efficiency (especially for <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-geo-bounding-box-query.html">bounding boxes</a>), complex distance and polygon queries still required a check of every point within the bounding box.

The 2.2 indexing improvements minimize these checks by applying the benefits provided by the inverted index. As illustrated by the following distance query graphic (taken from a live demo in this <a href="https://youtu.be/l2zB9TDUAL4">YouTube video</a>), each query is &#x201C;rasterized&#x201D; into a set of &#x201C;within&#x201D; and &#x201C;boundary&#x201D; terms. 
<center><img src="https://api.contentstack.io/v2/assets/575e4d1458208ba076e29740/download?uid=bltc914e484538c7a05?uid=bltc914e484538c7a05" data-sys-asset-uid="blt29ff4cb8ede3dd41" style="max-width:100%;"></center>
 

To minimize the number of terms visited, the rasterization step attempts to maximize the coverage area of each term (cell). Terms that intersect the query shape use doc values to further scrutinize candidate points, while terms that are fully contained by the query area simply return all documents from the postings list. This raster decomposition technique reduces the number of brute force checks required by throwing out all terms that are represented by the bounding box but not the shape. 

<h2>Streamlined mapping parameters</h2>
Prior to 2.2, the geo_point field included 8 optional <a href="https://www.elastic.co/guide/en/elasticsearch/reference/2.1/geo-point.html#geo-point-params">parameters</a> whose default values were partially based on best practices. For example, whether to index <a href="https://www.elastic.co/guide/en/elasticsearch/reference/2.1/lat-lon.html">lat_lon</a> or <a href="https://www.elastic.co/guide/en/elasticsearch/reference/2.1/geohash.html">geohash</a> (or both) was often a question that could not be answered until much later in the maturity of the application use-case. By that time geo queries may have already become the culprit for poor quality of service. Compliance with geospatial data standards, created by the <a href="http://www.opengeospatial.org/standards/sfa">Open Geospatial Consortium</a> and <a href="http://www.iso.org/iso/catalogue_detail.htm?csnumber=26012">International Standards Organization</a>, have been a work in progress requiring leniency options such as <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/coerce.html">coerce</a> and <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/ignore-malformed.html">ignore_malformed</a>. Other &#x201C;expert&#x201D; parameters such as <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/precision-step.html">precision_step</a> and <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/doc-values.html">doc_values</a> are becoming more &#x201C;look don&#x2019;t touch&#x201D; than valuable performance enhancing tools.

Since the new GeoPointField structure is designed to obtain the best geospatial index and search performance possible within the construct of the inverted index, the number of parameters is being reduced in the coming releases. The image below provides the parameters for the 2.2 release.

<img src="https://api.contentstack.io/v2/assets/575e4d133dc542cb38c0997d/download?uid=blt6d19ca55e7e499e7?uid=blt6d19ca55e7e499e7" data-sys-asset-uid="blt9b92caa65f4ea7af" style="line-height: 1.6em;">

The coerce and doc_values options are completely removed as they are already handled by the new GeoPointField type. The ignore_malformed option will remain to provide users with the flexibility of throwing an exception if Elasticsearch receives non-compliant data (e.g., points outside the standard coordinate system). For backward compatibility the remaining parameters will remain. Users can still store geo_points in lat_lon and/or geohash sub-fields (setting the numeric precision_step, geohash_precision, and geohash_prefix parameters will still affect the size of the terms dictionary) but the <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/geo-queries.html">geo Query DSL</a> will no longer search using these sub-fields. They are purely for retrieving the geo_point data using the .lat, .lon, or .geohash path.

<h2 dir="ltr">Performance results</h2>
The performance results below are a 1.5 week average benchmark using the following parameters: index 60.8M documents (attributed to <a href="http://wiki.openstreetmap.org/wiki/Planet.osm#Downloading">Planet OSM</a>) using 8 client threads and 5000 docs per _bulk request against a single node running on a <a href="https://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i7-4760HQ+%40+2.10GHz&amp;id=2378">Intel Core i7-4760HQ</a> (4 real cores, 8 with hyperthreading), 16 GB RAM and 500 GB Samsung 840 EVO mSATA SSD.
<center><img src="https://api.contentstack.io/v2/assets/575e4d139985d589763780c5/download?uid=blta15ececb82787fa0?uid=blta15ececb82787fa0" data-sys-asset-uid="blt73d38c7a7b6711e0" style="max-width:100%;"></center>
 While the benchmarks demonstrate a significant supercharge in performance using the new indexing and query approach, we feel we can do far better using a data structure designed specifically for multi-dimensional geospatial data. For this reason we are working hard to bring a new <a href="https://issues.apache.org/jira/browse/LUCENE-6477">dynamic tree structure</a> specifically designed for spatial data to a future version of Lucene and Elasticsearch. Stay tuned... 
</body></html>

Articles by Nick Knize

BKD-backed geo_shapes in Elasticsearch: precision + efficiency + speed

This Week in Elasticsearch and Apache Lucene - 2019-10-21

Life@ Elastic | Geospatial mapping with Nick Knize

Numeric and Date Ranges in Elasticsearch: Just Another Brick in the Wall

Supercharging geo_point fields in Elasticsearch 2.2

产品

公司

资源