K-nearest neighbour spatial queries on a spatial database
AssigneeOrdnance Survey Limited
InventorSheng Zhou
Life of this patent
Estimating the term…
Abstract
K-NN spatial queries may be performed, and the results of one K-NN query are re-used to perform a plurality of K-NN queries on a set of query points. More specifically, a K-NN query is performed on a pre-defined location, for example, an object point, to find the nearest K data objects for this pre-defined location, the results of this K-NN query being used to perform further K-NN queries on the query points near the pre-defined location. In doing so, the efficiency of large scale K-NN spatial queries is improved by limiting the spatial search range of the K-NN queries to be performed and re-using pre-computed K-NN data.
Claims20
A computer implemented method of performing K-nearest neighbor (K-NN) spatial queries on a spatial database, wherein K is an integer value, the method comprising:
- receiving instructions to perform a K-NN query on a spatial database stored in one or more computer readable media to find a set of K-NN data objects for a plurality of query locations;
- processing, by one or more processors of a data processing device, a plurality of pre-defined locations within the spatial database to calculate a plurality of object distances, wherein an object distance corresponds to a maximum distance between a pre-defined location and a set of K-NN data objects of said pre-defined location;
- identifying, by the one or more processors, a first pre-defined location and determining a candidate set of query locations therefrom;
- computing, by the one or more processors, a range of the K-NN query for the candidate set of query locations in dependence on the object distance calculated for the first pre-defined location, and a maximum distance between the first pre-defined location and one of the query locations within the candidate set;
- and
- determining, by the one or more processors, a set of K-NN data objects for each of the candidate set of query locations in dependence on the computed range.
A system comprising:
- a processor;
- and
- a computer readable medium storing one or more instruction(s) arranged such that, when executed by the processor, the system is configured to perform one or more K-nearest neighbour (K-NN) spatial queries on a spatial database, wherein K is an integer value, by:
- receiving instructions to perform a K-NN query on the spatial database to find a set of K-NN data objects for a plurality of query locations;
- processing a plurality of pre-defined locations within the spatial database to calculate a plurality of object distances, wherein an object distance corresponds to a maximum distance between a pre-defined location and a set of K-NN data objects of said pre-defined location;
- identifying a first pre-defined location and determining a candidate set of query locations therefrom;
- computing a range of the K-NN query for the candidate set of query locations in dependence on the object distance calculated for the first pre-defined location, and a maximum distance between the first pre-defined location and one of the query locations within the candidate set;
- and
- determining a set of K-NN data objects for each of the candidate set of query locations in dependence on the computed range.
Dependencies are inferred from the claim text.