Although location-based software for mobile devices often centers on the purely commercial, such as finding the nearest pizza joint, a pair of entrepreneurs based in the United Kingdom and The Netherlands have delivered a more socially conscious application. Their Carbon Hero software is a personal carbon calculator that ties into smartphones built-in GPS technology, tracks a users travels and automatically calculates the resulting CO2 emissions to give an immediate understanding of personal environmental impact.

With the threat of global warming, "people are increasingly interested in their personal carbon use, and how they can reduce it," says Andreas Zachariah, CEO of Carbon Diem, the company that developed Carbon Hero.

Until now, getting such data meant logging the relevant details and entering them into an online carbon calculator. But "we are all typically way too busy for that," notes Zachariah.

That sparked the idea for Carbon Hero, which rides along in technology already carried by millions of people. The application now is in field testing on BlackBerry devices, but company co-founders Zachariah and Nick Burch, chief technology officer, have deployed it on Nokia phones and plan to add other platforms.

Database Structures

Carbon Hero works via savvy coding in Java ME, the embedded Java technology deployed in billions of mobile devices worldwide. Its innovation includes custom algorithms that detect transport mode, such as car vs. jet airplane.

In writing the code that enables Carbon Hero to manage copious amounts of GIS data, the developers had to fixate on a different type of footprint. A major development challenge was keeping Carbon Heros memory and storage consumption (its "footprint") from exceeding a BlackBerry or Nokia devices limited resources.

This is a common obstacle for mobile-mapping software. With on-device data storage of just a few megabytes and severely limited RAM, programmers must wring the maximum efficiency from the smallest amount of code. This typically requires efficiencies gained by developing applications in Java, C, C++ or other third-generation programming languages.

GIS data typically must be stored on a device, and managing such data efficiently is critical in minimizing the softwares burden on scarce RAM, storage and CPU resources. Storing, sorting and retrieving data are the job of database management systems (DBMSs), which arent as common in mobile applications as in enterprise and desktop software. Many developers in this environment still are cobbling together "homegrown" databases, often in the form of flat operating system files.

But DBMS products (commercial, open-source and dual-licensed) designed specifically for integration within mobile devices are becoming more common. One advantage is that these systems often include special data structures and other capabilities to enable efficient management of mapping data.

A critical tool for Carbon Hero turned out to be the R-Tree (sometimes called Guttmans R-Tree, for its originator), a database structure designed specifically for efficient management of spatial data. Support for R-Trees is included in Perst Lite, an embedded database system designed to operate in BlackBerry devices Java ME environment. Carbon Heros developers chose to embed Perst Lite in their application.

Whats a Tree Index?

In database system software, a tree index is a data structure that enables a query to "zero in" on specific records without searching in linear fashion through entire database tables. The most common tree index, by far, is the B-Tree, which is efficient in "plain vanilla" data queries such as exact match, prefix and range searches. But B-Tree indexes are single-dimensional and cant deal with the R2 or R3 coordinates required in spatial searches.

The R-Tree algorithm excels in this job by mapping objects in space using a "wrapping rectangle" or "bounding box." If an object is represented by point coordinates (X, Y), then its bounding box is a degenerated rectangle in which the width and height are one.

For all other geographical objects (e.g., lines, polygons, other shapes, etc.), the bounding box is such that the coordinates of the top-left corner are smaller than or equal to the coordinates of any point of the object, and the coordinates of the bottom-right corner are greater than or equal to the coordinates of any point of the object. In other words, a wrapping rectangle is the smallest rectangle that fully contains the specified object.

R-Tree indexes are commonly used to speed spatial searches (e.g., find the rectangle that bounds this point, find all rectangles that overlap this rectangle, etc.). All manner of shapes can be stored and searched with the bounding box.

If a point is represented as a rectangle with width and height = 1, for example, a line that has starting and ending coordinates of (15, 844) and (0, 3647) is stored as a rectangle with its upper-left corner at (15, 844) and its lower-right corner at (0, 3647).

To determine if the two lines intersect or if a point is within a given area (described by a circle, rectangle, etc.), an R-Tree search is performed to find all overlapping bounding boxes. For each match, a further test is conducted in the application code to determine whether the condition is actually met.

In Figure 1, a search to discover all lines that intersect with (75, 15) (20, 70) would return the rectangle bounding (35, 25) (20, 30), because the rectangles overlap. The application would extract additional information for the object (e.g., that its a line, its starting and ending coordinates, etc.) and would conclude that this line doesnt intersect and continue to the next overlapping rectangle returned by the index search.

Note that any shape with coordinates {(X1, Y1), (X2, Y2), ... (Xn, Yn)} can be stored and searched in this manner. For example, consider the polygon in Figure 2, where there are X coordinates of 35, 55, 65, 70, 85 as well as Y coordinates of 30, 33, 35, 45, 50, 63.

The bounding rectangle is the rectangle with left-top vertex (Xmax, Ymin), and right-bottom vertex (Xmin, Ymax) where Xmin = min(Xi), Ymin = min(Yi), Xmax = max(Xi), Ymax = max(Yi). In this case, Xmax = 85, Ymin = 30, Xmin = 35, Ymax = 63 and the rectangle top left and bottom right is (85, 30) and (35, 63).

R-Tree searches can return rectangles that exactly match given coordinates, overlap given coordinates or are wholly contained by given coordinates.

Methods and Capabilities