Posts Tagged ‘edge’

Travellr: Behind the Scenes of our Region-Based Clusters (Google GeoDev)

Monday, July 6th, 2009

[Editor's note: The age-old rule for cloropleth mapping that suggests aggregation by multi-scale areal units based on the map's zoom level is slowly seeping into "clustering" for the point-based mashup geo community. This overview from Travellr published on the Google GeoDevelopers blog includes two illustrations that show the power of this technique. I used such a technique (different implementation) on The Washington Post's recent swine flu mapping.]

Republished from Google GeoDevelopers Blog.
Monday, June 22, 2009

Recently, there has been a lot of interest in clustering algorithms. The client-side grid-based MarkerClusterer was released in the open source library this year, and various server-side algorithms were discussed in the Performance Tips I/O talk. We’ve invited the Travellr development team to give us insight on their unique regional clustering technique.

Travellr is a location aware answers service where people can ask travel-related questions about anywhere in the world. One of its features is a map-based interface to questions on the site using Google Maps.

dxjmnbf_4t5qkqpfw_b1
Figure 1. An example of the Travellr Map, showing question markers for Australia.

Clustering for usability
We learned that the best way to display markers without cluttering our map was to cluster our questions depending on how far you zoom in. If the user was looking at a map of the continents, we would cluster our questions into a marker for each continent. If the user zoomed-in to France we would then cluster our questions into a marker for each region or city that had questions. By clustering our data into cities, regions/states, countries, and continents, we could display relevant markers on the map depending on what zoom level the user was looking at.

Optimizing for Clustering
Our next challenge was how to extract clustered data from our database without causing excessive server load. Every time the user pans and zooms on the map, we need to query and fetch new clustered data in order to display the markers on the map. We also might have to limit the data if the user has selected a tag, as we’re only interested in a questions related to a topic (ie: “surfing”). To execute this in real-time would be painstakingly slow, as you would need to to cluster thousands of questions in thousands of locations with hundreds of tags on the fly. The answer? Pre-cluster your data of course!

Step 1. Structure your location data
When a question is asked about a city on Travellr, we also know its region/state, country and continent. We store more than 55,000 location points as a hierarchy, with each location “owning” its descendent nodes (and all of their data). Our locations are stored in a Modified Preorder Tree (also called Nested Sets). Modified Preorder Trees are a popular method of storing hierarchical data in a flat database table, having a focus on efficient data retrieval, and easy handling of sub trees. For each location we also keep a record of its depth within the tree, its location type (continent, country, region/state, or city), and its co-ordinates (retrieved using the Google Maps geocoder).

Step 2. Aggregate your data
We calculate aggregate data for every branch of our locations tree ahead of time. By storing aggregate data for cities, regions/states, countries, and continents, we provide an extremely fast and inexpensive method to query our locations database for any information regarding questions asked about a particular location. This data is updated every few minutes by a server-side task.

Our aggregations include:

  • Total question count for a location
  • Most popular tags for that location
  • Number of questions associated with each of those tags.

How we query our structured, aggregate data on the map
Whenever the user zooms or pans the map we fire off a query to our (unpublished ;) API with the tags they are searching for, the current zoom level, and the edge co-ordinates of the map’s bounding box. Based on the zoom level (Figure 2) we work out whether we want to display markers for continents, countries, states, or cities. We then send back the data for these markers and display them on the map.

dc287ncr_29cb84v7ct_b
Figure 2. Clustering at different zoom levels (blue = continents, countries, pink = states, cities)

Everyone Wins
So what is the result of structuring and aggregating our data in such a way? It means that we have nicely organized, pre-clustered data that can be read from cheaply and easily. This allows us to provide a super-fast map interface for Travellr that puts minimal load on our infrastructure. Everyone is happy!

Comments or Questions?
We’d love to hear from you if you have any questions on how we did things, or suggestions or comments about Travellr’s map. This article was written by Travellr’s performance and scalability expert Michael Shaw (from Insight4) and our client-side scripting aficionado Jaidev Soin.

You can visit Travellr at www.travellr.com, or follow us on Twitter at twitter.com/travellr.

CIA World Factbook Relation Browser (moritz.stefaner)

Wednesday, June 10th, 2009

br-12_v2

[Editor's note: This interactive visualization browses the CIA World Factbook topology of geography by country. Featured edge relationships include neighboring countries, spoken language, and more.]

Republished from Moritz.Stefaner.

This radial browser was designed to display complex concept network structures in a snappy and intuitive manner. It can be used to visualize conceptual structures, social networks, or anything else that can be expressed in nodes and links.

The CIA Factbook demo displays the relations of countries, continents, languages and oceans found in the CIA world factbook database. Click the center node for detail information or click adjacent nodes to put them in the center. The arrows on the top left can be used to navigate your click history. Use the dropdown in the upper right to directly access nodes by name. The varying distance to the center node for nodes with many neighbors was only introduced to enhance legibility and does not have a special semantics.

Reviewing the Nokia 6210. An iPhone competitor? No.

Monday, April 20th, 2009

nokia6210navigator

Nokia’s WOM World was kind enough to loan me a Nokia 6210 Navigator (full specs) with the new Nokia Maps 3.0 beta to test in March. I was excited to use this phone because on the surface it has a similar feature set to my iPhone in a smaller profile with potentially less costly carrier subscription and not being tied to ATT. The phone has a GPS, camera, video phone capabilities, and better navigation software with 3d and walking modes via their OVI Nokia-branded maps service which came preloaded on my testing unit.

It took me a while to figure out that I could access the mapping functionality via a dedicated map “compass” button on the main button area (blue button on the bottom of top (LCD part) slider unit in photo above). The mapping functionality is not visible in the phone’s home screen of GUI buttons. After a while I figured out how to use the “Menu” key to get more than top level menus and then choose the map icon there, too. Maps are preloaded onto the phone, no need for net connection for basic functionality, a plus over the iPhone.

Compared to the iPhone, the Nokia 6210 has several great 3d map views more akin to GPS car navigaion systems (an app is available for the iPhone that brings some of this functionality over). The Nokia 6210 has better integrated search for POI around you (I have downloaded several 3rd party apps for my iPhone that do the same thing). The 6210 also does walking directions (and allows straight line walking, not just along roads).

It is strange this phone ships with the GPS turned off. When I pulled up the map application for the first time it did not ask me if it should turn on the GPS receiver. I had to go into the settings area and manual enable. While I can understand the goal of reducing the drain on the battery, this was inconvienent and confusing to turn on. During normal usage, the GPS would take a very long time to engage. The maps app would crash often (it was beta, after all). The 6210 doesn’t seem to use cell phone tower triangulation to get the fast fix (and GPS later to refine position), a serious downside compared to the iPhone’s rapid location display and then refinement. Route planning on the phone required a license code, compared to the free Google Maps routing on the iPhone. This adds potentially $100 extra per year for the same functionality.

The Nokia 6210 Navigator is a slider phone, but the slider functionality did not always engage the phone’s OS to unlock, or there would be a extremely long delay. The keypad interface instead of my iPhone’s touch screen was infuriating. I should note the phone has the old 3 abc-per numeric keypad layout, not a blackberry qwerty keypad.

Phone call quality seemed on par or slightly poorer than my iPhone. Same locations, same SIM, same carrier. Data connections were notably slower due to reliance on 2G (Edge) service. Web page rendering was terrible compared to the iPhone. Nokia has announced several new phones with 3G speeds.

I wanted to test the video conf. capability since this phone has two cameras, one pointed towards your face and the other at the back of the phone. But I didn’t know anyone else with a video conf. capable phone. It is rumored the summer 2009 iPhone hardware update will enable this.

The camera was okay, not as good as iPhone in low light. The 6210 does have a flash, though! and the battery is easily replaced. Just pop off the back of the case. The SIM card is located behind the battery and easy to swap out.

All in all I prefered my iPhone 3G over the Nokia 6210 Navigator. I see that Nokia is prepping a new touch screen version and has introduced the Ovi store to compete with the iTunes app store. But by the time that is released, we’ll have a new version of the iPhone.

Watch this YouTube video for views of the phone; Maps application shown at the very end.