Wondershare EdrawMind
MindMap Gallery Server side geo clustering for Drupal 7
- 108
- 1
Server side geo clustering for Drupal 7
This mind map is about Server-side geo clustering for Drupal 7.
Edited at 2020-09-27 13:30:24
- Wholesaling Blueprint - Steps to Wholesaling Real Estate Simple Systems
This mind map is about Wholesaling Blueprint - Steps to Wholesaling Real Estate + Simple Systems. Start to use a mind map to express and organize your ideas and knowledge right now.
- Western Front
This mind map is about Western Front. Start to use a mind map to express and organize your ideas and knowledge right now.
- THE SAMPLING PROCESS
This mind map is about THE SAMPLING PROCESS. Start to use a mind map to express and organize your ideas and knowledge right now.
Server side geo clustering for Drupal 7
- Wholesaling Blueprint - Steps to Wholesaling Real Estate Simple Systems
This mind map is about Wholesaling Blueprint - Steps to Wholesaling Real Estate + Simple Systems. Start to use a mind map to express and organize your ideas and knowledge right now.
- Western Front
This mind map is about Western Front. Start to use a mind map to express and organize your ideas and knowledge right now.
- THE SAMPLING PROCESS
This mind map is about THE SAMPLING PROCESS. Start to use a mind map to express and organize your ideas and knowledge right now.
- Recommended to you
- Outline
Server-side geo clustering for Drupal 7
Introduction
Motivation
Usability
summarize data at high zoom levels by clustering
allow exploration of individual points at lower zoom levels
Speed
Browser javascript/memory limitations
Even more for mobile
"sebgruhier: performance is the key word. To be efficient (according to me) enough it has to be done around 100ms"
http://blog.davebouwman.com/2012/03/24/server-side-clustering-why-you-need-it/
http://www.svennerberg.com/2009/01/handling-large-amounts-of-markers-in-google-maps/
Problem statement
Aim of the work
Use cases
Examples
http://www.crunchpanorama.com/
http://gmaps-utility-library.googlecode.com/svn/trunk/markerclusterer/1.0/examples/speed_test_example.html
http://www.panoramio.com/map/
http://www.usda.gov/recovery/map/
Methodological approach
Structure of the work
Foundations
Clustering foundations
What is clustering
why cluster data
what is a cluster
Task
Pattern proximity, similarity
grouping
History
Cluster types
Well-separated
Prototype-based
Graph-based
Density-based
Aspects
Agglomerative vs. divisive
Monothetic vs. Polythetic
Hard vs. Fuzzy
Incremental vs. Non-incremental
Distance
Euclidean
Manhattan
Chebychev
Representation of Clusters
Large data sets
Algorithms
Hierarchical
Single Link
Complete Link
Partitional
Square Error (k-means)
Graph theoretic
...
Spatial Data
Quadtrees
Order, Morton, Peano-Hilbert
Geohash
Web Mapping
About
http://en.wikipedia.org/wiki/Web_mapping
Geospatial web technologies
Collaborative mapping
http://en.wikipedia.org/wiki/Collaborative_mapping
OpenStreetMap
Google Map Maker
Licensing
http://mashable.com/2012/01/19/google-maps-world-bank/
Wikimapia
http://wikimapia.org/
http://en.wikipedia.org/wiki/Geosocial_networking
Classification
static vs dynamic
http://kartoweb.itc.nl/webcartography/webmaps/classification.htm
The layered mapping stack
Functional mapping metrics
Technological mapping metrics
Location based services
spatial db
raster vs vector mode
map layers - features and themes
Projections
http://www.progonos.com/furuti/MapProj/Dither/CartHow/cartHow.html
Basemap Tiles
Ready to go
MapQuest
MapBox
OpenStreetMap
CloudMade
Google, ...
Customize Services
Tile Tools
TileMill
mapquest background tiles
einfach beim embed generieren 'World baselayer' anhaken
http://map.peoplesdistrict.com/fullmap.html
Maperitive
http://maperitive.net/
Overlays
SVG vs Canvas
https://groups.google.com/d/msg/d3-js/4CQ7tmpDi-E/0auSzBMu10gJ
Dynamic Overlays vs. static tiles
http://developmentseed.org/blog/2011/sep/28/gains-dynamic-maps-bridging-couchdb-sqlite/
daten regelmaessig von drupal in sqlite pushen
UTFGrid
http://mapbox.com/mbtiles-spec/utfgrid/
Interaction
None
Per-point
Hybrid
Database
MySQL Spatial
http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html
PostGIS PostreSQL
http://postgis.org/
SOLR
MetaCarta - GeoSearch Toolkit for Solr (prorietary)
http://www.metacarta.com/products-overview.htm
http://lucidworks.lucidimagination.com/display/solr/Spatial+Search
http://cartodb.com/
Logic
GEOS
https://github.com/phayes/geoPHP/wiki/GEOS
State-of-the-art
Web Mapping Stack
Mapping JS
Compare them
http://www.spatialanalysis.ca/2012/alternatives-to-google-maps/
http://geotux.tuxfamily.org/index.php/en/geo-blogs/item/291-comparacion-clientes-web-v6
http://www.smartmapbrowsing.org/html/index_en.html
new modest + leaflet
http://mapbox.com/blog/modest-maps-and-leaflet-new-choices-web-apis/
OpenLayers
The Wary Guide to OpenLayers
http://macwright.org/2012/01/12/openlayers.html
OpenLayers with Canvas
http://trac.osgeo.org/openlayers/wiki/Future/OpenLayersWithCanvas
openlayers 3 plans
http://openlayers.org/blog/2012/11/14/why-are-we-building-openlayers-3/
goals for ol3
http://www.youtube.com/watch?v=cgHudJim07o
ol plus
support many protocols & formats
support multiple projections
ol minus
shows its age (-> make it look more like leaflet, modern web application)
small - fast loading and quick running
still powerful (keep all features)
ensure compatibility (automated tests)
friendly - clean API + pretty UI
Leaflet
Modest Maps
polymaps
http://polymaps.org/
SVG-based large-scale data overlays on interactive maps
d3 / Protovis
http://mbostock.github.com/d3/
http://mbostock.github.com/d3/tutorial/protovis.html
D3 + maps
https://groups.google.com/forum/?fromgroups#!topic/d3-js/4CQ7tmpDi-E
basic d3maps integration
https://github.com/bloomtime/d3map
Other
Tile5
http://www.tile5.org/
Canvas
Openlayers heatmap canvas
http://www.websitedev.de/temp/openlayers-heatmap-layer.html
SVG vs Canvas in Openlayers
http://unterbahn.com/2010/07/comparison-of-svg-and-canvas-in-openlayers/
Drupal & Mapping
General
Drupal Geo Stack
http://groups.drupal.org/node/138884
http://groups.drupal.org/node/89769
Mapping Book
Mapping
http://drupal.org/project/mapping
http://groups.drupal.org/node/91114
Podcast
http://drupaleasy.com/podcast/2012/01/drupaleasy-podcast-73-lots-options
05:35; Drupal was one of the first CMS to integrate with Maps
13:30; TileMill
19:00; Client-side performance issues & clustering
24:35; Geocode & center map on users location by using HTML5 Geolocation
29:53; OpenLayers complexities, CTools, Display using Views, Panels or API
34:05; OpenLayers related modules: Geofield, Geocoder, ...
35:20; Geofield in Drupal 7 instead of Location module before
37:40; Recommended setup - Quickstart for storing locations and displaying them
OpenLayers + Geofield + Addressfield
GMap + Location
42:10; Leaflet (Cloudmade)
44:55; Book wrapup
46:25; Book introduction chapters + Motivation on mapping
49:25; Popular mapping blogs, cartography, best map of the year
1:06; Location CCK migrate sandbox
transforms D6 location_cck fields into D7 geofields
1:07; Geocoder, get geospatial data from address field into geofield
1:09:20; Baraka samsara films - map site use case
http://barakasamsara.com/
http://stanford.edu/group/ruralwest/cgi-bin/drupal/visualizations/us_newspapers
http://brandonmorrison.com/sites/default/files/presentations-deckjs/drupal-geospatial/index.html
Storage
Geofield
Presentation
http://drupal.org/node/1570972
PostGIS
http://drupal.org/project/postgis
Sync PostGIS
http://drupal.org/project/sync_postgis
Query + Display
OpenLayers
3.x
http://drupal.org/node/1353122
Leaflet
Widgets
http://drupal.org/sandbox/Chi/1796796
https://drupal.org/sandbox/GoalGorilla/1792420
http://drupal.org/sandbox/thegreat/1802616
Gmap
Views GeoJSON
http://drupal.org/project/views_geojson
OL intergration
http://drupal.org/node/1370448
Documentaion, use cases
http://drupal.org/node/1471026
Bounding box filter
http://drupal.org/node/1333324
Leaflet GeoJSON
Drupal SOLR
Drupal Apachesolr Geo sandbox
http://drupal.org/sandbox/pwolanin/1497066
Search API Location
http://drupal.org/project/search_api_location
Support official Solr 3 spatial search APIs
http://drupal.org/node/1328490
Sandbox
http://drupal.org/sandbox/madmatter23/1799850
Search API
Support location based search
http://drupal.org/node/1744250
Geofield
Apache Solr 3.5 update
http://drupal.org/node/1800570
Blog
http://ericlondon.com/posts/250-geospatial-apache-solr-searching-in-drupal-7-using-the-search-api-module-ubuntu-version-part-2
OpenLayers Solr
http://drupal.org/project/openlayers_solr
solarium...
Other
Polymaps (depends on mapping)
http://drupal.org/project/polymaps
Mapstraction (only D6)
http://drupal.org/project/mapstraction
Modestmaps (no code)
http://drupal.org/project/modestmaps
Scenarios
Geofield + Sync_Postgis + Tilestache + Openlayers
http://affinitybridge.com/blog/gis-tools-pnwds-session-video
Article Server-side mapping
http://affinitybridge.com/blog/server-side-mapping
GeoServer + PostGIS
http://www.geops.de/blog/64-spatial-data-and-drupal-7
tilestash + drupal + leaflet
https://github.com/affinitybridge/drupal-tilestache
https://img.skitch.com/20120426-jfu9fj5c17y5rfa9392y48xmb7.jpg
More
http://denver2012.drupal.org/program/sessions/nodejs-javascript-and-future
Drupal Mapping presentation by levelos (overview + openlayers & leaflet focus)
http://www.slideshare.net/loubabe/drupal-mapping-9713919
Drupal Mapping presentation by zzolo 2012
https://github.com/zzolo/spatially-drupal
vector tiles
[2:01pm] friedjoff: dasjo: maybe vector tiles might be worth looking into
[2:01pm] tnightingale: some data doens't make sense to be pushed into drupal
[2:01pm] tnightingale: vector tiles++
[2:02pm] tnightingale: though last i looked, polymaps was the only lib that supported them
Mapping Office hours log
Notes + log
https://docs.google.com/document/d/19F8XCwyxQc4JwouNxDDspiDCjPAWFsVb--xxOyedpmw/edit?pli=1
server-side-clustering
[1:52pm] zzolo: there is still a pretty big hole when trying to map (and handle) lots of geospatial features in Drupal
[1:53pm] phayes: zzolo - I think the answer there is a combination of ViewsGeoJSON / server-side clustering
[1:58pm] dasjo: final question before i have to leave: do we need a server-side clustering like nod_ and me discussed? http://drupal.org/node/1547610
[1:59pm] nod_: dasjo: phayes seems to agree, see backscroll
[1:59pm] Brandonian: dasjo: Definitlely think it'd be a cool feature, not sure what other work is being done with that in php/drupal land though
[2:00pm] zzolo: dasjo: my initial thought is no, if we can focus on toolking up thinks like postgis and tilestache. but since that is not really going to happen overnight, a good stop gap solon could be server side clustering
[2:00pm] phayes: dasjo: Yes we need it! That's going to be critical as we scale to support larger data sets
[2:00pm] dasjo: yep Brandonian zzolo. basically some parts of the database implementation and client-side handling should be pluggable
[2:01pm] dasjo: but maybe we can come with some basic out-of-the-box implementations and leave it open to a database to optimize the clustering
tilestash + drupal + leaflet
log
[1:59pm] tnightingale: yeah - tilestache is (using mapnik) is able to generate tiles on demand from a postgis backend
[1:59pm] mackh: of data from the oil and gas commksion - like pipeline right-of-ways, access roads, wellsites, watercrossings
[2:00pm] tnightingale: zzolo: so we can sync drupal data into postgis and render that data into tiles using mapnik+tilestache
[2:00pm] zzolo: tnightingale: and mackh just to confirm, the postgi data is drupal data? (from sync_postgis, i assume)
[2:00pm] zzolo: sweet
[2:00pm] mackh: yes and no?
[2:00pm] tnightingale: yep
[2:01pm] mackh: stored in drupal, synced to postgis
[2:01pm] tnightingale: but doesn't have to be
[2:01pm] zzolo: awesome. thats what i was hoping. this is the stack i have been envisioning, but i don't get paid to do any of this stuff so i don't have time.
[2:02pm] Brandonian: for the more python/mapnik literate in the room: How feasible is it to do mapnik renders based directly off drupal field data if the database is Postgres/postgis and stored properly?
[2:02pm] tnightingale: Brandonian: that's essentially what we're doing with sync_postgis & tilestache
[2:03pm] zzolo: Brandonian: what i image is getting your design in tile mill, export out the mapnik xml file, then it should be pretty easy
[2:03pm] tnightingale: using a mapnik xml file produced in tilemill as our style guide
[2:06pm] tnightingale: zzolo: we also have a rough cut at a tilestache config management module on g.h
[2:06pm] phayes: ooo! link tnightingale?
[2:07pm] phayes: Oh tnightingale, what's the status of D7 Spatial-tools?
[2:07pm] zzolo: tnightingale: you have a link. i am actually gonna try to get this stack running locally this week as part of my presentation at the TC Drupal camp
[2:07pm] mackh: https://github.com/affinitybridge/drupal-tilestache]
[2:07pm] zzolo: i think this is definitely the future of geo
[2:07pm] tnightingale: re: tilestache module - still pretty rough, be warned
[2:08pm] zzolo: and i think postgis sync is the way to go to handle goespatial data and spatial querying.
https://github.com/affinitybridge/drupal-tilestache
https://img.skitch.com/20120426-jfu9fj5c17y5rfa9392y48xmb7.jpg
search api
[2:08pm] mackh: i also want to extend search api to return WKT onto maps
[2:08pm] mackh: from faceted results, hoping to get that client funded in the next 3 months
Office hours finishing
log
[2:07pm] tom_o_t: Brandonian: perhaps schedule dedicated Q&A time for stuff general questions that aren't related to module development?
[2:08pm] Brandonian: tom_o_t: Not a bad idea.
[2:09pm] jeffschuler: tom_o_t++ … this has been super useful, but It's been more of a facilitated discussion on high-level geo in drupal topics rather than a time for folks to come get help or figure out how they can pitch in… different from core office hours http://drupal.org/node/1242856
Use Case
Online-Biodiversitätsportale mit Indicia, Drupal und OpenLayers
http://www.fossgis.de/konferenz/2011/programm/events/239.en.html
CivicApps
http://civicapps.org/
OpenPublic Map Visualization Feature
http://www.openpublicapp.com/map-visualization-feature
broken?
Geofield proximity updates by brandonian
http://drupal.org/node/1469956#comment-6025452
http://en.wikipedia.org/wiki/Haversine_formula
Solr
Articles
Location-aware search with Apache Lucene and Solr
http://www.ibm.com/developerworks/opensource/library/j-spatial/?ca=drs-
Outdated localsolr
https://issues.apache.org/jira/browse/SOLR-773
Cluster Implementations
Client-side (Javascript)
Distance Grid
Leaflet Markercluster
MapBox Clustr Library
https://github.com/mapbox/clustr
Neighbor-check
Openlayers (client side)
http://dev.openlayers.org/releases/OpenLayers-2.11/lib/OpenLayers/Strategy/Cluster.js
Google MarkerClustering
http://code.google.com/p/google-maps-utility-library-v3/wiki/Libraries#MarkerClusterer
http://googlegeodevelopers.blogspot.com/2009/04/markerclusterer-solution-to-too-many.html
http://google-maps-utility-library-v3.googlecode.com/svn/trunk/markerclusterer/docs/reference.html
https://developers.google.com/maps/articles/toomanymarkers
K-means
Polymaps k-means
http://polymaps.org/ex/cluster.html
no interactivity, static
Server-side
Articles & recipes
Google maps Perl impl + discussion
Google Maps Hacks: Tips and Tools for Geographic Searching and Remixing
http://flylib.com/books/en/2.367.1.102/1/
siehe auch downloaded chm ebook
K-mean
Method
1. Select a center point for each of k clusters, where k is a small integer.
2. Assign each data point to the cluster whose center point is closest.
3. After all the data points are assigned, move each cluster's center point to the arithmetic mean of the coordinates of all the points in that cluster, treating each dimension separately.
4. Repeat from Step 2, until the center points stop moving.
Hierachical clustering
Method
1. Assign each point to its own cluster.
2. Calculate the distance from each cluster to every other cluster, either from their respective mean centers, or from the two nearest points from each cluster.
3. Take the two closest clusters and combine them into one cluster.
4. Repeat from Step 2, until you have the right number of clusters, or the clusters are some minimum distance apart from each other, or until you have one big cluster.
Naïve grid-based clustering
grid by display pixels / marker size
assign points to clusters within grid
order clusters by points
make superclusters (heavy clusters claim their neighbors)
Clustering Maps thesis
DB-Scan + R-Tree based implementation, tested up to 400-500 items only (~1 sec)
Demo http://www.wannesm.be/maps/
PHP Implementation of Google Marker Clustering
http://www.appelsiini.net/2008/11/introduction-to-marker-clustering-with-google-maps
artikel + links
http://labo.eliaz.fr/spip.php?article89
Vizmo
Hierarchical Clustering by Meaningful Units
PHP, Symphony2, closed source?
www.globalimpactstudy.org/wp-content/uploads/.../vizmo-poster.pdf
http://www.globalimpactstudy.org/2011/12/open-source-presentation/
Database
PostGIS
idea based on z-curve
http://postgis.refractions.net/pipermail/postgis-users/2006-March/011431.html
uses clustering on indices for fast retrieval
http://workshops.opengeo.org/postgis-intro/clusterindex.html
kmeans-postgresql
http://pgxn.org/dist/kmeans/doc/kmeans.html
http://gis.stackexchange.com/questions/11567/spatial-clustering-with-postgis
grid clustering
SnapToGrid
http://postgis.refractions.net/docs/ST_SnapToGrid.html
MySQL
SQLDM – implementing k-means clustering using SQL (linear)
http://www.abibasystems.com/white_paper/sqldm.pdf
http://www.maptimize.com/
Maptimize can deal with up to 50,000 markers - but the underlying algorithm can handle over one million!
http://v2.maptimize.com/faq#
http://seb.box.re/2009/5/1/maps-geolocalization-and-optimization-with-maptimize
interview
More
Google maps implementation
http://maps.forum.nu/server_side_clusterer/index2.php
with clustering POIs on a route
http://gis5.com/pois_along_route/gm_pois_along_route.php
R-Project
SGCS
Spatial Graph based Clustering Summaries for spatial point patterns
http://www.inside-r.org/packages/sgcs
http://cran.r-project.org/web/packages/SGCS/
graph-based implementation
Flex
http://thunderheadxpler.blogspot.co.at/2008/12/clustering-20k-map-points.html
insert into grid + check for overlaps
clusterPy
http://code.google.com/p/clusterpy/
http://www.rise-group.org/risem/clusterpy/index.html
clusterPy algorithms
AMOEBA A Multidirectional Optimum Ecotope-Based Algorithm
AriSeL - Automatic Rationalization with Initial Seed Location
Automatic Zoning Procedure (AZP)
Reactive tabu variant of Automatic Zoning Procedure (AZP-R-Tabu)
Simulated Annealing variant of Automatic Zoning Procedure (AZP-SA)
Tabu variant of Automatic Zoning Procedure (AZP-Tabu)
Geo Self Organizing Map(geoSOM)
Max-p-regions model (Tabu)
Generate random regions
Self Organizing Map(SOM)
Drupal & Clustering
Drupal 6 github
https://github.com/ahtih/Geoclustering
beschreibung
* source data (points) is in the form of Drupal nodes
* a new Drupal module maintains a DB table of multi-level geographic clusters, using hook_nodeapi() to track changes to source nodes and update the clusters table accordingly. Clusters table is accessible via a Views plugin
* WFS module accesses clusters view and serves out both clusters and source nodes, with clustering level and bbox as request parameters
* a new OpenLayers Strategy or layer type displays the map, selecting a suitable clustering level based on zoom and/or number of points in map view area
http://drupal.org/node/622720#comment-3239286
http://www.letsdoitworld.org/wastemap
Drupal TagMap Clusterer JS
http://drupal.org/project/tagmap
WFS (D6 wenig user)
http://drupal.org/project/wfs
Geohash with Drupal
Geospatial searching with solr 3.x
http://drupal.org/node/1187888
Apachesolr geo sandbox
http://drupal.org/sandbox/pwolanin/1497066
Solr clustering
http://stackoverflow.com/questions/8399152/how-to-best-do-server-side-geo-clustering
Implementierung ohne code
http://blog.sybit.de/2010/11/geografische-suche-mit-solr/
Good discussion
http://www.mail-archive.com/solr-user@lucene.apache.org/msg40651.html
http://searchhub.org/dev/2009/09/28/solrs-new-clustering-capabilities/
Spatial4j
https://github.com/spatial4j/spatial4j
SOLR-2155
https://github.com/dsmiley/SOLR-2155
solr geohash notes
http://spatial4j.16575.n6.nabble.com/Dev-My-Spatial-notes-from-Lucene-Revolution-td4980074.html#a4981005
http://codegouge.blogspot.co.at/2012/05/using-geohashing-in-solr.html
implemented, missing code
http://lucene.472066.n3.nabble.com/Geographic-clustering-td502559.html
Facet prefix filter (David Smiley)
http://stackoverflow.com/questions/11319465/geoclusters-in-solr/11321723#11321723
collpase, group
solr 4.0
http://www.searchworkings.org/blog/-/blogs/result-grouping-field-collapsing-with-solr/
http://lucene.472066.n3.nabble.com/How-to-facet-data-from-a-multivalued-field-td3897853.html
search api solr 4.0 (open)
http://drupal.org/node/1676224
Geohash
about
http://en.wikipedia.org/wiki/Morton_number_(number_theory)
http://en.wikipedia.org/wiki/Geohash
good presenation
http://www.lucidimagination.com/sites/default/files/Lucene%20Rev%20Preso%20Smiley%20Spatial%20Search.pdf
http://www.basistech.com/pdf/events/open-source-search-conference/oss-2011-smiley-geospatial-search.pdf
geohash explanation demo
http://openlocation.org/geohash/geohash-js/
SOLR-2155
edge n-gram'ed geohashes with a PrefixTree/Trie search algorithm
https://github.com/dsmiley/SOLR-2155
http://wiki.apache.org/solr/SpatialSearch#SOLR-2155
SOLR
http://lucene.apache.org/core/3_6_0/api/contrib-spatial/index.html?org/apache/lucene/spatial/geohash/GeoHashDistanceFilter.html
https://issues.apache.org/jira/browse/SOLR-2155
A new geospatial framework for Lucene and Solr
https://github.com/spatial4j/spatial4j
MongoDB
http://www.mongodb.org/display/DOCS/Geospatial+Indexing
PHP additional hilbert-curve
http://www.phpclasses.org/package/6202-PHP-Generate-points-of-an-Hilbert-curve.html
http://stackoverflow.com/a/9645315
geoPHP integration
https://github.com/phayes/geoPHP/issues/32
geohash efficiency
http://karussell.wordpress.com/2012/05/23/spatial-keys-memory-efficient-geohashes/
geohash neighbors java
https://github.com/kungfoo/geohash-java/blob/master/src/main/java/ch/hsr/geohash/GeoHash.java
Drupal Clustering
leaflet + drupal + client-side clustering
http://drupal.org/project/leaflet_markercluster
Clustering
Blog: exploring large sets of geodata
http://groups.drupal.org/node/104014
Benchmarking OpenLayers with Drupal
http://rjsteinert.com/content/benchmarking-openlayers-module-views-and-openlayersjs
Objectives
Design and implement a server-side clustering algorithm for Drupal
Open source
Integrative & Exensible
Use cases
Usability
Realization
Analysis
Algorithm considerations
speed, on-the-fly
database, abstract, geohash, portable
database vs. application layer
Planning for the Drupal mapping environment
Drupal integration
Drupal mapping
Recruiter
Geofield
Views
Search API
Recruiter
Solr
Configuring maps in Drupal
Data model
Query
Mapping Library
Mapping stack
Data flow
Views
SAPI
Usability - Leaflet, client-side clustering
Algorithm
Geohash
Algorithm - theory
input
output
prototype-based clusters
Prototype-based clusters are defined so that objects are closer to their cluster’s prototype than to any other one. Prototypes of clusters are either centroids (the mean of all points for a cluster) for continuous data or medoids (the most central point within a cluster) for categorical data.
hierarchical vs. partitional
agglomerative vs. divisive
hard vs fuzzy
complete vs partial
proximity
STING (grid-based)
geohash
Implementation
Architecture
Index
Parameters
Processing
Visualization
Helpers
Spatial index - geofield
Configuration
Query - views
Display - views, leaflet, leaflet_geojson, ...
Solr
Solr
map requesthandler
handleSelect=true
?qt=/geocluster
Geospatial computation requirements
https://github.com/mapbox/clustr/blob/gh-pages/API.md#clustr
distance between two points
https://github.com/mapbox/clustr/blob/gh-pages/src/clustr.js#L34
centroid of multiple points
https://github.com/mapbox/clustr/blob/gh-pages/src/clustr.js#L55
meters to pixels
http://msdn.microsoft.com/en-us/library/aa940990.aspx
http://wiki.openstreetmap.org/wiki/Zoom_levels
https://github.com/mapbox/clustr/blob/gh-pages/src/clustr.js#L4
problem: kalibriert für äquator, wird weniger nach oben
bounding box strategy
http://www.geojson.org/geojson-spec.html#bounding-boxes
openlayers ok
http://openlayers.org/dev/examples/strategy-bbox.html
http://dev.openlayers.org/docs/files/OpenLayers/Strategy/BBOX-js.html#OpenLayers.Strategy.BBOX
leaflet custom?
https://github.com/CloudMade/Leaflet/issues/962
http://switch2osm.org/using-tiles/getting-started-with-leaflet/
http://boomphisto.blogspot.co.at/2011/07/nodejs-express-leaflet-postgis-awesome.html
movend
https://github.com/CloudMade/Leaflet/issues/327#issuecomment-2460917
Realization
Geocluster
geocluster_views_post_execute
not very flexible, prefer to do plugins
views_plugin_style_geocluster extends views_plugin_style_geojson
views_geojson has complicated _views_geojson_render_fields
geocluster_plugin_style_geofield_map extends geofield_map_plugin_style_map
fields already rendered by field handler post execute
geocluster_handler_field_geofield extends geofield_handler_field
ähnlich wie groupby, get_aggregation_info ?
display that uses another display
datenquelle = andere view
Subtopic 2
queryhandler clustering
alter views result research
Search API research 2008
Building a view from a different source (not Database)
http://groups.drupal.org/node/12838
Describing tables to Views
http://views-help.doc.logrus.com/help/views/api-tables
fake entities
geo data is stored in a field api field
think about the pager
group entity altering of views
http://drupalcode.org/project/views.git/blob/refs/heads/7.x-3.x:/modules/field/views_handler_field_field.inc#l727
views_plugin_query_default
$result = $query->execute();
post_process afterwards
register a custom handler to be exectued before the field handlers
problem: no way to modify views_object_types()
done
geofield + geohash support
http://drupal.org/node/1662584
Feedback
http://affinitybridge.com/blog/server-side-mapping#comment-297
Geohash algorithm
issue
http://drupal.org/node/1662432
Project phases
2011 AustroFeedr
January - March
Drupal + Mapping topics research
April
Frontend United: Geocluster kickoff
20-22 April
June
first sandbox draft
10 June
Drupal Developer Days Barcelona: Mapping Sprint
15 June
Drupal Developer Days Barcelona: Mapping Sprint
Geohash idea (Nick)
September
First demo
27 September
October
Alpha 1: PHP based clustering
Views GeoJSON integration
Solr plugin
November
Alpha2: MySQL + views aggregation baed clustering
December
Solr implementation finished
January + February
Documentation
Polishing
Use cases
GeoRecruiter
Daten
GeoTaxonomie verwenden / geofield
jobs
bezirke
Suche
Search API integration
http://drupal.org/project/search_api_location
Job
Job location auf karte anzeigen
Mapping & Recruiter
http://drupal.org/node/1254716
by Adam S, based on OpenPublic
Conclusions & outlook
Evaluation
Objectives
Performance
Algorithm optimization tasks issue
http://drupal.org/node/1828584
Demo data & test framework
Clustered/aggregated data
issue
http://drupal.org/node/1824954
cluster stability
visualization
Related work
Future work
More
Server-side implementation
http://www.ushahidi.com/
Clustering 6 example
http://www.letsdoitworld.org/wastemap#
People
Nick_vh
geohash, solr
Smiley, David W
solr
phayes
geophp
mollux, Matthias Michaux
http://drupal.org/user/785804
Search API Location
Underdark GIS
alex?
Österreich
Gomogi
http://www.gomogi.com/
micheal diener
FOSSGIS UG AT
fossgis@spektral.at
http://wiki.alpine-geckos.at/wiki/FOSSGIS_UserGroup_Austria
http://www.alpine-geckos.at/category/geowissenschaften/
Visual
http://vis4.net/blog/posts/clean-your-symbol-maps/
Vizualizing Large Spatial Datasets in Interactive Maps
Voronoi polygons
compare
d3
http://mbostock.github.io/d3/talk/20111116/airports-all.html
hierarchical aggregation.
can effectively be used with datasets of up to 1000 items.
Clutter not only reduces the background visibility, but also hinders the users understanding of the structure and content of the data.
Hierarchical aggregation is a common visualization technique to make visual representations more visually scalable and less visu- ally cluttered [1]. In particular, hierarchical aggregation tech- niques have been proposed for exploring spatial data sets [2], [3].
Ellis and Dix’s [7] distinguish three main types of clutter reduction techniques: appearance (alter the look of the data items), spatial distortion (displace the data items in some ways) and temporal (animation).
Heatmap
However, a problem with this approach is that users interactions with the data items are harder to deal with, as they need to be handled at the pixel level.
Icons
One of the main drawbacks of using icons as aggregation symbols is that they do not show the area covered by the clusters.
Visualization evaluation
Evaluating visualization techniques is a well-known prob- lem [16], [17].
Types
summative (i.e., comparison-based),
formative (evaluation that leads to suggestions for improving the evaluated technique)
exploratory analysis (evaluation that is helpful to discover new ideas and concepts about the technique).
Color
Color is used to drive user’s attention on denser clusters. The color assigned to a polygon is determined using a hot-to- cold color ramp where hot colors are assigned to dense clusters and cold colors to sparse ones [18].
if points are concentrated in small visible areas, polygons will cover a significantly wider area than the area of their points. In that case, using bounding boxes or hulls, as cluster footprints could be more effective.
Types
Heatmap
Clustering and Visualizing Geographic Data Using Geo-tree
http://en.wikipedia.org/wiki/Heat_map
Icons
Grid
Container shapes
Boxes
Hulls
Paper
compare
Circle Packing
d3
http://bl.ocks.org/mbostock/4063530
Properties
Size
Center (weighted)
Shape
Color
http://en.wikipedia.org/wiki/Map_coloring
Interaction, Animation
clustermap
https://code.google.com/p/clustermap/wiki/Introduction
example
Attribute clustering
https://github.com/Leaflet/Leaflet.markercluster/issues/96
http://openlayers.org/dev/examples/strategy-cluster-extended.html
Process
vis
Cluster quality Measures
Purity
Entropy
NMI Normlized Mutual Information
Allgemein
Analysis Visualization
– Flat Tree Viewer, 2D Matrix or Heat Map, Hyperbolic Lens
Viewer, Table Viewer
Examples
https://developers.google.com/maps/documentation/javascript/training/visualizing/earthquakes
Basic markers, sized circles, and heatmaps.
SnapToGrid example
http://developers.cartodb.com/examples/point-clustering.html
Chart Maps
Pie vs Bar
http://kartograph.org/showcase/charts/
Choroplath Maps
Kartograph
http://kartograph.org/showcase/choropleth/
Dot Grid Maps
Kartograph
http://kartograph.org/showcase/dotgrid/
Symbol Maps
Kartograph
http://kartograph.org/showcase/symbols/
3-dim
Kartograph
http://kartograph.org/showcase/3d/
compare
d3
animated wind chart
http://prcweb.co.uk/lab/ukwind/
Icons
MapBox
http://www.mapofthedead.com/map#14.00/48.8607/2.3440
Wind Icons
http://windhistory.com/map.html#9.00/37.8931/-121.7366
Scaled Data Values
MapBox
http://mapbox.com/blog/scaled-data-value-design-in-tilemill/
Scaled Dots
MapBox
http://mapbox.com/blog/scaled-data-value-design-in-tilemill/
Hexagonal Binning(Heatmap)
MapBox
http://mapbox.com/blog/binning-alternative-point-maps/
Animated OpenLayers
OL
http://acuriousanimal.com/blog/2012/08/19/animated-marker-cluster-strategy-for-openlayers/
More Intro
More
Clustering Theory
Names, Keywords
Geospatial clustering
Analytical regionalization
Spatially constrained clustering
Approaches
Where to cluster
Clustering Client-side
Clustering by Logic
Clustering by Database
When to cluster
realtime / on-request
Pre-cluster / store clusters in db
How to cluster
Questions
what about performance?
how do filters work?
how well does it integrate with current drupal mapping technologies?
how does caching work?
how does client interaction work?
how does it work with and without spatial database capabilities?
Articles, soso
Google maps with lots of data, comparison of libs
http://www.svennerberg.com/2009/01/handling-large-amounts-of-markers-in-google-maps/
Damn Cool Algorithms: Spatial indexing with Quadtrees and Hilbert Curves (Geohash)
http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
zitat Quadtrees -> Geohashes
article
link
http://web.archive.org/web/20071121140547/http://trib.tv/tech/clustering-points-on-a-google-map/
http://trib.tv/
Basic Types
Well-separated: Points belong to a cluster when they are closer to every point in the cluster than they are to any point not in the cluster. This requires each cluster of points to be separated by a distance at least equal to the diameter of the largest cluster at its longest point.
Prototype-based: Points belong to a cluster when they are closer or more similar to the cluster’s prototype, ie. a point representing the cluster as a whole, than they are to any other cluster’s prototype. This tends to result in circular clusters since the prototype (in a geospatial dataset anyway) is usually the centrepoint of the cluster.
Graph-based: A cluster is defined as a set of points that are all connected, directly or via a chain of other points, to each other, and which are not connected to any point not in the cluster.
Density-based: A cluster exists where there is a region of high density surrounded by a region of low density. These clusters can end up being any shape, and vary widely in size.
Conceptual: A cluster exists where all points in the cluster share a common attribute which is not present in any point outside the cluster.
Implementation types
Variable gridding
Interleaved digits
K-Means
http://macwright.org/2012/09/16/k-means.html
QT-Clust
DBSCAN
Agglomerative Hierarchical Clustering
Grid based viral growth argorithm
More
Utils
php haversine (c)
https://github.com/php-geospatial/geospatial
PHP hilbert curve
http://sourceforge.net/projects/hilbert-curve/