Method and computer system for detecting crowds in a location tracking system

• US 9,210,542 B2
• Filed: 12/09/2013
• Issued: 12/08/2015
• Est. Priority Date: 12/09/2013
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Europe Ltd
• Inventors: Longo, Salvatore, Jacobs, Tobias
• Primary Examiner(s): Beaulieu, Yonel
• Application Number:
  US14/100,098
• Publication Number:
  US 20150160035A1
• Time in Patent Office: 729 Days
• Field of Search: 701/400, 701/409, 701422-423, 701/533, 705/1.1, 705/7.11, 705/14.4, 342/450
• US Class Current: 1/1
• CPC Class Codes: G01S 5/02 using radio waves using satellite radio beacon systems for determining position G01S19/00
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A method and computer system for detecting crowds in a location tracking system utilizes a grid and the pigeonhole principle to minimize an amount of hardware, memory and/or processing capability required in the location tracking system. In particular, an amount of storage required to determine whether a location update has resulted in a crowd grows only linearly, rather than quadratically, with the number of objects being tracked because a number of active grid points will be, at most, four times the number of objects being tracked. By determining whether an individual active grid point is within a crowd area, the computational time required for detecting a crowd within this crowd area is independent from the total number of objects being tracked.

Claims

1. A method for detecting crowds in a location tracking system, the method comprising:

defining, using at least one computer system, a grid in two dimensions in a geographic coordinate system, the grid having a predetermined spacing in each dimension between grid points of the grid;

receiving a geographic location from each of a plurality of objects, the geographic location including coordinates in each of the two dimensions in the geographic coordinate system;

comparing the geographic locations to the grid points and defining as an active grid point each of a plurality of the grid points that are positioned within the predetermined spacing to at least one of the objects in each of the two dimensions;

storing each of the active grid points using at least one memory device of the at least one computer system;

receiving an updated geographic location from a first one of the objects; and

checking, by at least one processing unit of the at least one computer system and using the updated geographic location and the geographic locations of other ones of the objects, for an existence of a crowd by determining whether there are four or more times a predetermined threshold number of the objects that are located within the predetermined spacing in each of the two dimensions to a first one of the active grid points that is within the predetermined spacing in each of the two dimensions to the updated geographic location.

2. The method according to claim 1, further comprising:

outputting a result indicating the existence of the crowd where the determining results in a determination that there are four or more times the predetermined threshold number of the objects that are located within the predetermined spacing in each of the two dimensions to the first one of the active grid points;

or

determining the existence of the crowd using a sweep-line approach where the determining results in a determination that there are not four or more times the predetermined threshold number of the objects that are located within the predetermined spacing, an amount of storage required by a segment tree of the sweep-line approach being independent from a total number of the objects.

3. The method according to claim 2, further comprising sending a notification to an event consumer indicating the existence of the crowd.

4. The method according to claim 3, wherein the notification includes a geographic location of the crowd.

5. The method according to claim 3, wherein the event consumer is a user of a mobile device and the notification is a text or multimedia message including directions out of or away from the crowd.

6. The method according to claim 1, further comprising storing, for each respective one of the active grid points, a set of all of the objects within the predetermined spacing in each of the two-dimensions to the respective active grid point using the at least one memory device.

7. The method according to claim 1, wherein the at least one computer system includes at least one of a smartphone, tablet, laptop, server device, navigation system and personal computer.

8. The method according to claim 1, wherein the at least one computer system includes a cluster of server devices, each of the server devices storing a respective one of the active grid points and being assigned to perform the processing with respect to the respective one of the active grid points using a hash function.

9. The method according to claim 8, further comprising notifying respective ones of the server devices responsible for the active grid points that are within the predetermined spacing in each of the two dimensions to the updated location.

10. The method according to claim 1, wherein the geographic coordinate system is the Global Positioning System (GPS) and the objects are GPS-enabled devices configured to send the geographic locations automatically or in response to a request from the at least one computer system.

11. A computer-readable, tangible, non-transitory medium having instructions therein which cause one or more processing units of at least one computer system to collectively perform the following steps:

comparing geographic locations received from each of a plurality of objects to grid points of a grid defined in two dimensions in a geographic coordinate system, the grid having a predetermined spacing in each dimension between the grid points and the geographic locations including coordinates in each of the two dimensions in the geographic coordinate system, each of a plurality of the grid points that are positioned within the predetermined spacing to at least one of the objects in each of the two dimensions being defined as active grid points; and

checking, using an updated geographic location received from a first one of the objects and the geographic locations of other ones of the objects, for an existence of a crowd by determining whether there are four or more times a predetermined threshold number of the objects that are located within the predetermined spacing in each of the two dimensions to a first one of the active grid points that is within the predetermined spacing in each of the two dimensions to the updated geographic location.

12. The medium according to claim 11, further comprising instructions which cause the one or more processing units of the at least one computer system to collectively perform the following additional steps:

outputting a result indicating the existence of the crowd where the determining results in a determination that there are four or more times the predetermined threshold number of the objects that are located within the predetermined spacing in each of the two dimensions to the first one of the active grid points;

or

determining the existence of the crowd using a sweep-line approach where the determining results in a determination that there are not four or more times the predetermined threshold number of the objects that are located within the predetermined spacing, an amount of storage required by a segment tree of the sweep-line approach being independent from a total number of the objects.

13. The medium according to claim 12, further comprising instructions which cause the one or more processing units of the at least one computer system to collectively perform the farther step of sending a notification to an event consumer indicating the existence of the crowd.

14. The medium according to claim 11, wherein the medium is embodied in at least one of a smartphone, tablet, laptop, server device, navigation system and personal computer.

15. A computer system for detecting crowds in a location tracking system, the computer system comprising:

at least one memory device storing coordinates of geographic locations of a plurality of objects and grid points of a grid in two dimensions in a geographic coordinate system, the grid having a predetermined spacing in each dimension between the grid points; and

at least one processing unit configured to detect, based on an updated geographic location received from a first one of the plurality of objects, an existence of a crowd using an amount of storage of the at least one memory device that is independent from a total number of the objects;

wherein an amount of memory of the at least one memory device is linearly proportionate to the total number of objects being tracked in the location tracking system.

16. A computer system for detecting crowds in a location tracking system, the computer system comprising:

at least one memory device storing coordinates of geographic locations of a plurality of objects and grid points of a grid in two dimensions in a geographic coordinate system, the grid having a predetermined spacing in each dimension between the grid points; and

at least one processing unit configured to detect, based on an updated geographic location received from a first one of the plurality of objects, an existence of a crowd using an amount of storage of the at least one memory device that is independent from a total number of the objects;

wherein the at least one processing unit is configured to access the at least one memory device and compare the geographic locations with the grid points and define as an active grid point each of a plurality of the grid points that are positioned within the predetermined spacing to at least one of the objects in each of the two dimensions;

wherein the at least one processing unit is configured to determine whether there are four or more times a predetermined threshold number of the objects that are located within the predetermined spacing in each of the two dimensions to a first one of the active grid points that is within the predetermined spacing in each of the two dimensions to the updated geographic location.

17. The computer system according to claim 16, wherein the at least one processing unit is configured to:

outputting a result indicating the existence of the crowd where the determining results in a determination that there are four or more times the predetermined threshold number of the objects that are located within the predetermined spacing in each of the two dimensions to the first one of the active grid points;

or

determine the existence of the crowd using a sweep-line approach where the determining results in a determination that there are not four or more times the predetermined threshold number of the objects that are located within the predetermined spacing.

18. The computer system according to claim 16, further comprising a plurality of server devices which collectively include the at least one processing unit and the at least one memory device, each of the server devices having an active one of the grid points assigned to it by a hash function and being configured to detect the existence of the crowd for the active one of the grid points.