Efficient proximity detection

• US 8,447,516 B1
• Filed: 08/31/2012
• Issued: 05/21/2013
• Est. Priority Date: 08/31/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wren, Christopher Richard, Koulomzin, Daniel George, Grabkovsky, Sergey
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US13/601,820
• Time in Patent Office: 263 Days
• Field of Search: 701/468, 701/300, 701/302, 701/466, 701/516, 701/301, 377/21, 705/413, 455/456.2, 455/456.3, 455/456.6
• US Class Current: 701/468
• CPC Class Codes: G01S 5/0295 Proximity-based methods, e.g. position inferred from reception of particular signals
• CPC Class Codes: H04W 64/006 with additional information processing, e.g. for direction or speed determination

Abstract

A server device may receive from a first computing device current location information associated with the first computing device. The server device may estimate a travel radius of a second computing device based at least in part on location information previously received from the second computing device, and may determine that the travel radius of the second computing device overlaps a proximity radius of the first computing device. The server device may query the second computing device for updated location information. The server device may receive the updated location information for the second computing device, and may determine that the second computing device is physically located substantially within the proximity radius of the first computing device based at least in part on the updated location information. In response, the server device may send to the first computing device an identification of the second computing device.

Claims

1. A method comprising:

receiving, by a server device from a first computing device, current location information associated with the first computing device;

estimating, by the server device, a travel radius of a second computing device based at least in part on location information previously received from the second computing device, wherein the travel radius includes a region of possible movement by the second computing device since the location information was previously received from the second computing device;

determining, by the server device, that the travel radius of the second computing device overlaps a proximity radius of the first computing device, wherein the proximity radius includes a region that extends outwards for a specified distance from a current location of the first computing device;

responsive to determining that the travel radius of the second computing device overlaps the proximity radius of the first computing device, querying, by the server device, the second computing device for updated location information;

receiving, by the server device, the updated location information for the second computing device;

determining, by the server device, that the second computing device is physically located substantially within the proximity radius of the first computing device based at least in part on the updated location information received for the second computing device; and

responsive to determining that the second computing device is physically located substantially within the proximity radius, sending, by the server device to the first computing device, an identification of the second computing device.

2. The method of claim 1, wherein estimating the travel radius of the second computing device further comprises:

estimating a speed of movement for the second computing device.

3. The method of claim 2, wherein estimating the travel radius of the second computing device is based at least in part on the estimated speed of movement for the second computing device and an elapsed time since the server device last received location information from the second computing device.

4. The method of claim 3, wherein estimating the travel radius of the second computing device further comprises:

multiplying the estimated speed of movement for the second computing device by the elapsed time since the server device last received location information from the second computing device.

5. The method of claim 2, wherein estimating the speed of movement for the second computing device is based at least in part on a location of the second computing device.

6. The method of claim 2, wherein estimating the speed of movement for the second computing device comprises:

estimating that the second computing device is stationary.

7. The method of claim 1, wherein:

the first computing device is associated with a first user;

the second computing device is associated with a second user; and

the travel radius of the second computing device is determined only if the first computing device determines that the second user is associated with the first user.

8. The method of claim 7, wherein the first computing device determines that the second user is associated with the first user if a contact list of the first computing device includes contact information associated with the second user.

9. The method of claim 7, wherein the first computing device determines the second user is associated with the first user if the first user is associated with the second user in a social network.

10. The method of claim 1, wherein the current location information and the updated location information comprises global positioning system (GPS) data.

11. The method of claim 1, wherein the current location information comprises wireless hotspots detected by the first computing device.

12. The method of claim 1, further comprising:

querying, by the server device, the second computing device for the updated location information.

13. The method of claim 1, further comprising:

responsive to determining that the second computing device is physically located substantially within the proximity radius, sending, by the server device to the second computing device, an identification of the first computing device.

14. The method of claim 1, wherein receiving, from the first computing device, the current location information associated with the first computing device further comprises:

receiving, by the server device from the first computing device, a request for an indication of computing devices that are proximate to the first computing device.

15. The method of claim 1, further comprising:

periodically receiving, by the server device from the second computing device, updated location information.

16. The method of claim 1, wherein periodically receiving comprises:

receiving the updated location information no more than once every hour.

17. The method of claim 1, wherein determining, by the server device, that the travel radius of the second computing device overlaps the proximity radius of the first computing device further comprises:

determining that the travel radius overlaps the proximity radius by more than a minimum threshold.

18. The method of claim 1, wherein determining, by the server device, that the travel radius of the second computing device overlaps the proximity radius of the first computing device further comprises:

determining that the travel radius overlaps the proximity radius by less than a maximum threshold.

19. A computer-readable medium comprising instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:

receiving, from a first computing device, current location information associated with the first computing device;

estimating a travel radius of a second computing device based at least in part on location information previously received from the second computing device, wherein the travel radius includes a region of possible movement by the second computing device since the location information was previously received from the second computing device;

determining that the travel radius of the second computing device does not overlap a proximity radius of the first computing device, wherein the proximity radius includes a region that extends outwards for a specified distance from a current location of the first computing device; and

determining not to query the second computing device for updated location information.

20. A server device comprising:

one or more processors; and

a proximity module operable by the one or more processors and configured to;

receive, from a first computing device, current location information associated with the first computing device;

estimate a travel radius of a second computing device based at least in part on location information previously received from the second computing device, wherein the travel radius includes a region of possible movement by the second computing device since the location information was previously received from the second computing device;

determine that the travel radius of the second computing device overlaps a proximity radius of the first computing device, wherein the proximity radius includes a region that extends outwards for a specified distance from a current location of the first computing device;

responsive to determining that the travel radius of the second computing device overlaps the proximity radius of the first computing device, query the second computing device for updated location information;

receive the updated location information for the second computing device; and

determine that the second computing device is not physically located substantially within the proximity radius of the first computing device based at least in part on the updated location information received for the second computing device.