A new Google Patent application entitled Ranking and Clustering of Geo-Located Objects appears to describe a method in which geographical location objects of the type seen in Google Earth and Google Maps would be more efficiently classified in a database.
This is potentially very helpful for third-party licensors of Google mapping tools, and perhaps even for power mashers who work with these utilities.
From reading the Patent application Abstract and accompanying literature, the problem is more intense than you might think.
Unlike what I usually do with patents, I am going to skip over the Abstact's arcane (what in the heck is a "leaf node," anyway?- and go to the areas that are easier to understand.
The literature here notes:
GIS systems can provide particular challenges for proper database design. That is because GIS information does not fit nicely into a single data type that can be stored in one type of flat-file or relational database.
Rather, GIS systems often involve use a variety of data types, such as imagery, maps, and tables. GIS systems may also be very large, such as when they cover a large area and include expansive amounts of information about various points in an area, or cover a very large area like the entire world.
Addressing, topographical, or demographic data for various areas may be stored, and may be fairly large to store. In addition, GIS systems that provide graphical representations of data (such as on a map or a 3D representation of the globe) have even more challenges in organizing data, and storing massive amounts of data.
Graphical data, such as 3D structures to be placed on a geographic representation, such as on Google Maps or Google Earth, may be especially large and unwieldy.
When many different pieces of data are stored for a large area, and those pieces themselves are large, it can be a real challenge to organize, update, and search the data, and to present it quickly and accurately to users of a system.
This document describes systems and methods for storing and accessing geo-located content, such as 3D content to be displayed on a model of the earth. The content is stored in a multi-level hierarchical index having embedded therein information about descendants at each level of the index.
Such an arrangement of data may permit for quick retrieval of items even as the number of stored items increases to a large number. In addition, the index structure can generally be updated dynamically as objects are added, without the need for timely rebalancing of the index tree, as may be required with other indexing approaches.
The described systems and methods, in particular implementations, may provide for one or more of the following features and/or advantages. Users of a system may benefit by being able to quickly and conveniently locate objects associated with a very large geography such as the earth, and within a very large database of objects.
The system may permit, for example, bounding box queries in lat/lng space (generated by a graphical interface such as Google Earth or Google Maps), and may also prevent showing too many items, such as when a user is viewing a very large geography (such as an entire country).
The system may also permit for the ranking of items so as to show them in a preferred order.
So why is this important?
Geographic information providers may benefit by being able to more easily store information about geo-located objects, and may be able to readily search for and recall such objects for display with a related geographic area.
In addition, the system may permit for dynamic updates to the index without requiring a rebuild of the index, in certain implementations. Moreover, the data may be stored in a relatively compact form.