An Introduction to Information Retrieval

/ Christopher D. Manning, Prabhakar Raghavan, and Hinrich schutze. - cambridge, England. Cambridge Univ. Press., (c) 2009 - Online edition.

1. Boolean retrieval

1. Boolean retrieval

Information retrieval이란 용어의 의미는 매우 광범위적일 수 있다. 카드번호를 입력하기 위하여 여러분의 지갑으로부터 신용카드를 커내는 것 또한 정보검색의 한 형태이다. 그렇지만 정보검색의 학술적 정의는 다음과 같다:

“IR is finding material (usually documents) of an unstructured nature(usually text) that satisfies an information need from within large collections(usually stored on computers."

이런 식으로 정의함으로써  정보검색은 단지 소수의 사람(reference librarians, paralegals, similar professional searchers)만의 activity로 여겨져 왔다. 이제 세상은 변하였고, 수 억 명의 사람이 매일매일 웹 탐색엔진을 이용하거나 전자우편을 탐색함으로써 정보검색에 참여하고 있다(modern parlance(어투)로, “search"란 단어는 ”(information) retrieval"을 replace하는 경향이 있다; “search"란 단어는 quite ambiguous하지만 이 책에서는 두 가지를 synonymously하게 사용한다). 정보검색은 (”미안합니다. 당신의 OrderID를 저에게 줄 때만 당신의 주문을 look up할 수 있습니다.“라고 어떤 clerk가 여러분에게 말할 때 진행되는 the sort)와 같은 전통적인 데이터베이스 스타일의 탐색하기를 overtake(추월)하여 신속하게 dominant form of information access가 되고 있다.

IR은 위에서 정의한 것을 벗어나 다른 종류의 데이터와 정보문제 또한 cover할 수 있다.  “unstructured data”란 용어는 어의적으로 분명한 easy-for-a-computer structure를 가지고 있지 않은 데이터를 말한다. 이것은 관계형 데이터베이스의 canonical example인 structured data의 반대이며, structured data는 product inventories와 personnel records를 유지관리하기 위하여 sort companies에서 일반적으로 사용하는 데이터이다. 현실에서 대부분의 데이터는 사실상 “unstructured" 하지 않다. 만일 여러분이 인간 언어의 latent(잠재적) linguistic structure를 고려해 보면, 이것은 모든 텍스트 데이터에서 분명한 사실이다. 대부분의 텍스트는 일반적으로 그리고 의도적으로 explicit markup(웹페이지의 기저가 되는 코딩처럼)에 의해 문서 속에 표현되는 headings, paragraphs, footnotes와 같은 구조를 가지고 있다. IR은 또한 title에 Java를 포함하고 body에 threading을 포함하고 있는 도큐멘트를 찾는 것과 같은  ”semi-structured" 탐색을 하는데도 용이하게 사용된다.

정보검색 분야 또한 다큐멘트군(document collections)을 browsing하거나 filtering하거나 또는 더 나아가서 a set of retrieved documents를 processing하려는 이용자를 지원한다. 한 세트의 다큐멘트가 주어졌을 때, clustering이란 콘텐츠에 근거하여 다큐멘트를 훌륭하게  grouping하는 task 이다. 이것은 서가에서 주제별로 책을 배열하는 것과 비슷하다. 한 무리의 주제, 지속적인(standing) 정보요구, 또는 기타 카테고리(나이가 서로 다른 그룹을 위한 텍스트의 suitability와 같은) 가 주어졌을 때, 분류는 만일 있다면 각각의 a set of documents가 어떠한 class(es)에 속하는가를 결정하는 task 이다.

정보검색시스템은 그것이 담당하는 scale에 따라 구별될 수 있다. web search에서, 그 시스템은 수 백만개의 컴퓨터에 저장된 수십억개의 다큐를 탐색할 수 있어야 한다. 이렇게 하려고 할 때, 필요한 이슈들을 살펴보면, 색인화를 위해 도큐를 수집하는 것, 이러한 엄청난 규모에서 효율적으로 작동할 수 있는 시스템을 구축하는 것, 그 웹이 가지고 있는 하이퍼텍스트의 탐색과 같은 특별한 aspects를 처리할 수 있는 것, 그리고 웹의 상업적 중요성을 높이기 위해 탐색엔진 서열을 높이려는 시도로 웹페이지를 조작하려는 사이트 제공자에 의해 농락당하지 않아야 한다는 것 등이다.

또 다른 극단적인 것은 personal information retrieval 이다. 지난 몇 년간 소비자운영시스템은 정보검색을 통합하였다(예, Apple의 Mac OS X Spotlight or Windows Vista's Instant Search). 현재 메일 프로그램은 보통 탐색뿐만 아니라 텍스트 분류도 제공하고 있다: 적어도 이것들은 spam(junk mail) filter를 제공하며, 공통적으로 특별한 폴더에 직접 보관할 수 있도록 메일을 수동이나 자동으로 분류하는 수단을 제공하고 있다. 여기 distinctive issues에는 전형적인 개인 컴퓨터에서 다양한 범위의 도큐 타입을 handling하는 것, 그리고 소유자를 화내지 않게 컴퓨터를 기동할 수 있는 startup, processing, disk space usage와 관련해서 그 탐색시스템의 유지관리를 자유롭고도 충분하게 가볍게 만드는 것을 포함한다. 이 양자사이에(in between) 검색이 기업의 내부 문서, 특허 데이터베이스, 또는 생화학 연구학술기사와 같은 컬렉션용으로 제공될 수도 있는 enterprise, institutional, and domain-specific search의 space가 있다. 이런 경우에, 그 도큐들은 전형적으로 집중식 파일 시스템에 저장될 것이고 한 개 또는 한 줌의 전용 기계가 그 컬렉션을 탐색하도록 제공될 것이다. 이 책에서는 이러한 모든 스펙트럼에 대한 technique of value를 제공하지만, web-scale search systems에 있어 parallel and distributed search에 대한 몇가지 aspects를 우리가 다루는 것은 그러한 시스템의 details를 다룬 문헌이 비교적 적기 때문에 비교적 가볍게 다루었다. 그렇지만, 소수의 웹 탐색 회사에서 벗어나 있는 어떤 소프트웨어 개발자는 개인적 탐색과 기업 시나리오를 가장 많이 encounter하기 쉬울 것이다.

이제 정보검색문제의 간단한 예로 시작하여 a term-document matrix의 아이디어와 the central inverted index data structure를 소개한 다음에, 불리안 검색 모델과 어떻게 불리안 쿼리가 처리되는지를 알아보기로 한다.

1.1 정보검색문제의 간단한 예제

많은 사람이 갖고 있는 두툼한 책이 바로 Shakespeare's Collected Works이다. 여러분이 섹스피어의 어떤 희곡 속에 Brutus AND Caesar AND NOT Calpurnia가 포함되어 있는지를 알아보려 한다고 가정해 보자.

이것을 아는 한 가지 방법은 처음부터 모든 텍스트를 읽고 각 희곡에 Brutus와 Caesar는 포함되어 있지만 Calpurnia가 포함되어 있는 것은 제외시켜는 것이다. 다큐 검색의 가장 간단한 form은 컴퓨터를 가지고 다큐 전체를 이런 식으로 선형적으로 스캔하는 것이다. 이러한 과정을 일반적으로 Grepping through text라고 부르며, Unix 명령어 grep(특정한 문자열을 찾는 명령어)는 이러한 과정을 수행한다. 이것은 특히 오늘날의 컴퓨터 속도를 고려한다면 매우 효과적인 과정일 수 있으며, regular expression의 사용을 통해 wildcard pattern matching용으로도 유용하게 사용할 수 있다. 현대적인 컴퓨터만 있다면, 적당한 다큐 군의 간단한 쿼리용으로 이 방식 이외엔 실재로 아무 것도 필요치 않다(Shakespeare's Collected Works의 크기는 전체적으로 텍스트가 100만 단어보다 조금 모자란다).

그렇지만, 여러분은 다음과 같은 여러 가지 목적으로 더 많은 기법을 필요로 할 것다:

가. To process large document collection quickly.

온라인 데이터의 양이 컴퓨터의 속도만큼 빠르게 증가하고 있으며, 우리는 지금 수십억 또는 수조의 단어들이 모두 질서정연하게 들어있는 collections를 탐색하고 싶어 한다.

나. To allow more flexible matching operations.

예를 들어 grep를 가지고 Romans NEAR countrymen 쿼리를 사용하는 것은 비실용적이다. 왜냐하면 NEAR는 “within 5 words" 또는 ”within the same sentence"로 정의되기 때문이다.

다. To allow ranked retrieval:

다수의 경우에, 여러분은 찾고자 하는 단어가 포함된 많은 다큐를 대상으로 자신의 정보요구에 대한 최상의 결과를 원한다.

각 쿼리에 맞춰서 텍스트를 선형적으로 스캐닝하는 것을 피하는 방법은 미리 그 문서를 색인(index)하는 것이다.

이 글에서는 Shakespeare's Collected Works를 대상으로 Boolean retrieval model의 basics를 소개하기로 한다. 우리는 섹스피어가 사용한 모든 단어들 속에서 그의 특정한 희곡 속에 들어 있는 각각의 단어를 사용하고 있는 다큐를 레코드한다고 가정해 보자(섹스피어는 32,000개의 서로 다른 단어를 사용했다). 그 결과를 나타낸 것이 아래의 도 1.1의 a binary term-document incidence(발생, 빈도) matrix 이다. 여기서 terms은 indexed 요소(units)이다; 색인요소는 대부분이 words이다.

이제 우리가 매트릭스의 로우 또는 칼럼을 살펴보면, 그곳에 표현된 다큐의 각각의 term용인 vector를 파악할 수 있으며, 그것의 terms가 포함되어 있는 각각의 다큐용 vector를 알 수 있다.

쿼리: Brutus AND Caesar AND NOT Calpurnia에 대답하기 위하여, 우리는 Brutus, Caesar and Calpurnia의 vector를 가지고 a bitwise AND를 실행하면 다음과 같다:

110100  AND 110111 AND 101111 = 100100

따라서 이 쿼리에 대한 결과는 Antony and Cleopatra와 Hamlet 이다(도 1.2).

Boolean retrieval model은 정보검색을 위한 모델이며, 우리는 a Boolean expression of terms의 형태로 어떠한 쿼리도 작성(pose)할 수 있고 terms는 연산자 AND, OR, NOT을 사용하여 결합시킨다. 이 모델은 각각의 다큐를 단지 a set of words로만 인식한다(view).

Figure 1-2: Results from Shakespeare for the query Brutus AND Caesar AND NOT Calpurnia.

관련 terminology와 notation을 소개하기 위하여 보다 현실적인 시나리오를 생각해 보자. 우리가 N=1million개의 다큐를 갖고 있다고 가정해 보자. 다큐 별로, 우리는 그것의 단위( units)가 무엇이든지 그것의 검색시스템을 수립해야 한다. 예를 들어, 이것들은 individual memos이거나 chapters of a book일 수도 있다. 우리가 검색을 수행할 다큐의 집단을 collection이라 부르며, 때때로 이것은 corpus(a body of texts)라고도 한다. 각 다큐는 약 1,000개의 단어 길이(2-3 페이지)로 되어 있다고 가정하자. 만일 spaces와 punctuation을 포함하여 단어별로 평균 길이가 6bytes라고 가정한다면, 이 collection은 규모에 있어서 약 6GB의 다큐 군이다. 전형적으로 이러한 다큐에는 약 M=500,000 distinct terms가 내재되어 있다. 그렇지만 이러한 숫자는 특별한 것이 아무것도 없으며, 단지 규모에 따라 크기의 순서가 변할 수 있다. collection의 규모에 따라 우리가 다뤄야할 the dimension of the kinds of problems가 다르다.

우리의 목적은 ad hoc retrieval task에 address하는 시스템을 개발하는 것이다. 이것이 가장 표준적인 IR의 task 이다. 어떤 시스템은 collection으로부터 arbitrary user information need에 - a one-off(일회성의), user-initiated query를 가지고 시스템과 교신함으로써 - 적합한 다큐를 제공하는 것에 초점을 맞추고 있다. information need란 이용자가 더 많이 알기를 원하는 주제(topic)이며, query와는 다르다. 쿼리란 이용자가 정보요구를 교신하기 위하여 컴퓨터에 전달하는 어떤 무엇이다. 만일 이용자가 자신의 개인적 정보요구와 관련해서 가치있는 정보를 포함하고 있는 것으로 인식한다면, 그 다큐는 적합한 것이다. IR 시스템의 effectiveness 평가(i.e. the quality of its search results)를 하기 위하여, 이용자는 쿼리와 시스템의 returned results에 관한 두 가지 중요한 통계에 대하여 잘 알아야 한다:

1) Precision: What fraction of the returned results are relevant to the

information need?

2) Recall: What fraction of the relevant documents in the collection were

returned by the system?

우리는 지금 순진하게(in a naive way) a term-document matrix를 구축하진 않을 것이다. 500K x 1M matrix는 half-a-trillion의 0과 1을 갖는다 - 너무 많아서 우리 컴퓨터의 메모리에 적합하지 않다. 그러나 중요한 것은 이러한 메트릭스는 매우 sparse(이빨이 빠진, 듬성듬성하다)하다는 것이다 - 즉, non-zero entries가 드물다는 것이다. 각 다큐마다   1,000개씩의 단어를 가지고 있기 때문에, 그 매트릭스는 단지 one billion 1's를 가지고 있으며, 따라서 그 셀들의 최소한 99.8%는 zero로 되어있다. 한 가지 정말 좋은 것은 1 positions가 발생하는 things 만을 record로 표현할 수 있다는 것이다.

이러한 아이디어가 바로 정보검색의 첫 번째 주요한 개념인 inverted index의 핵심이다. 이것의 이름은 실재로 여러 가지(redundant)가 있다: 색인은 항상 그것의 terms로부터 그것들이 발생/존재하고 있는 다큐의 여러 부분들까지도 나타내야 한다(maps back). 오늘날 inverted index 또는 때때로 inverted file은 정보검색에서 표준어가 되었다(어떤 정보검색연구자들은 inverted file을 더 선호하지만 index construction 그리고 index compression과 같은 표현이 inverted file construction 그리고 inverted file compression보다 훨씬 더 일반적이다). inverted index의 기본적인 아이디어가 도 1.3에 나타나 있다. 우리는 a dictionary of terms을 가지고 있다(때때로 또한 vocabulary 또는 lexicon이라고도 부를 것이다; 이 책에서 data structure용으로 dictionary로, 그리고 the set of terms용으로 vocabulary로 사용한다). 각 용어와 관련해서, 우리는 그 용어가 발생하고 있는 다큐가 어떤 것인지를 기록하고 있는 리스트를 갖고 있다. 그 리스트- 하나의 다큐에 나타난 하나의 용어를 기록하고 있으며, 나중에 종종, 그 다큐의 위치를 나타냄 - 에 있는 각 아이템을 전통적으로 posting이라 부른다(a non-positional inverted index에서 posting은 단지 document ID이지만, 이것은 자신이 위치하고 있는 postings list를 통해 하나의 term으로 인식되고 있다: 때때로 우리는 하나의 posting으로 (term, docID) pair를 취급하기도 한다). 이러한 리스트를 postings list(또는 inverted list)라 부르며, 그 postings list에서 함께 묶인(taken together) 모든 것을 postings라고 부른다. 도 1.3에 있는 dictionary는 자모순으로 분류(sorted)되어 있으며, 각 postings list는 document ID로 분류(sorted)되어 있다.

1.2 A first take at building an inverted index

검색 시에 색인화의 신속한 이익을 얻기 위하여, 우리는 미리 색인을 만들어야 한다. 이것의  중요한 개념은 다음과 같다:

1. Collect the documents to be indexed:
...

2. Tokenize the text, turning each document into a list of tokens:

...

3. Do linguistic preprocessing, producing a list of normalized tokens, which are the

indexing terms:     ...

4. Index the documents that each term occurs in by creating an inverted index,

consisting of a dictionary and postings.

tokens와 normalized tokens는 크게 보면 words라고 생각할 수 있다. 그럼, a basic inverted index by sort-based indexing의 작성에 대하여 알아보자.

a document collection에 있는 각 다큐는 document identifier(docID)라 부르는 a unique serial number를 가지고 있다고 가정하자. index를 구축하는 동안, 우리는 각각의 새로운 다큐를 처음 만날 때, 그것에 successive integers를 매길 수 있다. indexing용  input은 각 다큐에 관한 normalized tokens의 a list - 도 1.4처럼 term과 docID의 pairs로 되어 있는 리스트 - 이다.

the core indexing step은 이런 용어들이 자모순으로 나타나도록 그 리스트를 sorting 하는 것이다. 동일한 다큐에서 동일한 용어가 multiple occurrences하는 것은 합체(merge) 하여야 한다. 그런 다음, 동일한 용어의 instances를 그룹화한 다음, 결과적으로 도 1.4의 오른쪽 칼럼에서처럼 a dictionary 와 postings로 분리한다. 어떤 용어는 일반적으로 수많은 다큐에 나타나므로, 이러한 data organization을 통해 storage requirement of the index를 줄일 수 있다.

dictionary 또한 각 용어를 포함하고 있는 다큐의 빈도(document frequency)와 같은 어떤 통계들을 기록하고 있다. 이러한 통계정보는 기본적인 불리안 탐색엔진에선 중요하지는 않지만, query time에 탐색엔진의 efficiency를 증진시키는데 도움을 주며, 나중에 많은 ranked 검색 모델에서 사용되었다.

postings는 docID에 의해 두 번째로 sorted된다. 이것은 효율적인 쿼리과정을 위한 근거(basis)를 제공한다. 이러한 inverted index structure는 ad hoc text search를 지원하기 위한 가장 효율적인 구조로서 어떠한 경쟁상대도 아직 존재하지 않는다.

the resulting index에서, 우리는 dictionary와 postings 둘 다에 storage를 제공하여야 한다. 후자가 훨씬 더 크지만, dictionary는 일반적으로 memory 속에 보관된다. 반면에 postings는 disk에 보관된다. 그러므로 각각의 사이즈가 중요하며, 제 5장에서 각각의 storage and access efficiency를 최적화하는 방법을 조사할 것이다. 어떤 데이터 구조가 pl용으로 사용되어야 하는가? a fixed length array는 어떤 단어가 많은 다큐에 나타나고 나머지는 극소수 다큐에 날 때 wasteful 할 수 있다. an in-memory pl을 위해, 두 가지 훌륭한 대안은 singly linked lists 이거나 variable length arrays 이다. singly linked lists는 pl에 다큐의 cheap insertion(갱신된 다큐를 위해 그 웹을 recrawling 할 때 처럼 갱신으로 이어지는)을 가능하게 하며, 자연스럽게 추가적인 points가 필요한 skip lists와 같은 보다 고급스러운 색인전략으로 확대가능하다. 가변장 array는 pointers의 overhead를 피함으로써 space requirements를 충족시키고 있으며, contiguous(끊이지 않는) memory를 pointers가 사용함으로써 memory caches를 가진 현대의 processors의 속도를 높이기 때문에 time requirements 도 충족시키고 있다. extra pointers는 실재로 offsets 처럼 리스트에 encoded될 수 있다. 만일 갱신이 비교적 뜸하게 이루어진다면, 가변장 array는 traverse 하기 위하여 더 compact하고 더 빨라질 것이다. 우리는 또한 각 용어를 위한 고정장 array의 a linked list을 갖고 있는 hybrid scheme을 사용할 것이다. pl이 디스크에 저장될 때, 그것들은 메모리에서 pl을 읽기 위해 필요한 pl의 사이즈와 disk의 수를 최소화하기 위하여 explicit pointers 없이 a contiguous run of postings로서 저장(아마도 compressed하게)될 것이다.

Exercises.

Draw the inverted index that would be built for the following document collection. (See Figure 1.3 for an example.)

Doc 1    new home sales top forecasts
Doc 2    home sales rise in july
Doc 3    increase in home sales in july
Doc 4    july new home sales rise

Consider these documents:

Doc 1    breakthrough drug for schizophrenia
Doc 2    new schizophrenia drug
Doc 3    new approach for treatment of schizophrenia
Doc 4    new hopes for schizophrenia patients

Draw the term-document incidence matrix for this document collection.

Draw the inverted index representation for this collection, as in Figure 1.3 (page ).

For the document collection shown in Exercise 1.2 , what are the returned results for these queries:

schizophrenia AND drug

for AND NOT(drug OR approach)

Exercise 1.1

다음의 콜렉션에 적합한 도치색인을 작성하라.

Doc 1 new home sales top forecasts

Doc 2 home sales rise in july

Doc 3 increase in home sales in july

Doc 4 July new home sales rise

Exercise 1.2

다음 문서를 생각해 보라(consider)

Doc 1 breakthrough drug for schizophrenia

Doc 2 new schizophrenia drug

Doc 3 new approach for tratment of schizophrenia

Doc 4 new hopes for schizophrenia patioents

a. the term-document incidence matrix를 작성하라

b. the inverted index를 작성하라.

Exercise 1.3

예제 1.2의 콜렉션을 가지고 다음과 같은 쿼리의 returned results가 무엇인지를 밝혀라.

a. schizophrenia AND drug

b. for AND not(drug OR approach)

1.3 Processing Boolean queries

inverted index와 기본적인 불리안 검색 모델을 사용하여 쿼리에 대해 알아보자. the simple conjunctive query의 processing을 생각해 보자:

Brutus AND Calpurnia //Calpurnia

도 1.3에서 부분적으로 보여준 도치색인을 참고하여,  우리는:

1. Locate Brutus in the Dictionary

2. Retrieve its postings

3. Locate Calpurnia in the Dictionary

4. Retrieve its postings

5. intersect the two postings, as shown in Figure 1.5.

intersection operation은 중요한 것이다: 우리는 두 가지 용어 모두를 포함하고 있는 다큐를 신속하게 발견할 수 있도록 효율적으로 postings lists를 intersect 하여야 한다(이러한 오퍼레이션은 때때로 postings lists를 통합(merging)한다고 말한다)

Figure:

Intersecting the postings lists for Brutus and Calpurnia from Figure 1.3 .

Figure 1.6: Algorithm for the intersection of two postings lists  and .

merge algorithm을 사용하여 postins lists를 intersecting하는 간단하고도 효과적인 방법이 존재한다(도 1.6을 보라). 우리는 pointers를 양 쪽 리스트 속에 유지하고 있으며, postings entries의 전체 수에서 time linear한 방식으로 동시에 두 개의 posting lists를 처리(walk through) 한다. 각 단계마다, 우리는 both pointers에 의해 pointed된 docID를 비교한다. 만일 그것들이 같다면, 우리는 그 docID를 결과 리스트에 입력하고, both pointers를 advance 한다. 그렇지 않다면, 우리는 보다 작은 docID를 pointing하는 pointer를 advance 한다. 만일 postings listsl의 길이가 x와 y 라면, 그 intersection은 O(x+y) 오퍼레이션이 이루어진다. 공식적으로, querying의 복잡성은 Θ(N)이고, N은 콜렉션에 들어있는 다큐의 수이다( notation Θ(.)은 알고리즘의 복잡성에 대한 an asymptotically tight bound 를 표현하는데 사용된다. 그러나 이 notation은 tight되지 않아야 하는 사실상의 an asymptotic upper bound를 표현한다). 우리가 색인하는 방법은 우리에게 단지 a constant 를 제공한다. Θ time complexity에서 나타나는 difference를 a linear scan에 비교하는 것이 아니지만, 실재로 the constant는 huge 하다. 이러한 알고리즘을 사용하기 위하여 중요한 것은 postings를 a single global ordering으로 sorted 하는 것이다. docID로 sort한 a numeric을 사용하는 것은 이것을 달성하는 한가지 간단한 방법이다.

우리는 intersection operation을 사용하면, 다음과 같은 보다 복잡한 쿼리를 처리할 수 있다:

(Brutus OR Caesar) AND NOT Calpurnia

Query optimization이란 시스템에 의해 작업의 the least total amount of work가 이루어질 수 있도록 쿼리에 대답하는 작업을 조직화하는 최선의 방법을 선택하는 과정이다. Boolean queries용으로 사용되는 이것의 한 가지 중요한 요소는 postings listsl에 접근하는 순서(order) 이다. 쿼리처리를 하는데 있어서 최상의 order는 무엇인가? 예를 들어, t-변수 terms와 하나의 AND가 포함된 쿼리에 대해 생각해 보자:

Brutus AND Caesar AND Calpurnia

t-변수 terms 각각에 대하여, 우리는 그것의 postings lists를 얻은 다음에 그것들을 AND로 결합(together) 시킨다. the standard heuristic 은 document frequency를 늘려서 해당 용어들을 처리하는 것이다: 만일 우리가 두 개의 가장 작은 postings lists를 intersecting하면서 시작한다면, 모든 intermediate results는 그 가장 작은 postings lists보다 결코 더 크지 않을 것이다. 그러므로 the least amount of total work를 하게 될 것이다. 따라서 우리는 도 1.3에 있는 postings lists와 관련해서 위의 쿼리를 다음과 같이 수행한다:

(Calpurnia and Brutus) AND Caesar

이것이 dictionary에 용어들의 빈도를 유지하기 위한 a first justification이다: 이것은 우리에게 어떤 postings lists에 접근하기 전에 in-memory data를 근거로 이러한 ordering decision이 이루어지도록 허용한다.

이제 다음 예제에 대하여, 보다 일반적인 최적화(optimization)에 대하여 생각해 보자:

(madding OR crowd) AND (ignoble OR strife) AND (killed OR slain)

Exercises.

For the queries below, can we still run through the intersection in time

,

where  and  are the lengths of the postings lists for Brutus and Caesar? If not, what can we achieve?

Brutus and not Caesar

Brutus or not Caesar

Extend the postings merge algorithm to arbitrary Boolean query formulas. What is its time complexity? For instance, consider:

(Brutus OR Caesar) AND NOT (Antony OR Cleopatra)

Can we always merge in linear time? Linear in what? Can we do better than this?

We can use distributive laws for and and or to rewrite queries.

Show how to rewrite the query in Exercise 1.3 into disjunctive normal form using the distributive laws.

Would the resulting query be more or less efficiently evaluated than the original form of this query?

Is this result true in general or does it depend on the words and the contents of the document collection?

Recommend a query processing order for

(tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes)

given the following postings list sizes:

Term	Postings size
eyes	213312
kaleidoscope	87009
marmalade	107913
skies	271658
tangerine	46653
trees	316812

If the query is:

friends AND romans AND (NOT countrymen)

how could we use the frequency of countrymen in evaluating the best query evaluation order? In particular, propose a way of handling negation in determining the order of query processing.

For a conjunctive query, is processing postings lists in order of size guaranteed to be optimal? Explain why it is, or give an example where it isn't.

Write out a postings merge algorithm, in the style of Figure 1.6 (page ), for an  OR  query.

How should the Boolean query  AND NOT  be handled? Why is naive evaluation of this query normally very expensive? Write out a postings merge algorithm that evaluates this query efficiently.