Method for storing map data in a database using space filling curves and a method of searching the database to find objects in a given area and to find objects nearest to a location
US6021406A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Nov 14, 1997 |
| Grant date | Feb 1, 2000 |
| Priority date | — |
| Expiry date | Nov 14, 2017 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99936
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method for storing map data in a database and a method of searching the database to find objects in a given area and to find objects nearest to a location. To generate the map data, a map plane is divided into a number of squares and the squares are numbered with spatial key numbers according to a space filling curve. Objects identifying places such as restaurants or hotels are placed in a main table of the database along with one of the spatial keys (object keys) intersecting an area of the map occupied by the object. A secondary table of the database is then created with one column including object keys corresponding to the main table, and other columns identifying ranges of spatial keys for objects identified by the object keys. To search the database to find objects in a given area, ranges of spatial keys are calculated for the given area and compared with ranges in the secondary table to identify object keys. The object keys identified are then used to obtain the desired objects from the main table.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.