{"id":8882,"date":"2013-08-01T10:26:35","date_gmt":"2013-08-01T08:26:35","guid":{"rendered":"https:\/\/blog.trifork.com\/?p=8882"},"modified":"2013-08-01T10:26:35","modified_gmt":"2013-08-01T08:26:35","slug":"server-side-clustering-of-geo-points-on-a-map-using-elasticsearch","status":"publish","type":"post","link":"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/","title":{"rendered":"Server-side clustering of geo-points on a map using Elasticsearch"},"content":{"rendered":"

Plotting markers on a map is easy using the tooling that is readily available. However, what if you want to add a large number of markers to a map when building a search interface? The problem is that things start to clutter and it’s hard to view the results. The solution is to group results together into one marker. You can do that on the client using client-side scripting, but as the number of results grows, this might not be the best option from a performance perspective.<\/p>\n

This blog post describes how to do server-side clustering of those markers, combining them into one marker (preferably with a counter indicating the number of grouped results). It provides a solution to the \u201ctoo many markers\u201d problem with an Elasticsearch facet.<\/p>\n

<\/p>\n

The Problem<\/h3>\n

The image below renders quite well the problem we were facing in a project:<\/p>\n

\"serversideclustering_elasticsearch_1\"<\/p>\n

The mass of markers is so dense that it replicates the shape of the Netherlands! These items represent monuments and other things of general interest in the Netherlands; for an application we\u00a0 developed for a customer we need to manage about 200,000 of them and they are especially concentrated in the cities, as you can see in this case in Amsterdam: The\u00a0\u00a0\u201cdraw everything\u201d strategy doesn\u2019t help much here.<\/p>\n

\"serversideclustering_elasticsearch_2\"<\/p>\n

Looking for a solution<\/h3>\n

This article by Google<\/a> gives a good overview of the problem, but it presents only client side solutions. As the start of this post anticipates, client side processing is not good in our case: if the browser received all of the 200,000 points of interest the webpage would freeze every time the user drags or zooms.<\/p>\n

Therefore we looked at means for doing this server side.<\/p>\n

Since we are using Elasticsearch<\/a> as our storage, we searched for a solution which was either built-in or available in a plugin, and found https:\/\/github.com\/zenobase\/geocluster-facet<\/a>. It is an Elasticsearch plugin which uses a clustering algorithm to group nearby documents.<\/p>\n

We installed the plugin and tried some use cases, and although liking the base idea we concluded that we needed more control over the grouping: in our tests, the way groups were calculated by the plugin varied a lot depending on the particular bounding box used in the query. This would result in unstable group icons while a user pans around the map.<\/p>\n

The \u201cgrid\u201d idea mentioned in Google\u2019s article would allow us to fine control the level of grouping. It basically consists in dividing the earth\u2019s surface in cells of a rectangular grid, with the grid lines following meridians and parallels, and grouping the items according to the cell they fall into. Since we want the grouping level to vary with the zoom level, there is no single grid which accommodates all cases but instead grids of different granularity are needed. If the map is showing the whole world, the surface should be divided in a few \u2018mega\u2019 cells, spanning big portions of the continents; on the other extreme, if the map is set on a single neighbourhood the cells should be as small as buildings, in order to group only very close documents.<\/p>\n

So we put together 2 good ideas: a grid-based grouping algorithm, packed as an Elasticsearch plugin.<\/p>\n

Enter GeoHash<\/h3>\n

In the end, we didn\u2019t have to deal directly with calculations on grids because a nice idea called geohash handles it in a concise and elegant way.<\/p>\n

A geohash is a way to encode a pair of geographical coordinates as a string, where the encoded value has an interesting property: the more two locations are close to each other, the more chars their respective geohashes have in common. For example, the Dam in Amsterdam (geohash u173zq4xmc<\/code>) and the Nieuwemarkt, also in Amsterdam (geohash u173zw0m3wes<\/code>) share the first 5 chars, while two places as distant as the Colosseum (sr2yk3bse2q<\/code>) and the Liberty Statue (dr5r7p4rn<\/code>) have no chars in common (shared chars are intended as shared prefixes<\/i>).<\/p>\n

In other words, a geohash prefix (which, by the way, is a valid geohash in itself) identifies a region; the shorter the prefix, the bigger the region.<\/p>\n

You can look on http:\/\/www.bigdatamodeling.org\/2013\/01\/intuitive-geohash.html<\/a> for a nice visual exposition of the concept; the article shows cells corresponding to different geohash lengths.<\/p>\n

Grouping using this technique boils down to group together documents with identical geohashes to the n<\/em>th char. The smaller n<\/em>, the more \u201caggressive\u201d the grouping, because a short prefix specifies a wide region, which includes more items. On the other end, if you consider the whole geohash length for the matching (elasticsearch uses geohashes of 12 chars) then the only items which end up grouped together are the ones with identical coordinates.<\/p>\n

The Plugin<\/h3>\n

The plugin we made is a facet plugin: this means that the output of the grouping will be available as the result of a facet request, where a single facet instance is one group. The code relies on the geohash calculated by Elasticsearch and available through the GeoPoint#geohash()<\/code> method. We’ve made this available for your use.<\/p>\n

Interested?<\/h3>\n

If so then first;\u00a0Download plugin<\/a><\/strong><\/p>\n

Use<\/h3>\n

The project started as a fork of the original geocluster-facet mentioned before. The plugin infrastructure and domain classes are still there, but the base algorithm relies now on the geohashes. So, go and clone the project if you want to know how it works! In the following I\u2019ll go into details of the usage of the plugin.Once you you have installed the plugin: launch a mvn clean package<\/code> to build the jar, copy it to $ES_HOME\/plugins\/somefolder\/ and restart Elasticsearch.<\/code><\/code><\/p>\n

Let\u2019s assume that the documents in the index contain a field \u201clocation\u201d of type geopoint; then an example query to see the plugin in action might be:<\/p>\n

\ncurl -XPOST http:\/\/localhost:9200\/myindex\/venues -d \u2018{\n    "query" : { ... }\n    "facets" : {\n        "places" : {\n            "geohash" : {\n                "field" : "location",\n                "factor" : 0.9\n            }\n        }\n    }\n}\u2019\n<\/pre>\n
The factor parameter must have a value in the interval [0, 1], where 0 mean \u201cdon\u2019t do any grouping\u201d and 1 corresponds to the most aggressive grouping. The value of factor is translated in the number of geohash chars to consider in the grouping algorithm.<\/p>\n
The response would be something like:<\/p>\n
\n{\n    ...,\n\n  "facets" : {\n\t"places" : {\n  \t"_type" : "geohash",\n  \t"factor" : 0.9,\n  \t"clusters" : [ {\n    \t"total" : 8,\n    \t"center" : {\n      \t"lat" : 16.95292075,\n      \t"lon" : 122.036081375\n    \t},\n    \t"top_left" : {\n      \t"lat" : 33.356026,\n      \t"lon" : 121.00589\n    \t},\n    \t"bottom_right" : {\n      \t"lat" : 14.60962,\n      \t"lon" : 129.247421\n    \t}\n  \t}, {\n    \t"total" : 5,\n    \t"center" : {\n      \t"lat" : 37.12715661612766,\n      \t"lon" : -83.15270566\n    \t},\n    \t"top_left" : {\n      \t"lat" : 40.78255308063828,\n      \t"lon" : -85.50469199999998\n    \t},\n    \t"bottom_right" : {\n      \t"lat" : 36.177174,\n      \t"lon" : -73.96547029999999\n    \t}\n  \t} ]\n\t}\n  }\n}\n<\/pre>\n
The first element of the “clusters” array is a group made of 8 documents, with its bounding box and center coordinates (the center is calculated as the mean of the coordinates of the documents composing the group).<\/p>\n
A map done using the Plugin<\/h3>\n
Time again for some map screenshots! Here is the center of Amsterdam and its points of interest:<\/p>\n
\"serversideclustering_elasticsearch_3\"<\/p>\n
Most of the icons are now groups, collapsing together 2 or more documents (the number of documents is shown inside the icon). You can also see a couple of single documents at the bottom right.<\/p>\n
The work of the plugin becomes more visible when we zoom in two levels from the previous view:<\/p>\n
\"serversideclustering_elasticsearch_4\"<\/p>\n
The big groups we had before have bursted in smaller ones, better representing the distribution of the documents in the space. And if we get even closer we start seeing more single documents, each one in its real location:<\/p>\n
\"serversideclustering_elasticsearch_5\"<\/p>\n
That\u2019s it, I hope this will help someone else with a use case like ours. I have a couple of closing thoughts about the topic:<\/p>\n
    \n
  • The latest Elasticsearch (0.90.2 as of writing) allows you to do powerful things with geohashes, and I don\u2019t exclude that some future versions might even make this plugin superfluous! Which would make me happy, having one plugin less to install.<\/li>\n
  • But while this plugin is still needed, I\u2019m thinking about improvements on the fine tuning of the grouping at various zoom levels. A single char of difference in a geohash represents a big change in scale (32x in the area of the cell); going to a sub-character level would probably help finding the most appropriate grouping for a certain map view.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
    Plotting markers on a map is easy using the tooling that is readily available. However, what if you want to add a large number of markers to a map when building a search interface? The problem is that things start to clutter and it’s hard to view the results. The solution is to group results […]<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"content-type":"","footnotes":""},"categories":[15,65,10],"tags":[61],"class_list":["post-8882","post","type-post","status-publish","format-standard","hentry","category-enterprise-search","category-big_data_search","category-development","tag-elasticsearch"],"acf":[],"yoast_head":"\nServer-side clustering of geo-points on a map using Elasticsearch - Trifork Blog<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Server-side clustering of geo-points on a map using Elasticsearch - Trifork Blog\" \/>\n<meta property=\"og:description\" content=\"Plotting markers on a map is easy using the tooling that is readily available. However, what if you want to add a large number of markers to a map when building a search interface? The problem is that things start to clutter and it’s hard to view the results. The solution is to group results […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/\" \/>\n<meta property=\"og:site_name\" content=\"Trifork Blog\" \/>\n<meta property=\"article:published_time\" content=\"2013-08-01T08:26:35+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2013\/07\/serversideclustering_elasticsearch_1.png\" \/>\n<meta name=\"author\" content=\"Gianluca Ortelli\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Gianluca Ortelli\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"7 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/\",\"url\":\"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/\",\"name\":\"Server-side clustering of geo-points on a map using Elasticsearch - Trifork Blog\",\"isPartOf\":{\"@id\":\"https:\/\/trifork.nl\/blog\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2013\/07\/serversideclustering_elasticsearch_1.png\",\"datePublished\":\"2013-08-01T08:26:35+00:00\",\"author\":{\"@id\":\"https:\/\/trifork.nl\/blog\/#\/schema\/person\/0f5a4d92d4a7704cad27bfbdc2a71c7b\"},\"breadcrumb\":{\"@id\":\"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/#primaryimage\",\"url\":\"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2013\/07\/serversideclustering_elasticsearch_1.png\",\"contentUrl\":\"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2013\/07\/serversideclustering_elasticsearch_1.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/trifork.nl\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Server-side clustering of geo-points on a map using Elasticsearch\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/trifork.nl\/blog\/#website\",\"url\":\"https:\/\/trifork.nl\/blog\/\",\"name\":\"Trifork Blog\",\"description\":\"Keep updated on the technical solutions Trifork is working on!\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/trifork.nl\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/trifork.nl\/blog\/#\/schema\/person\/0f5a4d92d4a7704cad27bfbdc2a71c7b\",\"name\":\"Gianluca Ortelli\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/trifork.nl\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/eaf077709d7fdae692d5bdf94f50d86c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/eaf077709d7fdae692d5bdf94f50d86c?s=96&d=mm&r=g\",\"caption\":\"Gianluca Ortelli\"},\"url\":\"https:\/\/trifork.nl\/blog\/author\/gianluca\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Server-side clustering of geo-points on a map using Elasticsearch - Trifork Blog","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/","og_locale":"en_US","og_type":"article","og_title":"Server-side clustering of geo-points on a map using Elasticsearch - Trifork Blog","og_description":"Plotting markers on a map is easy using the tooling that is readily available. However, what if you want to add a large number of markers to a map when building a search interface? The problem is that things start to clutter and it’s hard to view the results. The solution is to group results […]","og_url":"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/","og_site_name":"Trifork Blog","article_published_time":"2013-08-01T08:26:35+00:00","og_image":[{"url":"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2013\/07\/serversideclustering_elasticsearch_1.png","type":"","width":"","height":""}],"author":"Gianluca Ortelli","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Gianluca Ortelli","Est. reading time":"7 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/","url":"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/","name":"Server-side clustering of geo-points on a map using Elasticsearch - Trifork Blog","isPartOf":{"@id":"https:\/\/trifork.nl\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/#primaryimage"},"image":{"@id":"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/#primaryimage"},"thumbnailUrl":"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2013\/07\/serversideclustering_elasticsearch_1.png","datePublished":"2013-08-01T08:26:35+00:00","author":{"@id":"https:\/\/trifork.nl\/blog\/#\/schema\/person\/0f5a4d92d4a7704cad27bfbdc2a71c7b"},"breadcrumb":{"@id":"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/#primaryimage","url":"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2013\/07\/serversideclustering_elasticsearch_1.png","contentUrl":"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2013\/07\/serversideclustering_elasticsearch_1.png"},{"@type":"BreadcrumbList","@id":"https:\/\/trifork.nl\/blog\/server-side-clustering-of-geo-points-on-a-map-using-elasticsearch\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/trifork.nl\/blog\/"},{"@type":"ListItem","position":2,"name":"Server-side clustering of geo-points on a map using Elasticsearch"}]},{"@type":"WebSite","@id":"https:\/\/trifork.nl\/blog\/#website","url":"https:\/\/trifork.nl\/blog\/","name":"Trifork Blog","description":"Keep updated on the technical solutions Trifork is working on!","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/trifork.nl\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/trifork.nl\/blog\/#\/schema\/person\/0f5a4d92d4a7704cad27bfbdc2a71c7b","name":"Gianluca Ortelli","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/trifork.nl\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/eaf077709d7fdae692d5bdf94f50d86c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/eaf077709d7fdae692d5bdf94f50d86c?s=96&d=mm&r=g","caption":"Gianluca Ortelli"},"url":"https:\/\/trifork.nl\/blog\/author\/gianluca\/"}]}},"_links":{"self":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/posts\/8882","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/comments?post=8882"}],"version-history":[{"count":0,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/posts\/8882\/revisions"}],"wp:attachment":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/media?parent=8882"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/categories?post=8882"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/tags?post=8882"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}