数据库系统概念(databasesystemconcep

1、C H A P T E R 21Information RetrievalPractice Exercises21.1Compute the relevance (usingappropriate denitionsof term fre-quency and inverse document frequency of each of the Practice Ex-ercises in this chapter to the query “SQL relation ”. Answer:We do not consider the questions containing neither of

2、 the keywords as their relevance to the keywords is zero. The number of words in a question include stop words. We use the equations given in Section 21.2to compute relevance; the log term in the equation is assumed to be to the base 2. 21.2Suppose you want to nddocuments that contain at least k of

3、a givenset of n keywords. Suppose also you have a keyword index that gives you a (sortedlist of identiersof documents that contain a speciedkeyword. Give an efcientalgorithm to ndthe desired set of docu-ments. Answer:Let S be a set of n keywords. An algorithm to ndall docu-ments that contain at leas

4、t k of these keywords is given below :12Chapter 21Information RetrievalThis algorithm calculates a reference count for each document identi-er.A reference count of i for a document identierd means that at least i of the keywords in S occur in the document identiedby d . The algorithm maintains a lis

5、t of records, each having two eldsa document identier,and the reference count for this identier.This list is maintained sorted on the document identiereld.initialize the list L to the empty list; for (eachkeyword c in S dobeginD :=the list of documents identierscorresponding to c ;for (eachdocument

6、identierd in D doif (arecord R with document identieras d is on list L thenR . re f erence :=R . re f erence count +1;else beginmake a new record R ; R . document :=d ;R . re f erence :=1;add R to L ; end ;end ;for (eachrecord R in L doif (R . re f erence >=k thenoutput R ;Note that execution of

7、the second for statement causes the list D to “merge ”with the list L . Since the lists L and D are sorted, the time taken for this merge is proportional to the sum of the lengths of the two lists. Thus the algorithm runs in time (atmost proportional to n times the sum total of the number of documen

8、t identierscorresponding to each keyword in S .21.3Suggest how to implement the iterative technique for computing Page-Rank given that the T matrix (evenin adjacency list representation does not tin memory. Answer:No answer21.4Suggest how a document containing a word (suchas “leopard ” canbe indexed

9、 such that it is efcientlyretrieved by queries using a more general concept (suchas “carnivore ”or “mammal ”. You can assume that the concept hierarchy is not very deep, so each concept has only a few generalizations (aconcept can, however, have a large number of specializations. You can also assume

10、 that you are provided with a func-tion that returns the concept for each word in a document. Also suggest how a query using a specialized concept can retrieve documents using a more general concept. Answer:Add doc to index lists for more general concepts also.Practice Exercises 321.5Suppose inverte

11、d lists are maintained in blocks, with each block not-ing the largest popularity rank and TF-IDF scores of documents in the remaining blocks in the list. Suggest how merging of inverted lists can stop early if the user wants only the top K answers. Answer:For all documents whose scores are not complete use u