Techniques for K-Nearest Neighbour Queries
AssigneeOrdnance Survey Limited
InventorSheng Zhou
Life of this patent
Estimating the term…
Loading patent…
AssigneeOrdnance Survey Limited
InventorSheng Zhou
Estimating the term…
Methods and systems for performing K-nearest neighbour (K-NN) queries on a spatial dataset in a distributed or parallel computing system are described herein, where the spatial data comprises query data and object data. The spatial dataset is pre-processed, whereby the query space (i.e., the spatial extent of the query data) is partitioned according to a particular partition scheme. For each partition, an area (defined as the object range of the partition) is calculated based on the geometry of the partition and a set of K candidate objects allocated to that partition, with all objects within the object range defining the extent of any subsequent K-NN queries performed on that partition. When the query dataset is subsequently partitioned using the same partition scheme to perform a K-NN query, the pre-processed object range information can be used to retrieve the objects to be queried for each partition.
A computer-implemented method of performing K-nearest neighbour (K-NN) queries on a spatial dataset in a distributed or parallel computing system, the distributed or parallel computing system comprising a plurality of processing means, and the spatial dataset comprising a query dataset and an object dataset, wherein the method comprises:
A system for performing K-nearest neighbour (K-NN) queries on a spatial dataset, the spatial dataset comprising a query dataset and an object dataset, wherein the system comprises:
A computer-implemented method of pre-processing a spatial dataset for use in K-nearest neighbour (K-NN) queries to be performed in a distributed or parallel computing system, the spatial dataset comprising a query dataset and an object dataset, wherein the method comprises:
A system for pre-processing a spatial dataset for use in K-nearest neighbour (K-NN) queries to be performed in a distributed or parallel computing system, the spatial dataset comprising a query dataset and an object dataset, the system comprising:
Dependencies are inferred from the claim text.