Scaling out moving objects for geo-fence proximity determination

• US 10,349,210 B2
• Filed: 01/16/2019
• Issued: 07/09/2019
• Est. Priority Date: 09/30/2017
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Kumar, Santosh, Singh, Santosh Kumar, Singh, Prithviraj, Gupta, Rahul, Gatty, Yathish, Mulay, Kunal
• Primary Examiner(s): Khan, Suhail
• Application Number:
  US16/249,468
• Publication Number:
  US 20190149949A1
• Time in Patent Office: 174 Days
• Field of Search: None
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds

Abstract

An event processing system for distributing geospatial computations with geo-fences is disclosed. The system can partition and distribute geo-fences efficiently for parallel computation, and can track a potentially unlimited number of moving objects. A computing device determines a minimum bounding rectangle (MBR) covering a geographic area indexed by a geo-grid, and partitions the MBR and a set of geo-fences to a plurality of processing nodes. The computing device receives input events of a stream comprising locations within the geographic area. The device distributes the events to partitions on processing nodes, based at least on the events'"'"' locations. The device can determine a partition identifier corresponding to a respective location in constant time. The computing device then combines partition results to obtain a single geospatial computation result.

Claims

1. A method, comprising:

distributing, by a computing device, information that defines a plurality of geo fences among a plurality of processing nodes, the plurality of geo fences identifying bounding regions within a geographic area;

receiving input events of a stream, a respective input event of the input events comprising respective location information for a location within the geographic area;

transmitting the respective input event to a respective partition on a respective processing node of the plurality of processing nodes based at least in part on the respective location information;

receiving, from the respective processing node, an output result corresponding to a respective partition result;

combining, by the computing device, the output result with a second partition result to obtain a single result corresponding to a geospatial computation; and

preparing, for output, the single result corresponding to the geospatial computation for a user.

2. The method of claim 1, wherein distributing the information that defines the plurality of geo fences comprises:

obtaining one or more fence partition identifiers for a respective geo fence in the plurality of geo fences, the one or more fence partition identifiers based at least in part on a respective bounding region of the geographic area associated with the respective geo fence;

mapping the one or more fence partition identifiers to at least the respective processing node; and

transmitting respective information that defines the respective geo fence to at least the respective processing node.

3. The method of claim 2, wherein the one or more fence partition identifiers are obtained from a sparse partitioner.

4. The method of claim 3, wherein the sparse partitioner obtains the one or more fence partition identifiers from an RTree or another data structure.

5. The method of claim 2, wherein the respective processing node stores an index of an RTree or another data structure, the index corresponding to the respective geo fence.

6. The method of claim 2, wherein the one or more fence partition identifiers correspond to one or more grid cells of a geo grid corresponding to the geographic area, a respective grid cell of the one or more grid cells containing at least a part of the respective bounding region.

7. The method of claim 1, wherein distributing the information that defines the plurality of geo fences comprises replicating the information that defines the plurality of geo fences to the plurality of processing nodes.

8. The method of claim 1, further comprising:

adjusting a cell size for a plurality of grid cells in a geo grid, wherein the grid cells correspond to partitions used to distribute the respective input event to the respective processing node; and

updating a distribution of events across the processing nodes based on adjusted partitions associated with the adjusted cell size.

9. The method of claim 8, wherein the adjusted cell size is determined based on a cutoff distance for the geospatial computation.

10. The method of claim 8, wherein a number of the adjusted partitions exceeds a number of processing nodes of the plurality of processing nodes.

11. 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;

distributing information that defines a plurality of geo fences among a plurality of processing nodes, the plurality of geo fences identifying bounding regions within a geographic area;

receiving input events of a stream, a respective input event of the input events comprising respective location information for a location within the geographic area;

transmitting the respective input event to a respective partition on a respective processing node of the plurality of processing nodes based at least in part on the respective location information;

receiving, from the respective processing node, an output result corresponding to a respective partition result;

combining, by the computing device, the output result with a second partition result to obtain a single result corresponding to a geospatial computation; and

preparing, for output, the single result corresponding to the geospatial computation for a user.

12. The system of claim 11, wherein distributing the information that defines the plurality of geo fences comprises:

obtaining one or more fence partition identifiers for a respective geo fence in the plurality of geo fences, the one or more fence partition identifiers based at least in part on a respective bounding region of the geographic area associated with the respective geo fence;

mapping the one or more fence partition identifiers to at least the respective processing node; and

transmitting respective information that defines the respective geo fence to at least the respective processing node.

13. The system of claim 11, wherein distributing the information that defines the plurality of geo fences comprises replicating the information that defines the plurality of geo fences to the plurality of processing nodes.

14. The system of claim 11, further comprising:

adjusting a cell size for a plurality of grid cells in a geo grid, wherein the grid cells correspond to partitions used to distribute the respective input event to the respective processing node; and

updating a distribution of events across the processing nodes based on adjusted partitions associated with the adjusted cell size.

15. The system of claim 14, wherein the adjusted cell size is determined based on a cutoff distance for a geospatial computation.

16. The method of claim 14, wherein a number of the adjusted partitions exceeds a number of processing nodes of the plurality of processing nodes.

17. 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:

distributing information that defines a plurality of geo fences among a plurality of processing nodes, the plurality of geo fences identifying bounding regions within a geographic area;

receiving input events of a stream, a respective input event of the input events comprising respective location information for a location within the geographic area;

transmitting the respective input event to a respective partition on a respective processing node of the plurality of processing nodes based at least in part on the respective location information;

receiving, from the respective processing node, an output result corresponding to a respective partition result;

combining, by the computing device, the output result with a second partition result to obtain a single result corresponding to a geospatial computation; and

preparing, for output, the single result corresponding to the geospatial computation for a user.

18. The non-transitory computer-readable medium of claim 17, wherein distributing the information that defines the plurality of geo fences comprises:

obtaining one or more fence partition identifiers for a respective geo fence in the plurality of geo fences, the one or more fence partition identifiers based at least in part on a respective bounding region of the geographic area associated with the respective geo fence;

mapping the one or more fence partition identifiers to at least the respective processing node; and

transmitting respective information that defines the respective geo fence to at least the respective processing node.

19. The non-transitory computer-readable medium of claim 18, wherein the one or more fence partition identifiers are obtained from a sparse partitioner.

20. The non-transitory computer-readable medium of claim 18, wherein the one or more fence partition identifiers correspond to one or more grid cells of a geo grid corresponding to the geographic area, a respective grid cell of the one or more grid cells containing at least a part of the respective bounding region.