HK40010089B - Geo-locating individuals based on a derived social network - Google Patents

Description

Geo-locating individuals based on derived social networks

Cross Reference to Related Applications

This application claims priority to U.S. provisional application No.62/373664, filed on 2016, 8, 11, which is incorporated herein by reference.

Technical Field

Embodiments of the invention relate generally to analyzing user location data and, in particular, to geo-locating (geo-locating) individuals based on a derived social network.

Background

Although mobile phones are able to record the user's geographic location (latitude, longitude) at a point in time, it is still difficult to pinpoint the venue (venue) where the person resides. This is because location points typically lack both density and accuracy.

Mobile phones typically record locations sparsely due to battery limitations (frequent location points will drain the phone's battery). When they are recorded, the point is not always accurate and usually contains a large amount of uncertainty (e.g., 100 meter radius). This uncertainty is further complicated in densely populated urban areas, where there may be many sites within an uncertainty radius. Thus, it is still difficult to know where the user actually lives.

Disclosure of Invention

Systems and methods for determining a user's location based on the locations of other users are disclosed. In some embodiments, a computing device determines, from a first user device, first user location information associated with a first user, the first user location information including a first centroid (centroid) and a first radius associated with a first user location. In some embodiments, the computing device receives, from the second user device, second user location information associated with a second user, the second user location information including a second centroid and a second radius associated with a second user location, the second user also associated with second user venue information. In some embodiments, the computing device determines a venue-relevance score between the first user and the second user based on: the amount of overlap between the first user radius and the second user radius and the social metric indicative of the strength of the social relationship between the first user and the second user, the social relationship defined at least in part by the number of times and the amount of time the first user is in proximity to the second user prior to receiving the first user location information and the second user location information. In some embodiments, the computing device creates venue information for the first user based on the second user venue information when the relationship score exceeds a threshold.

In some embodiments, the first centroid is associated with a first latitude and longitude, the first radius is associated with an accuracy of a location of the first centroid, the second centroid is associated with a second latitude and longitude, and the second radius is associated with an accuracy of a location of the second centroid. In some embodiments, the first user information further includes a first user device identifier and a first user duration, the first user duration including a start time and an end time corresponding to the first user associated with the first centroid. In some embodiments, the second user information further includes a second user identifier and a second user duration, the second user duration associated with the start time and the end time corresponding to a second user associated with the second centroid. In some embodiments, the venue-relevance score is based on an amount of overlap between the first user duration and the second user duration. In some embodiments, the venue-relevance score is further based on a confidence level assigned to the second user venue information. In some embodiments, the social metric is further defined by at least one of: a length of a relationship between the first user and the second user; and as a personal or professional relationship. In some embodiments, the threshold is based on at least one of: a received threshold; a distribution of relationship scores associated with a plurality of users; and the application of a machine learning algorithm to the location information and the location information of a plurality of users.

These and other capabilities of the disclosed subject matter will be more fully understood after a review of the following figures, detailed description, and claims. It is to be understood that the phraseology and terminology employed herein are for the purpose of description and should not be regarded as limiting.

Drawings

Various objects, features and advantages of the disclosed subject matter can be more fully understood by reference to the following detailed description of the disclosed subject matter when considered in connection with the following drawings in which like reference numerals identify like elements.

Fig. 1 is a system diagram illustrating a networked system according to some embodiments of the present disclosure.

Fig. 2 is a diagram illustrating a social graph, according to some embodiments of the present disclosure.

FIG. 3 is a diagram illustrating GPS information associated with user access according to some embodiments of the present disclosure.

FIG. 4 is a diagram illustrating collecting location information associated with user visits, according to some embodiments of the present disclosure.

Fig. 5 is a diagram illustrating the collection of venue information associated with a user visit according to some embodiments of the present disclosure.

Fig. 6 is a flow chart illustrating assigning venue information to a user according to some embodiments of the present disclosure.

Fig. 7 is a diagram illustrating an example of allocating venue information according to some embodiments of the present disclosure.

Detailed Description

Techniques are described herein to overcome constraints of tracking the location of individual users by leveraging a user's derived social networks. That is, even if the user does not disclose her exact location, if the user is co-located with a social connection (co-listening) that already discloses his location, the user's most likely location may be inferred based on the location of the social connection.

In some embodiments, the techniques described herein leverage the user's social network and other data sources to make reliable inferences about the user's exact location based on GPS information associated with the user (e.g., generated by their phone). In some embodiments, the amount of time that the user resides at a particular location (also referred to herein as "visit") is also notified of venue information associated with the user with reference to the amount of time that the social connection stays at the same location.

In some embodiments, the systems and methods described herein receive information about two users a and B, as well as information about their residences (latitude and longitude, horizontal accuracy, arrival and departure times). The systems and methods described herein determine that a is located at a venue V (e.g., retaurant Mario) (because the user tells the system and/or because of strong algorithmic evidence) and can mark B at the same venue by leveraging social connection information between a and B as well as other contextual information (e.g., the time and geographic proximity that the users each visit, the users own preferences and habits).

Various techniques may be used to collect user information and create a derived social network, for example, as described in fig. 1 and 2 below. Additionally, a System and Method for gathering user information to create and modify a derived social network is described in more detail in U.S. application No.15/298,353 entitled "System and Method for Detecting Interaction and infinity in Networks," filed on 10/20/2016, the contents of which are incorporated herein.

Fig. 1 is a system diagram illustrating a networked system 100 according to some embodiments of the present disclosure. Fig. 1 shows a user device 102, a network 104, a server 106, and a database 108.

The user device 102 may be associated with a user participating in the location tracking systems and methods described herein and may collect information from users participating in the networked system. In some embodiments, the user device 102 may comprise any computerized device capable of recording and transmitting information regarding the user's proximity to another user or location. In some embodiments, the computerized device may include a smart watch, smart phone, tablet, computer, laptop, or automobile that may be installed with a mobile application that facilitates collecting data.

In some embodiments, the user device 102 may include an onboard data collection agent, such as an automated on-board diagnostic module, telemetry and telematics module, transponder, on-board GPS module, and other systems that collect relevant data.

In some embodiments, the user device 102 may include a consumer wearable device or health monitor, such as a Jawbone Up, Fitbit Charge, or Apple Watch device.

In some embodiments, data may be transferred directly from the user device 302 to the network 304 (e.g., in the case of mobile applications), or may be collected through intermediate steps. For example, in the case of a vehicle telemetry system, information may be collected from the onboard device using an intermediate module and transmitted over a wireless link to a smartphone, where it may then be transmitted to network 304.

In some embodiments, a mobile application may be installed on a user's smartphone computing device and provide the user with the ability to opt-in to various data collection mechanisms. For example, a user may allow the system described herein to collect the user's contacts, Facebook friends, Instagram friends, location data over time, and payment, phone, and messaging patterns using a smartphone computing device through a mobile app.

In some embodiments, the user device 102 may take the form of an application or applet provided with various connected devices. For example, an app embedded in a DVR may communicate data about viewing habits and preferences, while software embedded in a car navigation system may communicate data about positioning and driving patterns.

Those skilled in the art will appreciate that there is no limitation on the type and variety of user equipment that may be used with the system described in this disclosure.

The network 104 enables communication between the user devices 102. The network 104 may be a public network such as the internet, where each of the user device 102 and the server 104 are connected via a gateway using a communication protocol such as Wi-Fi, ethernet, and 4G wireless. Alternatively, the network 104 may be a closed network, such as a Local Area Network (LAN), in which the various components of the relationship analysis system are not accessible over the open Internet. In some embodiments, communications over network 304 may be encrypted, or additional security protocols may be utilized, such as a Virtual Private Network (VPN) or Secure Shell (SSH) tunnel.

The server 106 may include one or more server computers that implement a database 108 for holding data collected about users. In some embodiments, the particular configuration of the server 106 may depend on many factors, such as the type of database, the expected size of the database, and user performance expectations. In some embodiments, the system is scalable and additional processing capacity may be added as demand increases.

Fig. 2 is a diagram illustrating a social graph 200, according to some embodiments of the present disclosure. The social graph 200 includes a node 202204206, a node parameter 212214216, and a link 220222224.

As described above, the social graph 200 is one way to represent entities and relationships between entities. Other methods (e.g., matrices) of visualizing entities and relationships to entities are equally applicable to the systems and methods described herein.

The nodes 202204206 represent entities and are each associated with a set of parameters 212214216. As described above, the parameters 212214216 may be assigned to the nodes 202204206, respectively, based on information received from the data collection node 110. Entities may include people, organizations, and equipment. The parameters 212214216 may include information identifying the entity and describing at least one of a location, an activity, or a relationship of a transaction associated with the entity. For example, if the entity is a person, the parameters may include identification number, birthday, gender, employer, credit rating, location (and location accuracy), payroll, recent transactions, and recent activities. As another example, if the entity is a company, the node may include attributes such as: company ID, vendor ID, company name, year of creation, address, industry ranking, credit rating, location information expressed as longitude and latitude of the company, and an indicator of confidence level of location coordinate accuracy. Company location information can be used to determine movement and interaction of individuals. In some embodiments, the parameter information may be associated with a time at which the parameter information is observed, received, or processed.

As used herein, a transaction may refer to a purchase (e.g., clothing, food, travel, merchandise), and an activity may refer to an event (e.g., sporting event, lesson, party).

A node (e.g., node 202) may be connected to other nodes (e.g., node 204 and node 206) via link 220222224. The links may represent the strength of relationships between entities or the strength between parameters associated with the entities. The strength of the relationship between entities may vary depending on the nature and the evidence at hand of the entities involved. In some embodiments and as described in more detail below, a smaller score is considered better and similar to distance. The strength of relationship value may be referred to as the distance between nodes and is measured in units referred to herein as axons.

In an embodiment, a subgraph representing the effective range of an entity is provided. These subgraphs (called self-centric networks) are distance-limited subgraphs of entities. In an embodiment, once the social graph is created, the egocentric network is the basic unit for all further processing. The following criteria may be used to generate a self-centric network:

a maximum traversal distance may be set, limiting the subgraph to paths smaller than the maximum traversal distance measured with the axon. In some embodiments, the maximum traversal distance may be set to 100000 axons, although other settings may be utilized depending on the application.

The hop penalty may be applied to the distance of each hop in the path by multiplying the distance by the penalty. For example, if the first hop between nodes has a penalty of 5 and the distance of the first hop is 100 axons, it will effectively have a scaling distance of 500 axons.

Traversal timeouts may be incorporated to limit large networks that can cause processing delays. Traversal timeouts are mitigation measures that should not be necessary in the equalization graph. In some embodiments, the traversal timeout may be set to 15 seconds, but variations may be used depending on the system.

Depending on whether the origin of the egocentric network is an individual or an entity, additional restrictions on the generation of the egocentric network, such as restrictions on the network characteristics considered during traversal, may be enforced.

In some embodiments, different social graphs may be created based on desired commonality factors between entities. In this case, the related egocentric networks may be different from each other. For example, in determining the impact of an entity on node 202, link 220 to node 204 may be stronger if the query relates to the entity that would have the greatest relevance to node 202 in terms of relevant restaurant suggestions in city a, while link 224 to node 206 may be stronger if the query relates to the entity that would have the greatest relevance to node 202 in terms of relevant retailers of casual clothing.

In some embodiments and as described in more detail below, information associated with a user's access to various tables of locations (and possibly venues) may be used to calculate similarities between each pair of users. If two users are found to be similar enough, they can become entities in the entire connection graph. For each connection, there are two nodes (e.g., 202 and 204) representing each of the two users and a weight (or score) (e.g., 220), which is a real number between 0 and 1 indicating the strength of the connection between the two nodes.

In some embodiments, when two users spend a relatively high proportion of time in close proximity, the confidence level associated with the presence of a social connection between the users is therefore increased. Closer connections often take more time in different places (e.g. not only at work, but also after work at a bar and weekends together in one user's home). More distant connections will often take relatively less time together at less varying locations.

The commonality factor of an entity may be determined based on a varying parameter of the entity. For example, when an entity travels to a new location, a social graph may be created based on factors related to traveling to the new place (e.g., hotel, rental car, restaurant). As another example, the variation parameter may include a particular purchase or noticed purchase pattern. In some embodiments, the variation parameter may determine the familiarity of an entity with a region. The social graph may appear very different in the hometown of the entity than it has never visited before. For example, a hotel may have a different relevance value in the hometown of the entity than the new place (less familiar place) that the entity is visiting. In some embodiments, the variation parameter information includes both a location and a time associated with the variation parameter.

In some embodiments, the scoring relationship strength may vary depending on the nature of the entities involved and the information available. For example, a relationship between two people may be evaluated using a metric such as: the length of the relationship, whether the relationship is personal or professional, the frequency with which two people are in the same location, and the frequency with which individuals visit similar locations, etc. Similarly, the relationship between an individual and a particular brand may include: the time an individual purchases the brand, the frequency with which an individual purchases a competing brand, and the frequency with which an individual purchases one product at the same time as another product, etc. Although there may be overlap between relationship characteristics depending on the type, there may also be differences.

In measuring the strength of the relationship, the score may be evaluated as axons, which is briefly mentioned above. A smaller score is considered better and is similar to distance. In addition to scoring relationships, the centrality of an entity may also be scored to quantify the connectivity of the entity in the network, which in turn measures the impact of the entity.

Personal relationships may be represented using a weighted interconnection that scores relationships based on their characteristics. In embodiments, the characteristics include duration, year, interaction, trust/change, control, and harmony. Additional details describing the calculation of the weight of a connection between two users may be found in U.S. application No.15/298,353 entitled "System and Method for Detecting Interaction and fluorescence in Networks," filed 10/20/2016, the contents of which are incorporated herein.

FIG. 3 is a diagram illustrating GPS information associated with user access according to some embodiments of the present disclosure. FIG. 3 shows a centroid 300 and centroid radius 301.

In some embodiments, an "access" is a GPS pair (lat, lon) having a start time and an end time (e.g., "2016/28/1110: 30: 00+00: 00") generated by a particular user device (e.g., a mobile phone). The access may be represented in space by a circle: centroid 300 is where the device records visit, and radius 301 depicts the horizontal accuracy of the record as judged by the device. Generally, the larger the radius, the less confidence in the user's location.

FIG. 4 is a diagram illustrating collecting location information associated with user visits, according to some embodiments of the present disclosure. FIG. 4 shows an access object 402, a database 404, a user data table 406, an access ID 410, and a device ID 412.

The access object 402 is uploaded from the user device 102 to the server 106. The access object 402 includes the user's location information including centroid, accuracy, start time, and end time. The format of the access object may be any format agreed upon by the user device 102 and the server 106, for example in JSON format, as follows:

the server 106 may persistently access the object 402 information in the database 108 for further analysis. The information in the database 108 may be organized in an access data table 404 that assigns each object an access ID 410 and a device ID 412 in the table 404. Any data structure that stores an association between an ID and an object may be used, for example, the integer table is as follows:

access Id	Device Id
		111	AAAABBBB
222	CCCCDDDD
		...	….

As described in more detail below in the text of fig. 5, the access ID 410 may be used to associate the venue with the user.

Fig. 5 is a diagram illustrating the collection of venue information associated with a user visit according to some embodiments of the present disclosure. Fig. 5 shows venue data 502 and a venue ID 504 stored in a data table 501.

Venue data 502 corresponds to venue information associated with a location of a user. In some embodiments, venue data 502 is obtained by "check-in". As used herein, "check-in" refers to an action performed voluntarily by the user of the user device 102 confirming that access should be marked with a venue (e.g., restaurant marrio). The venue may be provided from a venue list to an application running on user device 102. Other venue confirmation processes that map access to a venue may also be used (e.g., credit card transactions, strong algorithmic evidence from other software applications). The venue information may be tagged with a venue ID 504, for example, as follows:

site Id	Name (R)
		2222	Bar X
3333	Dining room Y
		...	….

The confirmed venue data 502 may be uploaded as an object mapping the access ID 410 with the venue ID 504. Venue ID 504 may correspond to a unique ID assigned to a venue. The venue data 502 object may be in any format agreed upon by the user device 102 and the server 106, for example in JSON format, as follows:

venue ID 504 may be stored in a database in a manner that associates access ID 111 with venue ID 504. For example, an integer table may be used, as follows:

access Id	Device Id	Site ID
			111	AAAABBBB	2222
222	CCCCDDDD	….
			...	….	…..

Fig. 6 is a flow chart illustrating assigning venue information to a user according to some embodiments of the present disclosure.

Referring to step 602, first user location information is received, the first user location information including a centroid and a radius associated with a first user location. As described above, the location information may include: a user's location (e.g., represented as a centroid using longitude and latitude), a duration associated with the user's presence at the location (e.g., as measured by a start time and an end time), and a confidence level of the user at the location (e.g., as measured by a radius associated with the centroid).

Referring to step 604, second user location information is received, the second user location information including a centroid and a radius associated with a second user location and venue information associated with the second user. As described above, the location information may include: a user's location (e.g., represented as a centroid using longitude and latitude), a duration associated with the user's presence at the location (e.g., as measured by a start time and an end time), and a confidence level of the user at the location (e.g., as measured by a radius associated with the centroid).

Also as described above, the server receives information about a particular venue at which the second user is located. A venue may be a location (lat, lon pair) with semantic metadata as a parameter: such as category (restaurant, hotel, stadium, etc.), name, business hours, etc. In some embodiments, the "check-in" information is also associated with a confidence level regarding the reliability of the match between the stop and the venue in question. Factors contributing to reliability include: user confirmation of the venue (e.g., manual enrollment of the user with respect to the venue), third party verification of the venue (e.g., purchase of the user at the venue), and other algorithmic evidence.

Referring to step 606, a relationship score between the first user and the second user is determined based on an amount of overlap between the first user radius and the second user radius and a social metric indicative of a strength of a social relationship between the first user and the second user. Note that the following is merely an example of such an algorithm, which may take various forms (e.g., threshold decision, probabilistic decision tree, etc.) is:

temporal overlap metric spatial overlap metric social connection metric > threshold → user2 will be assigned user1 site information

In some embodiments, the threshold may be selected to be relatively small, for example, to collect more user data (e.g., to trigger more user acknowledgements and improve user engagement with the software application), while in other embodiments the threshold may be set higher in order to minimize the number of false positives (e.g., in highly sensitive data applications, one may prefer to make fewer inferences, but also reduce errors).

Referring to step 608, when the venue-related score exceeds the threshold, venue information is created for the first user based on the venue information associated with the second user. For example, assume the following scenario:

USER1, with access focused on <40.708793, -74.011013>, from 09:10 to 09:45

USER2, with access focused on <40.708616, -74.011145>, from 09:12 to 09:48

USER1 confirmed access to Starbucks located at Bulback number 115 (10006, N.Y.).

For both USERs, feature values in the decision algorithm may be calculated, and if a condition is met, site matching may be performed for USER2, for example:

the time overlap metric: 33/38 ═ 0.86 (time overlap measured in Jaccard distances between sets of minutes in two intervals)

The spatial overlap metric: 1-0.044 ═ 0.956 (distance between visits (point-to-point) 0.022km, scaling to theoretical maximum 0.5km)

Social connection metrics: 0.75 (reading attributes from social graph, assuming they are close friends)

Each of the above-mentioned features may be computed in a different way (e.g., horizontal accuracy may be explicitly used in spatial overlap). Furthermore, the algorithm that makes the final decision may be different in different embodiments: for example, three features may be multiplied and the threshold set heuristically based on domain-specific knowledge (similar to the IF-THEN relationship explained above); or, as another example, a distribution of these scores may be estimated and a threshold determined as the value that marks the nth percentile (i.e., such that the value of n% of the scores is insufficient to allow a site match). Finally, with sufficient training data, machine learning algorithms (e.g., logistic regression, decision trees) appropriate to the decision-making problem can be used to learn the best way to make the final site matching decision based on spatiotemporal features and social connections.

Fig. 7 is a diagram illustrating an example of allocating venue information according to some embodiments of the present disclosure. FIG. 7 shows a spatial overlap map 700, a user A centroid 701, a user B centroid 702, a user A access object 703, and a user B access object 704.

User a, as mentioned with reference to fig. 7, is a user who already has a confirmed venue, while user B is a user who is assigned a venue based on the systems and methods described herein. As shown in the spatial overlap map 700, the user a centroid 701 and the user B centroid 702 are very close, and the horizontal (radial) components of each centroid overlap. Even if user a centroid 701 and user B centroid 702 do not match exactly (e.g., the GPS signals (access) generated by their devices shift slightly), both users have an opportunity to be in the same venue.

User a access object 703 and user B access object 704 include location information. The location information includes a device ID, latitude, longitude, hAccuracy (horizontal accuracy of latitude/longitude, as opposed to vertical accuracy of altitude), start time, and end time. As shown in FIG. 7, the time overlap of user A and user B is found at the locations shown in the spatial overlap map 700 (e.g., start and end times for user A are 10:30 and 12:32, and start and end times for user B are 10:21 and 12: 43). That is, user B's access begins just a few minutes before and ends a few minutes after user A's access. Generally, the closer the user access times match, the more likely they are to be together.

The user a access object 703 also includes venue ID information, while the user B access object 704 does not include venue ID information. As described above, the venue ID information may be assigned when the confidence level regarding the reliability of the venue information exceeds the threshold. Factors contributing to the reliability of the venue information include user confirmation of the venue (e.g., manual enrollment of the user with respect to the venue) and third party verification of the venue (e.g., purchases made by the user at the venue). In this example, user a accesses object 703 with venue information because the system determines that user a has reliable venue information.

User B may be assigned to user a's venue information based on the strength of the correlation between their location information and their social connection information. As described, the systems and methods described herein may take into account the strength of the social connection between a and B as described in U.S. application No.15/298,353 entitled "System and Method for Detecting Interaction and influx in Networks," filed in fig. 2 and 2016, 10, 20, the contents of which are incorporated herein, above. Assuming that user a and user B are close social connections (e.g., have a score of 0.96) and the location information overlap is significant (exceeding a confidence threshold), user B may be assigned or suggested a venue ID for user a.

As another example, assume that a group of users all go to a restaurant together. Their mobile location points are replaced, appearing that they are most likely to be at another site across the street; furthermore, there are several possible sites within the uncertainty radius of the location point. However, one user discloses her location (e.g., paying a bill with a credit card or tagging a photo with a venue) to confirm her presence at that particular restaurant. The system described herein may determine that the first user is closely geo-located to other individuals with strong social relationships therewith and may infer that the other individuals are in the same location.

The subject matter described herein can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structural means disclosed in this specification and structural equivalents thereof, or in combinations of them. The subject matter described herein can be implemented as one or more computer program products, such as one or more computer programs tangibly embodied in an information carrier (e.g., in a machine-readable storage device) or in a propagated signal, for execution by, or to control the operation of, data processing apparatus (e.g., a programmable processor, a computer, or multiple computers). A computer program (also known as a program, software application, or code) can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file. A program can be stored in a portion of a file that holds other programs or data, in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers at one site or distributed across multiple sites and interconnected by a communication network.

The processes and logic flows described in this specification, including the method steps of the subject matter described herein, can be performed by one or more programmable processors executing one or more computer programs to perform functions of the subject matter described herein by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus of the subject matter described herein can be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).

Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. The essential elements of a computer are a processor for executing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. Information carriers suitable for embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices (e.g., EPROM, EEPROM, and flash memory devices); magnetic disks, (e.g., internal hard disks or removable disks); magneto-optical disks; and optical discs (e.g., CD and DVD discs). The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

To provide for interaction with a user, the subject matter described herein may be implemented on a computer having: a display device for displaying information to a user, such as a CRT (cathode ray tube) or LCD (liquid crystal display) monitor; and a keyboard and a pointing device (e.g., a mouse or a trackball) by which a user can provide input to the computer. Other types of devices may also be used to provide for interaction with a user. For example, feedback provided to the user can be any form of sensory feedback (e.g., visual feedback, auditory feedback, or tactile feedback), and input from the user can be received in any form, including acoustic, speech, or tactile input.

The subject matter described herein may be implemented in a computer system that includes: a back-end component (e.g., a data server); a middleware component (e.g., an application server); or a front-end component (e.g., a client computer having a graphical user interface or a web browser through which a user can interact with an implementation of the subject matter described herein); or any combination of such back-end, middleware, and front-end components. The components of the system can be interconnected by any form or medium of digital data communication (e.g., a communication network). Examples of communication networks include a local area network ("LAN") and a wide area network ("WAN"), such as the Internet.

It is to be understood that the disclosed subject matter is not limited in its application to the details of construction and to the arrangements of the components set forth in the following description or illustrated in the drawings. The disclosed subject matter is capable of other embodiments and of being practiced and carried out in various ways. Also, it is to be understood that the phraseology and terminology employed herein is for the purpose of description and should not be regarded as limiting.

As such, those skilled in the art will appreciate that the conception upon which this disclosure is based may readily be utilized as a basis for the designing of other structures, methods and systems for carrying out the several purposes of the disclosed subject matter. It is important, therefore, that the claims be regarded as including such equivalent constructions insofar as they do not depart from the spirit and scope of the disclosed subject matter.

While the disclosed subject matter has been described and illustrated in the foregoing exemplary embodiments, it is understood that the present disclosure has been made only by way of example, and that numerous changes in the details of implementation of the disclosed subject matter may be made without departing from the spirit and scope of the disclosed subject matter, which may be limited only by the following claims.

Claims (20)

1. A computerized method of determining a user's location based on locations of other users, the computerized method comprising:

receiving, at a computing device from a first user device over a network, first user location information associated with a first user, the first user location information including a first centroid and a first centroid radius associated with a first user location, wherein the first centroid is where records of the first user device are visited and the first centroid radius is associated with an accuracy of a location of the first centroid;

receiving, at the computing device from a second user device over a network, second user location information associated with a second user, the second user location information including a second centroid and a second centroid radius associated with a second user location, the second user further associated with second user venue information, wherein the second centroid is where the second user device records access and the second centroid radius is associated with an accuracy of a location of the second centroid;

determining, at the computing device, a venue-relevance score between the first user and the second user based on an amount of overlap between a first centroid radius of the first user and a second centroid radius of the second user and a social metric indicative of a strength of a social relationship between the first user and the second user, the social relationship defined at least in part by a number of times and an amount of time the first user is in a proximate location of the second user prior to receiving the first user location information and the second user location information; and

creating, at the computing device, venue information for the first user based on the second user venue information when the venue-relevance score exceeds a threshold.

2. The computerized method of claim 1, wherein the first centroid is associated with a first latitude and longitude and the second centroid is associated with a second latitude and longitude.

3. The computerized method of claim 1, wherein:

the first user location information further includes a first user device identifier and a first user duration, the first user duration including a first start time and an end time corresponding to a first user associated with the first centroid; and is

The second user location information further includes a second user device identifier and a second user duration, the second user duration associated with a second start time and an end time corresponding to a second user associated with the second centroid.

4. The computerized method of claim 3, wherein the venue-relevance score is based on an amount of overlap between the first user duration and the second user duration.

5. The computerized method of claim 1, wherein the venue-relevance score is further based on a confidence level assigned to the second user venue information.

6. The computerized method of claim 1, wherein the social metric is further defined by at least one of:

a length of a relationship between the first user and the second user; and

as a personal or professional relationship.

7. The computerized method of claim 1, wherein the threshold is based on at least one of:

a received threshold;

a distribution of relationship scores associated with a plurality of users; and

application of a machine learning algorithm to a plurality of user location information and user venue information.

8. A computing system for determining a user's location based on locations of other users, the computing system comprising:

a processor; and

a memory coupled to the processor and comprising computer readable instructions that, when executed by the processor, cause the processor to:

receiving, over a network from a first user device, first user location information associated with a first user, the first user location information including a first centroid and a first centroid radius associated with a first user location, wherein the first centroid is where the first user device records access and the first centroid radius is associated with an accuracy of a location of the first centroid;

receiving, over a network from a second user device, second user location information associated with a second user, the second user location information including a second centroid and a second centroid radius associated with a second user location, the second user further associated with second user venue information, wherein the second centroid is where the second user device records access and the second centroid radius is associated with an accuracy of a location of the second centroid;

determining a venue-relevance score between the first user and the second user based on an amount of overlap between a first centroid radius of the first user and a second centroid radius of the second user and a social metric indicative of a strength of a social relationship between the first user and the second user, the social relationship being defined at least in part by a number of times and an amount of time the first user is in a proximity location of the second user prior to receiving the first user location information and the second user location information; and is

Creating venue information for the first user based on the second user venue information when the venue-relevance score exceeds a threshold.

9. The computing system of claim 8, wherein the first centroid is associated with a first latitude and longitude and the second centroid is associated with a second latitude and longitude.

10. The computing system of claim 8, wherein:

the first user location information further includes a first user device identifier and a first user duration, the first user duration including a first start time and an end time corresponding to a first user associated with the first centroid; and is

The second user location information further includes a second user device identifier and a second user duration, the second user duration associated with a second start time and an end time corresponding to a second user associated with the second centroid.

11. The computing system of claim 10, wherein the venue-relevance score is based on an amount of overlap between the first user duration and the second user duration.

12. The computing system of claim 8, wherein the venue-relevance score is further based on a confidence level assigned to the second user venue information.

13. The computing system of claim 8, wherein the social metric is further defined by at least one of:

a length of a relationship between the first user and the second user; and

as a personal or professional relationship.

14. The computing system of claim 8, wherein the threshold is based on at least one of:

a received threshold;

a distribution of relationship scores associated with a plurality of users; and

application of a machine learning algorithm to a plurality of user location information and user venue information.

15. A non-transitory computer readable medium having executable instructions operable to cause an apparatus to:

receiving, over a network from a first user device, first user location information associated with a first user, the first user location information including a first centroid and a first centroid radius associated with a first user location, wherein the first centroid is where the first user device records access and the first centroid radius is associated with an accuracy of a location of the first centroid;

receiving, over a network from a second user device, second user location information associated with a second user, the second user location information including a second centroid and a second centroid radius associated with a second user location, the second user further associated with second user venue information, wherein the second centroid is where the second user device records access and the second centroid radius is associated with an accuracy of a location of the second centroid;

determining a venue-relevance score between the first user and the second user based on an amount of overlap between a first centroid radius of the first user and a second centroid radius of the second user and a social metric indicative of a strength of a social relationship between the first user and the second user, the social relationship being defined at least in part by a number of times and an amount of time the first user is in a proximity location of the second user prior to receiving the first user location information and the second user location information; and is

Creating venue information for the first user based on the second user venue information when the venue-relevance score exceeds a threshold.

16. The non-transitory computer-readable medium of claim 15, wherein the first centroid is associated with a first latitude and longitude and the second centroid is associated with a second latitude and longitude.

17. The non-transitory computer-readable medium of claim 15, wherein:

the first user location information further includes a first user device identifier and a first user duration, the first user duration including a first start time and an end time corresponding to a first user associated with the first centroid; and is

The second user location information further includes a second user device identifier and a second user duration, the second user duration associated with a second start time and an end time corresponding to a second user associated with the second centroid.

18. The non-transitory computer-readable medium of claim 17, wherein the venue-relevance score is based on an amount of overlap between the first user duration and the second user duration.

19. The non-transitory computer-readable medium of claim 15, wherein the venue-relevance score is further based on a confidence level assigned to the second user venue information.

20. The non-transitory computer-readable medium of claim 15, wherein the social metric is further defined by at least one of:

a length of a relationship between the first user and the second user; and

as a personal or professional relationship.