Wikipedia for the iPhone/OLPC: storing the sum of human knowledge in 2GB

This talk details the technical story behind creating a GPL’d application for storing and reading a copy of Wikipedia on the iPhone and OLPC—basically, realizing The Hitchhiker’s Guide to the Galaxy. Now one of the most popular iPhone apps (with over 100,000 downloads), and a pre-installed OLPC app (bringing Wikipedia to kids who’ve never used the internet), we describe the challenges and hacks involved in making it all work.

To store Wikipedia in 2GB requires finding highly space-efficient compression for article text and search indices. Doing this as part of an interactive application on a device with very limited processing and memory resources introduces further constraints that require unusual solutions.

Some of the hacks we describe include:

• partial decompression and indexing of bzip2 files;
• fast prefix and substring matching using a single compressed index, based on James A. Woods’ work (“Finding Files Fast”, USENIX ;login: February 1983), to enable near-instantaneous search of article titles;
• efficient storage, parsing and rendering of MediaWiki markup, using fairly computationally-intensive preprocessing to enable a rapid, single-pass parser on the device itself.

In addition, we describe some of the systems involved on the server side, such as creating an ad-hoc CDN for distributing our customised dumps.