Lucene

Prelude

• my background..
  
• please interrupt with questions
• blog this talk now so that we can search for it later
  
(using a Lucene-based blog search engine, of course)

• In this course, Paolo and Antonio have presented many techniques.
• I present real software that uses many of these techniques.
  

Lucene is

• software library for search
• open source
  
• not a complete application
• set of java classes
• active user and developer communities
• widely used, e.g, IBM and Microsoft.

Lucene Architecture

Lucene API

• org.apache.lucene.document
• org.apache.lucene.analysis
• org.apache.lucene.index
• org.apache.lucene.search

Package: org.apache.lucene.document

• A Document is a sequence of Fields.
• A Field is a <name, value> pair.
• name is the name of the field, e.g., title, body, subject, date, etc.
• value is text.
• Field values may be stored, indexed or analyzed (and, now, vectored).

Example

 public Document makeDocument(File f) throws FileNotFoundException {
    Document doc = new Document();
    doc.add(new Field("path", f.getPath(), Store.YES, Index.TOKENIZED));

    doc.add(new Field("modified",
        DateTools.timeToString(f.lastModified(), Resolution.MINUTE),
        Store.YES, Index.UN_TOKENIZED));

    // Reader implies Store.NO and Index.TOKENIZED
    doc.add(new Field("contents", new FileReader(f)));

    return doc;
  }

Example (continued)

Package: org.apache.lucene.analysis

• An Analyzer is a TokenStream factory.
• A TokenStream is an iterator over Tokens.
• input is a character iterator (Reader)
• A Token is tuple <text, type, start, length, positionIncrement>
  
• text (e.g., “pisa”).
• type (e.g., “word”, “sent”, “para”).
• start & length offsets, in characters (e.g, <5,4>)
• positionIncrement (normally 1)
• standard TokenStream implementations are
• Tokenizers, which divide characters into tokens and
  
• TokenFilters, e.g., stop lists, stemmers, etc.
  

Example

  private Set stopWords = 
    StopFilter.makeStopSet(new String[] {"il", "la", "in"};

  public TokenStream tokenStream(String fieldName, Reader reader) {
    TokenStream result = new WhitespaceTokenizer(reader);
    result = new LowerCaseFilter(result);
    result = new StopFilter(result, stopWords);
    result = new SnowballFilter(result, "Italian");
    return result;
 }
}

Package: org.apache.lucene.index

• Term is <fieldName, text>
• index maps Term → <df, <docNum, <position>* >*>
• e.g., “content:pisa” → <2, <2, <14>>, <4, <2, 9>>>
• new: term vectors!
  

Example

IndexWriter writer = new IndexWriter("index", new ItalianAnalyzer());
File[] files = directory.listFiles();
for (int i = 0; i < files.length; i++) {
  writer.addDocument(makeDocument(files[i]));
}
writer.close();

Some Inverted Index Strategies

1. batch-based: use file-sorting algorithms (textbook)
+ fastest to build
+ fastest to search
- slow to update
2. b-tree based: update in place (http://lucene.sf.net/papers/sigir90.ps)
+ fast to search
- update/build does not scale
- complex implementation
3. segment based: lots of small indexes (Verity)
+ fast to build
+ fast to update
- slower to search

Lucene's Index Algorithm

• two basic algorithms:
1. make an index for a single document
2. merge a set of indices

• incremental algorithm:
• maintain a stack of segment indices
• create index for each incoming document
• push new indexes onto the stack
• let b=10 be the merge factor; M=∞

for (size = 1; size < M; size *= b) {
  if (there are b indexes with size docs on top of the stack) {
   pop them off the stack;
   merge them into a single index;
   push the merged index onto the stack;
 } else {
   break;
 }
}

• optimization: single-doc indexes kept in RAM, saves system calls
• notes:
• average b*log_b(N)/2 indexes
• N=1M, b=2 gives just 20 indexes
• fast to update and not too slow to search
  
• batch indexing  w/ M=∞, merge all at end
• equivalent to external merge sort, optimal
  
• segment indexing w/ M<∞

Indexing Diagram

• b = 3
• 11 documents indexed
• stack has four indexes
• grayed indexes have been deleted
• 5 merges have occurred

Index Compression

VInt Encoding Example

This provides compression while still being efficient to decode.

Package: org.apache.lucene.search

• primitive queries:
• TermQuery: match docs containing a Term
  
• PhraseQuery: match docs w/ sequence of Terms
• BooleanQuery: match docs matching other queries.
  e.g., +path:pisa +content:“Doug Cutting” -path:nutch
• new: SpansQuery
  
• derived queries:
  
• PrefixQuery, WildcardQuery, etc.

Example

Query pisa = new TermQuery(new Term("content", "pisa"));
Query babel = new TermQuery(new Term("content", "babel"));

PhraseQuery leaningTower = new PhraseQuery();
leaningTower.add(new Term("content", "leaning"));
leaningTower.add(new Term("content", "tower"));

BooleanQuery query = new BooleanQuery();
query.add(leaningTower, Occur.MUST);
query.add(pisa, Occur.SHOULD);
query.add(babel, Occur.MUST_NOT);

Search Algorithms

Lucene's Disjunctive Search Algorithm

• described in http://lucene.sf.net/papers/riao97.ps
• since all postings must be processed
• goal is to minimize per-posting computation
• merges postings through a fixed-size array of accumulator buckets
• performs boolean logic with bit masks
• scales well with large queries
  

Lucene's Conjunctive Search Algorithm

• use linked list of pointers to doc list
  
• initially sorted by doc
• loop
  
• if all are at same doc, record hit
  
• skip first to-or-past last and move to end of list
  

Scoring

Lucene's Phrase Scoring

• approximate phrase IDF with sum of terms
• compute actual tf of phrase
• slop penalizes slight mismatches by edit-distance

Thanks!