Distributed in-memory spatial data store for k-nearest neighbour search
AssigneeGrabtaxi Holdings Pte. Ltd.
InventorsZhiyin ZHANG, Xiaocheng HUANG, Chaotang SUN, Shaolin ZHENG
Life of this patent
Estimating the term…
Abstract
A database system is configured to enable fast searching for neighbours nearest to a mobile object located in a geographical space made up of plural spatially distinct subspaces, each being made up of plural cells. The database system has an operating system controlling storage of object data amongst the plural storage nodes, to represent one or more spatially distinct subspaces, in a respective single one of the storage nodes. Location data of each object is used to index that object with respect to cells making up each spatially distinct subspace in each node.
Claims17
A database system configured to search plural mobile objects, each object having attributes including location data, to determine neighbouring objects nearest to a specific location, said object being located in a geographical space made up of plural spatially distinct subspaces, each being made up of plural cells, the database system comprising plural storage nodes;
- and an operating system, the operating system being configured to control storage of object data amongst the plural nodes, wherein the operating system is configured to cause storage of data representative of one or more spatially distinct subspaces in a respective single one of the storage nodes, and wherein location data of each object is used to index that object with respect to cells making up each spatially distinct subspace in each node.
A method of storing data representing plural mobile objects, each object having attributes including location data, to enable fast searching for neighbours nearest to a specific location in a geographical space made up of plural spatially distinct subspaces, each being made up of plural cells, the database system comprising plural storage nodes;
- the method comprising:
- storing object data amongst the plural storage nodes, such that data representative of one or more spatially distinct subspaces is stored in a respective single one of the storage nodes, and
- using current location data of each object to index that object with respect to cells making up each spatially distinct subspace in each storage node.
A method of accelerating a nearest-neighbour search comprising distributing data in plural storage nodes according to the geographical relationship between the data, such that data representative of one or more spatially distinct subspaces is stored in a respective single one of the storage nodes and indexing the data with respect to location within cells making up each spatially distinct subspace thereby allowing a search of data to be performed using a reduced number of remote calls.
Dependencies are inferred from the claim text.