Evaluation of content of a data set using multiple and/or complex queries
First Claim
1. A method for evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the contents of the set of data capable of being described by one or more pieces of evidence, the queries being arranged in an execution plan of queries in which each query is operably related to one or more other queries, each of the plurality of queries including one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence, the method comprising the steps of:
- comparing each piece of evidence as the data set is received to one or more of the evidence descriptors;
identifying each evidence descriptor that is satisfied by a piece of evidence;
evaluating each query term that includes a satisfied evidence descriptor or another query term that has been satisfied to determine whether the query term is satisfied; and
identifying each query for which all query terms have been satisfied as a query that is satisfied by the set of data.
4 Assignments
0 Petitions
Accused Products
Abstract
The invention enables evaluation of the content of a set of data to determine whether the data set satisfies one or more queries. The invention enables rapid evaluation of large numbers of data sets much more rapidly than has previously been possible, even when the number of queries is large and/or the queries are complex. The queries are evaluated using an execution plan of query terms that is constructed from one or more specified queries by translating each query term of each query into one or more evidence descriptors and one or more combination operators, and operably relating each of the combination operators to at least one of the evidence descriptors or other combination operators, such that each query is defined by one or more of the evidence descriptors and one or more of the combination operators that are operably related to each other. Preferably, none of the evidence descriptors or combination operators are duplicated in the execution plan. The invention can be used to evaluate data sets of a variety of types, such as text documents and databases. The invention can be further optimized to achieve rapid evaluation of a data set with respect to the queries in two steps. First, one or more candidate queries that may be satisfied by the data set are identified by approximately evaluating each query. Second, each of the candidate queries is fully evaluated to determine whether the candidate query is satisfied by the data set.
-
Citations
57 Claims
-
1. A method for evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the contents of the set of data capable of being described by one or more pieces of evidence, the queries being arranged in an execution plan of queries in which each query is operably related to one or more other queries, each of the plurality of queries including one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence, the method comprising the steps of:
-
comparing each piece of evidence as the data set is received to one or more of the evidence descriptors; identifying each evidence descriptor that is satisfied by a piece of evidence; evaluating each query term that includes a satisfied evidence descriptor or another query term that has been satisfied to determine whether the query term is satisfied; and identifying each query for which all query terms have been satisfied as a query that is satisfied by the set of data. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14, 15, 16, 17, 24, 25, 26, 27)
-
-
9. A method for evaluating a set of data to enable identification of, from a plurality of queries that each include at least one evidence descriptor, each candidate query that may be satisfied by the set of data, the method comprising the steps of:
-
identifying the type of each of the evidence descriptors; identifying the type of each piece of evidence in the set of data; comparing each piece of evidence in the set of data to each of the evidence descriptors that are of the same type as the piece of evidence; and identifying each of the evidence descriptors that is satisfied by a piece of evidence, wherein only a query including a satisfied evidence descriptor can be a candidate query. - View Dependent Claims (10)
-
-
18. A method for evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, each query having a query term and an approximation of the query term, comprising the steps of:
-
identifying one or more candidate queries that may be satisfied by the set of data using the approximation of the query term; and evaluating each of the candidate queries using the query term to determine which, if any, of the candidate queries are satisfied by the set of data. - View Dependent Claims (19, 20, 21, 22, 23)
-
-
28. A method for use in evaluating a set of data to determine whether the set of data satisfies one or more queries, the one or more queries including a plurality of evidence descriptors that can be compared to one or more pieces of evidence that represent a portion of the content of the set of data to ascertain whether a piece of evidence satisfies an evidence descriptor, the method comprising the steps of:
-
defining one or more types of evidence; identifying the type or types of the evidence descriptors; and modifying the one or more types of evidence in response to the identified type or types of evidence descriptors. - View Dependent Claims (29, 30, 31)
-
-
32. A method for constructing an execution plan of queries for use in evaluating a set of data to determine whether the set of data satisfies one or more of the queries, comprising the steps of:
-
inputting a plurality of queries; and operably relating each query to another query. - View Dependent Claims (33, 34, 35, 36, 37, 38, 39, 40, 41)
-
-
42. A method for constructing an execution plan of queries for use in evaluating a set of data to determine whether the set of data satisfies one or more of the queries, the contents of the set of data capable of being described by one or more pieces of evidence, the method comprising the steps of:
-
inputting a plurality of queries; translating each query into one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence; and defining, for at least one evidence descriptor or combination operator, a corresponding approximation of the evidence descriptor or combination operator. - View Dependent Claims (43)
-
- 44. An execution plan stored within a memory for use in controlling a system for evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the execution plan comprising a plurality of independent queries, wherein each of the queries of the execution plan has one or more query terms and each query sharing a query term with another query so that the queries are operably related to another of the queries of the execution plan.
- 46. An execution plan stored in a memory for use in evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the contents of the set of data being described by one or more pieces of evidence, the execution plan comprising a plurality of queries, each query including one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence, wherein at least one evidence descriptor is shared by more than one query term.
-
49. An execution plan stored in a memory for use in evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the contents of the set of data being described by one or more pieces of evidence, the execution plan comprising a plurality of queries, each query including one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence, wherein each evidence descriptor of a query term that is equivalent to an evidence descriptor of another query term is shared with that query term, and wherein each combination operator of a query term that is equivalent to a combination operator of another query term is shared with that query term.
- 50. An execution plan stored in a memory for use in evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the contents of the set of data capable of being described by one or more pieces of evidence, the execution plan comprising a plurality of queries wherein each query including one or more query terms, each query term including one or more evidence descriptors that can be operably related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence, wherein for at least one evidence descriptor or combination operator, a corresponding approximation of the evidence descriptor or combination operator is defined.
-
52. A system for evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the contents of the set of data capable of being described by one or more pieces of evidence, the queries being arranged in an execution plan of queries in which each query is operably related to one or more other queries, each of the plurality of queries including one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence, the system comprising:
-
means for comparing each piece of evidence to one or more of the evidence descriptors as the data set is received; means for identifying each evidence descriptor that is satisfied by a piece of evidence; means for evaluating each query term that includes a satisfied evidence descriptor or another query term that has been satisfied to determine whether the query term is satisfied; and means for identifying each query for which all query terms have been satisfied as a query that is satisfied by the set of data.
-
-
53. A system for evaluating a set of data to enable identification of, from a plurality of queries that each include at least one evidence descriptor, each candidate query that may be satisfied by the set of data, the system comprising:
-
means for identifying the type of each of the evidence descriptors; means for identifying the type of each piece of evidence in the set of data; means for comparing each piece of evidence in the set of data to each of the evidence descriptors that are of the same type as the piece of evidence; and means for identifying each of the evidence descriptors that is satisfied by a piece of evidence, wherein only a query including a satisfied evidence descriptor can be a candidate query.
-
-
54. A system for evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, each query having a query term and an approximation of the query term, comprising:
-
means for identifying one or more candidate queries based on the approximation of the query term that may be satisfied by the set of data; and means for evaluating each of the candidate queries based on the query term to determine which, if any, of the candidate queries are satisfied by the set of data.
-
-
55. A system for use in evaluating a set of data to determine whether the set of data satisfies one or more queries, the one or more queries including a plurality of evidence descriptors that can be compared to one or more pieces of evidence that represent a portion of the content of the set of data to ascertain whether a piece of evidence satisfies an evidence descriptor, the system comprising:
-
means for defining one or more types of evidence; means for identifying the type or types of the evidence descriptors; and means for modifying the one or more types of evidence in response to the identified type or types of evidence descriptors.
-
-
56. A system for constructing an execution plan of queries for use in evaluating a set of data to determine whether the set of data satisfies one or more of the queries, comprising:
-
means for inputting a plurality of queries; and means for operably relating each query to another query.
-
-
57. A system for constructing an execution plan of queries for use in evaluating a set of data to determine whether the set of data satisfies one or more of the queries, the contents of the set of data capable of being described by one or more pieces of evidence, the system comprising:
-
means for inputting a plurality of queries; means for translating each query into one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence; and means for defining, for at least one evidence descriptor or combination operator, a corresponding approximation of the evidence descriptor or combination operator.
-
Specification