US20040243632A1 - Adaptive evaluation of text search queries with blackbox scoring functions - Google Patents

Abstract

Disclosed is an evaluation technique for text search with black-box scoring functions, where it is unnecessary for the evaluation engine to maintain details of the scoring function. Included is a description of a system for dealing with blackbox searching, proofs of correctness, as well experimental evidence showing that the performance of the technique is comparable in efficiency to those techniques used in custom-built engines.

Description

CROSS REFERENCE TO RELATED APPLICATION
• This application claims priority under 35 U.S.C. §119(e) to co-pending U.S.[0001]Provisional patent application 60/474,877 filed on May 30, 2003.
TECHNICAL FIELD OF THE INVENTION
• This invention relates generally to methods, apparatus and computer programs for execution of text search queries over a large body of data.[0002]
BACKGROUND OF THE INVENTION
• Searching a body of documents for specific information is increasingly important, in an increasing number of systems. This introduction examines searching and ranking techniques for responding to a specific search request. Typically, providing best available information calls for scoring information in each document and then by ranking the information or the documents according to relevance. A variety of techniques are used to complete such tasks.[0003]
• Custom built solutions typically offer acceptable performance for searching large bodies of data. Examples include those available for searching the Internet. Some of the commercially available solutions include biases that either speed the search or qualify data.[0004]
• Experience has shown that it is typically a substantial challenge to meet performance expectations within the confines of certain systems. Examples of systems where challenges arise include general purpose database management systems and content management systems. For developers of searching algorithms, challenges to meeting expectations in such systems include balancing the concepts of ranking and approximation, as well as providing for a generality of purpose. These, and other concepts, are discussed in more detail to provide some perspective.[0005]
• Ranking and approximation specify what to return when there are too many or too few results. One may consider these concepts to be at different ends of a single continuum. In order to provide desired searching capabilities, it is considered preferable that typical database systems should incorporate ranking into the generic and extensible architecture of the database engine. Typical database systems do not integrate the concepts of ranking and approximation. New and different ranking criteria and ranking functions should be easily incorporated into a query processing runtime. Preferably, database systems should not use a biased ranking method.[0006]
• For more perspective, consider the following aspects of ranking text in databases. Note that information retrieval (IR) literature contains many ranking heuristics. A few of these heuristics, to which later reference will be made,include the Term Frequency Inverted Document Frequency (TFIDF) function, Static Rank functions, Searching by Numbers, Lexical Affinities (LA) and Salience Levels (SL), as well as other functions.[0007]
• One common method for ranking text is by use of the TFIDF score. This is calculated as:[0008]$\mathrm{TFIDF}\left(q,d\right)=\sum _{t\in q}\frac{{\varphi }_{t,d}}{{\Gamma }_t}$

  
• Here, q represents the query, φ[0009]_t,dis the number of times term t occurs in document d, divided by the total number of terms in the document d. Γ_tis the number of documents which contain term t. A discussion of TFDIF is provided in the reference “Managing Gigabytes,” I. H. Witten, A. Moffat, and T. C. Bell. Morgan Kaufman, San Francisco, 1999.
• One example of a search engine that uses the Static Rank is the GOOGLE search engine, which uses PageRank. Typically, Static Ranks are used in combination with query dependent ranks such as TFIDF. As an example, scoring where the combination is used can be accomplished using a metric such as:[0010]
• COMBIN(q, d)=αSTATIC(d)+TFIDF(q, d)
• The combination presumes that some documents are generally better than others, and therefore, should be favored during retrieval. A discussion of Static Ranks is presented in the publication by S. Brim and L. Page, and entitled “The Anatomy of a Large-Scale Hypertextual Web Search Engine,” as published in Proceedings of the 7th International World Wide Web Conference (WWW7), 1998. This publication also discusses PageRank.[0011]
• As an example of keyword based querying of structured datasets, consider the following example of Searching by Numbers. In the example, a user enters a few numbers into a search bar, for instance, “1 GHz, 256M” and the search system translates the query automatically to something like:[0012]
• (processorSpeed≈1 GHz)
• .and. (memoryCapacity≈256 MB)
• In addition to automated translation to a structured form, results are ranked based on a discrepancy between the requested value and actual value returned for the two parameters of interest. A discussion of Searching by Numbers is presented in the publication by R. Agrawal and R. Srikant, entitled “Searching with Numbers,” published in the Proceedings of the 2002 International World Wide Web Conference (WWW2002), Honolulu, Hi., May 2002.[0013]
• Lexical Affinities and Salience Levels are described as score boosting heuristics. In the case of Lexical Affinities (LA), a score is boosted when two terms in the query appear within a small window of each other. In the case of Salience Levels (SL), the score is boosted when a query term appears with increased prominence such as in the title, a paragraph heading, or with bold and/or italicized text. Score boosting methods such as the use of LA and SL are commonly used in modern information retrieval systems. A discussion of Lexical Affinities and Salience Levels is provided in the publication by Y. Maarek and F. Smadja, and entitled “Full text indexing based on lexical relations: An application: Software libraries,” appearing in the Proceedings of the Twelfth International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 198-206, Cambridge, Mass., June 1989. Further examples are provided in the publication by E. M. Voorhees and D. K. Harman, and entitled “Overview of the Tenth Text Retrieval Conference (TREC-10),” appearing in the Proceedings of the Tenth Text Retrieval Conference (TREC-10), National Institute of Standards and Technology, 2001.[0014]
• Another popular scoring function, referred to as OKAPI, is discussed in the publication by S. E. Robertson, S. Walker, S. Jones, M. M. Hancock-Beaulieu, and M. Gatford, entitled “Okapi at TREC-3,” appearing in Proceedings of the Third Text REtrieval Conference (TREC-3), pages 109-126. National Institute of Standards and Technology. NIST, 1994.[0015]
• Presently, there is a debate by those skilled in the art over the choice of “term at a time” (TAAT) search strategies versus “document at a time” (DAAT) search strategies. One example of the various perspectives on these strategies is provided in the publication by H. Turtle and J. Flood, entitled “Query evaluation: Strategies and optimizations,” appearing in Information Processing and Management, 31(6):831-850, 1995.[0016]
• Typically, a TAAT search engine maintains a sparse vector spanning the documents. The TAAT search engine iterates through the query terms and updates the vector with each iteration. The final state of the vector becomes the score for each document. TAAT search engines are relatively easy to program and new ranking functions are easily included in TAAT runtimes. Conversely, a DAAT search engines make use of document indices. Typically, a DAAT runtime search engine iterates through documents subject to the search and scores a document before proceeding to the next one. A heap maintains the current top l documents identified.[0017]
• In the context of large data sets, it is considered by some that the index based DAAT runtime search engine outperforms the vector based TAAT search engine during query execution. However, DAAT runtimes are hard to implement. For example, each DAAT ranking engine is typically built as a custom system, rather than being implemented on top of a general purpose platform such as a database system. Typically, this is due to the fact that commercial database indices have little or no support for the ranking heuristics used in the text.[0018]
• To address this issue, DAAT engines have typically been built using a two layer architecture. The user's query would first be translated into a Boolean query. A lower stage performs retrieval based on the Boolean query (or near Boolean query, that is a Boolean query with a “near” operator) which is then passed to a ranking stage for a complete evaluation. Thus, the Boolean stage acts as a filter which eliminates documents which have little or no relevance to the query or are otherwise unlikely to be in the result set.[0019]
• From a runtime optimization perspective, two layer DAAT architecture has two potential problems. First, there is the need for a middle layer which translates a query into the Boolean form. This can be a complicated process. For example, translating to a Boolean “AND” of all the query terms may not return a potential hit, while translating to a Boolean “OR” may be an ineffective filter. Thus, depending on how effective the Boolean filters are, the DAAT search may end up performing a significant amount of extra input and output operations. Second, effective translations can lead to complicated intermediate Boolean queries. Consequently, the filters associated with even simple scoring functions such as TFIDF or COMBIN can present daunting optimization problems.[0020]
• For further reference, the merge operator and the zig-zag join operators are described in the publication by Sergey Melnik, Sriram Raghavan, Beverly Yang, and Hector Garcia-Molina, entitled “Building a Distributed Full-Text Index for the Web,” appearing in ACM Transactions on Information Systems, 19(3):217-241, July 2001; and the publication by H. Garcia-Molina, J. Uliman, and J. Widom, entitled “Database System Implementation,” appearing in Prentice-Hall, 2000. (another incomplete reference).[0021]
• From a functional perspective, a scoring function uses more information than the Boolean filters. For instance, a TFIDF requires determination of the quantity φ[0022]_t,d,which requires more resources than determining if a term is present in a document. Per document scores (such as STATIC) and per term statistics (such as Γ_t) are used in scoring. Scoring in Searching by Numbers requires use of the numerical values in addition to indices. Heuristics such as LA and SL require information about where in the document and in what context any term occurred. In short, a typical information retrieval engine may use many heuristics and combine them in complicated ways. Examples are provided in two further publications. Consider the publication by David Carmel, Doron Cohen, Ronald Fagin, Eitan Farchi, Michael Herscovici, Yoelle S. Maarek, and Aya Soffer, entitled “Static index pruning for information retrieval systems,” appearing in the Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 41-50, New Orleans, LA., September 2001; and the publication by “R. Fagin, R. Kumar and D. Sivakumar, entitled “Top k Orderings and Near Metrics,” appearing in To appear, 2001. (note that this is an incomplete citation to a reference). Such schemes often require data to be provided to support the ranking decisions.
• In a typical modern day search engine, the scoring function and the runtime engine are co-designed. This prior art arrangement is depicted in FIG. 1.[0023]
• Referring to FIG. 1, a prior[0024]art search engine5 receives aquery8 and providesresults9. This process calls for use ofparser3, which builds a token table4 from a base table2. Typically, the base table8 is a collection ofdocuments7. The token table4 includestokens13, which may be considered as segments or compilations of relevant information from adocument7. From the token table4, an index table6 is built. Using theinput query8, the priorart search engine5 typically includes an embedded scoring function to provide scoring and ranking of information in the index table6.
• While this arrangement usually means that runtime optimization performs well, such designs come at the cost of versatility. For example, some text search engines have been customized to the extent of including special purpose hardware to speed up critical operators. This has made sense for certain applications, especially in the case where there are few scoring functions which are of concern. In such instances, there is no need for versatility as understanding the scoring function allows for better scheduling of the runtime operators. However, such engines are typically not very useful in contexts other than those for which they were developed.[0025]
• It is important that a generic search engine provide a generic interface to support the varied search functions. In particular, the scoring function used to rank results should be “plug and play.” That is, what is needed is a runtime search engine for text search and ranking where the scoring function is queried as a “black box.”[0026]
SUMMARY OF THE INVENTION
• The foregoing and other problems are overcome by methods and apparatus in accordance with embodiments of this invention.[0027]
• Disclosed herein is a computer program product embodied on a computer readable medium, the computer program product providing computer instructions that implement a text and semi-structured search algorithm having a function having an input for receiving, while there is at least one candidate location in an order of locations, a score range for the candidate location, the algorithm comparing the score range to a threshold- within a range of possible scores, wherein if a lower bound of the score range for the candidate location exceeds the threshold then the candidate location is retained as a result and a next location is selected, and wherein if an upper bound of the score range is at or below the threshold the candidate location is discarded and the next location is selected, and wherein if the score of the candidate location is indeterminate, then the score range for the candidate location is refined.[0028]
• Also disclosed is a system for implementing a text and semi-structured search algorithm, that includes a processor for operating an algorithm that has an input for receiving from a blackbox scoring function a score for at least one candidate location in an order of locations, wherein the algorithm compares the score to a threshold, and if the score exceeds the threshold then the candidate location is stored as a result and a next location is selected, and if the score is at or below the threshold the candidate location is discarded and the next location is selected, and wherein if the score of the candidate location is indeterminate, then the score for the candidate location is refined; wherein each result is stored in a table of results ordered by relevance.[0029]
• Further disclosed is a method for implementing a search of locations in a body of text and semi-structured data for relevant terms, which includes: providing an index of locations formed of terms, wherein a score for the relevant terms in a candidate location is provided by a scoring function and associated with the candidate location; and, while there are candidate locations: refining the score range if the score of the candidate location is indeterminate, otherwise, storing each candidate location as a result if a lower bound of the score range for the candidate location exceeds a threshold within a range of possible scores, discarding the candidate location if the score range is at or below an upper bound for the score range and selecting a next location.[0030]
BRIEF DESCRIPTION OF THE DRAWINGS
• The above set forth and other features of the invention are made more apparent in the ensuing Detailed Description of the Invention when read in conjunction with the attached Drawings, wherein:[0031]
• FIG. 1 depicts a prior art embodiment of a search engine;[0032]
• FIG. 2 depicts a search engine in accordance with the teachings herein;[0033]
• FIG. 3 depicts progress of a query through a series of documents d[0034]_x;
• FIG. 4 depicts the processing expense for running a blackbox learning algorithm;[0035]
• FIG. 5 depicts the processing expense as a fraction of total processing requirements;[0036]
• FIG. 6 depicts performance of the Algorithm A for a complex query;[0037]
• FIG. 7 depicts aspects of performance as a result of adjusting the threshold;[0038]
• FIGS. 8- 9 depict performance as a result of “unsafe” approximations;[0039]
• FIG. 10 depicts performance where scoring functions are combined; and,[0040]
• FIG. 11 depicts aspects of components for execution of Algorithm A.[0041]
DETAILED DESCRIPTION OF THE INVENTION
• Disclosed herein is a generic search engine that provides a generic interface to support a variety of search functions. In particular, scoring functions[0042]12 used to rank results are queried as a “black box,” where an evaluation engine does not require information regarding aspects of the scoring functions12. An example is depicted in FIG. 2.
• Referring to FIG. 2, searching is completed by use of a[0043]runtime engine11 that receives aninput query8. Using theinput query8, theruntime engine11 employs an algorithm, disclosed herein in non-limiting embodiments as “Algorithm A,” or as “A”, to generateresults9. Algorithm A provides an interface to any one or more of various preselected scoring functions12 to obtain scoring and ranking information used to provide theresults9. Non-limiting examples of scoring functions12 useful for practice of the teachings herein include: TFIDF, OKAPI, Static Rank, Lexical Affinities, Salience Levels, in addition to Boolean functions and threshold predicates. As one may surmise, the techniques disclosed herein generally provide for scoring and ranking at the level where indexing occurs.
• Blackbox Scoring. A first device, the[0044]parser3, produces data for interpretation by thescoring function12. Thus, parsing and scoring are intimately related. Therefore, a blackbox model for scoring, as depicted in FIG. 1, specifies a corresponding model for parsing and tokenization. In the context of a database, the flow may be triggered by a statement, such as call in the form of the SQL statement below:
• CREATE TEXT INDEX <indexname>[0045]
• ON TABLE <tablename>[0046]
• USING <[0047]parsername1>FOR <column1>
• USING <[0048]parsername2>FOR <column2>
• RANKED BY SCORE <scoringfunction>[0049]
• First Steps: As an introduction, it is clear that blackbox scoring for a top-i query can be performed via a table scan of the base table[0050]2. This is shown in Table 1. Note that the algorithm in Table 1 does not address aspects of the functionality ofparsers3 and scoring functions12, and is therefore only illustrative.

  TABLE 1
  Table Scan
  (prior art)

  1	Initialize heap
  2	while(docs left)
  2.1	score the next document
  2.2	if it is in top l, put inheap
  3	return the heap

• Since the score is zero unless the[0051]document7 contains some token in thequery8, only thosedocuments7 which contain at least one token13 related to thequery8 need be scored. This provides a basis for speeding theruntime engine11 by use of the index table6. Another example is shown in Table 2.

  TABLE 2
  Faster Scan
  (prior art)

  1	initialize heap
  2	while(docs containing a query token left)
  2.1	score the next such document
  2.2	if it is in top l, put inheap
  3	return the heap

• Note that the algorithm in Table 2 is not optimal. For example, some scoring functions[0052]12 may evaluate to zero, even when some terms in thequery8 are present. One example is the Boolean AND function. Thus, the filtering provided instep2 leaves room for improvement.
• As disclosed herein, a[0053]scoring function12 which allows input of generic parameters (i.e., “wildcards”) can be used as a black box within an efficient andgeneric runtime11. Such ascoring function12 can be used to do a partial evaluation of the score without having to collect all relevant parameters associated with thedocument7. This can present significant benefits, as in the case where the relevant parameters are scattered in storage (e.g., over a disk in a text index).
• The algorithm disclosed herein is one (non-limiting) embodiment of a generic algorithm “A.” One embodiment of Algorithm A is presented in Table 3, below. Algorithm A is described herein in terms of two non-limiting subroutines, nextCand( ) and refine( ). In some embodiments, Algorithm A iterates through[0054]documents7 using the function nextCand( ). Algorithm A uses partial score evaluations to avoid retrieving document parameter values from storage. As used herein, the terms “lower” and “upper” represent the lower bounds and the upper bounds on a range of possible scores for “candidate.” As Algorithm A proceeds, Algorithm A takes one of three options. For example, if the current candidate is in the top l found so far (see step2.2), Algorithm A adds it to the heap and continues to the next candidate. If the candidate is not in the top l (step2.3) Algorithm A goes on to the next candidate. If the status of candidate cannot be determined (step2.4), then Algorithm A tries to refine( ) the score. As a side effect both refine( ) and candidate change the values of lower and upper.

  TABLE 3
  Algorithm A

  1	initialize heap and set candidate = 0
  2	while(candidate exists)
  2.1	Let threshold be the smallest score in heap
  2.2	If(threshold < lower)
  	add candidate to the heap
  	candidate = nextCand( )
  2.3	else if (threshold μ upper)
  	candidate = nextCand( ).
  2.4	Else
  	refine( )
  3	return the heap

• Note that both algorithms in Tables 1 and 2 are specializations of Algorithm A. In the case of the algorithm in Table 1, nextCand( ) returns[0055]candidateDoc+1. In the case of the algorithm in Table 2, nextCand( ) returns thenext document7 which contains at least one of the terms in thequery8. In both cases, refine( ) does a full evaluation of the score, preferably by reading all the parameters from disk. Also, note that Algorithm A can be modified to work in “streaming” mode. In this case, there will be no heap and the threshold will be provided by a caller. Refer to Table 4 for a non-limiting example of the Algorthm A modified to work in streaming mode. Note that in the Algorithm A provided in Table 4, the threshold can be increased in each call to next( ).

  TABLE 4
  Algorithm A
  modified for streamingmode

  1	init( ) {
  	set candidate = 0
  	}
  	next(threshold) {
  	candidate = nextCand( )
  	while( candidate exists ) {
  	if( threshold < lower )
  	return candidate
  	else if ( threshold >= upper )
  	candidate = nextCand( )
  	else
  	refine( )
  	}
  	return end of results
  	}

• Efficient design of nextCand( ) and refine( ) is important to providing desired performance in the operation of Algorithm A. To this end, some additional introduction is provided regarding parsing, scoring functions[0056]12,text indexes6, and howtext indexes6 incur I/O penalties. Subsequently, aspects of implementing both nextCand( ) and refine( ) for a blackbox scoring function21 that supports wildcarding is provided.
• The[0057]Parser3. Aparser3 effects the transformation from the base table2 to the token table4 shown in FIG. 2 and detailed in Tables 5 and 6. The token table4 need not be stored, but can be streamed directly into the index build phase. The token table4 represents a ternary relation, (d, t, θ_t,d). Here, d is the “document”7 or the row identifier (RID) where the token t was found. The symbol θ^t,drepresents information about token t within document d needed by thescoring function12 in determining the score of thedocument7. This could, for instance, include information about the salience of the token13, its location(s) within thedocument7, the number of times the token13 occurred in thedocument7, as well as other information. The generic search system considers θ_t,dopaque binary data and does not attempt to interpret it. However, it is responsible for storing and retrieving θ_t,dto and from the index table6.

  TABLE 5
  d	Subject	Student	Grade
  1	English	Adam Smith	B
  2	Math	John Grisham	C
  3	Math	John English	A
  4	English	Johnny Davis	A

• [0058]

  TABLE 6
  d	t	θ	t,d
  1	English	Subject
  1	Adam	Student
  1	Smith	Student,Bold
  2	Math	Subject
  2	John	Student,Emphasis
  2	Grisham	Student
  .	.	.
  .	.	.
  .	.	.

• In this example, Table 5 represents the base table[0059]2 having two indexable columns, “Subject” and “Student.” Table 6 provides a first few rows of the token table4 corresponding to the base table2.
• Assume, without loss of generality, that the pair (t, d) is a unique key for the token table[0060]4 (otherwise, concatenate the set of associated θ values). Thus, the reference to θ_t,dis unambiguous. Consider that θ_t,dis null if the token table4 contains no entry corresponding to the pair (t, d). Otherwise, assume that document d contains t. Thus, per the example in Table 6, θ_John,1is null and the document d contains “Grisham” and “Math.”
• Preferably, a user can create and register[0061]new parsers3 for any column or data type in concert with creating and registering new scoring functions12.
• Scoring Functions[0062]12. Consider scoring functions12 having generic input capability (i.e., “wildcard” capability). In the following discussion, differences between SCORE, the intended scoring function12 (e.g., TFIDF and OKAPI) and score, an implementation of SCORE which supports wildcarding are discussed. Specifically, associated with each query q involving tokens t₁, t₂, . . . t_k, is a blackbox scoring function score(x₁, x₂, . . . , x_k). If partial evaluation is performed by setting some of the x_ito θ_ti,dand others to “huh” (a wildcard value), score returns a range (lower, upper) giving lower and upper bounds on the document scoreSCORE(d). Preferably, the score function exhibits the properties set forth in Table 7.

  TABLE 7
  score Function Properties

  1	Monotonicity: lower does not decrease and upper does not increase
  	if a huh parameter is changed to any definite null or non-null θ value.
  2	If no parameter is set to huh, upper = lower = SCORE (d)
  3	lower ≦ upper

• Note that any correctly implemented score function does not impose restrictions on the scoring metric SCORE. Most, if not all, commonly used scoring functions[0063]12 admit wildcard capable implementations that satisfy the properties in Table 7.
• [0064]Text Indexes6 and Skip Sequential Iterators. A Skip Sequential Iterator (SSI) is a convenient interface to atext index6. The iterator I_tcorresponds to a token t (i.e., term) and iterates over all documents d containing t. Table 8 contains a definition for one embodiment of an SSI.

  TABLE 8
  Skip Sequential Iterator (SSI) - Definition
  The iterator Itis associated with a state s, initially 0.
  Unless s is 0 or ≡, s is a document id containing t.
  In addition, the iterator Ithas the following interface:

  1	loc( ) returns the current state s.
  2	data( ) returns θt,s.
  3	next(a) sets s the smallest b μ a such that b contains t. If there is
  	no such document id, it sets s to ≡.

• The Algorithm A maintains a collection of SSIs, {I[0065]_t}, one per token t in the query. Initially, each iterator I_tis at 0. The Algorithm A moves the iterators I_tby making calls to I_t.next(candidate). This call is denoted herein as: toss(t).
• Note that a side-effect of the toss(t) operation is that the data value, θ[0066]_{t, candidate}is known. If after a toss(t) call I_t.loc( )=candidate, θ_{t, candidate}is known to be I_t.data( ). Otherwise, θ_{t, candidate}=null. Algorithm A uses toss(t) calls to read parameter values in the refine( ) subroutine.
• The following assertion follows from the discussion regarding the steps taken by algorithm A.[0067]
• Lemma: As long as candidate only increases, and the iterators I[0068]_tare only moved using toss(t) operations, θ_t,dis null whenever candidate≦d≦I_t.loc( ).
• Defining Subroutines. Aspects of the subroutines nextCand( ) and refine( ) are now defined.[0069]
• The nextCand( ) function. For convenience, changes are made in the notation used, where the[0070]tokens13 are renamed so that I_t1.loc( )≦I_t2.loc( )≦. . . I_tk.loc( ). Consider S(d) to be defined as:
• S(d)=score (huh,huh,^{. . .}, θ_ti,d, θ_ti+1,d,^{. . .}, null, null ).upper   (Eq. 1)
• where t[0071]_i, t_i+1, . . . are the tokens t, whose iterators I_tare at I_t.loc( )=d. For thesetokens13, θ_t,dis available to use without I/O, since θ_t,d=I_t.data( ). Terms t, whose iterators I_tare at I_t.loc( )<d, are parameterized by huh, and those whose iterators I_tare at I_t.loc( )>d are parameterized by null.
• As shown in FIG. 3, nextCand( ) returns the smallest d>candidate such that S(d)>threshold. As d increases from left to right, the x[0072]_iin Eq. 1 changes from null to a definite θ (at d=I_t.loc( )( )), to huh at d=I_t.loc( )( )+1. Therefore, it is considered that nextCand( ) can be implemented via a linear search using at most 2k blackbox invocations of score. The computation of nextCand( ) typically does not involve I/O, as all the parameter values required for computing S(d) are available. Referring to FIG. 3, the nextCand( ) function returns the smallest document id d such that S(d) exceeds threshold. In this case, this is d₃+1.
• The Lemma implies that S(d) is an upper bound on SCORE(d). This is because all definite parameters (not huh) used in the evaluation of S(d) are in fact the correct parameters for document d (either θ[0073]_t,dor null). Therefore, alldocuments7 skipped by nextCand( ) are not qualified to enter the heap. Finally, since candidate is only updated using a nextCand( ) call, the score for candidate does not decrease. Therefore, a corollary to the Lemma is proffered.
• Corollary. As long as refine( ) is implemented using only toss(t) operations, Algorithm A will produce[0074]correct results9.
• The refine( ) function. Notice that a toss(t) operation simultaneously reads several θ values. Letting s be I[0075]_t.loc( ) after the toss(t) operation, θ_t,dis known for any d χ [candidate, s]. In this case, all but θ_t,sare null. Therefore, refine( ) should operate to choose a term t to toss such that the status of candidate and as many succeeding document ids as possible are resolved by the toss. Clearly, refine( ) can only toss terms whose current locations are smaller than candidate. For all other terms t, θ_t,candidateis identified by refine( ). One can measure (or “learn”) the effectiveness of t dynamically by noting exactly how far candidate advanced following a toss(t) operation and attributing this progress to t. The amount attributed to t can be 0 if the status of candidate was not resolved, or a larger number if candidate was advanced by a lot. To this end,Equation 2 provides:$\begin{array}{cc}{\Gamma }_t=\frac{\mathrm{total}\mathrm{progress}\mathrm{attributed}\mathrm{to}t}{\mathrm{number}\mathrm{of}\mathrm{toss}\left(t\right)\mathrm{operations}}& \mathrm{Eq}.\left(2\right)\end{array}$

  
• Assuming that the values Γ[0076]_thave converged, the token t with the largest value of Γ_tis chosen for the toss. Tossing any token13 such that I_t.loc( ) μ candidate would be meaningless since the ordering invariant implies that the value of θ_{t, candidate}is known. Thus, the token13 with the largest value of Γ_tamong those for which I_t.loc( )<candidate is tossed. Γ_tmay be evaluated using other techniques such as geometric mean, moving averages, logarithmic scaling and others. In some embodiments, Γ_tis provided as an input having a known value.
• Experimental Evidence Supporting Algorithm A. This section provides experimental evidence affirming the utility of algorithm A. Consider that Algorithm A trades processing speed (CPU cost) for the benefit of the versatility offered. Therefore, criteria for evaluating the utility of Algorithm A evaluates whether the trade is warranted. In order to address this evaluation, three tests are proffered, with a subsequent evaluation of performance.[0077]
• First, the additional computational cost (i.e. CPU cost) of dealing with blackbox scoring functions is considered. Secondly, the fraction of the total cost of query processing that the CPU cost represents is evaluated. Third of all, functions which are difficult to optimize are considered.[0078]
• In short, it has been determined that CPU cost is moderate. In tests performed, the CPU cost was never worse than a factor of two, even when the scoring functions[0079]12 were simplistic (i.e., BooleanANDand BooleanORfunctions). These were considered to be the worst case, since the optimized non blackbox code was shown to perform well in these cases. It was found that the fraction of the total cost of query processing depends on the cost of input and output (I/O). Testing showed that CPU cost was a negligible fraction of the runtime, as the cost of the I/O operations increased. For instance, if the cost of a toss( ) was at least 0.001 millisecond, (which is considered to be an aggressive estimate by any standard), then the additional cost of the learning computation and using the blackbox was shown to be less than 3%. Since A does not depend on knowing theSCOREfunction, this overhead is likely to be small even for complicated SCORE functions. Last of all, considering functions where optimization presents challenges, it was found that for a simple four node, two level, tree of un-weighted threshold gates, much like what is commonly used in text processing, Algorithm A performs significantly better in terms of both CPU cost and I/O than the natural extension of a Zig-Zag search or a Merge search. Notice that Zig-Zag and Merge are “locally optimal” for each of the nodes in the tree, and do not share the global perspective on optimization of Algorithm A.
• Performance testing was undertaken by implementing Algorithm A on two platforms. The first (P[0080]1) provided an artificial test platform for testing the algorithm function. The second (P2) used a full text index with blackbox scoring functions12, such as TFIDF, OKAPI, Static Rank, Lexical Affinities, in addition to Boolean functions and threshold predicates.
• An index containing 8 GB of index data and over 1M documents was built on the platform. Both algorithms were run on a personal computer (PC) in a Linux environment, with a 2 GHz CPU. The experiments were performed with a cold I/O subsystem. In the P[0081]1 system, thetokens13 included integers and document d contained alltokens13 which exactly divided d. Thus, the document “10” contains the words “1,” “2,” “5,” “1.” Document “11” contains the words “1,” “11.” The query “3” and “5” should return all multiples of “15.” The reason that this platform was considered useful was that no I/O is required in implementing the SSIs. The documents d containing a token t are all multiples of t, and so the next( ) function could be implemented “on the fly.” This provided for separating the CPU cost of running A from the cost of the I/O and thus the separate measurement of each. Experiments in this section were implemented on platform P1.
• Aspects of CPU cost are depicted in FIG. 4. FIG. 4 shows that the CPU cost (but for a tiny startup cost) of all algorithms is linear in the number of documents processed. This FIG. establishes that the total CPU cost of running a blackbox learning algorithm is rather small, less than half a second on a base table[0082]2 containing 100 M documents.
• FIG. 4 shows that the CPU cost of query processing algorithms scales linearly with the number of documents to be processed. The figure depicts results for four[0083]scoring functions12, and the CPU cost in msec on a 2 GHz CPU. The X-axis depicts the number ofdocuments7. The curves depicted represent Algorithm A running BooleanANDand BooleanOR(labeled as and-learn and as or-learn) as well as the optimal Zig-Zag and Merge algorithms forANDandORrespectively. As can be seen, even with 109 (1 Billion) documents, the total CPU time taken in the worst case is rather small, about 5 seconds.
• FIG. 5 depicts aspects of CPU cost as a fraction of total cost. As discussed above, blackbox function evaluations and all the learning needed in picking the correct parameterization for blackbox score functions takes very little CPU usage. FIG. 5 provides an assessment of how this number compares with the total cost of running the[0084]query8.
• In FIG. 5, the overhead CPU cost of the learning Algorithm A is negligible. The figure shows two curves, corresponding to the Boolean[0085]ANDand the BooleanORfunction respectively. The number shows the ratio of clock time taken as a function of I/O cost. The I/O cost was modeled by implementing a spin loop to model a disk access. The X-axis shows the time expended in the spin loop per I/O operation. As can be seen, if the I/O operation were to cost 0.001 millisecond, Algorithm A is 3% worse than the optimal Zig-Zag onANDqueries and only 1% worse than Merge onORqueries. Recall that Algorithm A does not know the difference betweenANDandOR, but self tunes to the correct execution strategy in both cases.
• In FIG. 6, performance for a complex query is depicted. On a two level threshold tree with four gates using a set of strongly correlated and strongly anticorrelated terms (a typical optimization nightmare), Algorithm A performed about[0086]100 times better on both CPU and I/O measures when compared to an algorithm which choose the optimum join method for each node in the tree. Thus, the “global” perspective that Algorithm A takes on optimization results in far more efficient runtime performance.
• About Algorithm A: Generalizing Zig-Zag and Merge. If the[0087]SCOREfunction is a k-way BooleanAND, the optimal runtime strategy is the Zig-Zag join algorithm. In the case of BooleanSCOREfunctions, the θ values are not relevant. Thus, the interest is only in whether a term t is contained in document d. In the case of BooleanAND, is easy to see that candidate should be the maximum I_t.loc( ) value. Also, the token t in toss(t) is chosen to be the rarest token whose location is not candidate. Hardcoding these choices results in the Zig-Zag join algorithm. A will automatically mimic this tuned strategy. That is, since score will return a 0 upper and lower bound if even one parameter is set to null, candidate will always be the maximum I_t.loc( ). S(d) will be 0 for alldocuments7 having lower scores. Moreover, Γ_twill converge to be large forrare tokens13 and small forcommon tokens13. Algorithm A also generalizes the merge operator for BooleanORqueries. Note that Algorithm A will converge to the optimum behavior in both cases while only making blackbox calls to score.
• Minterms: As stated above, refine( ) is free to toss any input I[0088]_tsuch that I_t.loc( )<candidate. However, tossing some input I_tis fruitless when knowledge of θ_t,candidatewill not affect the decision to keep or discard the candidate. For example, consider the Boolean query (A & B)|(C & D). When I_C.loc( )<I_A.loc( )<I_B.loc( )<I_D.loc( ), then candidate=I_B.loc( ). Knowledge of whether C contains candidate is irrelevant; the next location where we are interested in C is at I_D.loc( ). Therefore, C should not be tossed until candidate=I_D.loc( ). We say that an-input I_tis part of a minterm in the current state when its θ_t,candidatecan affect the decision to keep or discard the candidate when combined with other inputs.
• An input that is part of a minterm can be found efficiently using monotonicity of the score upper bound when a parameter is changed from huh to null: Order the inputs with I[0089]_t.loc( )<candidate arbitrarily. Recall that these inputs pass huh parameters to the score function. We will use the known θ_t,candidate(null or non-null) for inputs with I_t.loc( )≧candidate. Notice that with all these θ_t,candidateand huh values, lower≦threshold<upper because we are in refine( ). We can find the first input from our ordering that is part of some minterm in the following way: one-by-one change a huh to null and reevaluate the score bounds. By monotonicity, upper will decrease or remain constant and lower will increase or remain constant. The first input to make upper≦threshold or threshold<lower is part of some minterm. Such an input will be always be found because if the last huh value is changed to null, then lower=upper and one of the two conditions must be met.
• The minterm algorithm works with any ordering, but some orderings are better than others. In particular, we can order the inputs based upon our preference to toss them, based upon sparsity (given or learned), cost to toss, or some combination. In doing so, we toss the most preferred input from some minterm. Note that that a more preferred input may be part of another minterm. However, every minterm will need to be handled before we can advance the candidate, unless we conclude that the candidate is in the result. For sparsity-ordered inputs, we choose the sparsest input from the densest minterm; this gives us the best chance to prove the candidate is in the result and advance the candidate. To minimize cost, the algorithm can be easily extended to find the least cost input that is part of some minterm (order by decreasing cost and find the complete minterm by restoring the last value to huh and continuing to set huh to null looking for each input that causes a bound to cross the threshold).[0090]
• Hard-Coding nextCand( ): In some cases, it is possible to compute nextCand( ) for all[0091]possible θ_t4 huh values. This computation further reduces repeatedly calling score.
• Aggressive Heap Initialization. The efficiency of Algorithm A can be increased by using Aggressive Heap Initialization. In embodiments involving this optimization, dummy entries with high (but not too high) scores are inserted in the heap during initialization. This inflates the value of threshold, and consequently, fewer candidate values get examined. In order to illustrate this, refer FIG. 3, and consider what will happen if the threshold value is increased. The danger incurred in using optimization is that fewer than l documents may be returned. Depending on the[0092]query8, such initialization can (but does not always) result in a performance enhancement. In this regard, consider FIG. 7.
• FIG. 7 shows that Algorithm A benefits by aggressive threshold setting, as is expected. The figure shows four standard scoring functions[0093]12, TFIDF, Lexical Affinities (LA), and the aggressively thresholded versions of TFIDF-t and LA-t. The bars chart the performance in terms of the number of toss( ) operations of Top-10 queries on run on a single platform. The threshold for TFIDF-t and LA-t was set to be the best possible, (i.e. the tenth highest score with the conjunctive and disjunctive Boolean queries in the last two columns to provide a baseline to interpret the main results). In queries Q3.2 and Q3.3, aggressive heap initialization helped. In query Q3.2, it helped TFIDF by a factor of 4. In query Q3.3, it helped both TFIDF and LA by a factor of 2.7 and 1.9 respectively. The queries used were proper name search queries of increasing complexity (i.e., they expanded initials, and looked for alternate forms (“Bob” OR “Robert”)).
• Static Scores. Many search engines have a static component to the[0094]SCOREfunction. One example involves use of PageRank, which measures the desirability of a page independent of the query q. Algorithm A can be used to account for static scores as well. In one embodiment, avirtual token13 is added (e.g., :static:) to eachdocument7 and set θ_:static:,dto be the static score (predetermined score) for d. In another embodiment, the static score is included in every θ_t,d. When the documents are ordered by decreasing static score in the index (i.e., the documents are considered by Algorithm A in decreasing static score), then the partial score function can use the static score of any document≦candidate as an upper bound for all locations≧candidate. Typically, this results in a decrease in the upper bounds of future documents. In particular, the upper bound when nothing is known about a document (i.e., score (huh, huh, . . . , huh) given the upper bound of static) generally decreases; when the upper bound of score with all huh values is below threshold, Algorithm A terminates early without considering any of the remaining documents.
• Unsafe Approximations in upper. Algorithm A permits under-estimates when computing upper, which trades recall for performance. Typically, the closer the under-estimate, the better the recall. If upper is always an over-estimate, then A will find the exact result. Typically, the closer the over-estimate, the better the performance. Testing in this instance involved use of the Lexical Affinity[0095]SCOREfunction, which scoresdocuments7 based on the reciprocal of the distance between the query terms. The closer the terms are located within thedocument7, the higher the score. A conservative value of upper was derived assuming that each wildcard query term occurs at a distance of one from every other query term. FIGS. 8-9 depict the effect of relaxing this assumption. The X-axis is the reciprocal of the assumed distance between query terms. Unsafe approximations can offer large gains in performance, without necessarily sacrificing significant quality of theresults9.
• Referring to FIGS. 8-9, the two figures show the loss in recall and the gain in performance respectively when the implementation of score does increasingly unsafe approximations of the LA (Lexical Affinity) function by assuming that the default reciprocal distance is the X axis.[0096]
• Incremental Evaluation: Algorithm A treats evaluations of SCORE as cheap and consequently may use a number of evaluations. However, if SCORE is relatively expensive to evaluate, A may run into a computational (rather than an I/O) bottleneck. Preferably, incremental evaluation is used to at least partially address potential computational problems. In the Boolean context, this concern can be addressed by hard coding the evaluation of nextCand( ) and refine( ). When dealing with scoring functions, both nextCand( ) and refine( ) are not simply functions of the location order of the simple predicates, but depend in a non-trivial manner on the data associated with iterator locations. Accordingly, an object interface to scoring functions may be used, rather than a functional one. In this embodiment, the scoring object will maintain the state of each of the k input parameters as well as the current candidate location, loc. One example of interface methods to manipulate the state is provided as follows:[0097]
• 1. set(i, x, θ) sets the state of parameter i[0098]_χ[k] to (x, θ).
• 2. setLoc(loc) sets the candidate location to loc.[0099]
• 3. getScoreo returns the score.[0100]
• Incremental evaluation of[0101]SCOREcan result in a more streamlined runtime at the cost of some additional programming work. Recalculating theSCOREdynamically when a variable is updated can be significantly cheaper than de novo evaluations of the score.
• Combining Scores and Aggregation. Combining[0102]SCOREfunctions may be performed. For example, if the desired scoring metric isSCORE(d)=λ₁SCORE₁(d)+λ₂SCORE₂(d), then the implementations of score can be combined using the same ratio. Thus, upper=λ₁upper₁+λ₂upper₂and likewise lower. Arguably, the most important combined score mixes a document's static score (e.g., PageRank) with a dynamic score (e.g., TFIDF or LA). FIG. 10 shows that Algorithm A behaves sublinearly when it combines scores. This is preferred over when the two score functions are computed independently and then added together.
• As one may surmise, refining the score range for the candidate location may involve any one, or a combination of, techniques for advancing the input iterator I[0103]_t. For example, in one embodiment, the input iterator I_tthat is set to a location before the candidate location is advanced to the candidate location and the score range is reevaluated. In another embodiment, the input iterator I_tis randomly selected for advancement. In another embodiment, input iterators I_tare advanced in a round-robin fashion. In another embodiment, the input iterator that is the least expensive is advanced. In one embodiment, the sparsest input iterator I_tis advanced. One example of this embodiment calls for identifying the sparsest input iterator by measuring the effectiveness of the input iterator I_tto advance the candidate location. In this case, one measure includes measuring the effectiveness by dividing total progress attributed to the input iterator I_tby a number of toss operations for the input iterator I_t.
• In a further embodiment, refining the score range for the candidate location involves advancing a first iterator in an order of iterators set before the candidate location which is chosen such that when all iterators set after the chosen iterator are assumed to occur at the candidate location, all iterators before the chosen iterator are assumed to not occur at the candidate location, the upper bound is above the threshold when the chosen iterator is assumed to occur at the candidate location, and the upper bound is below the threshold when the chosen iterator is assumed to not occur at the candidate location.[0104]
• Consider again the choice of index based document at a time (DAAT) strategies versus term at a time vector based (TAAT) strategies for implementing a query. The modern opinion is that for large data sets, the index based runtimes outperform the vector based runtimes. However, index based runtimes are hard to implement and each ranking engine is built as a specially engineered, custom system.[0105]
• To address this issue, information retrieval engines are typically built using a two layer architecture. The[0106]scoring function12 is approximated using a Boolean query. The lower stage performs index based retrieval based on the Boolean query (or near Boolean query—Boolean with a “near” operator) which is then passed downstream to the ranking stage for a complete evaluation. This strategy is a more efficient version of algorithm 1.2. The filtering predicate is more selective than a simple Boolean “OR.”
• From a runtime optimization perspective, this architecture has two potential problems. First, there is the need for a layer for approximating query into Boolean form. This can be a complicated or even an impossible process for black box scoring functions. The only viable option may be using a mostly ineffective filter like the Boolean “OR” used in algorithm of Table 2. Second, even if effective approximations were possible, the resulting Boolean filter can be complicated and lead to daunting runtime optimization problems. As an example, a TFIDF like threshold Boolean query requiring any 3 of 5 given terms has a Boolean DNF form involving:[0107]$\left(\begin{array}{c}5\\ 3\end{array}\right)=10\mathrm{distinct}\mathrm{disjuncts},\text{-}\mathrm{each}\mathrm{of}\mathrm{size}3.$

  
• From a functional perspective, scoring functions[0108]12 use more information than Boolean filters do. For instance, TFIDF requires an input of the frequency of a term within adocument7, which is more intensive than whether a term is present in thedocument7. This information, available but not used in Boolean processing, represents a significant lost opportunity for runtime optimization. This opportunity is usually reclaimed by more special purpose code and compensation within the filtering phase.
• The database point of view. The database equivalent of the Information retrieval TAAT/DAAT question is the choice between bulk join methods such as Sort/Merge and Hash Join and small footprint, index aided joins such as Index Nested Loop joins. A further challenge is in handling XML documents. The challenge is two fold. First, current database community focus in XML retrieval largely concerns the Boolean domain, and does not consider information retrieval issues such as scoring concerns. Second, the retrievable entity is generally no longer a “document” but is arranged within a hierarchy.[0109]
• Having described aspects of Algorithm A, one may recognize with reference to FIG. 11 that a[0110]system100 suited for implementation of Algorithm A includes aprocessor101, which is coupled tostorage102. Also coupled to the processor is at least one input and output (1/0)device103, such as a keyboard for inputting auser query8.
• The[0111]storage102 includes a Base Table2, which is typically managed by a database manager106. Also stored instorage20 is the Algorithm A,105, which draws upon scoring functions12 as needed. The scoring functions12 may include those discussed herein, such as Boolean functions or queries, and may include intermediate devices, such as posting lists. Operation of theAlgorithm A105 occurs by the operation of theprocessor101, which queries the Base Table2, to provideresults9. Other components, such as theparser3, the token table4 and the index table6 are typically contained instorage102.
• This invention thus also pertains to a computer program product embodied on a computer readable medium, such as disk, tape and/or semiconductor or other memory. The computer program product includes computer instructions that, when executed by a data processor, such as the[0112]processor101 of FIG. 11, result in the implementation of the Algorithm A, and methods as described above.
• One skilled in the art will recognize that the invention disclosed herein is not limited to the embodiments set forth. More specifically, it is considered that the embodiment of Algorithm A, as well as the scoring functions discussed, are only illustrative of the invention herein, and are not limiting as other embodiment may be apparent to one skilled in the art.[0113]

Claims (19)

What is claimed is:

1. A computer program product embodied on a computer readable medium, the computer program product comprising computer instructions that implement a search algorithm comprising a function having an input for receiving, while there is at least one candidate location in an order of locations, a score range for the candidate location, the algorithm comparing the score range to a threshold within a range of possible scores, wherein if a lower bound of the score range for the candidate location exceeds the threshold then the candidate location is retained as a result and a next location is selected, and wherein if an upper bound of the score range is at or below the threshold the candidate location is discarded and the next location is selected, and wherein if the score of the candidate location is indeterminate, then the score range for the candidate location is refined.

2. The computer program product as inclaim 1, wherein the next location is selected by choosing the next location greater than the candidate location such that the upper bound exceeds the threshold.

3. The computer program product as inclaim 1, wherein the algorithm receives the score range from a blackbox scoring function.

4. The computer program product as inclaim 3, wherein the blackbox scoring function comprises a Boolean function.

5. The computer program product as inclaim 4, wherein the function comprises instructions for selecting the next location by choosing the next location greater than the candidate location such that the upper bound exceeds the threshold.

6. The computer program product as inclaim 3, wherein the blackbox scoring function comprises at least one of a Term Frequency Inverted Document Frequency (TFIDF) function, a Static Rank function, a Searching by Numbers function, a Lexical Affinities (LA) function a Salience Levels (SL) function and a threshold predicate function.

7. The computer program product as inclaim 3, wherein the blackbox scoring function provides an under-estimate of the score range.

8. The computer program product as inclaim 1, wherein the score range for the candidate location is refined by advancing an input iterator that is set before the candidate location to the candidate location and reevaluating the score range.

9. The computer program product as inclaim 8, wherein advancing the input iterator comprises advancing a randomly selected input iterator.

10. The computer program product as inclaim 8, wherein advancing the input iterator comprises advancing the input iterator in a round robin fashion.

11. The computer program as inclaim 8, wherein advancing the input iterator comprises advancing the input iterator that is the least expensive to advance.

12. The computer program product as inclaim 8, wherein advancing the input iterator comprises advancing the sparsest input iterator.

13. The computer program product as inclaim 12, wherein advancing the sparsest input iterator comprises measuring the effectiveness of the input iterator to advance the candidate location.

14. The computer program product as inclaim 13, wherein measuring the effectiveness comprises dividing total progress attributed to the input iterator by a number of toss operations for the input iterator.

15. The computer program product as inclaim 8, wherein advancing the input iterator comprises selecting a first iterator in an order of iterators set before the candidate location such that when all iterators after the chosen iterator are assumed to occur at the candidate location, and all iterators set before the chosen iterator are assumed to not occur at the candidate location, and the upper bound is above the threshold when the chosen iterator is assumed to occur at the candidate location, and the upper bound is below the threshold when the chosen iterator is assumed to not occur at the candidate location.

16. The computer program product as inclaim 8, wherein advancing the input iterator comprises selecting a combination of techniques.

17. The computer program product as inclaim 1, wherein the candidate location comprises a predetermined score for the score range.

18. A system for implementing a search algorithm, comprising:

a processor for operating an algorithm that comprises an input for receiving from a blackbox scoring function a score for at least one candidate location in an order of locations, wherein the algorithm compares the score to a threshold, and if the score exceeds the threshold then the candidate location is stored as a result and a next location is selected, and if the score is at or below the threshold the candidate location is discarded and the next location is selected, and wherein if the score of the candidate location is indeterminate, then the score for the candidate location is refined; wherein each result is stored in a table of results ordered by relevance.

19. A method for implementing a search of locations in a body of data for relevant terms, the method comprising:

providing an index of locations comprised of terms, wherein a score for the relevant terms in a candidate location is provided by a scoring function and associated with the candidate location; and,

while there are candidate locations:

refining the score range if the score of the candidate location is indeterminate, otherwise, storing each candidate location as a result if a lower bound of the score range for the candidate location exceeds a threshold within a range of possible scores, discarding the candidate location if the score range is at or below an upper bound for the score range and selecting a next location.

Images