System, method and computer program product for performing unstructured information management and automatic text analysis, including a search operator functioning as a Weighted AND (WAND)
View Patent ↗Disclosed is a system architecture, components and a searching technique for an Unstructured Information Management System (UIMS). The UIMS may be provided as middleware for the effective management and interchange of unstructured information over a wide array of information sources. The architecture generally includes a search engine, data storage, analysis engines containing pipelined document annotators and various adapters. The searching technique makes use of a two-level searching technique. A search query includes a search operator containing of a plurality of search sub-expressions each having an associated weight value. The search engine returns a document or documents having a weight value sum that exceeds a threshold weight value sum. The search operator is implemented as a Boolean predicate that functions as a Weighted AND (WAND).
1. A data processing system for processing stored data, comprising:
data storage for storing a collection of data units; and
coupled to the data storage, a search engine responsive to a query for retrieving at least one data unit from said data storage; where
the query comprises a search operator comprised of a plurality of search sub-expressions each having an associated weight value, and where said search engine returns a data unit having a weight value sum that exceeds a threshold weight value sum; and
where said search operator comprises a weighted AND function, where varying the threshold weight value varies the operation of the weighted AND function from being substantially a logical OR function to being substantially a logical AND function.
2. A data processing system as in claim 1 , where said data units comprise documents.
3. A data processing system as in claim 1 , where at least one of the weight values and threshold weight value are variable during a search.
4. A data processing system for processing stored data, comprising:
data storage for storing a collection of data units; and
coupled to the data storage, a search engine responsive to a query for retrieving at least one data unit from said data storage; where
the query comprises a search operator comprised of a plurality of search sub-expressions each having an associated weight value, and where said search engine returns a data unit having a weight value sum that exceeds a threshold weight value sum,
where said data units comprise documents; and
where said data processing system comprises an inverted file system for storing annotations derived from a tokenization of document data, a list comprising occurrences of respective annotations and, for each listed occurrence of a respective annotation, a set comprised of a plurality of token locations spanned by said respected annotation.
5. A data processing system for processing stored document data, comprising:
data storage for storing a collection of document data; and
coupled to the data storage, a search engine responsive to a query for retrieving at least one document from said data storage; where
the query comprises a Boolean predicate that functions as a Weighted AND (WAND), the WAND taking as arguments a list of Boolean variables X 1 , X 2 , . . . , X k , a list of associated positive weights, w 1 , w 2 , . . . , w k , and a threshold θ, where:
(WAND) (X 1 , w 1 , . . . X k , w k , θ)
is true if:
∑
1
≤
i
≤
k
x
i
w
i
≥
θ
,
where x i is the indicator variable for X i , where
x
i
=
{
1
,
if
X
i
is
true
0
,
otherwise
.
said search engine comprising an output for outputting a result of a search of the collection of document data using the query.
6. A data processing system as in claim 5 , where the WAND is used to implement one of an (AND) function or an (OR) function via:
AND ( X 1 , X 2 , . . . X k )≡WAND( X 1 , 1 , X 2 , 1 , . . . X k , 1 , k ),
and
OR ( X 1 , X 2 , . . . X k )≡WAND( X 1 , 1 , X 2 , 1 , . . . X k , 1 , l ).
7. A data processing system as in claim 6 , where the WAND is generalized by requiring an arbitrary monotonically increasing function of the x i 's to be above the threshold.
8. A data processing system as in claim 6 , where the WAND is generalized by requiring an arbitrary monotonic Boolean formula to be True.
9. A data processing system as in claim 8 , where the monotonic Boolean formula is not explicitly given, but is given by a black box computation.
10. A data processing system as in claim 5 , where a query comprising WAND(w 0 , pat 1 , w 1 , pat 2 , w 2 , . . . ) returns at least one document that sufficiently matches enough of pat 1 , pat 2 , . . . so that the sum of weights over the matched patterns pat 1 , pat 2 , . . . is greater than w 0 .
11. A data processing system as in claim 10 , where the pat_i represent an arbitrary Boolean function of the content of the document, and where returned documents satisfy enough of pat 1 , pat 2 , . . . so that the sum of weights over the satisfied functions pat 1 , pat 2 , . . . is greater than w 0 .
12. A data processing system as in claim 5 , where each term is associated with an upper bound on its maximal contribution to any document score, UB t such that:
UB t ≧α t max( w ( t, d 1), ( w ( t, d 2), . . . ),
where the upper bounds of all query terms appearing in a document are summed to determine an upper bound on the document's query-dependent score as:
UB
(
d
,
q
)
=
∑
t
∈
q
⋂
d
UB
t
≥
Score
(
d
,
q
)
:
and where preliminary scoring involves evaluating, for each document d:
WAND( X 1 , UB 1 , X 2 , UB 2 , . . . , X k , UB k , θ)
where X i is an indicator variable for the presence of query term i in document d, and the threshold θ is varied during operation based on a minimum score m among the top n results found by said search engine thus far, where n is a number of requested documents.
13. A data processing system as in claim 5 , where the documents in the data storage are represented as inverted files with respect to a particular ordering of the documents in the data storage.
14. A data processing system as in claim 5 , further comprising at least one iterator over occurrences of terms in documents.
15. A data processing system as in claim 5 , further comprising at least one iterator for indicating which documents satisfy specific properties.
16. A data processing system as in claim 5 , where the WAND employs at least one iterator for documents that satisfy the Boolean predicates X_ 1 , X_ 2 , . . . , respectively, and where a WAND operator creates an iterator for indicating which documents satisfy the WAND predicate.
17. A data processing system as in claim 16 , where the WAND operator maintains a current document variable that represents a first possible document not yet known to not satisfy the WAND predicate, and where a procedure indicates which iterator of a plurality of iterators is to advance if the WAND predicate is not satisfied at a current document variable.
18. A computer program product embodied on a computer-readable medium and comprising program code for directing operation of a text intelligence system in cooperation with at least one application, comprising:
a computer program segment for storing a collection of data units; and
a computer program segment implementing a search engine that is responsive to a query for retrieving at least stored one data unit; where
the query comprises a search operator comprised of a plurality of search sub-expressions each having an associated weight value, and where said search engine returns a data unit having a weight value sum that exceeds a threshold weight value sum; and
where said search operator comprises a weighted AND function, where varying the threshold weight value varies the operation of the weighted AND function from being substantially a logical OR function to being substantially a logical AND function.
19. A computer program product as in claim 18 , where said data units comprise documents.
20. A computer program product as in claim 18 , where at least one of the weight values and threshold weight value are variable during a search.
21. A computer program product embodied on a computer-readable medium and comprising program code for directing operation of a text intelligence system in cooperation with at least one application, comprising:
a computer program segment for storing a collection of data units; and
a computer program segment implementing a search engine that is responsive to a query for retrieving at least stored one data unit; where
the query comprises a search operator comprised of a plurality of search sub-expressions each having an associated weight value, and where said search engine returns a data unit having a weight value sum that exceeds a threshold weight value sum;
where said data units comprise documents; and
further comprising a computer program segment for implementing an inverted file system for storing annotations derived from a tokenization of document data, a list comprising occurrences of respective annotations and, for each listed occurrence of a respective annotation, a set comprised of a plurality of token locations spanned by said respected annotation.
22. A computer program product embodied on a computer-readable medium and comprising program code for directing operation of a text intelligence system in cooperation with at least one application, comprising:
a computer program segment for storing a collection of data units; and
a computer program segment implementing a search engine that is responsive to a query for retrieving at least stored one data unit; where
the query comprises a search operator comprised of a plurality of search sub-expressions each having an associated weight value, and where said search engine returns a data unit having a weight value sum that exceeds a threshold weight value sum;
where the query comprises a Boolean predicate that functions as a Weighted AND (WAND), the WAND taking as arguments a list of Boolean variables X 1 , X 2 , . . . , X k , a list of associated positive weights, w 1 , w 2 , . . . , w k , and a threshold θ, where:
(WAND) (X 1 , w 1 , . . . X k , w k , θ)
is true if:
∑
1
≤
i
≤
k
x
i
w
i
≥
θ
,
where x i is the indicator variable for X i , where
x
i
=
{
1
,
if
X
i
is
true
0
,
otherwise
.
23. A computer program product as in claim 22 , where the WAND is used implement one of an (AND) function or an (OR) function via:
AND ( X 1 , X 2 , . . . X k )≡WAND( X 1 , 1 , X 2 , 1 , . . . X k , 1 , k ),
and
OR( X 1 , X 2 , . . . X k )≡WAND( X 1 , 1 , X 2 , 1 , . . . X k , 1 , l ).
24. A computer program product as in claim 22 , where the WAND is generalized by requiring an arbitrary monotonically increasing function of the x i 's to be above the threshold.
25. A computer program product as in claim 22 , where the WAND is generalized by requiring an arbitrary monotonic Boolean formula to be True.
26. A computer program product as in claim 22 , where a query comprising WAND(w 0 , pat 1 , w 1 , pat 2 , w 2 , . . . ) returns at least one document data unit that sufficiently matches enough of pat 1 , pat 2 , . . . so that the sum of weights over the matched patterns pat 1 , pat 2 , . . . is greater than w 0 .
27. A computer program product as in claim 26 , where the pat_i represent an arbitrary Boolean function of the content of the document, and where returned documents satisfy enough of pat 1 , pat 2 , . . . so that the sum of weights over the satisfied functions pat 1 , pat 2 , . . . is greater than w 0 .
28. A computer program product as in claim 22 , where each term is associated with an upper bound on its maximal contribution to any document data unit score, UB t such that:
UB t ≧α t max( w ( t, d 1), ( w ( t, d 2), . . . ),
where the upper bounds of all query terms appearing in a document data unit are summed to determine an upper bound on the document's query-dependent score as:
UB
(
d
,
q
)
=
∑
t
∈
q
⋂
d
UB
t
≥
Score
(
d
,
q
)
:
and where preliminary scoring involves evaluating, for each document d:
WAND( X 1 , UB 1 , X 2 , UB 2 , . . . , X k , UB k , θ)
where X i is an indicator variable for the presence of query term i in document data unit d, and the threshold θ is varied during operation based on a minimum score m among the top n results found by said search engine thus far, where n is a number of requested documents.
29. A method for processing document data, comprising:
receiving a query; and
responding to the query for retrieving at least one document from a data storage; where
the query comprises a Boolean predicate that functions as a Weighted AND (WAND), the WAND taking as arguments a list of Boolean variables X 1 , X 2 , . . . , X k , a list of associated positive weights, w 1 , w 2 , . . . , w k , and a threshold θ, where:
(WAND) (X 1 , w 1 , . . . X k , w k , θ)
is true if:
∑
1
≤
i
≤
k
x
i
w
i
≥
θ
,
where x i is the indicator variable for X i , where
x
i
=
{
1
,
if
X
i
is
true
0
,
otherwise
.
further comprising outputting as a result of using the query a retrieved at least one document.
30. A method as in claim 29 , where the WAND is used to implement one of an (AND) function or an (OR) function via:
AND ( X 1 , X 2 , . . . X k )≡WAND( X 1 , 1 , X 2 , 1 , . . . X k , 1 , k ),
and
OR ( X 1 , X 2 , . . . X k )≡WAND( X 1 , 1 , X 2 , 1 , . . . X k , 1 , l ).