Automatic Query Expansion Using SMART : TREC 3 (cid:3) Chris Buckley, Gerard Salton, James Allan, Amit Singhal Abstract TheSmartinformationretrievalproject emphasizescompletelyautomaticapproachestotheunderstand- ingandretrievaloflargequantitiesoftext. WecontinueourworkinTREC3,performingrunsintherouting, ad-hoc,andforeignlanguageenvironments. Ourmajorfocusismassivequeryexpansion: addingfrom300to 530termstoeachquery. These termscomefromknownrelevantdocumentsinthe case ofrouting,andfrom just the top retrieved documents in the case of ad-hoc and Spanish. This approach improves e(cid:11)ectiveness from7% to 25% in the variousexperiments. Other ad-hocworkextends ourinvestigationsintocombiningglobalsimilarities,givinganoverallindica- tion of how a document matches a query, with local similarities identifyinga smaller part of the document whichmatchesthequery. Usinganoverlappingtextwindowde(cid:12)nitionof\local",weachievea16%improve- ment. Introduction For over 30 years, the Smart project at Cornell University has been interested in the analysis, search, and retrieval of heterogeneous text databases, where the vocabulary is allowed to vary widely, and the subject matter is unrestricted. Such databases may include newspaper articles, newswire dispatches, textbooks, dictionaries,encyclopedias, manuals,magazinearticles,andsoon. Theusualtextanalysisandtext indexing approaches that are based on the use of thesauruses and other vocabulary control devices are di(cid:14)cult to applyinunrestricted textenvironments,because thewordmeaningsarenotstableinsuchcircumstancesand theinterpretationvariesdependingoncontext. Theapplicabilityofmorecomplextextanalysissystemsthat are based onthe construction ofknowledgebases coveringthe detailed structure ofparticularsubject areas, together with inference rules designed to derive relationships between the relevant concepts, is even more questionable in such cases. Complete theories of knowledge representation do not exist, and it is unclear what concepts, concept relationships, and inference rules maybe needed to understand particular texts.[13] Accordingly, a text analysis and retrieval component must necessarily be based primarilyon a study of the availabletexts themselves. Fortunately verylarge text databases are now availablein machine-readable form, and a substantial amount of information is automatically derivable about the occurrence properties of words and expressions in natural-language texts, and about the contexts in which the words are used. This information can help in determining whether a query and a text are semantically homogeneous, that is, whether they coversimilarsubject areas. When that is the case, the text can be retrieved in response to the query. Automatic Indexing In the Smart system, the vector-processing model of retrieval is used to transform both the available infor- mationrequests as well as the stored documents intovectors of the form: Di =(wi1;wi2;:::;wit) where Di represents adocument(or query) text and wik isthe weightoftermTk indocumentDi. Aweight of zero is used for terms that are absent from a particular document, and positive weights characterize (cid:3)Departmentof ComputerScience,Cornell University,Ithaca, NY 14853-7501. This studywas supportedin part bythe NationalScienceFoundationundergrantIRI93-00124. terms actually assigned. The assumption is that t terms in all are available for the representation of the information. In choosinga termweightingsystem, lowweightsshould be assigned tohigh-frequency terms that occur in many documents of a collection, and high weights to terms that are important in particular documents but unimportantin the remainder of the collection. The weightof terms that occur rarely in a collection is relatively unimportant, because such terms contribute little to the needed similarity computation between di(cid:11)erent texts. A well-knownterm weightingsystem followingthat prescription assigns weightwik to term Tk in query Qi in proportion to the frequency ofoccurrence of the termin Qi, and ininverseproportion to `the number of documents to which the term is assigned.[14, 12] Such a weighting system is known as a tf(cid:2)idf (term frequency times inverse document frequency) weighting system. In practice the query lengths, and hence the numberofnon-zero termweightsassignedto aquery,varieswidely. Toallowameaningful(cid:12)nalretrieval similarity, it is convenient to use a length normalization factor as part of the term weighting formula. A high-qualityterm weightingformulafor wik, the weightof term Tk in query Qi is (log(fik)+1:0)(cid:3)log(N=nk) wik = Ptj=1[(log(fij)+1:0)(cid:3)log(N=nj)]2 (1) where fik is the occurrence frequency of Tk in Qi, N is the collection size, and nk the number of docu- ments with term Tk assigned. The factor log(N=nk) is an inverse collection frequency (\idf") factor which decreases as terms are used widely in a collection, and the denominatorin expression (1) is used for weight normalization. This particular formwillbe called \ltc" weightingwithin this paper. The weights assigned to terms in documents are much the same. In practice, for both e(cid:11)ectiveness and e(cid:14)ciency reasons the idf factor in the documents is dropped.[2, 1] The terms Tk included in a given vector can in principle represent any entities assigned to a document for content identi(cid:12)cation. In the Smart context, such terms are derived by a text transformation of the followingkind:[12] 1. recognize individualtext words 2. use a stop list to eliminateunwantedfunction words 3. perform su(cid:14)x removalto generate word stems 4. optionallyuse termgroupingmethodsbased on statisticalwordco-occurrence or wordadjacency com- putations to formterm phrases (alternativelysyntactic analysis computationscan be used) 5. assign term weights to all remaining word stems and/or phrase stems to form the term vector for all informationitems. Once term vectors are availablefor allinformationitems, allsubsequent processing is based on term vector manipulations. Thefactthattheindexingofbothdocumentsandqueries iscompletelyautomaticmeansthatthe results obtained are reasonably collection independent and should be valid across a wide range of collections. No humanexpertise inthesubject matterisrequiredforeithertheinitialcollectioncreation,ortheactualquery formulation. Phrases Thesamephrasestrategy(andphrases) usedinTREC1andTREC2([2,1])areusedforTREC3. Anypair of adjacent non-stopwords is regarded as a potential phrase. The (cid:12)nal list of phrases is composed of those pairs of words occurring in 25 or more documents of the initial TREC 1 document set. Phrase weighting is again a hybrid scheme where phrases are weighted with the same scheme as single terms, except that normalization of the entire vector is done by dividing by the length of the single term sub-vector only. In this way, the similarity contribution of the single terms is independent of the quantity or quality of the phrases. Text Similarity Computation When the text ofdocumentDi is represented byavectors ofthe form(di1;di2;:::;dit) andquery Qj bythe vector (qj1;qj2;:::;qjt), a similarity (S) computation between the two items can conveniently be obtained as the inner product between corresponding weightedterm vector as follows: t S(Di;Qj)= (dik(cid:3)qjk) (2) k=1 Thus, the similarity between two texts (whether query or document) depends on the weights of coinciding terms in the twovectors. TREC 3 Approaches One way to improve e(cid:11)ectiveness is to better represent the information need by adding useful terms to the query. The classical example of this is relevance feedback, where terms occurring in known relevant documents are added to the query. The relevance feedback process can be divided into two phases: query term selection and query term weighting. Our basic approach to relevance feedback heavily emphasizes query term weighting. Proper weighting allows us to massively expand the query by adding any term for which we have any evidence of usefulness. Experiments show that e(cid:11)ectiveness improves linearly as the log of the number of added terms, up to a pointofdiminishingimprovement[3]. This pointof diminishingreturns for the TREC environment seems to be about 300 terms. How can so many terms be added, when it is known that many of them are poor terms and have no connection with relevance? One contributing factor is simply that the good terms tend to co-occur non- randomlywithin the relevantdocuments (as opposed to the rest of the collection) and the poor terms tend to co-occur randomly. Massive expansion establishes a background \noise" similarity due to random poor term matches. The good documents escape the noise due to several good terms co-occurring within the document. Some other expansion methods (eg naive thesaurus lookup) do not share the above property. When expansion occurs inappropriately,several connected poor words are added. Attemptingto expand the word \bank"forinstance,onemightaddseveral(cid:12)nancialterms,whichmayreinforceeachotherandcause(cid:12)nancial documentstobe retrieved. This wouldresult in poorretrievalif\bank"werereferring tothe side ofariver. The poor terms for this query expansion are not co-occurring randomly and have a much greater e(cid:11)ect on the (cid:12)nal similarity. Expansionbyhundredsoftermsoccurringinknownrelevantdocumentsworkedsosuccessfullyinrouting of TREC 2, that it was decided to use the sameexpansion techniques in the ad-hoc portion of TREC 3. In the ad-hoc environment,there are no known relevantdocuments. Instead, the top retrieved documents are all assumed to be relevant for the purposes of expansion and weighting. If many of the top documents are relevant,then the process achieves the same e(cid:11)ect as relevance feedback. If none of the top documents are relevant,then the expansion is likelyto have a very negative e(cid:11)ect as the refashioned query will emphasize the same mistakes that caused the poor initial retrieval. The end result is thus likely to be a mixture of improvements for manyqueries, but deterioration of results for others. The ideaoftreatingthe top documentsasbeing relevantinthe absence ofanyrealrelevancejudgements is not a new one. It has probably been done dozens of times in the past (eg, it was a standard Cornell information retrieval class project in the early 1980's). In general, at least in the Cornell experience, it helped some queries but the negative results predominated on the standard small test collections. What makes the approach successful in the TREC environment is the combinationof better initial retrieval, and the collection characteristics of TREC. There are manymore relevant documents per query within TREC, andthosedocumentsarelongerthaninthesmalltestcollections. Sothere ismoreofachancefortermsfrom the relevantretrieved documentsto meaningfullydistinguish themselves fromthe terms in the non-relevant documents. Other groupsinTREC2wereabletotakeadvantageofthissituationandimproveperformance, noticeably UCLA and CMU [6, 7]. Another focus of our work the past few years, both within TREC and outside it, has been trying to take advantageof local similarities between a smallpart of the documentand the query. We'veshown that local similarities can be used very e(cid:11)ectively to ensure that terms in commonbetween documentand query are being used in the same semantic sense. However, while this semantic disambiguation is important in otherenvironments[16],theverylongandrichTRECqueriesprovideenoughglobalcontexttodisambiguate withoutgoingtoalocallevel. Oure(cid:11)orts toimprovee(cid:11)ectiveness usinglocaldisambiguationusingsentences and short paragraphs did not workin TREC 1 and TREC 2. For TREC 3, we lengthen our local contexts, and treat the localpassage as beinga mini-document. Adoptingthe approachofUMass [17,4,5],wede(cid:12)ne our local contexts to be a set of overlapping text windows, each of (cid:12)xed size. This avoids the length and normalizationproblems that adversely a(cid:11)ected our approachin TREC 2. System escription The Cornell TREC experiments use the SMART InformationRetrievalSystem, Version 11, and are run on a dedicated Sun Sparc 20/51with 160 Megabytes of memoryand 18 Gigabytes of local disk. SMART Version 11 is the latest in a long line of experimental information retrieval systems, dating back over 30 years, developed under the guidance of G. Salton. Version 11 is a reasonably complete re- write of earlier versions, and was designed and implemented primarily by C. Buckley. The new version is approximately44,000 lines of C code and documentation. SMART Version 11 o(cid:11)ers a basic framework for investigations of the vector space and related models of information retrieval. Documents are fully automatically indexed, with each document representation being a weighted vector of concepts, the weight indicating the importance of a concept to that particular document(asdescribed above). Thedocumentrepresentativesarestored ondiskasaninverted(cid:12)le. Natural languagequeries undergo thesameindexingprocess. The queryrepresentativevectoristhen comparedwith the indexed document representatives to arrive at a similarity (equation (2)), and the documents are then fully ranked bysimilarity. Routing Experiments OurroutingexperimentsinTREC3areonlyslightlydi(cid:11)erentfromthosecarried outforTREC2. Thebasic routing approach chosen is the feedback approach of Rocchio [11, 15, 1]. Expressed in vector space terms, the (cid:12)nal query vector is the initialquery vector moved towardthe centroid of the relevant documents, and awayfromthe centroid of the non-relevantdocuments. Qnew = A(cid:3)Qold + B(cid:3)average wt in rel docs (cid:0) C(cid:3)average wt nonrel docs Terms that end up with negative weights are dropped (less than 3% of terms were dropped in the most massive query expansion below). The parameters of Rocchio'smethod are the relativeimportance of the originalquery,the relevantdoc- uments,andthe non-relevantdocuments(A,B,C above);and then exactly whichterms are tobe considered part of the (cid:12)nal vector. The investigationsofTREC 2 and elsewhere [3]suggest that the decision of whichterms to add is not a hard decision: just add all terms occurring in relevant documents that can be e(cid:14)ciently handled. We sort all terms occurring in the relevant documents by the number of relevant documents in which they occur, with ties being broken by considering the highest average weight in the relevant documents. We then add the top 300 single terms and top 30 phrases to the original query and reweight according to the Rocchio formulaabovewith A,B,C parameters being 8,16,4. This forms the queries for our CrnlRRrun. uery-by- uery ariations WhilethemassiveexpansionRocchioapproachworkswellformostqueries, examiningpastindividualquery results reveals that for about 15% of the queries, not expanding works better than massive expansion[3]. Run Best median median CrnlRR 1 44 5 Crnl R 2 37 11 Table1: Comparative RoutingResults Run : A:B:C R-prec TotalRel recall-prec 1. no fdbk 0.0 8.0.0 3461 5975 2985 2. no expand 0.0 8.8.4 3698 6342 3163 3. CrnlRR 300.30 8.16.4 4064 7134 3699 4. Crnl R varies varies 4013 7215 3725 Table2: Routingevaluation Our second o(cid:14)cialrun, likeour second o(cid:14)cialrun of TREC2, isan attemptto choosefeedback parameters onaper-query basistoavoidexpandingon those queries where no expansionmightbe appropriate. Wealso want to examine other feedback approaches for those queries with no, or little, expansion. In TREC 1 and TREC 2 it was noticed that the probabilistic approaches, e.g., the classical probabilistic formula [10] and Dortmund'sRPI formula[8, 9],did better than the Rocchioapproachifthere waslittleexpansion. Perhaps a choice amongfeedback methods wouldimprovee(cid:11)ectiveness; our TREC 2 results suggested just changing expansion amountson a per-query basis wouldyield only a smallimprovement. We examineseven di(cid:11)erent approaches: 1. : Originalquery, no expansion or reweighting. 2. : Probabilistic weights,no expansion. 3. : RPI model,no expansion 4. : RPI model,expansion by 30 single terms 5. : Rocchio,expansion by 30 single terms and 10 phrases 6. : Rocchio,expansion by 500 single terms 7. : Rocchio,expansion by 500 single terms and 30 phrases, with A,B,C parameters being 8,32,4 We ran each of these approaches using the 50 queries of the TREC 3 routing task, learning on D1 and testing on D2. This determined which approach should be used for which queries in the routing task. The (cid:12)nal queries for the Crnl R run are formed by using the best approach on each query, and learning from the full D12 set of relevance judgements. outing esults Both CrnlRR and Crnl R do quite well in comparison with other TREC 3 routing runs (Table 1). These comparative results are not quite as good as in TREC 2, suggesting that some other groups might have caught up to us. Evaluation measures in Table 2 for both the o(cid:14)cial and some non-o(cid:14)cial runs show the importance of query expansion. Run1isthe base case originalquery only(ltc weights). Just re-weightingthe query terms without addinganyterms according to Rocchio'salgorithmgivesa 6% improvement. Both reweightingand massivelyexpanding givesa 24% improvement. The run Crnl R is actually quite disappointing. Like our initial attempts at per-query variations in TREC 2, we get very little improvement over using massive expansion for all queries. Table 3 shows that Approach Expansion Rocchio Num Num better Sing.phrs A:B:C ueries than CrnlRR 1. Orig. query 0.0 n.a. 3 1 2. Prob 0.0 n.a. 4 0 3. RPI 0.0 n.a. 9 3 4. RPI 30.0 n.a. 2 1 5. Rocchio 30.10 8.16.4 3 1 6. Rocchio 500.0 8.16.4 9 5 7. Rocchio 500.30 8.32.4 20 15 Table3: RoutingApproach Variation of all the feedback variations tried, the only ones that consistently do better than the CrnlRR Rocchio expansion by 330 terms, are the queries which use Rocchio and expand by even more terms. The low expansion approaches did better on their queries when learning on D1 and testing on D2, but tended to do worse on their queries when learning on D12 and testing on D3. This suggests that there is no inherent property of the semantics of an individual query that can predict whether massive expansion will work. Instead, it suggests the e(cid:11)ectiveness of massive expansion depends on the properties of the documents, in both the learning set and the test set. Ad-hoc Results The(cid:12)rstofCornell'stwoad-hocruns,CrnlEA,isverysimilartotheRocchioroutingrun,CrnlRR.Theinitial query isexpanded andreweightedusingRocchio'sfeedbackapproach. Themajordi(cid:11)erence isthatthere are no knownrelevantdocumentsfromwhich to drawthe expansion terms. Instead, an initialretrievalis done, and the top 30 documents are all assumed to be relevant for the purposes of expansion and reweighting. While this is certainly not as good as having real relevance judgements (especially if the initial retrieval obtains no relevantdocuments), these terms should still havesome connection to relevance. The initialquery is expanded by 500 terms and 10 phrases. In the future, perhaps more phrases should be chosen. However, in this initialexperiment havingmanyphrases would complicate the analysis of what is actually happening. The A:B:C parameters of the Rocchio equation are set to 8.8.0. These parameters weighttheoriginalquerytermshigherthaninstandardrelevancefeedback,anddisregardoccurrences among the non-relevant documents. The parameters were chosen after a smallset of trial runs using the (cid:12)rst 150 queries on D12. The second of Cornell's ad-hoc runs, CrnlLA, is this year's local/global run. At retrieval time, each documentis assigned a similaritybased upon both the document's globalsimilarityto the query,and upon thesimilaritiesofsmallerpartsofthedocumenttothequery. Forthisexperiment,thepartsofthedocument are de(cid:12)ned to be text windows of 200 words in length. One set of text windows starts at the beginning of the document, with a new window every 200 words. Another set of text windows on that document starts 100 words into the document, with a new window every 200 words. The two sets of overlapping windows ensure that every semantically coherent chunk of text of length less than 100 words will be included whole in at least one text window. The text ofeachlocalwindowisindexed and weightedwith binarytermweights(SMART-nomenclature \bnn" weights). The weights in the text windows do not need to be normalized since the text windowsare almost all of the same length. An \idf" factor does not need to be included in the local document weights since it will be included in the query weight of any matchingterm. A pure \tf" factor that gives a weight proportionaltothenumberoftimesatermoccurs inthetext windowwillover-weightcommonwords. Thus the \bnn" weightingscheme wouldseem to be appropriate. The question of how to combine a global similarity with the local similarity of a document has yet to be resolved. Work done in preparation for TREC 2 strongly suggested that the result should be some combination of the global similarity with the best local similarity of the document (as opposed to, say, an Run Best median median CrnlEA 3 38 9 CrnlLA 0 49 1 Table 4: ComparativeAd-hoc results average of local similarities). Other work showed that the values of both global and local similarities are querydependent. Agoodlocalsimilarityforonequerymaybeapoorlocalsimilarityforanotherquery. This suggests some sort of query relativizationfactor maybe needed. Severalfunctions were tried in preparation for TREC 3; the one used for the run CrnlLA is FinalSim = GlobalSim+2(cid:3)GlobalSim(cid:3)LocalSim=BestLocalSim (3) where (cid:15) GlobalSimis the global similarity between an \ltc" weighted query, Q, and an \lnc" weighted docu- ment,D. (cid:15) LocalSim is the highest similarity of any \bnn" weighted text window of D with the \ltc" weighted query Q. (cid:15) BestLocalSim is the highest LocalSimfor any examineddocument for this query Q. The CrnlLA retrieval procedure to return rankings for 1000 documentsis to 1. Performa global search retrieving the top 1750 documents. 2. Foreach retrieved document, (a) Fetch the originaldocument, (b) Break it intotext windows, (c) Index and weighteach text windowseparately (d) Calculate the similarityof each text windowto the query. (e) Set the document'sLocalSimto the highest of these similarities. 3. Set BestLocalSim to the highest LocalSimamongthe 1750documents 4. Use Equation 3 to calculate a (cid:12)nal similarityfor the 1750 documents. 5. Rank the (cid:12)nal similarities and return the top 1000. The expansion run, CrnlEA, and the local/globalrun, CrnlLA, are very di(cid:11)erent but each perform well when comparedagainstother systems. Both approaches performator abovethe medianinmostqueries, as can be seen in in Table 4. As could be expected, CrnlEA issomewhatinconsistent,performingextremelywellon somequeries, but dipping below the median on several others. Presumably this is related to the quality of the initial search, though this has not yet been tested. CrnlLA is almostalwaysabove the median,but was never the highest rated run. Table5givestheresultsofseveralevaluationmeasuresforCrnlEA,CrnlLA,andasimple\lnc.ltc"vector run. EachoftheTREC3approachesgivessubstantialrecall-precisionimprovementoverthepurevectorrun (20.3% for CrnlEA, and 16.2%for CrnlLA). However,they get this improvementin very di(cid:11)erent fashions. Run Recall- TotalRel Precision Precision Precision Retrieved 5 docs 100 docs lnc.ltc 2842 6531 5530 3780 CrnlEA 3419 7267 5760 4168 CrnlLA 3302 6808 6800 4216 Table5: Ad-hoc results CrnlEA is a recall oriented approach. It shows a very mild.023 improvement in precision at 5 documents, but retrieves a very strong 736 more relevant documents than the vector run. CrnlLA, on the other hand, is a precision oriented approach. It shows a very strong .1270 improvement in precision at 5 documents, but then a much weaker increase of 277 relevant documents retrieved. It remains to be seen whether the strengths of these twovery di(cid:11)erent approaches can be combinedin one run. Spanish One of the fun side-tracks of TREC 3 is the Spanish experiments. About 200 megabytes of Spanish text and 25 Spanish queries were madeavailablefor runs in the ad-hoc environment. Our claimhas alwaysbeen that SMARTis to a large extent language independent, as long as the language is based upon recognizable word tokens. TREC 3 Spanish presented a chance to test this claim. Spanis S Unlike other retrieval systems, SMARTuses almostno linguistic knowledge. Enabling SMART to run well on Spanish text only required 3 subtasks. 1. Make SMART8-bit clean. 2. Fashionstemmingrules for Spanish. 3. Construct a stopwordlist of commonSpanish words. Extending SMART to handle 8-bit characters (e.g., the accented Spanish characters) instead of 7-bit ASCIIwasverysimple. About8linesofcodeneeded changing,plusa128entrytableinthetokenizergiving the class of characters needed to be expanded to 256 entries. After this was done, the Spanish document set was indexed without any stemming rules or stopwords. Simple stemming rules were then derived by looking at the sorted dictionary entries and guessing which lexicographically adjacent entries really represented the same words (guessing since the person doing this does not speak Spanish!). The (cid:12)nal stemmingrules were: (cid:15) Remove(cid:12)nal \as", \es", \os", \a", \o",\e". (cid:15) Change (cid:12)nal \z" to \c". Initially the stopword list was composed of the 800 most frequently occurring words in the collection. This was later trimmedto 342 words by asking a native Spanish speaker to prune the list. The Spanish collection was then re-indexed using the new stemming rules and stopword list, and was ready for use. It was,however,somewhatdisconcerting to type the (cid:12)rst query \This is a test", and retrieve alargeset ofEnglishdocumentsdealingwithstandard tests! The explanationturned outtobe a partial(cid:12)le of English documentsthat had somehowcrept intothe distributed collection. The total timeto makeSMART Spanish ready wasabout 5-6 person-hours. Run Best median median CrnlES 11 8 4 CrnlVS 1 13 9 Table6: Comparative Spanish Ad-hoc results Run Recall- TotalRel Precision R-Precision Precision Retrieved 5 docs CrnlES 5692 2439 7917 5578 CrnlVS 5301 2402 7500 5328 Table 7: Spanish Ad-hoc results Spanis - oc uns The two Cornell Spanish runs are CrnlVS, a simple \lnc.ltc" vector run, and CrnlES, a massive expansion run. Both procedures are described above in the main-line ad-hoc description; aside from the di(cid:11)erent database names there is no di(cid:11)erence in the scripts whichrun the experiments. Table 6 shows the tworuns both do very well, though the expanded run is signi(cid:12)cantly better. CrnlES has the best results on 11 out of the 23 Spanish queries with relevance documents. (But remember that manyfewer groups submitted Spanish runs, so our \share" of best results is expected to be higher.) The results of the standard evaluation measures show extremely good retrieval e(cid:11)ectiveness in Table 7. However, many of these values are arti(cid:12)cially high. Unlike the mainstream ad-hoc and routing pools of judged documents, the Spanish pool was very small and narrow, and it's clear that a lower percentage of relevantdocumentswerejudged,thussomewhatin atingtherecall(cid:12)gures. Comparativeevaluationbetween runs shouldstillbevalidthough,evenbetweenjudgedandunjudgedruns. Forexample,CrnlESisde(cid:12)nitely better than CrnlVS even though CrnlVS was a judged run and CrnlES was not. After the actual conference, additional relevance judgements on the Spanish TREC runs were made by NIST. The top 150 documents from every Spanish run were judged (as opposed to the judgement of 100 documentsfromonerunofeachparticipant,whichiswhatTable7wasbased upon.) Table 8showthatthe additional judgements had very little e(cid:11)ect on the (cid:12)nal results, despite the addition of 50% more relevant documents to the total judged pool. E ciency E(cid:14)ciency issues are becoming increasingly important in these TREC experiments as retrieval methods become more complicatedand expensive. Thus it is importantto haveat least somediscussion of e(cid:14)ciency within a paper likethis. SMART is a reasonably fast system. It indexes documents at a rate of about 600 megabytes per hour. Simple vector retrieval runs can be quite fast. Calculating the similarities for the CrnlVS run took much less than 2 seconds for all 25 queries together (keeping track of the top 1000 documents for each query was Run Recall-Precision Old Judgements New Judgements CrnlES 5692 5697 CrnlVS 5301 5013 Table8: Spanish with New Judgements Methodology Run Recall- Improvementover Precision Previous ear TREC 1 ntc.ntc 2067 - TREC 2 lnc.ltc 2842 38% TREC 3 CrnlEA 3419 20% TREC 3 CrnlLA 3302 16% TREC 4 ??? ???? 20%? Table 9: Runs of queries 151{200 on D12 donerather ine(cid:14)cientlyandtookmuchlonger!). Butthemorecomplicatedretrievalmethodstakeanywhere from9 seconds per query (CrnlRR) to 189 seconds per query (CrnlLA). Luckily,in actual practice the execution times of the complicated methods can be cut down drastically. Themassivequeryexpansionapproacheswillbene(cid:12)tgreatlyfromoptimizatione(cid:11)ortssuchasthosediscussed inourTREC1work. Someofthee(cid:11)ectivenessincreaseofthemassivequeryexpansionwillhavetobetraded back in order to get reasonable e(cid:14)ciency, but the results of TREC 1 show the e(cid:11)ectiveness cost willnot be prohibitive. The other verytimeconsumingapproachofours is the local/globalmatching(CrnlLA).The re-indexing ofthelocalpartsofadocumentcanbedoneo(cid:11)-lineandstored. Whenthistimesavingsiscombinedwiththe decreased time due to a user asking for a reasonable number of documents (instead of 1000), retrieval time should be not muchmore than double an ordinary vector search. This should be quite feasible in practice, depending on the particular constraints of a site, of course. Comparison ith TREC and TREC It is di(cid:14)cultto determine howmuchsystems are improvingfromTRECto TREC since the queries and the documents are changing. For example, in TREC 3 the \Concept" (cid:12)eld of the queries was removed. These terms proved to be very good terms for retrieval e(cid:11)ectiveness in TREC 1 and TREC 2; thus the TREC 3 task without them is a harder task. To get a handle on how much SMART has improved in the past two years,Table9presents theresults ofrunningourTREC1andTREC2systemsontheTREC3ad-hoctask. SMART has been improving at a rate of over 20% per year so far, and given our work since we submitted the TREC 3 runs, we wouldexpect that improvementrate to continue at least another year. Conclusion Automaticmassivequery expansionprovesto be verye(cid:11)ective forrouting. Conventionalrelevancefeedback techniques are used to weight the expanded queries. Once again, however, the option to choose feedback approaches on a per-query basis doesn't help signi(cid:12)cantly,where the choice is based on what workedin the past for this query. Massivequeryexpansionalsoworksingeneralforthead-hocexperiments,whereexpansionandweighting are based onthe topinitiallyretrieved documentsinstead ofknownrelevantdocuments. In the ad-hocenvi- ronmentthisapproachmayhurtperformanceforsomequeries(e.g.,those withoutmanyrelevantdocuments in the top retrieved set), but overallproves to be worthwhilewith an average20% improvement. Incorporating both global and local similarity information in the (cid:12)nal ranking is useful, with improve- mentsof 16%. Care needs to be taken,though, both inthe de(cid:12)nition ofa localpart of a document(making all parts equal length helps the weightingtask enormously), and in the combinationof the local and global similarity. SMART is very easily adaptable to at least some foreign languages, even without knowledge of the languages. PerformanceofSMARTappears to be just as goodin the foreignlanguageas inEnglish,though this is tough to judge.