Refining location detection from a query stream
View Patent ↗Methods, systems, and apparatus, including computer programs encoded on computer storage media, for determining geographic locations of devices. One of the methods includes obtaining an estimated user location associated with each respective IP address block based on observed events from the IP address block; obtaining an estimate of a probability model p(ev|loc), the probability model p(ev|loc) including a respective probability distribution of interest locations for each of multiple user locations; wherein obtaining the estimate of the probability model p(ev|loc) includes calculating p(ev|loc) from a p(zone|loc) matrix and a p(ev|zone) matrix; and using the estimate for the probability model p(ev|loc) and the observed events to calculate an estimate for multiple probability distributions X(loc) associated with a respective IP address block.
1. A computer-implemented method, comprising:
obtaining an estimated user location of user devices associated with each respective internet protocol (IP) address block of a plurality of IP address blocks based on observed event queries from users associated with particular IP addresses of the IP address block;
obtaining an estimate of a probability model p(ev|loc) using the obtained estimated user locations, the probability model p(ev|loc) including a respective probability distribution of interest locations for each of a plurality of user locations, each value p(ev i |loc j ) of the probability model p(ev|loc) representing a respective probability that event queries issued from a particular user location loc j contain a particular interest location ev i ; wherein obtaining the estimate of the probability model p(ev|loc) includes calculating p(ev|loc) from a p(zone|loc) matrix and a p(ev|zone) matrix;
using the estimate for the probability model p(ev|loc) and the observed event queries to calculate an estimate for a plurality of probability distributions X(loc), each probability distribution X(loc) being associated with a respective IP address block and indicating a likelihood that event queries obtained from IP addresses of the respective IP address block were issued from user locations (loc); and
using the probability distribution X(loc) to estimate geographic locations for particular user devices.
2. The method of claim 1 , wherein calculating the p(zone|loc) matrix comprises:
establishing a specified number of zones, wherein each zone specifies a distance interval associating event queries and user locations; and
for each user location, determining a count of the event queries whose interest locations are within each zone of the user location.
3. The method of claim 1 , wherein calculating the p(ev|zone) matrix comprises:
for each interest location, identifying a respective set of user locations that is within each zone of the interest location;
determining a count of the event queries that were issued from the respective set of user locations in the zone; and
determining a count of the event queries that were issued from the respective set of user locations in the zone and there were for the interest location.
4. The method of claim 1 , wherein calculating p(ev|loc) includes calculating the matrix product of p(ev|zone)×p(zone|loc).
5. The method of claim 1 , comprising normalizing p(ev|loc) to generate a smoothed probability model.
6. The method of claim 1 , wherein the smoothed probability is refined by adding a multiplier such that the probability model is based on p(ev|zone), p (zone|loc), and multiplier f(dist).
7. The method of claim 6 , wherein the multiplier is a multiplier matrix.
8. The method of claim 1 , where using the estimate for the probability model p(ev|loc) and the observed events to calculate an estimate for a plurality of probability distributions X(loc) comprises:
calculating the estimate for the probability distribution X(loc) using an iterative Expectation Maximization (EM) process until a current estimate of the probability distribution X(loc) converges according to a second predetermined threshold, the EM process comprising:
computing a probability model q(loc|ev) based on the current estimate of the probability distribution X(loc) according to a first equation
q
(
loc
/
ev
)
=
p
(
ev
/
loc
)
·
X
(
loc
)
∑
loc
′
p
(
ev
/
loc
′
)
·
X
(
loc
′
)
;
and
updating the current estimate of the probability distribution X(loc) according to a second equation
x
(
loc
)
∝
∑
i
=
1
N
q
(
loc
/
ev
i
)
,
where ev 1 , ev 2 , . . . ev N , represents observed interest locations.
9. A system comprising:
one or more computers configured to perform operations comprising:
obtaining an estimated user location of user devices associated with each respective internet protocol (IP) address block of a plurality of IP address blocks based on observed event queries from users associated with particular IP addresses of the IP address block;
obtaining an estimate of a probability model p(ev|loc) using the obtained estimated user locations, the probability model p(ev|loc) including a respective probability distribution of interest locations for each of a plurality of user locations, each value p(ev i |loc j ) of the probability model p(ev|loc) representing a respective probability that event queries issued from a particular user location loc j contain a particular interest location ev i ; wherein obtaining the estimate of the probability model p(ev|loc) includes calculating p(ev|loc) from a p(zone|loc) matrix and a p(ev|zone) matrix;
using the estimate for the probability model p(ev|loc) and the observed event queries to calculate an estimate for a plurality of probability distributions X(loc), each probability distribution X(loc) being associated with a respective IP address block and indicating a likelihood that event queries obtained from IP addresses of the respective IP address block were issued from user locations (loc); and
using the probability distribution X(loc) to estimate geographic locations for particular user devices.
10. The system of claim 9 , wherein calculating the p(zone|loc) matrix comprises:
establishing a specified number of zones, wherein each zone specifies a distance interval associating event queries and user locations; and
for each user location, determining a count of the event queries whose interest locations are within each zone of the user location.
11. The system of claim 9 , wherein calculating the p(ev|zone) matrix comprises:
for each interest location, identifying a respective set of user locations that is within each zone of the interest location;
determining a count of the event queries that were issued from the respective set of user locations in the zone; and
determining a count of the event queries that were issued from the respective set of user locations in the zone and there were for the interest location.
12. The system of claim 9 , wherein calculating p(ev|loc) includes calculating the matrix product of p(ev|zone)×p(zone|loc).
13. The system of claim 9 , comprising normalizing p(ev|loc) to generate a smoothed probability model.
14. The system of claim 9 , wherein the smoothed probability is refined by adding a multiplier such that the probability model is based on p(ev|zone), p (zone|loc), and multiplier f(dist).
15. The system of claim 14 , wherein the multiplier is a multiplier matrix.
16. The system of claim 9 , where using the estimate for the probability model p(ev|loc) and the observed events to calculate an estimate for a plurality of probability distributions X(loc) comprises:
calculating the estimate for the probability distribution X(loc) using an iterative Expectation Maximization (EM) process until a current estimate of the probability distribution X(loc) converges according to a second predetermined threshold, the EM process comprising:
computing a probability model q(loc|ev) based on the current estimate of the probability distribution X(loc) according to a first equation
q
(
loc
/
ev
)
=
p
(
ev
/
loc
)
·
X
(
loc
)
∑
loc
′
p
(
ev
/
loc
′
)
·
X
(
loc
′
)
;
and
updating the current estimate of the probability distribution X(loc) according to a second equation
x
(
loc
)
∝
∑
i
=
1
N
q
(
loc
/
ev
i
)
,
where ev 1 , ev 2 , . . . ev N , represents observed interest locations.
17. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
obtaining an estimated user location of user devices associated with each respective internet protocol (IP) address block of a plurality of IP address blocks based on observed event queries from users associated with particular IP addresses of the IP address block;
obtaining an estimate of a probability model p(ev|loc) using the obtained estimated user locations, the probability model p(ev|loc) including a respective probability distribution of interest locations for each of a plurality of user locations, each value p(ev i |loc j ) of the probability model p(ev|loc) representing a respective probability that event queries issued from a particular user location loc j contain a particular interest location ev i ; wherein obtaining the estimate of the probability model p(ev|loc) includes calculating p(ev|loc) from a p(zone|loc) matrix and a p(ev|zone) matrix;
using the estimate for the probability model p(ev|loc) and the observed event queries to calculate an estimate for a plurality of probability distributions X(loc), each probability distribution X(loc) being associated with a respective IP address block and indicating a likelihood that event queries obtained from IP addresses of the respective IP address block were issued from user locations (loc); and
using the probability distribution X(loc) to estimate geographic locations for particular user devices.