Methods, systems, and media for determining location information from real-time bid requests

• US 9,179,264 B1
• Filed: 04/20/2015
• Issued: 11/03/2015
• Est. Priority Date: 04/16/2012
• Status: Active Grant

• Current Assignee: Dstillery, Inc.
• Original Assignee: Dstillery, Inc.
• Inventors: Provost, Foster J., Eliassi-Rad, Tina, Moores, Lauren S.
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Application Number:
  US14/691,442
• Time in Patent Office: 197 Days
• Field of Search: 705/14.64, 705/14.67, 705/26.1, 705/14.49, 455/456.1, 455/404.2, 455456-457, 455/517, 455/456.3, 709/206
• US Class Current: 1/1
• 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
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 8/02 Processing of mobility data, e.g. registration information at HLR [Home Location Register] or VLR [Visitor Location Register]; Transfer of mobility data, e.g. between HLR, VLR or external networks

Abstract

Methods, systems, and media for determining location information from real-time bid requests are provided. In some implementations, a method for determining device locations is provided, the method comprising: receiving a real-time data stream that includes location proxies corresponding to devices; generating a movement graph of interconnected nodes and edges, wherein each node represents one of the location proxies and wherein each edge represents movement information between the location proxies; calculating, for a node in the movement graph, location information by applying a predictive model having weights based on the movement information; and assigning, for the node in the movement graph, a census-based identifier to the calculated location information. The census-based identifier can be used, for example, to supplement or enrich bid requests within the real-time data stream.

Claims

1. A method, comprising:

receiving a plurality of signals, each signal from the plurality of signals including a location proxy from a plurality of location proxies for a user;

generating, at a server, a movement graph having a plurality of nodes and a plurality of edges, each edge from the plurality of edges interconnecting two nodes from the plurality of nodes, each node representing a location proxy from the plurality of location proxies;

calculating a predicted location for a first node from the plurality of nodes, the predicted location being based, at least in part, on the location proxy for the first node and a location proxy for a second node from the plurality of nodes, the predicted location being associated with a location different from a location associated with the location proxy for the first node;

receiving a signal associated with a request for a location-based service including the location proxy associated with the first node; and

sending a signal associated with the predicted location to a location-based service provider such that the location-based service provider provides the location-based service based on the predicted location.

2. The method of claim 1, wherein the location proxy is a hashed public IP address.

3. The method of claim 1, wherein each edge from the plurality of edges represents at least one of (1) a number of movements between two nodes or (2) an inter-arrival time between two nodes.

4. The method of claim 1, wherein the first node is associated with a mobile IP address and the second node is associated with a non-mobile IP address.

5. The method of claim 1, wherein the first node is associated with a mobile IP address, the second node is associated with a non-mobile IP address, and an edge from the plurality of edges interconnecting the first node and the second node is associated with an inter-arrival time between the first node and the second node, the method further comprising:

calculating a distance between the mobile IP address and the non-mobile IP address based, at least in part, on the inter-arrival time, the predicted location is calculated based, at least in part, on the distance between the mobile IP address and the non-mobile IP address.

6. The method of claim 1, wherein the predicted location for the first node is calculated based, at least in part, on (1) a first edge from the plurality of edges, the first edge disposed between the first node and the second node, (2) a location proxy for a third node from the plurality of nodes, and (3) a second edge from the plurality of edges, the second edge interconnecting the third node to at least one of the first node or the second node.

7. A non-transitory processor readable medium storing code representing instructions to be executed by a processor, the code comprising code to cause the processor to:

receive, at a first time, a first signal including a first location proxy for a user;

define a first node in a movement graph associated with the first location proxy;

receive, at a second time after the first time, a second signal, the second signal including a second location proxy for the user;

define a second node in the movement graph associated with the second location proxy;

define an edge of the movement graph between the first node and the second node, the edge representing a difference between the first time and the second time;

calculate a predicted location for the second node based, at least in part, on the first node and the edge; and

send a signal associated with the predicted location to a location-based service provider such that the location-based service provider provides a location-based service based on the predicted location.

8. The non-transitory processor readable medium of claim 7, wherein calculating the predicted location includes applying weighted-vote relational neighbor classifier to the movement graph.

9. The non-transitory processor readable medium of claim 7, wherein:

the predicted location includes location information; and

the first signal is devoid of location information such that the first node is devoid of location information and such that the predicted location, including location information, is calculated based, at least in part, on the first node devoid of location information.

10. The non-transitory processor readable medium of claim 7, the code further comprising code to cause the processor to:

receive, at a third time after the first time, a third signal including a third location proxy for the user; and

determine not to define a third node in the movement graph associated with the third location proxy based on a difference in time between the third time and the first time being below a threshold.

11. The non-transitory processor readable medium of claim 7, the code further comprising code to cause the processor to:

receive, at a third time after the second time, a third signal including the first location proxy for the user;

receive, at a fourth time after the third time, a fourth signal including the second location proxy for the user; and

update the edge between the first node and the second node based on a difference between the third time and the fourth time.

12. The non-transitory processor readable medium of claim 7, wherein:

the first signal includes a unique user identifier associated with the user;

the code to cause the processor to define the first node includes code to cause the processor to associate the first node with the user based on the unique user identifier;

the second signal includes the unique user identifier;

the code to cause the processor to define the second node includes code to cause the processor to associate the second node with the user based on the unique identifier; and

the code to cause the processor to define the edge includes code to cause the processor to define the edge associated with a movement of the user based on the first node and the second node each being associated with the user.

13. The non-transitory processor readable medium of claim 7, wherein:

the second signal is received after the first signal and without any other signals including a location proxy for the user received between the first signal and the second signal, and

the code to cause the processor to define an edge of the movement graph between the first node and the second node includes code to cause the processor to define the edge between the first node and the second node based, at least in part, on the second signal being received after the first signal and without any other signals including a location proxy for the user being received between the first signal and the second signal.

14. The non-transitory processor readable medium of claim 7, wherein

the predicted location associated with the second node is associated with location information, and

the location information associated with the predicted location differs from location information calculated based solely on the second location proxy.

15. The non-transitory processor readable medium of claim 7, the code further comprising code to cause the processor to:

receive, at a third time after the first time and before the second time, a third signal including a third location proxy for the user; and

determine that a distance between the third location proxy and the first location proxy is less than a predefined radius.

16. The non-transitory processor readable medium of claim 15, wherein the edge of the movement graph represents a movement of the user between a location associated with the first node and a location associated with the second node based, in part, on the distance between the third location proxy and the first location proxy being less than the predefined radius.

17. The non-transitory processor readable medium of claim 15, further comprising code to cause the processor to associate the third signal with the first node based on the distance between the third location proxy and the first location proxy being less than the predefined radius.

18. A non-transitory processor readable medium storing code representing instructions to be executed by the processor, the code comprising code to cause the processor to:

receive a request for a location-based service including a location proxy;

identify a first node from a plurality of nodes of a movement graph associated with the location proxy;

calculate a predicted location associated with the first node based, at least in part, on a location associated with a second node from the movement graph and movement data associated with an edge of the movement graph disposed between the first node and the second node; and

send a signal associated with the predicted location to a location-based service provider such that the location-based service provider provides the location-based service based on the predicted location.

19. The non-transitory processor readable medium of claim 18, wherein the location proxy is a first location proxy received at a first time and the edge is a first edge, the code further comprising code to cause the processor to:

receive a signal including a second location proxy at a second time after the first time;

identify a third node from the plurality of nodes based on the third node being associated with the second location proxy;

define a second edge between the first node and the third node associated with a movement between the first node and the third node;

receive a request for the location-based service including the second location proxy; and

calculate a predicted location associated with the third based, at least in part, on the first location proxy and the second edge; and

send a signal associated with the predicted location associated with the second node to the location-based service provider.

20. The non-transitory processor readable medium of claim 18, wherein the location proxy is a first location proxy received at a first time and the edge is a first edge, the code further comprising code to cause the processor to:

receive a signal including a second location proxy at a second time after the first time;

define a third node associated with the second location proxy;

define a second edge between the first node and the third node, the second edge associated with a movement between the first node and the second node;

receive a request for the location-based service including the second location proxy; and

calculate a predicted location for the third node based, at least in part, on the first location proxy and the second edge; and

send a signal associated with the predicted location for the third node to the location-based service provider.

21. The non-transitory processor readable medium of claim 18, wherein:

the request for the location-based service includes a user identifier; and

the movement graph is associated with a user associated with the user identifier, the code to cause the processor to identify a first node includes code to cause the processor to identify the first node of the movement graph based, in part, on the user identifier.