Science investigators need to quickly and effectively assess past observations of specific locations on a planetary surface. This innovation involves a location-based search technology that was adapted and applied to planetary science data to support a spatial query capability for mission operations software.

Conventional databases of planetary datasets are indexed and searchable by various metadata, such as acquisition time, phase of mission, and target. Searching these datasets will produce enormous datasets that are difficult, or impractical, to browse through to identify observations of very specific targets. For queries at specific locations, it is fundamentally more efficient to specify the location as the target of the query; and to have the database search based on the location of the data rather than metadata that is only indirectly or tangentially related to location.

High-performance location-based searching requires the use of spatial data structures for database organization. Spatial data structures are designed to organize datasets based on their coordinates in a way that is optimized for location-based retrieval. The particular spatial data structure that was adapted for planetary data search is the R+ tree. The R+ tree arranges data as a set of nodes that represents bounding rectangles. Every leaf node in the tree is a particular datum with coordinates. The root node represents a bounding box containing the entire set of data. Each level of the tree subdivides the search space into smaller and smaller bounding rectangles, each containing a smaller subset of the data. A query on the R+ tree for a set of coordinates will follow one unique path from the root to the leaf, and return the data contained in the coordinates. The complexity of the search is bounded by the depth of the tree, so the R+ tree insertion algorithm maintains a balanced tree such that the depth is minimized.

A map view provides an intuitive way to specify a set of coordinates for a location-based query. The software will let the user select any location on the map of the rover’s traverse path to date and return all of the results in under a second. This was particularly useful during tactical activity planning when the question of “what data do we have of this location” is asked every day. The wrong answer to this question is very expensive: false negatives result in missed science opportunities that may never come again, while false positives results in a waste of spacecraft time and bandwidth resources.

This work was done by Khawaja S. Shams, Thomas M. Crockett, Mark W. Powell, Joseph C. Joswig, and Jason M. Fox of Caltech for NASA’s Jet Propulsion Laboratory.

The software used in this innovation is available for commercial licensing. Please contact Daniel Broderick of the California Institute of Technology at This email address is being protected from spambots. You need JavaScript enabled to view it.. Refer to NPO-46637.

NASA Tech Briefs Magazine

This article first appeared in the April, 2011 issue of NASA Tech Briefs Magazine.

Read more articles from this issue here.

Read more articles from the archives here.