Document filtering via directed acyclic graphs
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
15 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
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.
-
Specification