# US 2026/0037527 A1 · Techniques for K-Nearest Neighbour Queries

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2026/0037527 A1
- Document ID: US20260037527A1
- Status: Published application
- Kind: A1
- Application number: 19/284,850
- Filed: 2025-07-30
- Published: 2026-02-05
- Earliest claimed: 2024-07-30
- Assignees: Ordnance Survey Limited
- Applicants: Ordnance Survey Limited
- Inventors: Sheng Zhou
- Web page: https://patentgrep.com/patent/US20260037527A1

## CPC

- G06F 16/2462: {Approximate or statistical queries}
- G06F 16/2471: {Distributed queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

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.

## Claims

### Claim 1

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:
receiving instructions to perform a K-NN query on the spatial dataset to find a set of k-NN objects for a plurality of query locations of the query dataset, wherein k is an integer value greater than or equal to one;
generating a plurality of partitions of the query dataset according to a first partition scheme;
determining, for each partition, a set of objects to be queried from the object dataset based on pre-processed object range information associated with the partition, wherein the pre-processed object range information is determined using the first partition scheme and K a predetermined number of candidate objects allocated to each partition, wherein K is an integer value greater than or equal to the integer value of k;
distributing the plurality of partitions and the respective sets of objects to be queried between the plurality of processing means to perform the K-NN query, wherein each processing means processes one or more partitions to determine a set of k-NN objects associated with each query location of a partition;
receiving one or more sets of k-NN objects from each processing means; and
collating the one or more sets of k-NN objects from each processing means for output.

### Claim 2 (depends on 1)

The computer-implemented method according to claim 1, wherein the plurality of partitions are generated such that each partition comprises at least one query location; and,
wherein generating the plurality of partitions comprises receiving pre-processed partition data for the query dataset, wherein the pre-processed partition data comprises the plurality of partitions.

### Claim 3 (depends on 1)

A computer-implemented method according to claim 1, wherein the pre-processed object range information comprises the set of objects to be queried for each partition.

### Claim 4 (depends on 1)

The computer-implemented method according to claim 1, wherein the pre-processed object range information comprises an object range for each partition, the object range comprising one or more areas of the spatial dataset, each area being enclosed by a circle having a radius calculated based on the maximum distance between a vertex of a boundary of the partition and K candidate objects allocated to the partition.

### Claim 5 (depends on 4)

The computer-implemented method according to claim 4, wherein the method further comprises pre-processing the spatial dataset to determine the object range of each partition, wherein the pre-processing comprising:
identifying each vertex of the boundaries of the partition;
allocating K candidate objects to the partition;
calculating, for each vertex of the partition boundary, an area being enclosed by a circle having a radius calculated based on the maximum distance between the vertex and the K candidate objects; and
determining the object range of the partition based on a union of the area calculated for each vertex of the partition boundary.

### Claim 6 (depends on 4)

The computer-implemented method according to claim 4, wherein determining the set of objects to be queried for each partition comprises identifying the objects within the area calculated for each vertex of the partition boundary.

### Claim 7 (depends on 1)

The computer-implemented method according to claim 1, wherein collating the one or more sets of k-NN objects comprises:
identifying a query location processed within two or more partitions, such that two or more sets of k-NN objects are received;
removing any duplicate k-NN objects contained within the two or more sets of K-NN objects; and
ranking the remaining k-NN objects in dependence on a distance from the query location and each k-NN object to thereby provide a final set of K-NN objects for the query location.

### Claim 8 (depends on 1)

The computer-implemented method according to claim 1, wherein the first partition scheme comprises one of: a grid system, a quadtree or a Voronoi diagram.

### Claim 9 (depends on 1)

The computer-implemented method according to claim 1, wherein the spatial dataset comprises geospatial data representative of a geographical region.

### Claim 10 (depends on 1)

The computer-implemented method according to claim 1, wherein the query dataset and object dataset each comprise one or more of: one or more data points, one or more line segments, and/or one or more polygons.

### Claim 11

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 processor; and
a computer readable medium storing one or more instruction(s) arranged such that when executed the processor is caused to:
receive instructions to perform a K-NN query on the spatial dataset to find a set of k-NN objects for a plurality of query locations of the query dataset, wherein k is an integer value greater than or equal to one;
generate a plurality of partitions of the query dataset according to a first partition scheme;
determine, for each partition, a set of objects to be queried from the object dataset based on pre-processed object range information associated with the partition, wherein the pre-processed object range information is determined using the first partition scheme and K a predetermined number of candidate objects allocated to each partition, wherein K is an integer value greater than or equal to the integer value of k;
distribute the plurality of partitions and the respective sets of objects to be queried between a plurality of processing means of a distributed or parallel computing system to perform the K-NN query, wherein each processing means processes one or more partitions to determine a set of k-NN objects associated with each query location of a partition;
receive one or more sets of k-NN objects from each processing means; and
collate the one or more sets of k-NN objects from each processing means for output.

### Claim 12 (depends on 11)

The system according to claim 11, wherein the system further comprises only one of:
a distributed computer system comprising a plurality of computing nodes, wherein the plurality of partitions are distributed between the plurality of computing nodes, or
a parallel computing system comprising a plurality of processors, wherein the plurality of partitions are distributed between the plurality of processors.

### Claim 13

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:
generating a plurality of partitions of the query dataset according to a first partition scheme;
allocating, to each partition, K candidate objects from the object dataset, wherein K is an integer value greater than or equal to one;
determining an object range for each partition, the object range of each partition comprising one or more areas of the spatial dataset, each area being enclosed by a circle having a radius calculated based on a maximum distance between a vertex of a boundary of the partition and the K candidate objects; and
storing object range information for use in K-NN queries of the spatial dataset, the object range information at least comprising the object range determined for each partition.

### Claim 14 (depends on 13)

The computer-implemented method according to claim 13, wherein determining the object range for each partition further comprises:
identifying each vertex of the boundaries of the partition;
calculating, for each vertex of the partition boundary, an area being enclosed by a circle having a radius calculated based on the maximum distance between the vertex and the K candidate objects; and
determining the object range of the partition based on a union of the area calculated for each vertex of the partition boundary.

### Claim 15 (depends on 13)

The computer-implemented method according to claim 13, wherein the allocating K candidate objects comprises allocating a predetermined number of candidate objects to each partition based on containment within the partition and/or adjacency to the partition.

### Claim 16 (depends on 13)

The computer-implemented method according to claim 13, wherein storing object range information further comprises storing the plurality of partitions as partition data; and optionally,
wherein storing object range information further comprises storing object data for use in K-NN queries, the object data comprising one or more objects contained within the area of the spatial dataset defined by the object range of each partition.

### Claim 17 (depends on 13)

The computer-implemented method according to claim 13, wherein the method further comprises determining a plurality of object ranges for each partition based on two or more sets of K candidate objects for each partition, each set of K candidate objects comprising a different number of objects.

### Claim 18 (depends on 13)

The computer-implemented method according to claim 13, wherein the first partition scheme comprises one of: a grid system, a quadtree or a Voronoi diagram.

### Claim 19 (depends on 13)

The computer-implemented method according to claim 13, wherein the spatial dataset comprises geospatial data representative of a geographical region; and optionally
wherein the object dataset comprises one or more of: data points, line segments and polygons.

### Claim 20

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:
a processor; and
a computer readable medium storing one or more instruction(s) arranged such that when executed the processor is caused to:
generate a plurality of partitions of the query dataset according to a first partition scheme;
allocate, to each partition, K candidate objects from the object dataset, wherein K is an integer value greater than or equal to one;
determine an object range for each partition, the object range of each partition comprising one or more areas of the spatial dataset, each area being enclosed by a circle having a radius calculated based on a maximum distance between a vertex of a boundary of the partition and the K candidate objects; and
store object range information for use in K-NN queries of the spatial dataset, the object range information at least comprising the object range determined for each partition.
