System for nearest neighbor search of dataset
US12166503B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 16, 2022 |
| Grant date | Dec 10, 2024 |
| Priority date | — |
| Expiry date | Dec 8, 2042 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M13/13
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
Abstract
Low latency search for nearest neighbors in a dataset containing a large number of entries is improved using an error correction code (ECC) for partitioning data into clusters and retrieval. During initialization and preprocessing a d-dimensional space with clusters corresponding to ECC codewords is specified. Entries in the dataset are embedded into this space and associated with respective codewords, each codeword specifying a cluster. An index associates the codewords, clusters, and entries. During a query of the dataset, a query entry is processed to determine a query embedding in the d-dimensional space. The query embedding is used as input for a list decoder of the ECC. The list decoder provides a set of nearest codewords, with those codewords representing a set of candidate clusters that may contain nearest neighbors. The dataset entries associated with the candidate clusters may then be searched to determine query results comprising specific entries.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.