Mobile Query Suggestions With Time-Location Awareness

• US 20120136855A1
• Filed: 11/29/2010
• Published: 05/31/2012
• Est. Priority Date: 11/29/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ni, Xiaochuan, Sun, Jian-Tao, Chen, Zheng
• Granted Patent: US 8,489,625 B2
• Time in Patent Office: Days
• US Class Current: 707/724
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

The techniques describe recommending mobile query suggestions by integrating time and location in response to a query input submitted on a mobile computing device. A process constructs a bipartite graph by extracting users that submitted queries from mobile search logs and associating time and location with the submitted queries. The process determines the users are similar having submitted similar queries at similar times and at similar locations. The process receives a query input associated with a current time and a current location of a mobile computing device. Next, the process computes a relatedness of candidate queries to the query input based on a similarity between the user groups having submitted both the candidate queries and the query input, and distances of times and locations at which the user previously issued the query input and the candidate queries.

Claims

1. A method implemented at least partially by a processor, the method comprising:

constructing a bipartite graph by extracting queries from mobile search logs and identifying users that sent the queries, times at which the users sent the queries, and locations from which the users sent the queries;

calculating a similarity between the users from the bipartite graph based at least in part on similarities between the queries, the times at which the users submitted the queries, and the locations from which the users submitted the queries;

receiving, from a mobile computing device of a particular user, a query input associated with a current time and with a current location of the mobile computing device; and

at least partly in response to the receiving of the query input;

identifying, from the bipartite graph, one or more queries previously submitted by users that have previously submitted the query input, the one or more other queries comprising candidate queries; and

computing a relatedness of each of the candidate queries to the received query input based at least in part on;

(1) a calculated similarity between a respective user that submitted the candidate query and the particular user, (2) a difference between the current time associated with the received query input and a time when the candidate query was submitted, and (3) a distance between the current location associated with the received query input and a location where the candidate query was submitted.

2. The method of claim 1, wherein the calculating of the similarities of the users comprises:

using distribution vectors to represent the times of the queries submitted by a first user and a second user;

representing the times of the queries submitted by the first user and the second user based on a 24-dimension vector as a count to identify an hour of a day; and

applying a cosine similarity function to compute a distance of the distribution vectors representing the times of the queries submitted by the first user and the second user to identify an hour between the distribution vectors.

3. The method of claim 1, further comprising:

ranking the candidate queries based at least in part on the computed relatedness of each of the candidate queries to the received query input; and

suggesting at least a portion of the candidate queries based at least in part on the ranking.

4. The method of claim 1, further comprising:

ranking the candidate queries based at least in part on the computed relatedness of each of the candidate queries to the received query input; and

recommending at least a portion of the candidate queries based at least in part on the candidate queries and the received query input have many common users, both submitted the received query input about a same time, and both submitted the received query input at about a same location of mobile computing devices.

5. The method of claim 1, further comprising providing one or more of the candidate queries as query suggestions in a descending order that is based at least in part on the computed relatedness of each of the candidate queries to the query input.

6. The method of claim 1, further comprising removing, from the mobile search logs, submitted queries that are not associated with time and location information.

7. The method of claim 1, wherein the computing the relatedness further comprises:

computing a weight of for a user that previously submitted the received query input based at least in part on measuring distances between (1) a time and a location at which the user has previously submitted the received query input, and (2) the current time and the current location.

8. The method of claim 7, applying the computed weight to one or more candidate queries, wherein the computed weight is higher based at least in part on being relative close to the current time and to the current location.

9. One or more computer-readable storage media encoded with instructions that, when executed by a processor, perform acts comprising:

receiving, from a mobile computing device of a particular user, a query input associated with a current time and with a current location of the mobile computing device; and

at least partly in response to the receiving of the query input;

accessing a query-user graph constructed from mobile search logs that identifies for, each of multiple queries, a user that sent the query, a time at which the user sent the query, and a location from which the user sent the query; and

identifying candidate queries that are related to the query input based at least in part on;

calculating a similarity between the users from the query-user graph based at least in part on similarities between the queries, the times at which the users submitted the queries, and the locations from which the users submitted the queries, and

calculating a relatedness of each of the candidate queries to the received query input based at least in part on;

(i) a difference between the current time associated with the received query input and a time when the candidate query was submitted, and (ii) a distance between the current location associated with the received query input and the location where the candidate query was sent.

10. The computer-readable storage media of claim 9, wherein the mobile search logs include, for at least a portion of the multiple queries, a location of where the query was submitted as global positioning system (GPS) coordinates in a longitude and a latitude pair.

11. The computer-readable storage media of claim 9, wherein the candidate queries comprise at least a portion of multiple queries previously submitted by users represented in the query-user graph that have previously submitted the received query input.

12. The computer-readable storage media of claim 9, wherein the calculating the similarity comprises:

representing the times of queries submitted by a first user and a second user using 24-dimension vectors to identify an hour of a day; and

applying a cosine similarity function to compute a distance of the 24-dimension vectors representing the times of the queries submitted by the first user and the second user to identify an hour between the 24-dimension vectors.

13. The computer-readable storage media of claim 9, wherein the calculating the relatedness further comprises:

computing a weight of a user based at least in part on measuring distances between a time and a location at which the user has previously submitted the received query input and the current time and the current location; and

applying the computed weight to one or more candidate queries.

14. The computer-readable storage media of claim 9, further comprising serving a user interface for display on the mobile computing device, the user interface to access a service application that provides mobile query searches.

15. The computer-readable storage media of claim 9, further comprising ranking the candidate queries based at least in part on the calculated relatedness of each of the candidate queries to the received query input.

16. A system comprising:

a memory;

a processor coupled to the memory;

a bipartite graph module stored in the memory and executable on the processor to construct a bipartite graph from mobile search logs to identify queries from mobile search logs and to identify, for each of the queries, a user that sent a query, a time at which the user sent the query, and a location from which the user sent the query; and

a similarity module stored in the memory and executable on the processor to compute a similarity between the users from the bipartite graph based at least in part on similarities between;

(1) the queries, (2) the times at which the users submitted the queries, and (3) the locations from which the users submitted the queries.

17. The system of claim 16, further comprising:

a time-location awareness application module stored in the memory and executable on the processor to receive, from a mobile computing device of a particular user, a query input associated with a current time and a current location of the mobile computing device; and

a relatedness module stored in the memory and executable on the processor to compute a relatedness of each of multiple candidate queries to the query input based at least in part on the calculated similarity between the users, calculating a difference between the current time associated with the received query input and a time when the candidate query was submitted, and calculating a distance between the current location associated with the received query input and a location where the candidate query was submitted.

18. The system of claim 16, wherein the bipartite graph module is further executable on the processor to construct the bipartite graph by representing each of the users as a vertex, the query sent by the user as another vertex, and a time at which the user sent the query and a location from which the user sent the query represented as an edge, the edge representing an issuing action from the user when submitting the query.

19. The system of claim 16, further comprising:

a time-location awareness application module stored in the memory and executable on the processor to receive, from a mobile computing device of a particular user, a query input associated with a current time and a current location of the mobile computing device;

and wherein the bipartite graph module is further executable on the processor to;

construct the bipartite graph by representing each of the users and the a query sent by the user as two nodes and by representing the time at which the user sent the query and the location from which the user sent the query represented as an edge of the bipartite graph; and

calculate distances between the current time and the current location and the times and the locations with the edges between the two nodes.

20. The system of claim 16, wherein the similarity module is further executable on the processor to:

represent times of queries submitted by a first user and a second user based on a 24-dimension distribution vector to identify an hour of a day; and

apply a cosine similarity function to compute a distance of the 24-dimension distribution vectors representing the times of the queries submitted by the first user and the second user to identify an hour between the distribution vectors.