Location monitoring using clusters of entities

• US 8,792,905 B1
• Filed: 03/28/2012
• Issued: 07/29/2014
• Est. Priority Date: 03/01/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Li, Guanfeng, Bao, Hongji, Chang, Edward Y.
• Primary Examiner(s): Ajayi, Joel
• Application Number:
  US13/433,138
• Time in Patent Office: 853 Days
• Field of Search: 455/414.2, 4554561-4563
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/0027 of actual mobile position, i.e. position determined on mobile
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 64/006 with additional information processing, e.g. for direction or speed determination

Abstract

Systems, methods, and machine-readable media for monitoring the locations of a number of entities are provided. The system may be configured to track the locations of a multitude of entities by grouping entities together into clusters of entities based on their geographic proximity and trajectories. A member of a cluster may be identified as a leader or a follower. The system may receive a number of location reports for the entities and update the locations of the entities based on whether the entity is a leader or a follower. For example, the system may update a back-end location database with the location information for a leader while location updates for followers may be converted into locations that are relative to the corresponding leader'"'"'s and cached at the system.

Claims

1. A computer-implemented method for monitoring locations for a plurality of entities that are grouped into a plurality of clusters, the method comprising:

receiving a location report for a first entity, the location report comprising location information for the first entity and an entity identifier for the first entity;

searching an affiliation table using the entity identifier to determine whether the first entity is a leader entity or a follower entity;

transmitting the location information in the location report for the first entity to a location database to be stored when the first entity is the leader entity; and

storing, in a local cache, displacement information for the first entity that is indicative of a location of the first entity relative to an associated leader entity when the first entity is the follower entity, the displacement information being determined based at least in part on the location information in the location report and leader location information for the associated leader entity.

2. The computer-implemented method of claim 1, wherein when the first entity is the follower entity, the method further comprises:

identifying the associated leader entity that is associated with the first entity;

determining the leader location information for the associated leader entity; and

calculating the displacement information for the first entity based on the leader location information for the associated leader entity and the location information in the location report for the first entity.

3. The computer-implemented method of claim 1, wherein when the first entity is the follower entity, the method further comprises:

receiving another location report for the first entity, the another location report comprising another location information for the first entity and the entity identifier for the first entity;

identifying the associated leader entity that is associated with the first entity;

retrieving the leader location information for the associated leader entity and the displacement information for the first entity;

calculating a predicted location for the first entity based on the leader location information for the associated leader entity and the displacement information for the first entity;

comparing the predicted location for the first entity and another location indicated by the another location information in the another location report for the first entity; and

when a distance between the predicted location for the first entity and the another location for the first entity exceeds a threshold distance, converting the first entity into another leader entity and transmitting the another location information in the location report for the first entity to the location database.

4. The computer-implemented method of claim 3, wherein when the distance between the predicted location for the first entity and the another location for the first entity does not exceed the threshold distance, the method further comprises:

discarding the another location report for the first entity.

5. The computer-implemented method of claim 3, wherein the displacement information for the first entity is calculated based on the leader location information for the associated leader entity and the location information in the location report for the first entity.

6. The computer-implemented method of claim 3, wherein retrieving the displacement information for the first entity comprises retrieving the displacement information from the local cache.

7. The computer-implemented method of claim 1, wherein the location database is a back-end location database accessible via a network.

8. The computer-implemented method of claim 1, wherein the location information in the location report comprises Global Positioning System (GPS) coordinates.

9. A system for monitoring locations for a plurality of entities that are grouped into a plurality of clusters, the system comprising:

one or more processors; and

a non-transitory machine-readable medium comprising instructions stored therein, which when executed by the one or more processors, cause the one or more processors to perform operations comprising;

receiving a location report for a first entity, the location report comprising location information for the first entity;

determining whether the first entity is a leader entity or a follower entity;

updating a location database using the location information from the location report for the first entity when the first entity is the leader entity; and

storing, in a local cache, displacement information for the first entity that is indicative of a location of the first entity relative to an associated leader entity when the first entity is the follower entity, the displacement information being determined based at least in part on the location information in the location report and leader location information for the associated leader entity.

10. The system of claim 9, wherein the location report for the first entity further comprises an entity identifier for the first entity, and wherein determining whether the first entity is the leader entity or the follower entity comprises searching an affiliation table using the entity identifier.

11. The system of claim 9, wherein when the first entity is the follower entity, the operations further comprise:

identifying the associated leader entity that is associated with the first entity;

determining the leader location information for the associated leader entity; and

calculating the displacement information for the first entity based on the leader location information for the associated leader entity and the location information from the location report for the first entity.

12. The system of claim 9, wherein when the first entity is the follower entity, the operations further comprise:

receiving another location report for the first entity, the another location report comprising another location information for the first entity;

identifying the associated leader entity that is associated with the first entity;

retrieving the leader location information for the associated leader entity and the displacement information for the first entity;

calculating a predicted location for the first entity based on the leader location information for the associated leader entity and the displacement information for the first entity;

comparing the predicted location for the first entity and the another location indicated by the another location information from the another location report for the first entity; and

when a distance between the predicted location for the first entity and the another location for the first entity exceeds a threshold distance, converting the first entity into another leader entity and transmitting the location information from the location report for the first entity to the location database.

13. The system of claim 12, wherein when the distance between the predicted location for the first entity and the another location for the first entity does not exceed the threshold distance, the operations further comprise:

discarding the another location report for the first entity.

14. The system of claim 12, wherein converting the first entity into the another leader entity comprises:

locating an entry for the first entity in an affiliation table; and

updating the affiliation table to indicate that the first entity is the another leader entity.

15. A non-transitory machine-readable medium comprising instructions stored therein, which when executed by a machine, cause the machine to perform operations comprising:

receiving a location report for a first entity, the location report comprising location information for the first entity and an entity identifier for the first entity;

searching an affiliation table using the entity identifier to determine whether the first entity is a leader entity or a follower entity;

transmitting, via a network, the location information in the location report for the first entity to a location database to be stored when the first entity is the leader entity; and

storing, in a local cache, displacement information for the first entity that is indicative of a location of the first entity relative to a first leader entity of a first cluster comprising the first entity when the first entity is the follower entity, wherein the displacement information is determined based at least in part on the location information in the location report and leader location information for the first leader entity.

16. The non-transitory machine-readable medium of claim 15, wherein when follower entity, the operations further comprise:

identifying the first leader entity of the first cluster comprising the first entity;

determining the leader location information for the first leader entity; and

calculating the displacement information for the first entity based on the leader location information for the first leader entity and the location information in the location report for the first entity.

17. The non-transitory machine-readable medium of claim 15, wherein the network is an intranet.

18. A computer-implemented method for forming a cluster of entities, the method comprising:

identifying, in a geographic region, a first leader entity associated with a first cluster comprising a first follower entity and a second leader entity associated with a second cluster comprising a second follower entity, wherein leader location information for the first and second leader entities is stored in a database and displacement information for the first and second follower entities is stored in a local cache;

determining a first trajectory for the first leader entity and a second trajectory for the second leader entity;

comparing the first trajectory with the second trajectory; and

when a difference between the first trajectory and the second trajectory is less than a threshold trajectory difference, combining the first cluster associated with the first leader entity and the second cluster associated with the second leader entity.

19. The computer-implemented method of claim 18, further comprising partitioning a geographic area into a number of geographic regions, wherein entities identified in a same geographic region are considered within a geographic proximity of one another.

20. The computer-implemented method of claim 18, wherein combining the first cluster associated with the first leader entity with the second cluster associated with the second leader entity comprises:

locating an entry for the first leader entity in an affiliation table; and

updating the entry for the first leader entity to indicate that the first leader entity is a third follower entity of the second leader entity.

21. The computer-implemented method of claim 20, wherein combining of the first cluster associated with the first leader entity with the second cluster associated with the second leader entity further comprises:

locating another entry for the first follower entity of the first leader entity in the affiliation table; and

updating the another entry for the first follower entity of the first leader entity to indicate that the follower entity of the first leader entity is a fourth follower entity of the second leader entity.

22. A system for forming a cluster of entities, the system comprising:

one or more processors; and

a non-transitory machine-readable medium comprising instructions stored therein, which when executed by the one or more processors, cause the one or more processors to perform operations comprising;

identifying a first leader entity associated with a first cluster comprising a first follower entity and a second leader entity associated with a second cluster comprising a second follower entity within a geographic proximity, wherein leader location information for the first and second leader entities is stored in a database and displacement information for the first and second follower entities is stored in a local cache;

determining a first trajectory for the first leader entity and a second trajectory for the second leader entity;

comparing the first trajectory with the second trajectory; and

when a difference between the first trajectory and the second trajectory is less than a threshold trajectory difference, merging the first cluster associated with the first leader entity and the second cluster associated with the second leader entity.

23. The system of claim 22, wherein the identifying of the first leader entity and the second leader entity within the geographic proximity comprises:

partitioning a geographic area into a number of geographic regions, wherein first leader entity and the second leader entity are located in a same geographic region.

24. The system of claim 22, wherein merging the first cluster associated with the first leader entity with the second cluster associated with the second leader entity comprises:

locating an entry for the first leader entity in an affiliation table; and

updating the entry for the first leader entity to indicate that the first leader entity is a third follower entity of the second leader entity.

25. The system of claim 22, wherein the first trajectory for the first leader entity and the second trajectory for the second leader entity are velocities.

26. A non-transitory machine-readable medium comprising instructions stored therein, which when executed by a machine, cause the machine to perform operations comprising:

identifying a plurality of leader entities in a region, each of the plurality of leader entities being associated with one of a plurality of clusters and one of a plurality of trajectories, and each of the plurality of clusters comprising at least one follower entity, wherein leader location information for the plurality of leader entities is stored in a database and displacement information for the at least one follower entity of each of the plurality of clusters is stored in a local cache that is distinct from the database;

comparing a first trajectory of a first leader entity of the plurality of leader entities with a second trajectory of a second leader entity of the plurality of leader entities; and

when a difference between the first trajectory and the second trajectory is less than a trajectory deviation value, merging a first cluster associated with the first leader entity with a second cluster associated with the second leader entity.

27. The non-transitory machine-readable medium of claim 26, wherein the operations further comprise:

calculating the first trajectory for the first leader entity based on a first location history for the first leader entity; and

calculating the second trajectory for the second leader entity based on a second location history for the second leader entity.

28. The non-transitory machine-readable medium of claim 26, wherein the operations further comprise:

partitioning a geographic area into a number of geographic regions, wherein entities identified in a same geographic region are considered within a geographic proximity of one another.