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)

• US 7,146,361 B2
• Filed: 05/30/2003
• Issued: 12/05/2006
• Est. Priority Date: 05/30/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Carmel, David, Zien, Jason, Herscovici, Michael, Soffer, Aya, Broder, Andrei Z
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US10/449,265
• Publication Number:
  US 20040243557A1
• Time in Patent Office: 1,285 Days
• Field of Search: 707/3, 707/5, 707/100, 707/4
• US Class Current: 707/769
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 40/30 Semantic analysis
• 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

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).

Claims

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₁, X₂, . . . , X_k, a list of associated positive weights, w₁, w₂, . . . , w_k, and a threshold θ

, where;

(WAND) (X₁, w₁, . . . X_k, w_k, θ

)

is true if;

$\underset{1\le <br><br>i\le <br><br>k}{\sum <br><br>}<br><br>x_i<br><br>w_i\ge <br><br>\mathrm{\theta <br><br>},$

where x_i is the indicator variable for X_i, where

$x_i=\{\begin{array}{cc}1,& \mathrm{if}<br><br><br><br>X_i<br><br><br><br>\mathrm{is}<br><br><br><br>\mathrm{true}\\ 0,& \mathrm{otherwise}.\end{array}$

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₁, X₂, . . . X_k)≡

WAND(X₁, 1, X₂, 1, . . . X_k, 1, k),

and

OR (X₁, X₂, . . . X_k)≡

WAND(X₁, 1, X₂, 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(w0, pat1, w1, pat2, w2, . . . ) returns at least one document that sufficiently matches enough of pat1, pat2, . . . so that the sum of weights over the matched patterns pat1, pat2, . . . is greater than w0.

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 pat1, pat2, . . . so that the sum of weights over the satisfied functions pat1, pat2, . . . is greater than w0.

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≧

α

_tmax(w(t, d1), (w(t, d2), . . . ),

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;

$\begin{array}{cc}\mathrm{UB}<br><br>\left(d,q\right)=\underset{t\in <br><br>q\bigcap <br><br>d}{\sum <br><br>}<br><br>{\mathrm{UB}}_t\ge <br><br>\mathrm{Score}<br><br><br><br>\left(d,q\right);<br><br>& \end{array}$

and where preliminary scoring involves evaluating, for each document d;

WAND(X₁, UB₁, X₂, UB₂, . . . , 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₁, X₂, . . . , X_k, a list of associated positive weights, w₁, w₂, . . . , w_k, and a threshold θ

, where;

(WAND) (X₁, w₁, . . . X_k, w_k, θ

)

is true if;

$\underset{1\le <br><br>i\le <br><br>k}{\sum <br><br>}<br><br>x_i<br><br>w_i\ge <br><br>\mathrm{\theta <br><br>},$

where x_i is the indicator variable for X_i, where

$x_i=\{\begin{array}{c}1,<br><br>\mathrm{if}<br><br><br><br>X_i<br><br><br><br>\mathrm{is}<br><br><br><br>\mathrm{true}\\ 0,<br><br>\mathrm{otherwise}.\end{array}$

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₁, X₂, . . . X_k)≡

WAND(X₁, 1, X₂, 1, . . . X_k, 1, k),

and

OR(X₁, X₂, . . . X_k)≡

WAND(X₁, 1, X₂, 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(w0, pat1, w1, pat2, w2, . . . ) returns at least one document data unit that sufficiently matches enough of pat1, pat2, . . . so that the sum of weights over the matched patterns pat1, pat2, . . . is greater than w0.

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 pat1, pat2, . . . so that the sum of weights over the satisfied functions pat1, pat2, . . . is greater than w0.

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≧

α

_tmax(w(t, d1), (w(t, d2), . . . ),

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;

$\begin{array}{cc}\mathrm{UB}<br><br>\left(d,q\right)=\underset{t\in <br><br>q\bigcap <br><br>d}{\sum <br><br>}<br><br>{\mathrm{UB}}_t\ge <br><br>\mathrm{Score}<br><br><br><br>\left(d,q\right);<br><br>& \end{array}$

and where preliminary scoring involves evaluating, for each document d;

WAND(X₁, UB₁, X₂, UB₂, . . . , 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₁, X₂, . . . , X_k, a list of associated positive weights, w₁, w₂, . . . , w_k, and a threshold θ

, where;

(WAND) (X₁, w₁, . . . X_k, w_k, θ

)

is true if;

$\underset{1\le <br><br>i\le <br><br>k}{\sum <br><br>}<br><br>x_i<br><br>w_i\ge <br><br>\mathrm{\theta <br><br>},$

where x_i is the indicator variable for X_i, where

$x_i=\{\begin{array}{cc}1,& \mathrm{if}<br><br><br><br>X_i<br><br><br><br>\mathrm{is}<br><br><br><br>\mathrm{true}\\ 0,& \mathrm{otherwise}.\end{array}$

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₁, X₂, . . . X_k)≡

WAND(X₁, 1, X₂, 1, . . . X_k, 1, k),

and

OR (X₁, X₂, . . . X_k)≡

WAND(X₁, 1, X₂, 1, . . . X_k, 1, l).