Optimized KD-tree for scalable search
US8645380B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 5, 2010 |
| Grant date | Feb 4, 2014 |
| Priority date | — |
| Expiry date | Oct 24, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/2264
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques for constructing an optimized kd-tree are described. In an implementation, an optimized kd-tree process receives input of a set of data points applicable for large-scale computer vision applications. The process divides the set of the data points into subsets of data points with nodes while generating hyperplanes (e.g., coordinate axes). The process identifies a partition axis for each node based on the coordinate axes combined in a binary way. The optimized kd-tree process creates an optimized kd-tree that organizes the data points based on the identified partition axis. The organization of the data points in the optimized kd-tree provides efficient indexing and searching for a nearest neighbor.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.