Dynamic metadata filtering for classifier prediction

• US 7,925,645 B2
• Filed: 07/19/2007
• Issued: 04/12/2011
• Est. Priority Date: 07/19/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhao, Lei, Zhao, Yanbiao, Chen, Zhanliang
• Primary Examiner(s): Mahmoudi; Tony
• Assistant Examiner(s): Uddin; MD. I
• Application Number:
  US11/779,984
• Publication Number:
  US 20090024604A1
• Time in Patent Office: 1,363 Days
• Field of Search: 707/3, 707/4, 707/5, 707/601, 707/602, 707/736, 707/705, 707/714, 707/706, 707/713, 707/737, 707/752, 707/753, 707/754
• US Class Current: 707/714
• CPC Class Codes: G06F 16/3346 using probabilistic model

Abstract

A classifier is used to predict relevant results with arbitrary filtering conditions specified by the user. The classifier model is stored as a database table and joined with a metadata properties table instead of calculating the query result probability using the full classifier model. A user-specified query based filter is applied to the joined tables to obtain the list of documents satisfying the filter. The probability is then computed using the sub-model.

Claims

1. A method to be executed at least in part in a computing device for predicting query results in a document search system utilizing metadata properties, the method comprising:

receiving a user-specified metadata schema, the user-specified metadata schema comprising metadata stored according to a hierarchical structure;

generating the metadata property table based on the received schema;

receiving the metadata property table;

receiving a classifier model table, wherein the classifier model table comprises a sparse matrix of search terms, wherein the sparse matrix consumes significant system resources when processed;

joining the metadata property table and the classifier model table, wherein prior to joining the metadata property table and the classifier model table, the sparse matrix of search terms is condensed;

applying a filter condition to the joined table based on user-specified query conditions;

obtaining a list of documents satisfying the filter condition;

computing, using a sub-model, a probability of a document satisfying a user-specified query based on the list of documents, wherein computing, using the sub-model, comprises computing, for at least a first and second document in the list of documents, that a first probability of a first document is greater than a first probability of a second document if and only if a second probability of the first document is greater than a second probability of the second document, wherein the sub-model comprises the at least one filter condition applied to the joined metadata property table and the classifier model table; and

presenting the probability to the user.

2. The method of claim 1, wherein the metadata property table includes a column for a property identifier, a column for a property name, a column for a property type, and a column for a property value.

3. The method of claim 1, wherein the classifier model table includes a column for a search term, a column for documents where each search term can be found, and a column for a frequency of occurrence of the search term.

4. The method of claim 1, wherein the metadata properties include at least one of a single value property and a multi-value property.

5. The method of claim 1, wherein the same classifier model table is used without modification when the metadata property table is modified due to an update.

6. The method of claim 1, further comprising:

dynamically translating the filter condition to a Structured Query Language (SQL) where-clause for querying the classifier model table joined with the metadata property table.

7. The method of claim 1, wherein the classifier model is based on a Naï

ve Bayesian probability model.

8. The method of claim 1, wherein the probability is computed using:

9. A system for predicting query results in a document search system utilizing metadata properties, the system comprising:

a memory;

a processor coupled to the memory, capable of executing;

a service application configured to;

receive a user defined metadata schema, the user defined metadata schema comprising metadata stored according to a hierarchical structure;

generate a metadata property table based on the received schema;

a prediction engine configured to;

receive a classifier model table based on training data associated with documents stored by the document search system, wherein the classifier model table comprises a sparse matrix of search terms, wherein the sparse matrix consumes significant system resources when processed;

join the metadata property table and the classifier model table, wherein prior to joining the metadata property table and the classifier model table, the sparse matrix of search terms is condensed;

apply a filter condition to the joined table based on user-specified query conditions;

obtain a list of documents satisfying the filter condition; and

compute, using a sub-model, a probability of a document satisfying a user-specified query based on the list of documents, wherein computing, using the sub-model, comprises computing, for at least a first and second document in the list of documents, that a first probability of a first document is greater than a first probability of a second document if and only if a second probability of the first document is greater than a second probability of the second document, wherein the sub-model comprises the at least one filter condition applied to the joined metadata property table and the classifier model table.

10. The system of claim 9, wherein the service application is further configured to provide the probability to another application for presentation to a user requesting the query conditions.

11. The system of claim 9, further comprising:

a document store for storing documents searchable based on their metadata properties; and

a metadata store for storing metadata schema associated with the stored documents.

12. The system of claim 9, wherein the prediction engine is further configured to utilize a statistical algorithm that provides a monotone relationship between a probability of a document satisfying the user-specified query conditions based on a full classifier model and the probability of the document satisfying the user-specified query based on the list of documents.

13. The system of claim 12, wherein the statistical algorithm is based on a Naï

ve Bayesian model using a Bernoulli event model.

14. One or more computer-readable storage media, wherein the one or more computer-readable storage media do not consist of a propagated data signal, the one or more computer-readable storage media having stored thereon computer executable instructions that, when executed by a processor, predict query results in a document search system utilizing metadata properties, the instructions comprising:

receiving custom metadata schema, the custom metadata schema comprising metadata stored according to a hierarchical structure;

generating a metadata property table based on the received schema;

receiving a classifier model matrix based on a training data set associated with documents processed by the system, wherein the classifier model matrix comprises a sparse matrix of search terms, wherein the sparse matrix consumes significant system resources when processed;

generating a classifier model table from the sparse classifier model matrix;

joining the metadata property table and the classifier model table, wherein prior to joining the metadata property table and the classifier model table, the sparse matrix of search terms is condensed;

applying at least one filter condition to the joined table based on user-specified query conditions;

obtaining a list of documents satisfying the at least one filter condition; and

computing, using a sub-model, a probability of a document satisfying a user-specified query based on the list of documents, wherein computing, using the sub-model, comprises computing, for at least a first and second document in the list of documents, that a first probability of a first document is greater than a first probability of a second document if and only if a second probability of the first document is greater than a second probability of the second document, wherein the sub-model comprises the at least one filter condition applied to the joined metadata property table and the classifier model table.

15. The one or more computer-readable storage media of claim 14, wherein the instructions further comprise:

dynamically translating the at least one filter condition to an SQL where-clause for querying the classifier model table joined with the metadata properties table.

16. The one or more computer-readable storage media of claim 14, wherein the metadata property table includes a column for a property identifier, a column for a property name, a column for a property type, and a column for each property value;

and wherein the classifier model table includes a column for a search term, a column for documents where each search term can be found, and a column for a frequency of occurrence of the search term.

17. The one or more computer-readable storage media of claim 14, wherein the instructions further comprise:

enabling use of multi-value properties by generating row-based property tables that include a separate row for each value of a multi-value property and joining the row-based property tables with the classifier model table.

18. The one or more computer-readable storage media of claim 14, wherein the instructions further comprise:

enabling a query for performing the search to define a plurality of schemas to be included in the search.