K-nearest neighbor search method, k-nearest neighbor search program, and k-nearest neighbor search device
US8090745B2 · kind B2 · utility
Assignees
Inventors
Key dates
| Filing date | Jan 30, 2009 |
| Grant date | Jan 3, 2012 |
| Priority date | — |
| Expiry date | Jul 24, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F18/24147
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Provided is a k-nearest neighbor search method of searching for a query number k of nearest points to an arbitrary point in a DBMS for creating a spatial index from multidimensional points, comprising setting a search conditions, judging which of a lowest branch and an intermediate branch of the spatial index a nearest region to the query point is, calculating, when the nearest region is judged to be the lowest branch, a distance between the query point and a child region of the nearest region, storing information of a divided region which has become a calculation target, calculating, when the nearest region is judged to be the intermediate region, a distance between the query point and a point included in the nearest region, storing information of the point which has become a calculation target, finishing search processing when the search conditions are satisfied, and obtaining a search result from the DBMS.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.