Spatial indexing
US8214371B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 18, 2003 |
| Grant date | Jul 3, 2012 |
| Priority date | — |
| Expiry date | Jul 28, 2032 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/29
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method, computer program, database system and data structure for indexing spatial objects are disclosed. Each spatial object has a location in an n-dimensional space. The indexing is for use in a partitioned parallel environment including P partitions. Each partition resides on one or more parallel processing systems. The n-dimensional space is divided into quad-tree cells (QTCs) in a quad-tree structure. Each spatial object is assigned to one or more QTCs based on the location of the spatial object in the n-dimensional space. A spatial object index entry is created which includes a designator for the QTC to which the spatial object is assigned and a pointer to the spatial object. The entries are sorted by their QTC numbers into a list. The list of entries is divided into P substantially equal parts. The entries associated with each part are stored in a different one of the P partitions.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.