android - Best option for supplying Quadtree GPS Data to an app?

Question

We have >25 MB of static Quadtree Data that we would like to provide as part of a cross platform app, which can then be searched by the app code to get details of locations close to the user's current GPS position.

We would like to search the data without loading all of the data into memory, in a quick time, and ideally without reinventing the wheel.

We have looked at supplying a database using R-Trees in SQLite for this, which sounds like it would be ideal, but apparently these are not available in the SQLite version supplied with android. Shipping our own version of SQLite for android (that includes the R-Tree structures) sounds like a lot of pain - but we would be interested to hear about others' experience with this.

We could create a filesystem model, but our data could be very large and it feels like we might run into trouble mis-using the filesystem this way.

We are hoping there might be some other file format already designed for this purpose and perhaps java/obj-c libraries existing to search this. Can anyone point us to such a thing?

The other obvious solution is to create our own file format and searching system, but this would probably be a lot of work.

The app is actually a cordova/phonegap app that will be available for ios and android, but its not a problem to write a native plugin for each platform to handle this.

Thanks in advance

Answer 1

Ignoring the off-topic aspects of the question, using R-tree data on Android requires that you compile SQLite with the NDK and ship it for whatever architecture(s) you want to support.

However, SQLite's R-tree module is implemented as an extension that uses 'normal' tables to store the R-tree data. The most complex part of handling R-trees is updating and rebalancing the tree; compared to that, searches are trivial. If you want to do nothing but searching on static data, you could just implement them manually.

The source code has this to say:

Database Format of R-Tree Tables

The data structure for a single virtual r-tree table is stored in three native SQLite tables declared as follows. In each case, the '%' character in the table name is replaced with the user-supplied name of the r-tree table.

CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)

The data for each node of the r-tree structure is stored in the %_node table. For each node that is not the root node of the r-tree, there is an entry in the %_parent table associating the node with its parent. And for each row of data in the table, there is an entry in the %_rowid table that maps from the entries rowid to the id of the node that it is stored on.

The root node of an r-tree always exists, even if the r-tree table is empty. The nodeno of the root node is always 1. All other nodes in the table must be the same size as the root node. The content of each node is formatted as follows:

1. If the node is the root node (node 1), then the first 2 bytes of the node contain the tree depth as a big-endian integer. For non-root nodes, the first 2 bytes are left unused.

2. The next 2 bytes contain the number of entries currently stored in the node.

3. The remainder of the node contains the node entries. Each entry consists of a single 8-byte integer followed by an even number of 4-byte coordinates. For leaf nodes the integer is the rowid of a record. For internal nodes it is the node number of a child page.

For searches, you would not need the _parent or _rowid tables.

The algorithm would look like this:

def search(nodeno = 1, root = True, tree_depth = -1, depth = 0):
    execute("SELECT data FROM X_node WHERE nodeno = ?", [nodeno])
    if root:
        tree_depth = first_two_bytes
    for entry in data:
        if entry.rectangle matches:
            if depth == tree_depth:
                result += entry.id
            else:
                search(entry.nodeno, False, tree_depth, depth + 1)