US7146361B2 — System, method and computer program product for p…

Claim 1

Independent Claim 121 words

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.

Claim 2

Dependent Claim 121 words

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.

Claim 3

Dependent Claim 15 words

A data processing system as in claim 1 , where said data units comprise documents.

Claim 4

Dependent Claim 26 words

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.

Claim 5

Dependent Claim 140 words

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.

Claim 6

Dependent Claim 140 words

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.

Claim 7

Dependent Claim 193 words

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.

Claim 8

Dependent Claim 193 words

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.

Claim 9

Dependent Claim 95 words

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

Claim 10

Dependent Claim 31 words

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.

Claim 11

Dependent Claim 24 words

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

Claim 12

Dependent Claim 26 words

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.

Claim 13

Dependent Claim 76 words

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 .

Claim 14

Dependent Claim 64 words

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 .

Claim 15

Dependent Claim 187 words

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.

Claim 16

Dependent Claim 34 words

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.

Claim 17

Dependent Claim 21 words

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

Claim 18

Dependent Claim 22 words

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

Claim 19

Dependent Claim 51 words

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.

Claim 20

Dependent Claim 60 words

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.

Claim 21

Dependent Claim 142 words

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.

Claim 22

Dependent Claim 142 words

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.

Claim 23

Dependent Claim 15 words

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

Claim 24

Dependent Claim 26 words

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.

Claim 25

Dependent Claim 163 words

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.

Claim 26

Dependent Claim 163 words

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.

Claim 27

Dependent Claim 235 words

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 .

Claim 28

Dependent Claim 235 words

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 .

Claim 29

Dependent Claim 93 words

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

Claim 30

Dependent Claim 31 words

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.

Claim 31

Dependent Claim 24 words

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

Claim 32

Dependent Claim 78 words

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 .

Claim 33

Dependent Claim 64 words

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 .

Claim 34

Dependent Claim 193 words

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.

Claim 35

Independent Claim 170 words

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.

Claim 36

Independent Claim 170 words

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.

Claim 37

Dependent Claim 93 words

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

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2009-12-04	2010-06-05	2010-12-05	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2013-12-04	2014-06-05	2014-12-05	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2017-12-04	2018-06-05	2018-12-05	$7700.00	Window Closed / Lapsed

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)

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag