Arduino Cycle Map

I’m trying to build a little mapping application for cyclists using an Arduino Mega, SD card, touch screen, and GPS module.
The first step in this process is generating an efficient map file that can be rendered on the AVR chip.

I thought I should generate an R tree with just the roads and whether they are bike-friendly.

I looked at the wiki, where I found “highway=cycleway” and “bicycle=yes”, but the resulting map is very patchy.
It appears that the cycle layer on the site has many more cycle paths. What am I missing?

Compare:

http://osm.org/go/0GQkIWs?layers=C

The second question is whether there are existing formats for efficient range queries on ways.
It seems a common thing to do is to dump everything in an SQLite DB.
This is not an option on AVR, so I need something different.

Indeed, bicycle=yes is only one of the many variations that allow cyclists. There is also the highway=cycleway for separate cycleways, or cycleway=track or lane. Furthermore there is bicycle=use_sidepath (instead of yes) which is getting tracking in NL, D and B.
Furthermore, bicycle=yes is normally not tagged when the street normally allows cyclist, e.g. on highway=residential

And of course there is bicycle=designated

some stuff you might use