HK1174719A - Framework for track-based mobile applications - Google Patents

Description

Framework for trajectory-based mobile applications

Background

Targeted advertising is a popular and efficient technique for providing advertisements. One approach to targeted advertising is to target advertisements based on published content. For example, stores specializing in music may display their advertisements in magazines or on web pages visited by people related to music or known to be purchasing music.

Another technique for targeting advertisements is to target advertisements based on a location associated with a user. The location of the user may be determined by an IP (internet protocol) address associated with the user, or by a global positioning system or other location-aware technology associated with the user. For example, when a cellular telephone determines that its user is near a coffee shop, the user of the cellular telephone may receive an advertisement for the coffee shop. However, targeted advertising based on the user's current location may not be particularly effective because the user's current location may not be an accurate identifier of the user's true preferences. Continuing with the example above, the user may dislike coffee, or the user may be located near a coffee shop when he generally does not want to drink coffee.

Disclosure of Invention

A mobile device, such as a cellular telephone, monitors the location of a user over time. The monitored locations are organized into a track that describes a path or route that the user has traversed over a period of time. The track server collects and stores the tracks associated with the user, as well as the tracks associated with other users. The track server may analyze the stored tracks to identify similar tracks and to identify users who have similar tracks with each other. The track server may also support an application programming interface that allows developers to create applications that use tracks. Examples of such applications may include applications that recommend a ride to a user (e.g., based on the commute information of the user), applications that recommend a lane or trail to the user to take (e.g., based on the trajectory of the friends of the user), and applications that provide targeted advertising or commercial recommendations (e.g., based on the trajectory of the user).

In one implementation, a computing device identifies a track associated with a first user. Each track may include a location identifier. The computing device clusters the identified tracks to generate a composite track for the first user. The computing device identifies at least one track that is similar to the composite track. The at least one track may be associated with a user other than the first user. The computing device provides information about the identified at least one track that is similar to the composite track over the network.

Implementations may include some or all of the following features. Each track may represent commute information. The identified at least one track may have associated advertisements, and providing information about at least one track that is similar to the composite track may include providing one or more of the associated advertisements to the first user. The clustering may be k-means clustering. Businesses associated with the at least one identified track may be identified, and providing information regarding the at least one identified track that is similar to the composite track may include providing one or more of the identified businesses to the first user. Each track may have associated metadata, and providing information about at least one track that is similar to the composite track may include providing metadata associated with the at least one track.

Identifying at least one track that is similar to the composite track may include defining an area around each location identifier of the composite track, selecting a track from the plurality of tracks that is associated with a user other than the first user, determining a percentage of location identifiers of the selected track that are within one of the defined areas, and identifying the selected track as a similar track if the percentage is greater than a threshold percentage. The defined area may be a circle and defining an area around each location identifier may include, for each location identifier of the composite track, determining a distance between the location identifier and a previous location identifier, determining a radius of the defined area based on the determined distance, and defining an area around the location identifier having the determined radius.

Identifying at least one track that is similar to the composite track may include defining a path through location identifiers of the composite track, selecting a track from a plurality of tracks that is associated with a user other than the first user, determining a percentage of location identifiers of the selected track that are within the defined path, and identifying the selected track as a similar track if the percentage is greater than a threshold percentage. The path may have an associated width at each location identifier of the composite track, and defining the path through the location identifiers of the composite track may include, for each location identifier of the composite track, determining a distance between the location identifier and a previous location identifier, and determining the width of the path at the location identifier based on the determined distance. Determining the width of the path at the location identifier based on the determined distance may include determining the width to be equal to the determined distance.

In an implementation, a computing device receives a query from a first user over a network. The computing device identifies one or more tracks that are responsive to the query. Each track may include a location identifier and may represent a route taken by a user other than the first user. The computing device presents at least one of the identified tracks to a first user over a network.

Implementations may include some or all of the following features. The first user may have an associated location identifier, and identifying one or more tracks responsive to the query may include identifying one or more tracks having a location identifier that identifies a location geographically near the location identified by the location identifier associated with the first user. The query may have an associated temporal identifier and each track may have an associated temporal identifier, identifying one or more tracks that are responsive to the query may include identifying one or more tracks having an associated temporal identifier that is proximate to the temporal identifier associated with the query. Each track may have associated metadata, and identifying one or more tracks that are responsive to the query may include identifying one or more tracks that have metadata that matches the query.

This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the detailed description. This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

Brief Description of Drawings

The foregoing summary, as well as the following detailed description of illustrative embodiments, is better understood when read in conjunction with the appended drawings. For the purpose of illustrating the embodiments, there is shown in the drawings exemplary constructions of the embodiments; however, the embodiments are not limited to the specific methods and instrumentalities disclosed. In the drawings:

FIG. 1 is an illustration of an example environment for generating and using trajectories;

FIG. 2 is a block diagram of an implementation of an example track server;

FIG. 3 is an illustration of two example trajectories;

FIG. 4 is an illustration of an example process for determining similar trajectories using defined regions;

FIG. 5 is an illustration of an example process for determining similar trajectories using paths;

FIG. 6 is an operational flow of an implementation that uses clustering to identify similar tracks and provide information about the similar tracks;

FIG. 7 is an operational flow of an implementation of a method for identifying similar tracks using defined regions;

FIG. 8 is an operational flow of an implementation of a method for using paths to identify similar tracks;

FIG. 9 is an operational flow of an implementation of a method of identifying one or more tracks in response to a query;

FIG. 10 is a block diagram of a computing system environment in accordance with one implementation of the present system.

Detailed Description

FIG. 1 is an illustration of an example environment 100 for generating and using trajectories. In some implementations, a track may be a collection of location identifiers and temporal identifiers indicating times during which some or all of the location identifiers are determined. The track may also be associated with a user. The trajectory may purport to represent a path or route taken by the associated user. In some implementations, the mobile device 110 using a Global Positioning System (GPS) collects the location identifiers that make up the track.

As described above, environment 100 may include mobile device 110. Mobile device 110 may include a variety of mobile computer devices including, but not limited to, cellular telephones, personal digital assistants, video game devices, audio and video players, watches, dongles, laptop computers, or any other type of computer device. Mobile device 110 may be any computer device that may be carried around while a user travels. Thus, the mobile device 110 may be a cellular telephone that the user carries with him or a computer installed in the vehicle that the user drives. Example computing devices may include, for example, computing device 1000 shown in fig. 10.

As shown in fig. 1, mobile device 110 includes a locator 112. The locator 112 may be a component of the mobile device 110 that determines the location of the mobile device 110. In some implementations, the locator 112 may be a GPS device. Other types of devices may also be used. For example, the locator 112 may use cellular telephone signal information (e.g., distance from a cellular tower) or Wi-Fi signal information (e.g., distance from a Wi-Fi hotspot having a known location) to determine the location of the mobile device 110. In some implementations, the locator 112 may not be located at the mobile device 110, but may be located at an external entity (e.g., a telephone company, cellular telephone carrier, etc.) that may track the location of the mobile device 110. Any system, method, or technique for determining location may be used.

In some implementations, the locator 112 can periodically determine the location of the mobile device 110. The rate or frequency at which the locator 112 can determine the location can vary depending on the type of mobile device 110, or the method by which the locator 112 determines the location of the mobile device 110.

The locator 112 may store an identifier of the location in the local track store 114. Locator 112 may store an identifier of the location, as well as a time identifier of the time at which each identifier of the location was determined. In some implementations, the identifier of the location and the time identifier may be grouped together and stored as a track. As described above, a trajectory may be an identifier of a set of locations that represents a path taken by the mobile device 110. The track may have identified start and end positions. The starting and ending positions of the trajectory may be determined by a user of the mobile device 110 or automatically by the mobile device 110 based on a time lapse between each detected movement of the mobile device 110. For example, if the mobile device 110 has not moved from the identified location within an hour, the end of the trajectory may be determined. As will be further described, the start and end positions of the track may also be determined by, for example, the track application 118a or the track server 142.

The environment 100 may also include a stationary device 130. The stationary device 130 may be similar to the mobile device 110, but may lack or may not have access to the locator 112. The user may use an application at the stationary device 130 that uses the trajectory information to view and organize the trajectories associated with the user, view the trajectories associated with other users, and perform various trajectory-related functions. For example, the stationary device 130 may be implemented using a variety of computing devices, including the computing device 1000 shown in fig. 10.

The mobile device 110 may also include a track client 116 a. The track client 116a may control the operation of the locator 112 and the local storage 114, interface with a track application 118a executing on the mobile device 110, and connect to the server device 140 and/or the stationary device 130 via the network 120. Network 120 may be a variety of network types including the Public Switched Telephone Network (PSTN), a cellular telephone network, and a packet-switched network (e.g., the internet). The stationary device 130 may similarly include a track client 116 b. The track client 116b may interface with a track application 118b executing on a stationary device 130 over a network 120.

The track client 116a may interface with the track application 118a through an Application Programming Interface (API). The track application 118a may contain tracks and use the API to perform track operations. Examples of trajectory applications 118a may include an application that recommends a trajectory to a user based on the trajectory of the user and the trajectories of other users, an application that recommends stores to the user by identifying stores located near the trajectory associated with the user, an application that recommends a ride-through to the user based on the trajectory associated with the user, an application that provides driving directions, and an application that provides advertisements. Other types of applications may be used. By using the API with the track client 116a, various applications 118a may perform track operations. Examples of trajectory operations may include query, clustering, and compare trajectories. The track client 116b and track application 118b may perform similar functions and operations with respect to the fixed device 130.

The track clients 116a and 116b may communicate with a track server application 142 executing on the server device 140. For example, server device 140 may be implemented on a variety of computing devices, such as computing device 1000 shown in FIG. 10. As will be described further below, the track server application 142 may perform a variety of services and track-related computations for the track clients 116a and 116 b. Since mobile device 110 may have limited storage and processing capabilities, it may be desirable to perform such calculations on server device 140. However, there may be implementations where mobile device 110 may perform some or all of the functions of server device 140. In addition, it is contemplated that multiple mobile devices may together perform the functions of server device 140 in a peer-to-peer or other type of distributed computing arrangement

The track server 142 may receive one or more tracks from the track client 116 a. The trajectory client 116a may periodically upload the trajectory determined at the mobile device 110. In some implementations, tracks may have associated metadata. The metadata may be user generated, or may be automatically generated. For example, the metadata may include a user-generated description of the track, such as "sightseeing" or "good shopping. The metadata may also include images or photographs generated by the user, videos generated by the user, and/or advertisements, for example. The user may generate metadata using, for example, the track application 118a or 118 b.

In some implementations, the track server 142 may receive the location identifier and the time identifier from the mobile device 110 instead of the track. In these implementations, the track server 142 may generate tracks from the received location and time identifiers. Similar to the mobile device 110 described above, the track server 142 may generate tracks from location identifiers by grouping the location identifiers with temporally related location identifiers.

In some implementations, the track application 118a may control the locator 112 and determine the particular location identifiers that make up the track. For example, a track application 118a that is involved in helping a user to ride may activate the locator 112 only during typical commute times in the morning and afternoon, and may determine the start and end of a track based on the user's travel during those time periods. Similarly, the application 118a that relates to running (e.g., jogging) may specify the start and end of the trajectory based on user input indicating that the user is running or when the mobile device 110 detects that the user is likely running.

The track server 142 may store the tracks in the global track store 144. In some implementations, the entry of a track in the global track store may include each location and time identifier associated with the track. In some implementations, users of the track applications 116a and 118a may also associate metadata with their tracks. The metadata may include a variety of data and data types. For example, a user may associate comments, videos, links, sounds, descriptions, notes, or any other type of data with a track. In addition, the track applications 118a and 118b may associate their own application-specific metadata with the track. The metadata may also be associated with location identifiers that make up the track, rather than the entire track. The metadata may be stored with the track in global track store 144.

As will be further described below with reference to, for example, FIG. 2, the track server 142 may provide various services and operations for the track clients 116a and 116 b. In some implementations, the track server 142 may receive and respond to queries from the track clients 116a and 116 b. For example, the track clients 116a and 116b may request identifiers of tracks having particular metadata or belonging to particular users. In addition, the track server 142 may determine whether one track is similar to another track, or may identify all tracks that are similar to the tracks specified by the track clients 116a and 116 b. The track server 142 may provide other services, such as providing advertisements that are targeted to the track, or identifying businesses near or proximate to the track. Additionally, the track server 142 may control or enforce privacy settings on the track data. For example, a user may specify which users are able to view their tracks and mark the tracks as private. The track server 142 may consider these privacy settings when responding to queries. In addition, the user or application may specify one or more constraints for the query. Constraints may control the trajectory returned in response to a query. For example, the constraints may specify categories of tracks, tracks being a subset or superset of reference tracks, or tracks having a common start or end location identifier. Other constraints may also be used.

FIG. 2 is a block diagram of an implementation of an example track server 142. As shown, in one implementation, the track server 142 includes several components, including a query engine 210, an advertisement engine 240, a clustering engine 250, and a comparison engine 260. However, the track server 142 may support more or fewer components than those shown. The track server 142 may also access data, including a global track store 144, advertisement data 245, and user interest data 255, also shown in FIG. 1.

The clustering engine 250 may generate a "composite track" using two or more tracks associated with a user. For example, to compare users based on their associated trajectories, it may be difficult to compare all of the trajectories associated with the users. Similarly, the user typically repeatedly takes the same route or path, resulting in redundant paths stored in global trajectory storage 144. Thus, composite tracks may be generated for one or more users for the purpose of comparing and avoiding redundant data in global storage 144.

In some implementations, composite tracks may be generated by clustering the location identifiers associated with each track using a clustering algorithm or other techniques (such as k-means and k-median clustering). However, other clustering or averaging techniques may be used. For example, the clustering engine 250 may store the user's composite track into the global track store 144.

The clustered tracks may be clusters of some or all tracks associated with the user for a particular time period. For example, to determine a trajectory representing a morning commute for a user to go to work, clustering engine 250 may generate a clustering trajectory of user trajectories with time identifiers between 7 am and 9 am. In some implementations, the track server 142 may cluster similar tracks into clusters. Example methods for identifying similar tracks are discussed with reference to comparison engine 260.

The comparison engine 260 may compare two or more tracks and determine whether the two tracks are similar tracks. For example, the track application 118a may determine users with similar tracks in order to make recommendations regarding a ride-share arrangement for the users. To perform such a recommendation, the track application 118a or 118b may request, via the track client 116a or 116b, the track server 142 to identify users with similar tracks or to compare two or more identified tracks.

In some implementations, the comparison engine 260 can return a binary value (e.g., 0 or 1) indicating whether the two tracks are similar. In other implementations, the comparison engine 260 may return a percentage or score indicating the degree of similarity between the two tracks.

The content comprising similar tracks may vary depending on the requirements or other aspects of the track applications 118a and 118 b. For example, for some applications, only trajectories that share an endpoint and/or start point may be considered similar. Other applications may require only that one of the two tracks be a subset of the other. For example, a trajectory application 118a that involves ride-sharing may only require that smaller trajectories be a subset of larger trajectories so that at least one user can drive to pick up another user. Thus, the APIs exposed by the track clients 116a and 116b to the track applications 118a and 118b can support a variety of arguments that allow the applications to specify what their likeness implies, and how they want to get their results based on the application's needs.

In some implementations, the comparison engine 260 may compare the tracks by defining an area (such as a circle) around each identified location associated with the first track. The comparison engine 260 may then determine a percentage, or number, of the identified locations associated with the second track that fall within the defined area. The first and second tracks may be similar tracks if a sufficient number of identified locations from the second track fall within the defined area. The particular threshold percentage or number of identified locations that need to fall within the defined area may be determined by an application, administrator, or other user, and may depend on how accurately the trajectory application 118a or 118b needs to be. The size or radius of the defined area may be similarly selected or determined.

In some implementations, the size of each defined area may depend on or be a function of the amount of distance between the current identified location and the previous identified location in the trajectory, rather than being the same size. Each track may have a variable amount of identified location due to variations in the frequency and performance of different types of locators 112 in the mobile device 110 (such as GPS) and cellular location. This may result in location identifiers for similar tracks located outside the defined area, where the two tracks differ in location identifier density. To illustrate this, the size of the defined area around the current location identifier may be adjusted based on the amount of distance between the current location identifier and the previous location identifier. In particular, the size of the defined area may grow as the distance between the current location identifier and the previous location identifier grows.

For example, consider the sample traces 300a and 300b shown in fig. 3. The track 300a includes location identifiers 301a-309 a. The track 300b includes location identifiers 301b-309 b. FIG. 4 is an illustration of an example process for determining similar trajectories using defined areas, e.g., comparing trajectory 300a and trajectory 300b using defined areas having static or fixed sizes. More specifically, circles of fixed radius r have been defined around location identifiers 301a, 303a, 305a, 307a, and 309 a. These circles are shown in fig. 4 as circles 401, 403, 405, 407, and 409, respectively. Although the defined area is shown as a circle, it is for illustrative purposes only. Any type of shape or boundary may be used for the defined area. For example, implementations may use rectangles rather than circles.

As shown in FIG. 4, two of the location identifiers of the track 300b are located within the defined area. Location identifier 307b and location identifier 309b are located within circles 407 and 409, respectively. If, for example, 2 out of 5 are below the similarity threshold, the comparison engine 260 may determine that the traces 300a and 300b are not similar (i.e., dissimilar).

In other implementations, the comparison engine 260 may compare the first and second tracks by defining a path of width w through the identified locations of the first track, and determining the percentage of the identified locations of the second track that are within the defined path. Similar to the method using defined regions described above, the size of w selected and the threshold may determine the accuracy of the similarity comparison and may be specified by, for example, the trajectory application 118a or 118 b.

In some implementations, the size of w may vary based on the distance between the current location identifier and the previous location identifier, rather than a fixed width w. To illustrate the curve in the path, the value of w may be set to be approximately the distance between the current location identifier and the previous location identifier, for example. Other methods may also be used to determine the size of w.

For example, consider the sample trajectory shown in FIG. 3 anew. As shown in fig. 5, a path 501 of fixed width w through the track 300a is defined. Two of the location identifiers of the track 300b (i.e., 307b and 309 b) are located inside the defined path 501. Assuming again that 2 of 5 are below the similarity threshold, the comparison engine 240 may determine that the traces 300a and 300b are not similar.

The track server 142 may also include a query engine 210. The query engine 210 may receive queries from the mobile device 110 and the stationary device 130 via the track clients 116a and 116b, respectively. The query engine 210 may identify one or more tracks from the global track store 144 and may present the identified one or more tracks, or information related to the identified one or more tracks, such as metadata, for example.

In an implementation, the query that may be received by the query engine 210 may contain a request to identify similar tracks or to determine whether a first track is similar to a second track. These types of queries may be provided to the comparison engine 260 for processing. The query engine 210 may receive the results of the comparison, or may receive identifiers of one or more tracks that match the request. The query engine 210 may return the results and/or identifiers to the requesting user.

Another type of request that the query engine 210 may receive is to identify one or more tracks that match the user-specified keywords or constraints. For example, a user may request to view a track associated with hiking near their area. Thus, the query engine 210 may search the global trajectory store 144 for trajectories with labels or associated metadata including hiking. For example, the user may have added hiking to metadata associated with the track using one of the track applications 118a or 118 b. Additionally, the query engine 210 may also refine the search by only searching tracks from the global track store 144 that have identified locations near the user or near tracks associated with the user.

In some implementations, the query engine 210 may also search or access the user interest data 255. The user interest data 255 may include entries for users associated with the tracks from the global track store 144. The user interest data 255 may include data describing interests and/or characteristics of the user. The user interest data 255 may be user generated or may be automatically generated based on queries submitted by the user to the query engine 210 or submitted by other users with whom the user is a friend or associated. In some implementations, the user interest data 255 may be extracted from one or more social networking applications. For example, the user interest data 255 may include information such as information describing the user's demographic information (e.g., marital status, hometown, occupation, age, residence, etc.), tastes (e.g., hobbies, favorite movies, favorite television shows, etc.), and friends (e.g., an identifier of the other user with whom a user is a friend or connected).

The query engine 210 may fulfill queries from the user interest data 255. For example, a user may submit a query asking for one or more tracks representing tracks submitted by one or more of their friends. The query engine 210 may then retrieve from the global track store 144 one or more synthetic tracks associated with the user identified by the user interest data 255 as being a friend of the user. The user may also submit queries for trajectories from users having similar interests, tastes, or professions (e.g., as indicated by user interest data 255),

the track server 142 may also include an advertisement engine 240. The ad engine 240 may identify relevant ads from the ad data 245. In some implementations, the advertisement engine 240 may identify relevant advertisements in response to requests received by the query engine 210. Relevant advertisements may be identified based on the keywords. For example, a user may submit a query for tracks related to travel by submitting a "traveler" query. The advertisement engine 240 may then identify one or more advertisements related to travel or advertisements from advertisers who have paid or will pay to have their advertisements for display of the keyword "travel". One or more of the advertisements identified by the advertisement engine 240 may be returned with the results generated by the query engine 210 where they may be displayed by, for example, the track application 116a or 116 b.

In some implementations, the advertisement engine 240 may identify one or more advertisements from the advertisements based on the one or more tracks. For example, an advertiser may want to target an advertisement for a particular restaurant to a user when the user views a track having a location identifier located within a particular distance of the restaurant. Thus, when the query engine 210 returns this track, the ad engine 240 may cause the corresponding ad to also be returned.

In some implementations, the advertisement engine 240 may also identify advertisements based on a time indicator associated with the track. For example, the advertisement engine 240 may identify that the user is traveling to a particular coffee shop around 3 pm every weekday based on the user trajectory. Thus, recognizing that the user may be interested in coffee at that time, the advertisement engine 240 may display an advertisement or recommend a competitive coffee shop to the user at around 3 pm.

In some implementations, the advertisement engine 240 may identify one or more advertisements 240 based on the user interest data 255. For example, an advertiser may wish to display an advertisement to its associated user interest data 255 indicating users who are interested in food. The advertisement engine 240 may also identify advertisements based on a combination of query data, tracks, time indicators, and user interest data 255. For example, an advertiser may specify that an advertisement for a restaurant be displayed to a user whose user interest data indicates interest in food and who is typically eating outside based on the user's location during a meal time.

FIG. 6 is an operational flow of an implementation of a method 600 for using clusters to identify similar tracks and provide information about the similar tracks. The method 600 may be performed by, for example, the track server 142.

A plurality of tracks associated with a first user is identified (601). The track server 142 may identify tracks from the global track store 144 using a user identifier associated with the first user. In some implementations, the identified plurality of tracks associated with the first user may also be associated with an identified time or time period. For example, the identified track may be a track associated with the first user that occurs between 11 pm on saturday and 2 am, or between 8 am and 10 am on a weekday. In addition, metadata or tags may be used to identify multiple tracks. For example, the identified trajectory may be a trajectory associated with a "nightlife" or "commute" tag.

The identified plurality of tracks are clustered to generate a composite track for the first user (603). The identified tracks may be clustered by, for example, the clustering engine 250 of the track server 142. In some implementations, trajectories may be clustered using k-means or k-median clustering. Other methods for clustering may also be used. By clustering user trajectories, comparisons between trajectory-based users may be made easier because a single composite trajectory may be used rather than several possible redundant trajectories.

At least one track similar to the composite track is identified (605). The at least one similar track may be identified by, for example, the comparison engine 260 of the track server 142. Some example methods for identifying similar tracks are also described with reference to fig. 7 and 8.

Information related to similar tracks may be provided (607). This information may be provided by the query engine 210 and/or the advertisement engine 240 of the track server 142. In some implementations, the information may be an identifier of the at least one track. In other implementations, the information may be some or all of the metadata associated with the track, such as a user associated with the track, or a tag associated with the track. The information may also be, for example, one or more advertisements associated with the at least one track, or identifiers of businesses located near the at least one track.

FIG. 7 is an operational flow of an implementation of a method 700 for identifying similar tracks using defined regions. The method 700 may be implemented by, for example, the comparison engine 260 of the track server 142.

An area is defined around each location identifier of the composite track associated with the first user (701). The area may be defined by the comparison engine 260 of the track server 142. In some implementations, the defined area may be a circle; however, other shapes may be used. The size of each defined area may be fixed, or alternatively, the size of each defined area may vary based on the distance between the location identifier it surrounds and the previous location identifier. For example, in implementations where the defined areas are circles, the radius of each defined area may increase as the distance between a location identifier and a previous location identifier in the track increases.

A track is selected from a plurality of tracks associated with users other than the first user (703). The comparison engine 260 may select the track from the global track store 144 for comparison with the first user's composite track. Alternatively, the track may have been specified by, for example, the query engine 210 and/or the track application 118a or 118 b.

A percentage of location identifiers of the selected track that are within one of the defined areas is determined (705). This determination may be made by the comparison engine 260.

The percentage may be compared to a threshold. In one implementation, it is determined whether the percentage is greater than a threshold percentage (707). This determination may be made by the comparison engine 260. If it is determined that the percentage is greater than the threshold percentage, the selected trajectory may be identified as a similar trajectory (709). Otherwise, the selected tracks are identified as not similar (i.e., not similar) (711). Alternatively, the comparison engine 260 may generate a score or percentage describing the degree of similarity between the tracks.

FIG. 8 is an operational flow of an implementation of a method 800 for using paths to identify similar tracks. The method 800 may be implemented by, for example, the comparison engine 260 of the track server 142.

A path is defined through each location identifier of the composite track associated with the first user (801). The path may be defined by the comparison engine 260 of the track server 142. In some implementations, the width of the path through each location identifier may be fixed or constant. In other implementations, the width of the path at each location identifier may vary. For example, the width of the track at each location identifier may vary in proportion to the distance between that location identifier and the previous location identifier. In some implementations, the width may be set to be about the distance between the location identifier and the previous location identifier, although other sizes may be used, such as half the distance or, for example, twice the distance.

A track is selected from a plurality of tracks associated with users other than the first user (803). The comparison engine 260 may select the track from the global track store 144 for comparison with the first user's composite track. Alternatively, the track may have been specified by, for example, the query engine 210 and/or the track application 118a or 118 b.

A percentage of location identifiers of the selected track that are within the path is determined (805). This determination may be made by the comparison engine 260.

The percentage may be compared to a threshold. In one implementation, it is determined whether the percentage is greater than a threshold percentage (807). This determination may be made by the comparison engine 260. If it is determined that the percentage is greater than the threshold percentage, the selected track may be identified as a similar track (809). Otherwise, the selected tracks are identified as not similar (811). Alternatively, the comparison engine 260 may generate a score or percentage describing the degree of similarity between the tracks.

FIG. 9 is an operational flow of an implementation of a method 900 of identifying one or more tracks in response to a query. The method 900 may be implemented by the query engine 210, for example, the track server 142.

A query is received from a first user (901). The query may be received from a user at the query engine 210 of the track server 142. The query may include one or more terms describing what the first user is looking for. For example, the query may be a request to identify one or more tracks that are similar to the identified track. The query may include one or more keywords, and may be a request to identify one or more tracks or users associated with tracks matching the keywords. In some implementations, the query may also include a time identifier that describes a time constraint of the query. For example, the first user may request a track associated with the keyword "lunch" and associated with a time between 11 am and 2 pm.

One or more tracks responsive to the query are identified (903). The query engine 210 may identify the track from, for example, the global track store 144. In some implementations, one or more tracks are identified by matching one or more keywords or temporal identifiers associated with the query. Additionally, no tracks may be identified when no tracks are responsive to the query. In other implementations, one or more tracks may be further identified using a location identifier associated with the first user. For example, the first user may be located in Redmond, Washington. The query engine 210 may identify a track in or near Redmond, Washington, or more specifically, the first user's actual location in Redmond.

At least one of the identified tracks is presented to the first user (905). At least one of the identified tracks may be presented by the query engine 210 of the track server 142. The track may be presented to, for example, a track application 118a or 118b associated with the first user that initiated the query.

FIG. 10 illustrates an exemplary computing environment in which example embodiments and aspects may be implemented. The computing system environment is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality.

Numerous other general purpose or special purpose computing system environments or configurations may be used. Examples of well known computing systems, environments, and/or configurations that may be suitable for use include, but are not limited to, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, network Personal Computers (PCs), minicomputers, mainframe computers, embedded systems, distributed computing environments that include any of the above systems or devices, and the like.

Computer-executable instructions, such as program modules, may be used that are executable by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Distributed computing environments may also be used where tasks are performed by remote processing devices that are linked through a communications network or other data transmission medium. In a distributed computing environment, program modules and other data may be located in both local and remote computer storage media including memory storage devices.

With reference to FIG. 10, an exemplary system for implementing aspects described herein includes a computing device, such as computing device 1000. In its most basic configuration, computing device 1000 typically includes at least one processing unit 1002 and memory 1004. Depending on the exact configuration and type of computing device, memory 1004 may be volatile (such as Random Access Memory (RAM)), non-volatile (such as read-only memory (ROM), flash memory, etc.) or some combination of the two. This most basic configuration is illustrated in fig. 10 by dashed line 1006.

Computing device 1000 may have additional features or functionality. For example, computing device 1000 may also include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated in fig. 10 by removable storage 1008 and non-removable storage 1010.

Computing device 1000 typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by device 1000 and includes both volatile and nonvolatile media, removable and non-removable media.

Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Memory 1004, removable storage 1008 and non-removable storage 1010 are all examples of computer storage media. Computer storage media includes, but is not limited to, RAM, ROM, electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technology, CD-ROM, Digital Versatile Disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computing device 1000. Any such computer storage media may be part of computing device 1000.

Computing device 1000 may contain communication connections 1012 that allow the device to communicate with other devices. Computing device 1000 may also include input device(s) 1014 such as keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s) 1016 such as a display, speakers, printer, etc. may also be included. All of these devices are well known in the art and need not be discussed at length here.

It should be understood that the various techniques described herein may be implemented in connection with hardware or software or, where appropriate, with a combination of both. Thus, the methods and apparatus of the presently disclosed subject matter, or certain aspects or portions thereof, may take the form of program code (i.e., instructions) embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the presently disclosed subject matter.

While exemplary implementations may involve utilizing aspects of the presently disclosed subject matter in the context of one or more stand-alone computer systems, the subject matter is not so limited, but may be implemented in connection with any computing environment, such as a network or distributed computing environment. Further, aspects of the presently disclosed subject matter may be implemented in or across a plurality of processing chips or devices, and storage may similarly be effected across a plurality of devices. These devices may include, for example, personal computers, network servers, and handheld devices.

Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.

Claims (15)

1. A method, comprising:

storing a plurality of tracks, wherein each track comprises a plurality of location identifiers and time identifiers,

receiving a query from a user at a computing device over a network;

identifying, by the computing device, one or more tracks responsive to the query; and

presenting at least one of the identified tracks to the user over the network.

2. The method of claim 1, wherein the specified location identifier is specified as a start of the track and an end of each track.

3. The method of claim 1, wherein the track includes a start of track location identifier and an end of track location identifier.

4. The method of claim 1, wherein a track has metadata associated therewith.

5. The method of claim 1, wherein the location identifier has metadata associated therewith.

6. The method of claim 1, further comprising clustering tracks into a plurality of categories.

7. A method, comprising:

receiving, at a computer device over a network, a first trajectory and a constraint;

identifying, by the network, a second trajectory that is responsive to the constraint and that is different from the first trajectory at the computer device; and

a similarity between the first and the second trajectory is determined.

8. The method of claim 7, wherein the constraint is one of: the first track is a subset or superset of the second track, the first track having a same start position identifier as the second track or the first track having a same end position identifier as the second track.

9. The method of claim 7, wherein each track includes a plurality of location identifiers, and determining the similarity between the first and the second tracks comprises:

defining an area around each location identifier of the first track; and

determining a percentage of location identifiers of the second track that are within one of the defined areas.

10. The method of claim 9, wherein the defined area is a circle and defining an area around each location identifier comprises, for each location identifier of the first track:

determining a distance between the location identifier and a previous location identifier;

determining a radius of the defined area based on the determined distance; and

defining an area around the location identifier having the determined radius.

11. The method of claim 9, wherein the defined area is a rectangle and defining an area around each location identifier comprises, for each location identifier of the first track:

determining a distance between the location identifier and a previous location identifier; and

determining a width of the rectangle at the location identifier based on the determined distance.

12. The method of claim 11, wherein the width is a function based on the determined distance.

13. A system, comprising:

at least one server device storing a plurality of tracks, each track comprising a plurality of location identifiers and being associated with a user; and

a client device executing an application, wherein the application:

recording one or more tracks associated with the user based on one or more locations of the client device;

providing one or more tracks to the at least one server device for storage; and

one or more trace operations are performed on the stored plurality of traces via the application programming interface.

14. The system of claim 13, the track operations comprise querying, clustering, and comparing tracks.

15. The system of claim 13, wherein the application or server determines the start and end of the generated trajectory based on an amount of time that the client device is fixed, or based on other application-specific criteria.