Document filtering via directed acyclic graphs

• US 5,873,081 A
• Filed: 06/27/1997
• Issued: 02/16/1999
• Est. Priority Date: 06/27/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Harel, Dov
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US08/883,286
• Time in Patent Office: 599 Days
• Field of Search: 707/4, 707/5, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and mechanism for for filtering incoming documents against user queries. A plurality of user queries including terms connected by logical operators is received. Terms and sub-expressions are combined into distinct sub-expressions and embedded into a directed acyclic graph (DAG) having a plurality of nodes. Each node in the DAG includes pointers to any successor nodes thereof, the terms in the queries are embedded as source nodes in the graph, and the operators embedded as internal nodes. When a document is received, the document is evaluated against the nodes in the DAG by comparing the relevant terms in the document with the source nodes in the DAG representative thereof. For each term that matches a source node, the internal successor node of the matched source node is evaluated based on the logical operator represented by the successor node and truth information of the predecessor nodes thereto, thereby determining a truth value of the internal successor node. Information is returned indicative of which of the successor nodes were evaluated as true. From that information, the queries which matched the document and the users corresponding thereto can be determined.

Claims

1. A method of filtering incoming documents against user queries, comprising the steps of:

receiving a plurality of user queries, the queries including terms connected by logical operators;

embedding the user queries in a directed acyclic graph having a plurality of nodes, each node in the graph including pointers to any successor nodes thereof, the terms in the queries embedded as source nodes in the graph and the operators embedded as internal nodes;

receiving at least one document;

evaluating the at least one document against the directed acyclic graph by comparing at least some of the terms in said document with the source nodes in the directed acyclic graph, and for each term that matches a source node, evaluating an internal successor node of the matched source node based on the logical operator represented by the successor node and truth information of the predecessor nodes thereto, to determine a truth value of said internal successor node; and

returning truth information indicative of which of the successor nodes were evaluated as true.

2. The method of claim 1 wherein the step of embedding the user queries in a directed acyclic graph includes the steps of combining common terms into a distinct set of terms, and

embedding terms from the distinct set of terms into the graph.

3. The method of claim 1 wherein the step of embedding the user queries in a directed acyclic graph includes the steps of combining common sub-expressions of terms and operators into a distinct set of sub-expressions, and embedding sub-expressions from the distinct set of sub-expressions into the graph.

4. The method of claim 1 further comprising the step of predetermining which terms in the document match which terms in the directed acyclic graph.

5. The method of claim 1 wherein a batch of documents is filtered at the same time.

6. The method of claim 1 further comprising the step of passing truth information from an evaluated predecessor node to each of the successor nodes thereof.

7. The method of claim 1 further comprising the step of maintaining pointers from each successor node to the predecessor nodes thereof, wherein the step of evaluating an internal successor node of the matched source node based on the logical operator represented by the successor node and truth information of the predecessor nodes thereto includes the step of determining the truth of each predecessor node via the pointer thereto.

8. The method of claim 1 further comprising the step of maintaining a default truth value for each node.

9. The method of claim 8 wherein the step of evaluating an internal successor node of the matched source node based on the logical operator represented by the successor node and truth information of the predecessor nodes thereto, includes the step of comparing the truth based thereon with the default truth value and determining that the internal node is true when the evaluated value does not equal the default value.

10. The method of claim 9 further comprising the step of resetting the truth values in the directed acyclic graph.

11. The method of claim 8 wherein each default value is a probability value, and wherein the step of evaluating an internal successor node of the matched source node based on the logical operator represented by the successor node and truth information of the predecessor nodes thereto, includes the step of comparing the evaluated truth value based on the predecessor nodes with the default truth value of the successor node to determine a level of truth of the successor node.

12. The method of claim 11 wherein the level of truth of an internal node corresponds to the amount of deviation from the default value.

13. The method of claim 11 wherein the internal node is considered false when the amount of deviation from the default value is below a threshold amount.

14. The method of claim 1 wherein at least one of the operators embedded as internal nodes is a negation operator.

15. A mechanism for filtering incoming documents against user queries, comprising:

a memory for receiving a plurality of user queries, the queries including terms connected by logical operators;

means for embedding the user queries into a directed acyclic graph in the memory, the directed acyclic graph having a plurality of nodes, wherein the terms in the queries embedded as source nodes in the graph and the operators embedded as internal nodes and each node in the graph includes pointers to any successor nodes thereof;

means for receiving a document;

means for determining which terms in the document correspond to which terms embedded in the directed acyclic graph;

means for evaluating the document against the directed acyclic graph including means for comparing at least some of the terms in the document with the source nodes in the directed acyclic graph;

means for evaluating an internal successor node of each term that matches a source node based on the logical operator represented by the successor node and truth information of the predecessor nodes thereto, to determine a truth value of said internal successor node; and

means for returning truth information indicative of which of the successor nodes were evaluated as true.