US 2019/0102387 A1 · GEO-HASHING FOR PROXIMITY COMPUTATION IN A STREAM OF A DISTRIBUTED SYSTEM

Abstract

An event processing system for distributing a geospatial computation, and processing events in an event stream, is disclosed. The disclosed system and methods can apply a spatial function, such as distance, within Distance, and proximity, in parallel to a stream comprising event locations. The disclosed system improves over existing geospatial computations by providing an efficient parallel implementation that can handle a large number of moving objects in real time with little latency. A computing device receives an event stream comprising locations and can geohash the locations to obtain geohashes identifying geo grid cells containing the locations. The computing device can determine respective sets of neighboring geohashes identifying neighboring cells in the geo grid. The computing device then partitions the geospatial computation by mapping, based on the respective geo hash and the respective set of neighboring geo hashes, the events to processors.

Claims20

Dependent claims

A method for distributing a geospatial computation, comprising:

receiving, by a computing device, a plurality of events comprising location information;
hashing, by the computing device, the location information of the events to obtain geo hashes identifying cells in a geo grid, a respective identified cell containing respective location information of a respective event;
determining, for a respective geo hash that identifies the respective cell containing the respective location information, a respective set of neighboring geo hashes identifying neighboring cells in the geo grid;
partitioning the plurality of events by mapping, based on the respective geo hash and the respective set of neighboring geo hashes, the respective event to a respective processor of a plurality of distributed processors;
receiving, by the computing device, an output result from the respective processor identifying a respective partition result of the geospatial computation;
combining, by the computing device, the respective partition result with a second partition result to obtain a single result corresponding to the geospatial computation;
and
outputting the single result corresponding to the geospatial computation for a user.

5 more elements

A system, comprising:

a memory configured to store computer-executable instructions;
and
a processor configured to access the memory and execute the computer-executable instructions to perform a method for distributing a geospatial computation, the method comprising:
receiving a plurality of events comprising location information;
hashing the location information of the events to obtain geo hashes identifying cells in a geo grid, a respective identified cell containing respective location information of a respective event;
determining, for a respective geo hash that identifies the respective cell containing the respective location information, a respective set of neighboring geo hashes identifying neighboring cells in the geo grid;
partitioning the plurality of events by mapping, based on the respective geo hash and the respective set of neighboring geo hashes, the respective event to a respective processor of a plurality of distributed processors;
receiving an output result from the respective processor identifying a respective partition result of the geospatial computation;
combining the respective partition result with a second partition result to obtain a single result corresponding to the geospatial computation;
and
outputting the single result corresponding to the geospatial computation for a user.

8 more elements

A non-transitory computer-readable medium storing computer-executable code that, when executed by a processor, cause the processor to perform a method for distributing a geospatial computation, the method comprising:

receiving a plurality of events comprising location information;
hashing the location information of the events to obtain geo hashes identifying cells in a geo grid, a respective identified cell containing respective location information of a respective event;
determining, for a respective geo hash that identifies the respective cell containing the respective location information, a respective set of neighboring geo hashes identifying neighboring cells in the geo grid;
partitioning the plurality of events by mapping, based on the respective geo hash and the respective set of neighboring geo hashes, the respective event to a respective processor of a plurality of distributed processors;
receiving an output result from the respective processor identifying a respective partition result of the geospatial computation;
combining the respective partition result with a second partition result to obtain a single result corresponding to the geospatial computation;
and
outputting the single result corresponding to the geospatial computation for a user.

5 more elements

Dependencies are inferred from the claim text.

Geo-hashing for proximity computation in a stream of a distributed system

Life of this patent

Geo-hashing for proximity computation in a stream of a distributed system

Life of this patent

Abstract

Claims20