Patent US4236514A successfully refreshed from Google Patents.
Patent US3834555A successfully refreshed from Google Patents.
Patent US5873081A successfully refreshed from Google Patents.
US5873081A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Document filtering via directed acyclic graphs
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-06-27
•
Granted: 1999-02-16
•
Expires: 2017-06-27
Abstract
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.
Inventors
- 👤 Dov Harel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 10:14
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/33; G06F16/335; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99935
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
170 words
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.
Claim 2
Independent Claim
170 words
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.
Claim 3
Dependent Claim
43 words
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.
Claim 4
Dependent Claim
47 words
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.
Claim 5
Dependent Claim
24 words
The method of claim 1 further comprising the step of predetermining which terms in the document match which terms in the directed acyclic graph.
Claim 6
Dependent Claim
16 words
The method of claim 1 wherein a batch of documents is filtered at the same time.
Claim 7
Dependent Claim
25 words
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.
Claim 8
Dependent Claim
68 words
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.
Claim 9
Dependent Claim
18 words
The method of claim 1 further comprising the step of maintaining a default truth value for each node.
Claim 10
Dependent Claim
69 words
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.
Claim 11
Dependent Claim
19 words
The method of claim 9 further comprising the step of resetting the truth values in the directed acyclic graph.
Claim 12
Dependent Claim
79 words
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.
Claim 13
Dependent Claim
24 words
The method of claim 11 wherein the level of truth of an internal node corresponds to the amount of deviation from the default value.
Claim 14
Dependent Claim
26 words
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.
Claim 15
Dependent Claim
20 words
The method of claim 1 wherein at least one of the operators embedded as internal nodes is a negation operator.
Claim 16
Dependent Claim
198 words
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.
Claim 17
Dependent Claim
198 words
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.
References Cited (Backward Citations)
US5175814A
Cited
US5265065A
Cited
US5418948A
Cited
US5488725A
Cited
US5430870A
Cited
US5765149A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-15 | 2002-08-17 | 2003-02-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-15 | 2006-08-17 | 2007-02-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-15 | 2010-08-17 | 2011-02-16 | $7700.00 | Window Closed / Lapsed |