Granted Patent B2

US 9,730,028 · App. 15/337,939 · Granted Aug 8, 2017

Inventors: Elena Rose (Los Altos Hills, CA); Mark Christopher Dixon (Belmont, CA); Kevin Toshio Ching (Berkeley, CA); Veronica Milenkiy (Burlingame, CA)

Assignee: NinthDecimal, Inc.

H04W4/028G01S5/0252G06F17/30241G06F17/30675H04W64/00

Abstract

Claims (71)

1. A computing device, comprising:

at least one microprocessor; and

memory storing instructions configured to instruct the at least one microprocessor to:

store location data of a mobile device, the location data specifying, for each respective time instance of a plurality of time instances in a period of time, a respective location of the mobile device determined by a position determination unit of the mobile device; and

identify a location of a home of a user of the mobile device, by:

identifying, for the respective location of the mobile device at the respective time instance, a respective region that has a predefined boundary and contains the respective location, wherein locations specified in the location data are contained within a plurality of regions containing the locations;

determining, for the respective location of the mobile device at the respective time instance, a visitation type, wherein the locations specified in the location data have a plurality of different visitation types;

identifying, from the plurality of regions visited by the respective mobile device, a plurality of region candidates for the home of the user of the mobile device;

computing, for each of the region candidates, a plurality of visitation frequencies corresponding to the plurality of different visitation types respectively;

computing, for each of the region candidates, a score based at least in part on the plurality of visitation frequencies, wherein the plurality of region candidates have a plurality of scores respectively; and

selecting, from the plurality of region candidates based on the plurality of scores, a home region as the home of the user.

2. The computing device of claim 1 , wherein the identifying of the respective region that contains the respective location includes:

storing a set of cell identifiers of a hierarchical grid system having grid lines aligned with numbers of digits of precision in longitudinal and latitudinal coordinates on the earth, including store each respective cell identifier of the set of cell identifiers in association with a set of region identifiers identifying one or more regions that are at least partially in a cell identified by the respective cell identifier;

converting to a cell identifier the respective location of the mobile device;

searching in the set of cell identifiers for a match of the cell identifier converted from the respective location of the mobile device;

retrieving a region identifier pre-associated with the matched cell identifier; and

identifying the respective region based on the retrieved region identifier.

3. The computing device of claim 1 , wherein the predefined boundary is a parcel boundary of land in residential areas.

4. The computing device of claim 3 , wherein the plurality of visitation types include:

visitations on different days;

visitations on different days in night hours; and

visitations on different days in weekends.

5. The computing device of claim 4 , further comprising:

determining, by the computing device, a count of different mobile devices having location in each of the regions during the period of time;

wherein the selecting of the home region is further based on the count of different mobile devices having location instances in each of the regions.

6. The computing device of claim 5 , wherein the selecting of the home region includes:

identifying a first subset of the region candidates, wherein each region candidate in the first subset has a count of different mobile devices less than a first threshold; and

selecting the home region from the first subset based on the scores.

7. A method implemented in a computing device, the method comprising:

receiving, in the computing device, location data of a mobile device, the location data specifying, for each respective time instance of a plurality of time instances in a period of time, a respective location of the mobile device determined by a position determination unit of the mobile device; and

identifying, by the computing device, a location of a home of a user of the mobile device, by:

identifying, by the computing device for the respective location of the mobile device at the respective time instance, a respective region that has a predefined boundary and contains the respective location, wherein locations specified in the location data are contained within a plurality of regions containing the locations;

determining, by the computing device for the respective location of the mobile device at the respective time instance, a visitation type, wherein the locations specified in the location data have a plurality of different visitation types;

filtering, by the computing device, the plurality of regions visited by the respective mobile device to identify a plurality of region candidates for the home of the user of the mobile device;

computing, by the computing device for each of the region candidates, a plurality of visitation frequencies corresponding to the plurality of different visitation types respectively;

computing, by the computing device for each of the region candidates, a score based at least in part on the plurality of visitation frequencies, wherein the plurality of region candidates have a plurality of scores respectively; and

selecting, by the computing device from the plurality of region candidates based on the plurality of scores, a home region as the home of the user.

8. The method of claim 7 , wherein the identifying of the respective region that contains the respective location includes:

storing a set of cell identifiers of a hierarchical grid system having grid lines aligned with numbers of digits of precision in longitudinal and latitudinal coordinates on the earth, including store each respective cell identifier of the set of cell identifiers in association with a set of region identifiers identifying one or more regions that are at least partially in a cell identified by the respective cell identifier;

converting to a cell identifier the respective location of the mobile device;

searching in the set of cell identifiers for a match of the cell identifier converted from the respective location of the mobile device;

retrieving a region identifier pre-associated with the matched cell identifier; and

identifying the respective region based on the retrieved region identifier.

9. The method of claim 7 , wherein the visitation type is determined based on a characteristic of the respective time instance of the respective location.

10. The method of claim 9 , wherein the characteristic is based on the respective time instance being outside of working hours.

11. The method of claim 9 , wherein the characteristic is based on the respective time instance being in weekends.

12. The method of claim 7 , wherein the score is based on a weight determined based on recency of location instances of the respective mobile device in the respective region.

13. The method of claim 7 , wherein the score is based on a weight determined based on a total number of different regions that contains the locations of the mobile device.

14. The method of claim 7 , wherein the score is based on a weight determined based on whether the region candidate has been previously identified as the home of the user of the mobile device.

15. The method of claim 7 , wherein the predefined boundary is a parcel boundary of land in residential areas.

16. The method of claim 15 , further comprising:

breaking a tie in the plurality of scores based on visitations to an area of a predetermined width surrounding but not within a boundary of each respective region candidate that has the tie.

17. The method of claim 7 , wherein the plurality of visitation types include:

visitations on different days;

visitations on different days in night hours; and

visitations on different days in weekends.

18. The method of claim 7 , further comprising:

determining, by the computing device, a count of different mobile devices having location in each of the regions during the period of time;

wherein the selecting of the home region is further based on the count of different mobile devices having location instances in each of the regions.

19. The method of claim 18 , wherein the selecting of the home region includes:

identifying a first subset of the region candidates, wherein each region candidate in the first subset has a count of different mobile devices less than a first threshold; and

selecting the home region from the first subset based on the scores.

20. A non-transitory computer storage medium storing instructions configured to instruct a computing device to perform a method, the method comprising:

receiving, in the computing device, location data of a mobile device, the location data specifying, for each respective time instance of a plurality of time instances in a period of time, a respective location of the mobile device determined by a position determination unit of the mobile device; and

identifying, by the computing device, a location of a home of a user of the mobile device, by:

identifying, by the computing device for the respective location of the mobile device at the respective time instance, a respective region that has a predefined boundary and contains the respective location, wherein locations specified in the location data are contained within a plurality of regions containing the locations;

determining, by the computing device for the respective location of the mobile device at the respective time instance, a visitation type, wherein the locations specified in the location data have a plurality of different visitation types;

filtering, by the computing device, the plurality of regions visited by the respective mobile device to identify a plurality of region candidates for the home of the user of the mobile device;

computing, by the computing device for each of the region candidates, a plurality of visitation frequencies corresponding to the plurality of different visitation types respectively;

computing, by the computing device for each of the region candidates, a score based at least in part on the plurality of visitation frequencies, wherein the plurality of region candidates have a plurality of scores respectively; and

selecting, by the computing device from the plurality of region candidates based on the plurality of scores, a home region as the home of the user.

Assignments (9)

Continuity (3)