Location-Aware Search Ranking

• US 20120317087A1
• Filed: 06/07/2011
• Published: 12/13/2012
• Est. Priority Date: 06/07/2011
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lymberopoulos, Dimitrios, Konig, Arnd C., Zhao, Peixiang, Liu, Jie, Berberich, Klaus L.
• Application Number:
  US13/154,456
• Publication Number:
  US 20120317087A1
• Time in Patent Office: Days
• US Class Current: 707/706
• CPC Class Codes: G06F 16/24578 using ranking

Abstract

A training system is described for generating at least one ranking module using features derived, in part, from region information. The region information encodes characteristics about regions which are associated with queries in search log data. A query processing system is also described for applying the ranking model generated by the training system to process queries in real time. In one implementation, the training system can also generate plural ranking models corresponding to plural respective map areas. The training system can also generate a mapping model which correlates each region with a ranking model to be applied when processing queries that originate from that region. The query processing system can process a query by determining a region associated with the query and then identifying and applying a ranking model which corresponds to the region.

Claims

1. A method, implemented by computing functionality, for providing at least one ranking model, comprising:

receiving original search log data that provides information regarding searches conducted by a plurality of users;

storing the original search log data in a data store;

augmenting the original search log data with region identifiers, to provide augmented search log data, each region identifier identifying a region associated with a query in the original search log data;

storing the augmented original search data in a data store;

generating features associated with the augmented search log data based on, at least in part, region information, the region information encoding characteristics about regions which are associated with the queries in the augmented search log data;

storing the features;

training at least one ranking model based on at least the features; and

storing said at least one ranking model,

wherein said receiving, storing the original search log data, augmenting, storing the augmented search log data, generating, storing the features, training, and storing said at least one ranking model are performed by the computing functionality.

2. The method of claim 1, wherein one feature encodes a population density of a region from which a query originated.

3. The method of claim 1, wherein one feature encodes an average traveling distance for a region from which a query originated, the average traveling distance corresponding to an average distance that users are willing to travel to reach target entities.

4. The method of claim 1, wherein one feature encodes a standard deviation of traveling distances for a region from which the query originated, the traveling distances corresponding to distances that users are willing to travel to reach target entities.

5. The method of claim 1, wherein one feature encodes a self-sufficiency value for a region from which a query originated, the self-sufficiency value indicating an extent to which users within the region have selected target entities outside the region in response to queries issued by the users.

6. The method of claim 1, wherein one feature encodes a fractional value for a region from which a query originated, the fractional value indicating a fraction of query volume that the region receives, with respect to a total volume associated with a more encompassing region.

7. The method of claim 1, wherein the features for a query include at least:

a first feature that encodes a population density of a region from which the query originated;

a second feature that encodes an average traveling distance for the region, the average traveling distance corresponding to an average distance that users are willing to travel to reach target entities;

a third feature that encodes a standard deviation of the traveling distances for the region;

a fourth feature that encodes a self-sufficiency value for the region, the self-sufficiency value indicating an extent to which users within the region have selected target entities outside the region in response to queries issued by the users; and

a fifth feature that encodes a fractional value for the region, the fractional value indicating a fraction of query volume that the region receives, with respect to a total volume associated with a more encompassing region.

8. The method of claim 1, wherein said training of said at least one ranking module comprises training a single ranking model that implicitly takes into account characteristics of different regions.

9. The method of claim 1, further comprising:

partitioning the augmented search log data into a plurality of datasets, each dataset corresponding to a respective map area,

wherein said generating is performed for each dataset to produce a plurality of collections of features, and

wherein said training is performed on the plurality of collections of features to produce a plurality of respective ranking models, each ranking model being associated with a respective map area.

10. The method of claim 9, further comprising:

testing a performance of each ranking model for each map area with respect to a dataset associated with each region, to provide a plurality of performance results for the respective regions; and

determining a mapping model based on the plurality of performance results, the mapping model mapping each region to a ranking model to be used to process queries in a query-time phase of operation.

11. The method of claim 1, further comprising deploying said at least one ranking model in a query processing system for processing new queries.

12. The method of claim 11, wherein a query-time phase of operation of the query processing system comprises:

receiving a new query from a user;

augmenting the new query with a region identifier, the region identifier identifying a region from which the new query originated;

generating sets of features for the augmented query based on, at least in part, region information that encodes characteristics about the region from which the new query originated;

a ranking module for generating search results for the augmented query based on the sets of features, using a ranking model; and

sending the search results to the user.

13. A query processing system, comprising:

an interface for receiving a query from a user;

a query augmentation module for augmenting the query with a region identifier, the region identifier identifying a region from which the query originated;

a feature generation module for generating sets of features for the augmented query based on, at least in part, region information that encodes characteristics about the region from which the query originated; and

a ranking module for generating search results for the augmented query based on the sets of features, using a ranking model,

the interface configured to send the search results to the user.

14. The query processing system of claim 13, wherein each set of features for the query includes at least one of:

a first feature that encodes a population density of the region from which the query originated;

a second feature that encodes an average traveling distance for the region, the average traveling distance corresponding to an average distance that users are willing to travel to reach target entities;

a third feature that encodes a standard deviation of the traveling distances for the region;

a fourth feature that encodes a self-sufficiency value for the region, the self-sufficiency value indicating an extent to which users within the region have selected target entities outside the region in response to queries issued by the users; and

a fifth feature that encodes a fractional value for the region, the fractional value indicating a fraction of query volume that the region receives, with respect to a total volume associated with a more encompassing region.

15. The query processing system of claim 14, wherein each set of features includes two or more of said first through fifth features.

16. The query processing system of claim 13, further comprising a data store which provides a plurality of ranking models for respective map areas, and wherein the ranking model that is used by the ranking module is selected from the plurality of ranking models in the data store.

17. The query processing system of claim 13, further comprising:

a model selecting module for mapping, based on a mapping model, the query identifier associated with the query to a ranking model identifier, and

wherein the ranking model that is used by the ranking module is associated with the ranking model identifier.

18. A computer readable storage medium for storing computer readable instructions, the computer readable instructions providing a training system when executed by one or more processing devices, the computer readable instructions comprising:

logic for receiving augmented search log data that provides information regarding searches conducted by a plurality of users, together with region identifiers, each region identifier identifying a region associated with a query in the augmented search log data;

logic for forming region information based on the augmented search log data, the region information encoding characteristics about regions which are associated with queries in the augmented search log data, the region information comprising two or more of;

population information that encodes population densities of respective regions from which queries in the augmented search log data originated;

average traveling distance information that encodes average traveling distances for the respective regions, each average traveling distance corresponding to an average distance for a particular region that users are willing to travel to reach target entities;

standard deviation information that encodes standard deviations for the respective regions, each standard deviation indicating a standard deviation of the traveling distances for a particular region;

self-sufficiency information that encodes self-sufficiency values for the respective regions, each self-sufficiency value indicating an extent to which users within a particular region have selected target entities outside the region in response to queries issued by the users; and

fractional volume information that encodes fractional values for the respective regions, each fractional value indicating a fraction of query volume that a particular region receives, with respect to a total volume associated with a more encompassing region; and

storing the region information in a data store.

19. The computer readable storage medium of claim 18, wherein the region information includes all of the population information, average traveling distance information, standard deviation information, self-sufficiency information, and fractional volume information.

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

logic for generating features associated with the augmented search log data based on, at least in part, the region information;

logic for storing the features;

logic for training at least one ranking model based on, at least in part, the features; and

logic for storing said at least one ranking model.