Posts Tagged ‘network topology’

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.

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.

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, or follow us on Twitter at

The Internet’s Undersea World (Guardian)

Wednesday, June 24th, 2009

[Editor's note: Wireless is all the buzz but good old copper and fiber-optic cables link most of us together, as this graphic from last year's Guardian newspaper shows.]

Republished from the Guardian newspaper (UK).

The vast majority of the world’s communications are not carried by satellites but an altogether older technology: cables under the earth’s oceans. As a ship accidently wipes out Asia’s net access [in 2008-ed], this map showss how we rely on collections of wires of less than 10 cm diameter to link us all together.

View larger JPG version (hi-res pdf).


First Look at Natural Earth Vector

Friday, June 12th, 2009

Tom Patterson and I collaborated on the precursor to his first Natural Earth Raster project several years ago and we now preview Natural Earth Raster + Vector, a new free product due Fall 2009 that complements and expands on the previous work by providing detailed GIS linework at the 1:15,000,000 (1:15 million) scale and new versions of the raster product (including cross-blended hyspometric tints). The Washington Post, where I work, is contributing 2 more vector GIS base maps at the 1:50m and 1:110m scales and new versions of Natural Earth Raster will be released for those scales. This is a NACIS and mapgiving co-branded product with assistance from the University of Wisconson-Madison cartography lab, Florida State University, and others.

Please attend the October NACIS 2009 map conference in Sacramento, California for the unveiling.

More description and preview images after the jump.


Tag Cloud Map as Interface (Net-Listings)

Thursday, June 11th, 2009


[Editor's note: This real estate pricing guide for London uses a tag cloud map as the main interface. Instead of showing a detailed street map or an alphabetical placename list, they use a geographic tag cloud map. Tags are not sized to price. Rather they is color coded for price. Placement of the labels matches their geographic location (roughly speaking). Like many subway maps, the River Thames provides overall orientation.]

Republished from Net-Listings. 

Finding property, flats or houses for sale or to rent in London


Simply click on any area of the map and watch the screen reveal information about that area, price guide for area and links to local Estate Agents.

The new page will show you links to Letting and Estate agents in that area of London, a brief description of that area and a rough guide to rents for typical accommodation. You can also use our “Let All Agents Know I am looking” to assist you find a suitable Estate Agent and Property. The price guide can help you decide an suitable areas based on the rental price of a flat or house in London, England.

More Screenshots:






CIA World Factbook Relation Browser (moritz.stefaner)

Wednesday, June 10th, 2009


[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.

Flow Mapping (Box Shaped World)

Tuesday, June 2nd, 2009


[Editor's note: Flow maps have always ranked high on my radar but constructing them has always been tedious. This post and academic paper link detail how they can be automated with programatically, including edge routing (not directly from A to B, but with bends to not overlap other connections).]

Republished from Box Shaped World.

Getting a head start on a new project that is more cartographic. It will involve mapping migration/flows from Australia to the Northern Territory (probably smaller geographic units than states). I like making maps, and so I’m excited to do some cartography beyond standard ArcGIS layouts. There are different possibilities on how to map this. Initially, I think I will use something like this that creates a more trunk/branch flow map instead of the typical straight line between places (Tobler’s Flowmapper). The project lead doesn’t like this style too much, but thought the trunk/branch style might work. We might pursue other mapping techniques, which would be cool to try and apply different map techniques to this area…

Continue reading at Box Shaped World . . .

Republished from Stanford Graphics paper.

Cartographers have long used flow maps to show the movement of objects from one location to another, such as the number of people in a migration, the amount of goods being traded, or the number of packets in a network. The advantage of flow maps is that they reduce visual clutter by merging edges. Most flow maps are drawn by hand and there are few computer algorithms available. We present a method for generating flow maps using hierarchical clustering given a set of nodes, positions, and flow data between the nodes. Our techniques are inspired by graph layout algorithms that minimize edge crossings and distort node positions while maintaining their relative position to one another. We demonstrate our technique by producing flow maps for network traffic, census data, and trade data.

Continue reading past abstract, includes source code . . .

“Subway Map” Album Art from KCRW Sounds Eclectic

Wednesday, May 27th, 2009


[Editor's note: I saw this album art CD cover at Starbucks last week. KCRW, the streaming public radio station out of California, puts out yearly live studio performance albums. This one features the likes of Dido, Rufus Wainwright, and Girls in Hawaii. The artists are arranged along subway lines with stations labeled with artist names. Not sure if there's a rhyme or reason to the layout, but the result is cool. ]

More info on CD from KCRW . . .

Transit on Google Maps comes to a Town Near You (Kelso)

Friday, April 3rd, 2009

[Editor's note: When I've traveled to Paris or Beijing I like to take public transit both below and above ground. It gives me a good sense of the people and the place. And it reduces my carbon footprint. But sometimes figuring out transit systems can be irksome. I've got a great pocket atlas of Beijing that shows major bus lines and their stops which is helpful. And Paris offers some good printed material. But figuring out which station or stop is closest to the start and end of the trip is just the beginning. Which route is best? And when will I get there are two important questions. If you've missed it, Google Transit solves many of these challenges. New transit systems are being added monthly, check to see if your city participates.]

I live in metro Washington DC and our transit agency finally released their network topology, routing, scheduling in Google Transit format after a long petition drive. Now 3rd party developers, including Google, can use this to build out web apps or even mobile phone apps like iBART. DCist has coverage of both the recalcitrance of this public agency in giving out data we’ve already paid for as tax payers (sound familiar). Cartographers should use the station and bus stop locations included in these transit feeds to locate these features on their city maps.

Cartographers need to get on the mobile app development bandwagon and provide customers with tools that leverage these types of datasets. Imagine an app that has a proximity sensor / alert for nearby bus or transit stops or tells you the bus you want is coming in 5 minutes, time to pack up. And can do all the routing for you. And can be leveraged to provide the customer with, say, trail routing in the backcountry, too.

Why is transit on Google Maps a big deal? From WorldChanging:

[Including transit on maps and routing] make public transit more accessible and easier for everyone to understand; and in doing so, it will certainly increase transit ridership and reduce driving.

One of the big barriers to public transit use is the knowledge required to use the system: where to wait, when to wait, where to transfer, how much to pay, etc. Some readers may remember that two years ago we helped cause Google Transit to happen, but it’s taken off far beyond what we had suggested, and they keep getting better. What’s more, they’re doing it at no charge to the transit agencies (a perpetually under-funded sector of local governments). More cities are coming on board, as well; if you live in one of the eleven cities now participating, enjoy! If you live elsewhere, consider writing to your local transit agency and telling them to join the 21st century. (ahem… San Francisco, right in Google’s back yard, no excuse… ahem.)

What are these tools? In addition to being able to type in your route and get comprehensive directions (including walking to stations, showing the bus or train route, walking directions between stations, how much it costs, etc.), you can plan trips by departure or arrival time and see when the next couple buses come if you miss the one you’re aiming for. Now, if you zoom in enough on any Google map in the right city, all the transit stops appear, with different icons for bus, light rail, etc.; click on a bus stop and up pops a list of the buses or trains that stop there; click on the bus number, and up pops the timetable for the next several buses stopping there.

Want to get your transit data on the map? Aaron Antrim, who heads Trillium Transit Internet Solutions helps smaller agencies get online with Google Transit, in particular, those small-to-midsized transit agencies that don’t have dedicated IT staffs (ref). Aaron went to the same university as me and is quite active in transit circles.

There’s a petition to add “By bike” like there is “Walking” and “Transit” to Google Maps (ref). See this in action at as seen at Treehugger.

Mental Map: How China Sees the World (Economist)

Monday, March 30th, 2009

[Editor's note: "Illustration by Jon Berkeley with apologies to Steinberg and The New Yorker". Map illustration shows China's world view / mental map with Tiananmen Square central, the US in the distance, and Europe but a spec on the horizon. This mental map is a good example of a network topology based projection.]

Republished from the March 21st, 2009 print edition of The Economist.

And how the world should see China

IT IS an ill wind that blows no one any good. For many in China even the buffeting by the gale that has hit the global economy has a bracing message. The rise of China over the past three decades has been astonishing. But it has lacked the one feature it needed fully to satisfy the ultranationalist fringe: an accompanying decline of the West. Now capitalism is in a funk in its heartlands. Europe and Japan, embroiled in the deepest post-war recession, are barely worth consideration as rivals. America, the superpower, has passed its peak. Although in public China’s leaders eschew triumphalism, there is a sense in Beijing that the reassertion of the Middle Kingdom’s global ascendancy is at hand (see article).

China’s prime minister, Wen Jiabao, no longer sticks to the script that China is a humble player in world affairs that wants to focus on its own economic development. He talks of China as a “great power” and worries about America’s profligate spending endangering his $1 trillion nest egg there. Incautious remarks by the new American treasury secretary about China manipulating its currency were dismissed as ridiculous; a duly penitent Hillary Clinton was welcomed in Beijing, but as an equal. This month saw an apparent attempt to engineer a low-level naval confrontation with an American spy ship in the South China Sea. Yet at least the Americans get noticed. Europe, that speck on the horizon, is ignored: an EU summit was cancelled and France is still blacklisted because Nicolas Sarkozy dared to meet the Dalai Lama.

Continue reading at The Economist . . .

Transit Time Maps from Walk Score (via Google Maps Mania)

Tuesday, March 24th, 2009

[Editor's note: Detailed maps help understand transportation time between point A and B. Network topology routing provided by open source software and then pushed out as a Google Maps mashup. WalkScore was previously featured here for their "walkability" maps which both help people figure out where to live.]

Republished from Google Maps Mania and Walk Score.

WalkScore have produced a Google Map mashup that can show you how far you can travel in San Francisco, Portland or Seattle on public transport in 15, 30 and 45 minutes. The map can show you how far you can travel on public transit from a given location and at any time of day.

How it Works

Transit schedules are downloaded in GTFS format and the XML street data is fetched from OpenStreetMap. These are compiled into a graph for use by the Graphserver trip planner. Street intersections are graph vertices and streets are graph edges.

Graphserver calculates the shortest path tree for a given location. The time of arrival at all street intersections is cross-referenced with a table of street intersection locations to create the contours for different travel times.

Go to Walk Score to try out the Transit Time map . . .