INFERENCE PIPELINE SYSTEM AND METHOD

• US 20130226857A1
• Filed: 02/24/2012
• Published: 08/29/2013
• Est. Priority Date: 02/24/2012
• Status: Active Grant

• Current Assignee: Foursquare Labs, Inc.
• Original Assignee: Placed, Inc. (Foursquare Labs, Inc.)
• Inventors: Shim, David, Bicknell, Brad, Varghese, George, Gerner, Nick, Yi, Weilie
• Granted Patent: US 8,768,876 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 5/048 Fuzzy inferencing
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A system to infer place data is disclosed that receives location data collected on a user'"'"'s mobile electronic device, recognizes when, where and for how long the user makes stops, generates possible places visited, and predicts the likelihood of a user to visit those places.

Claims

1. A system for using location data to infer a place name of a user, wherein the system is configured to receive location readings and sensor data from multiple mobile devices wirelessly coupled to a network, the system comprising:

at least one data storage device for storing a place database, reference data, a sequence of location readings, and sensor data,

wherein the place database includes place information and corresponding geolocation data,

wherein the reference data links a user or a user'"'"'s mobile device to a proposed place at an instance of time, and

wherein the sequence of location readings includes latitude and longitude coordinate data and an associated time;

at least one server coupled to the data storage device, wherein the server is configured to;

classify a sliding window of N contiguous location readings over the sequence of location readings as moving or not moving, wherein N is an integer number of location readings;

segment the sequence of location readings into two or more location clusters;

identify a centroid or sub-centroids of each of the two or more location clusters;

query the place database to identify two or more candidate places that are within a predetermined radius of the centroid of the cluster;

extract a feature from the candidate places, wherein the feature includes a place category, popularity, or hours of operation; and

calculate a probability that the user is located at each of the candidate places, wherein the probability is based on features of the candidate places.

2. The system of claim 1, wherein the reference data includes at least one of:

a user check-in at a certain place, a place category, a popularity of a place, hours of operation.

3. The system of claim 1, wherein the sensor data includes at least two of:

acceleration, magnetic orientation, proximity, light intensity, battery status, gyroscope, or temperature.

4. The system of claim 1, wherein the location readings also includes altitude, bearing, and speed of the mobile device.

5. The system of claim 1, wherein the at least one server is further configured to rank order a predetermined number of the candidate places for the user to validate as a confirmed location.

6. The system of claim 1, wherein the reference data is derived from at least one of:

place check-in, internet search activity, social networking site activity, geotagged image, email, phone call, or calendar appointment.

7. The system of claim 1, wherein the reference data is derived from a feature of a WiFi network, wherein the feature includes at least one of:

a network name, a signal strength, a MAC address, an IP address, a security setting, an available WiFi network, a connection status, a visible WiFi network, and a previously-connected WiFi network.

8. The system of claim 1, wherein calculating the probability that the user is located at the candidate places is based on hours of operation for candidate places or a distance between the reference data and each of the candidate places.

9. An apparatus for using location data to obtain a name of a place associated with the location data, comprising:

at least one memory;

at least one radio;

input/output components;

at least one processor coupled to the memory, radio, and input/output components, wherein the apparatus further comprises;

means for storing a place database, reference data, a sequence of location readings and sensor data,

wherein the place database includes place information and corresponding geolocation data,

wherein the reference data includes a user and a proposed place at an instance of time, and

wherein the sequence of location readings includes latitude and longitude coordinate data and an associated time;

means for filtering location readings to produce filtered location data;

means for identifying a location from the filtered location data;

means for identifying multiple candidate places based on the identified location; and

means for calculating a probability that the user is located at the multiple candidate places.

10. The apparatus of claim 9, wherein the means for filtering employs a sliding window of N contiguous location readings over the sequence of location readings as moving or not moving, wherein N is an integer number of location readings.

11. The apparatus of claim 10, further comprising means for segmenting the sequence of location readings into two or more location clusters, and wherein the means for identifying includes identifying a centroid of each of the two or more location clusters.

12. The apparatus of claim 9, wherein the means for identifying multiple candidate locations includes querying a place database to identify two or more candidate places that are within a predetermined radius of a centroid computed from the identified location.

13. The apparatus of claim 9, further comprising means for rank ordering a predetermined number of the multiple candidate places for the user to validate as a confirmed location.

14. The apparatus of claim 9, wherein the reference data is derived from at least one of:

internet search activity, social networking site activity, geo-tagged image, an email, a phone call, a calendar appointment, or a place check-in.

15. The apparatus of claim 9, wherein the means for calculating the probability also factors in hours of operation of the multiple candidate places.

16. A computer readable storage medium storing instructions for using validated place data to infer a location of a user, the computer readable storage medium comprising:

instructions for analyzing a series of location data received from a mobile device—

to identify a stop time when the mobile device has stopped for longer than a threshold time, and

to identify a location associated with the stop time;

instructions for querying a place name database to identify multiple candidate place names that are within a predetermined radius of the identified location;

instructions for obtaining attributes of the stop time and attributes of the multiple candidate place names; and

instructions for identifying one of the multiple candidate place names as a likely place name for the identified location at the stop time.

17. The computer readable storage medium of claim 16, further comprising instructions for storing the place name database, a reference data, the series of location data, and sensor data, wherein the place name database includes place information and corresponding geo-location data, wherein the reference data links a user to a proposed place at an instance of time, and wherein the series of location data includes latitude and longitude coordinate data and an associated time.

18. The computer readable storage medium of claim 16, further comprising:

instructions for classifying a sliding window of N contiguous location data over the series of location data as moving or not moving, wherein N is an integer number of location data;

instructions for segmenting the series of location data into two or more location clusters based on whether the sliding window is classified as moving or not moving; and

instructions for identifying a place name for each of the two or more location clusters.

19. A method of inferring a location of a user using location readings and sensor data from a mobile device wirelessly coupled to a network, the method comprising:

receiving multiple location readings,

wherein each location reading includes latitude and longitude coordinate data, and

wherein each location reading has an associated time and an estimated accuracy;

filtering the location readings to remove noise from the location readings;

determining if the mobile device is stationary from the filtered location readings;

temporally clustering the filtered location readings to identify a time and location of a stop; and

identifying a significant stop from the temporally clustered location readings.

20. The method of claim 19, further comprising purging one or more location readings with an estimated accuracy lower than an accuracy threshold to produce resulting location data, wherein the purging of one or more location readings includes location readings from cell-tower triangulation.

21. The method of claim 19, further comprising classifying a sliding window as moving or not moving by:

computing a duration of the sliding window of N contiguous location readings;

computing a great-circle distance of the sliding window of N contiguous location readings, wherein the great-circle distance is based on a minimum latitude, a minimum longitude, a maximum latitude, and a maximum longitude; and

computing a speed of the sliding window of N contiguous location readings, wherein computing includes dividing the great circle distance by the duration.

23. The method of claim 19, further comprising:

for each sliding window of N contiguous location readings;

computing a maximum distance between any of the location readings of the sliding window of N location contiguous readings;

when the maximum distance is equal to or greater than a distance threshold, classifying the sliding window of N contiguous location readings as moving; and

when the maximum distance is less than a distance threshold, classifying the sliding window of N contiguous location readings as not moving.

24. The method of claim 19,

wherein sensor data includes accelerometer data, and

wherein classifying the sliding window as moving or not moving further includes applying a Fourier transform to the accelerometer data in order to determine a base frequency;

25. The method of claim 19, further comprising:

merging two or more clusters of location data when a centroid of each of the two or more location clusters is below a centroid threshold.

26. The method of claim 19, further comprising receiving reference data, wherein the reference data links the user to a proposed place at an instance of time, and wherein the reference data includes a place confirmation at a particular place.

27. The method of claim 26, further comprising calculating a probability that the user is located at multiple candidate places, wherein the probability factors in a distance between reference data and each of the multiple candidate places;

and extracting a feature of the multiple candidate places, wherein the feature includes a place category and hours of operation.

28. The method of claim 19, further comprising receiving reference data, wherein the reference data links the user to a proposed place at an instance of time, and wherein the reference data is derived from at least one of:

place check-in, internet search activity, social networking site activity, geo-tagged image, email, phone call, or calendar appointment.

22. The method of 19, further comprising classifying a sliding window as moving or not moving by defining the sliding window as moving when the great-circle distance of the portion of the sequence of location readings is above a distance threshold.