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 20040243557A1
• Filed: 05/30/2003
• Published: 12/02/2004
• 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, Broder, Andrei Z., Herscovici, Michael, Soffer, Aya
• Granted Patent: US 7,146,361 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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.

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 as in claim 1, 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.

5. A data processing system as in claim 2, 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.

6. 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>\text{\hspace{1em}<br><br>}<br><br>X_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{true}\\ 0,& \mathrm{otherwise}\end{array}.$

7. A data processing system as in claim 6, 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).

8. A data processing system as in claim 7, where the WAND is generalized by requiring an arbitrary monotonically increasing function of the x_i'"'"'s to be above the threshold.

9. A data processing system as in claim 7, where the WAND is generalized by requiring an arbitrary monotonic Boolean formula to be True.

10. A data processing system as in claim 6, 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 6, 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>\text{\hspace{1em}<br><br>}<br><br>\left(d,q\right).& \left(3\right)\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.

12. A data processing system as in claim 9, where the monotonic Boolean formula is not explicitly given, but is given by a black box computation.

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

14. A data processing system as in claim 6, 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.

15. A data processing system as in claim 6, further comprising at least one iterator over occurrences of terms in documents.

16. A data processing system as in claim 6, further comprising at least one iterator for indicating which documents satisfy specific properties.

17. A data processing system as in claim 6, 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.

18. A data processing system as in claim 17, 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.

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

20. A computer program product as in claim 19, where said data units comprise documents.

21. A computer program product as in claim 19, where at least one of the weight values and threshold weight value are variable during a search.

22. A computer program product as in claim 19, 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.

23. A computer program product as in claim 19, 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.

24. A computer program product as in claim 19, 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;

25. A computer program product as in claim 24, 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).

26. A computer program product as in claim 24, where the WAND is generalized by requiring an arbitrary monotonically increasing function of the x_i'"'"'s to be above the threshold.

27. A computer program product as in claim 24, where the WAND is generalized by requiring an arbitrary monotonic Boolean formula to be True.

28. A computer program product as in claim 24, 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.

29. A computer program product as in claim 28, 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.

30. A computer program product as in claim 24, 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>\text{\hspace{1em}<br><br>}<br><br>\left(d,q\right).& \left(3\right)\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.

31. 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 is the indicator variable for X_i, where

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

32. A method as in claim 31, 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).