Laurent Dupuis's Home

This post is the logical following of the previous post concerning creating a geospacial database from the OpenStreetMap OSM files. The next logical step is to create a routing function (the classic “from to”) by using the data uploaded in the previous post.

Building the Graph

For this post, I have redesigned the OSM loader:

OpenStreetMap is a collaborative project to create a free map of the world. They provide their map in full as a computer readable format. The file is a BZIP2 compressed XML file sized north of 16GB. The XML format is quite simple and well documented on their Wiki.

Extracting, manipulating such large map is a challenge. It is unthinkable to simply use the XML DOM load function against a 250GB XML. Once the data is extracted, how can it be stored it in a usable form to allow the end user to render any part of it? This post is a practical approach to theses practical challenges.

What allowed Google to triumph over AltaVista, the first comprehensive Internet search engine, was the ability to sort the result by relevance to the user. Google used the fact that popular pages were mostly linked to than less relevant one to compute a static score, the famous page rank, and display pages in order. The rest is history: Google is multi-billion dollars business and AltaVista is gone.

The techniques used by search engines are also relevant in implementing search engines on every day databases. For search and query, the data are described in tables that relate to each other. This means that, like as web search were based on page links, it is possible to sort data by the way they link at each others.

Recently I had to configure a box with two Internet connections: one via the common network, one via a dedicated link which is used as a back-up. This is a situation which is not handled correctly by IP stacks: a packet received from one connection must be returned by the same. While setting up this, using the little documentation I could found over the Internet, I was amaze by the level of feature in the Linux IP stack.

The Windows IP stack has some hardcoded limitation that can't be disabled:

• You can't have more than 10 connections per port
  
• Raw socket are very limited on Windows
  
• Some port (eg SMB) are always in use by Windows kernel and services

There is no way around this issue except hacking Windows system binaries. However, it is possible to create your own IP stack in parallel of Windows one. Because that’s your stack, there will be no limitation and your process will be seen as a complete independent computer.

For a project, I wanted to measure performance of live production in a non invasive way (no special build, limited deployment, easy to disable). So I took a deep dive into the CLR Profiler API and I was able to create a very efficient solution where I could inject .NET Assembly reference and function calls into an existing application. Find more here.

Modern video cards are powered by Graphic Processing Units. These chips are designed to offload the main processor of the construction of bitmap frame buffer. They have their own memory and processing power and are optimized to process graphic data.
For a GPU, the main processing units are triangle lists. Modern graphic API which are designed to expose the GPU, like DirectX or OpenGL, only allow graphic primitive composed of lines or triangles.
To draw text or vector text in an efficient fashion you need first to convert your polygon based vector graphics to a list of triangle. This process is called “tessellation”. Modern GPU optimized APIs like WPF and Direct2D convert user’s vector graphics to triangle under the hood.
Converting a TrueType font to a triangle list is not trivial. The first step is to convert a glyph as list of polygon. For one project, I wanted to use DirectX for having the best graphic 2D performance. So I find myself with the same issue:

At my current job, I have sometime to search inside large flat log files that have been previously zipped for archive. The naïve way is to unzip and use some kind of tool (like the Windows XP search wizard) to find what I’m looking for. This is slow, tedious and requires a lot a free space on my hard drive that I generally don’t have.

So I searched for a better way by directly looking inside the ZIP file, I could :

• avoid the long file transfer, decompression and search for space I don’t have
• I could use a super charge text search algorithm like the Rabin-Karp with shifting hash and be faster than the ancient Windows wizard

Creating class for accessing your database is boring. Instead of manually write mock-able interfaces and long implementation of database access classes, I decided to take the aspect programming way by creating a full automatic generic and on the fly compiler of database class interface. Fully implemented using the System.Reflection.Emit, it is as efficient as manually coded interface but it just requires a few attributes.

For example:

public interface ISqlDemo
{
    // Return a primitive type
    [SqlStatement("select count(*) from master..sysdatabases")]
    int GetDatabaseCount();
 
    // Return a string.
    [SqlStatement("select CURRENT_USER")]
    string GetCurrentUser();
 
    // Populate and return an object collection.
    [SqlStatement("select name,id from master..sysobjects where type=@type")]
    IEnumerator<Value> GetObjectsByType(string type);
}
 
// Get a proxy!
ISqlDemo proxy = BridgeCompiler.CreateInstance<ISqlDemo>(databaseConnection);