What are tiled vectors?

Ever wanted to display a really big GPS track or other vector data set in a browser-based map like Virtual Earth? If you've tried, you've probably seen the browser melt trying to process thousands of data points in JavaScript.

With Tiled Vectors, you package your vector data into constant-sized tiles, so that the browser only fetches just as much data as needs to fill one screenful. This is the same basic technique used to display logically-enormous raster images, which you can generate with MapCruncher. Here, however, the data is transmitted as vector data all the way to the client, so you can attach JavaScript behavior to the vectors.

In this demo, Virtual Earth shows a polyline data set with 50,000 segments in it, with constant-time performance. Notice that the status line "showing n vectors": n will never grow beyond a small constant (200 times the number of tiles visible on your display). There's no hard limit to the total number of segments in the input data set; we've displayed the 60 million segment Tiger line data set the same way.

How it works

First, an offline preprocessor prepares the data set by summarizing it and chopping it into tiles. As the map is zoomed and panned, the JavaScript code fetches the tiled data on demand, and each tile-sized vector list as a Virtual Earth ShapeLayer. When a tile goes off-screen, the corresponding ShapeLayer is deleted.

The data on the server is divided up into exactly the same geographic regions ("tiles") that the raster image is divided into. But instead of raster images, the server sends the client a JavaScript file containing first-class JavaScript objects. In this demo, those objects are a VEShapeLayer, and can be programmed to enjoy the interactive functionality of any other VE object.

How can I try this with my own data set?

This demo is available under MSR's source code license:

The python script GpxToTiles processes a .gpx file containing tracks (waypoints are ignored) into a series of tiles containing polylines. As it runs, it emits lines telling how much of the segment budget is used by the median and 95th-percentile tiles in each zoom level. Once you find most tiles aren't spending the whole budget, that's probably as far as you need to render.

You'll need to get your data into .gpx format. If it's not already, you can write a script that uses the GpxEmitter to convert from some other format.

The code currently supports only polylines; not filled polygons or points. Changes required:

• For polygons, the code needs to correctly clip the polygons so that adjacent pieces of a polygon on separate tiles get filled correctly.
• For points, the code needs to cluster or prioritize points for summarization.
• In either case, the code needs to modify the emitted .js tiles to construct the appropriate VEShape() objects. The current code uses a shorthand function in TiledVectors.js to reduce the verbosity of the .js format; you may wish to provide similar support for other object types.

GpxToTiles processes all the vectors in memory. If you have a really big data set (such as the 60-million-segment Tiger data), you'll need to process it out-of-core. Here's one approach:

• Divide your input set into smaller pieces. (Tiger, for example, already comes divided into thousands of subfiles.)
• Run GpxToTiles over each piece with '--outputType gpx' to generate gpx-format tiles for that piece.
• Enumerate all the unique tile addresses across all pieces. For each tile address, create an instance of GpxToTiles and tell it to parse all gpx tiles for that address. Then emit the result (as a .js tile).

How else could this problem be solved?

Another way to display large data sets is to render them into rasters using MapCruncher. This approach works, and can produce very pretty representations, since clients can handle very complicated raster image tiles easily. However, rasters have no interactivity: users can't click on a line or point and get a pop-up, for example.

Recent releases of Virtual Earth can handle quite large data sets natively on the client. However, passing the entire data set to JavaScript will always cause at least a startup delay for large data sets, since the data must be transmitted and parsed by the client before display can begin.

In some situations, tiled vectors offer the best of both worlds, plus exposes new benefits:

• Tiled vectors can handle arbitrarily large data sets. At some point, client-side processing is limited by the startup time and browser memory required to download and preprocess a large data set. In contrast, tiled vectors use the same offline preprocessing principle that enables Virtual Earth to scale its two raster layers to arbitrary size; even billions of vectors.
• Tiled vectors preserve the semantics of the vectors on the client, enabling interactive behavior (like pop-up content) and dynamic rendering (change line size or color). For some applications, this beats rendering the vectors to raster tiles (such as with MapCruncher) and sending those rasters to the client where they sit on the screen still and lifeless.
• Offline tiling enables fancy, elaborate summarization techniques (notwithstanding this demo, which doesn't show off sophisticated summarization). An offline summarizer can include more complicated heuristics than one might be willing to code in JavaScript. Where online code has a short deadline to bound startup delay, offline code can spend more time approximating NP-hard optimization problems. An offline tilers can be customized by the application developer, and can thus exploit domain-specific knowledge, such as which features are most important.
• Offline tiling enables hybrid summarizations: at low zoom levels, millions of vectors are rendered into raster tiles (offline); at high zoom levels, the smaller set of vectors is transmitted directly to the client. This lets us have the best of both worlds: high-fidelity rendering of tiny details which behave interactively.

Contact

This demo and the tiled-vector architecture was developed by the folks in Microsoft Research that brought you MapCruncher: .

Demo limitations

Why do the states look chunky when zoomed out? My summarization algorithm is pretty simplistic, and I'm using a limited budget of 800 segments per tile for this demo. You can apply the same client-side code, and use a more sophisticated preprocessing and summarization step to spend your segment budget more effectively.