Nearest neighbor query processing in a linear quadtree spatial index
US6879980B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 29, 2001 |
| Grant date | Apr 12, 2005 |
| Priority date | — |
| Expiry date | Jan 6, 2023 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99945
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method for locating neighbor objects of a query object in a database. A query tile set is defined including a plurality of tiles that define an initial query radius that the query object is grouped within. Neighbor objects are located within the initial query radius. A number of neighbor objects within the initial query radius is determined. The query radius is expanded beyond the initial query radius by defining an expanded query tile set beyond the query tile set if the number of neighbor objects is less than a target number. Neighbor objects are located within the expanded query radius. It is determined whether a number of neighbor objects within the expanded radius corresponds to a target number. The query radius is expanded and neighbor objects located within the expanded radius until the number of neighbor objects equals or exceeds the target number.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.