You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by Vikas Gupta <vg...@cs.utexas.edu> on 2004/12/09 11:17:09 UTC

Exact search algorithm used in lucene

Hi developers,

    I am a new user/developer of lucene. I read Doug Cutting's paper
"Space Optimizations for Total Ranking". It has a number of algorithms for
searching in an index.

    I was curious which one(s) does lucene implement.

    Does it have something like "parallel merge" (Figure 4 in the paper)?
I think it wouldn't use simple inverted index search(Fig 2 in the paper)
because it is costlier (it takes O(N) space where N is number of documents
in the collection)?

    I have been able to drive lucene by nutch (thru eclipse java
debugger). I am trying to find out the search algorithm used for phrase
queries and regular queries. Which file has the code to read in the next
posting? If I could find the function which actually reads the indices
during search, then I could a breakpoint there and understand that code. I
have been able to follow a search upto this point

----    IndexSearch.java file---------
  public TopDocs search(Query query, Filter filter, final int nDocs)
       throws IOException {
    Scorer scorer = query.weight(this).scorer(reader);
    ...
    return new TopDocs(totalHits[0], scoreDocs);
  }


I realized that the first line actually does the core search - i.e.
getting the list of relevant documents.

Scorer scorer = query.weight(this).scorer(reader);

Is that correct? Things get a little hazy after I step into this function.
Can you point me to what's happening with buckets, scorers, weights? Can
someone write a small paragraph about the basic strategy being used here?

Since, I am not fully sure about the big picture, i.e. the exact algorithm
being used - it is difficult to follow the code.


Also, I was curious if there is some sort of Getting started guide for
developers? The Gettting started docs and FAQs for lucene users is very
extensive.

Thanks for reading this and your time.

 ____________________________________________________________________
 Vikas Gupta                   Email: vgupta@cs.utexas.edu
 Masters Student (Graduating in 2 weeks)
 Dept. of Computer Sciences,   http://www.cs.utexas.edu/users/vgupta
 Univ. of Texas at Austin, USA
 ____________________________________________________________________

---------------------------------------------------------------------
To unsubscribe, e-mail: lucene-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: lucene-dev-help@jakarta.apache.org


Re: Hit 2 has score less than Hit 3

Posted by Erik Hatcher <er...@ehatchersolutions.com>.
On Dec 14, 2004, at 4:53 AM, Vikas Gupta wrote:
> I have come across a scenario where the hits returned are not sorted.  
> Or
> maybe they are sorted but the explanation is not correct.
>
> Take a look at
> http://cofferdam.cs.utexas.edu:8080/search.jsp? 
> query=space+odyssey&hitsPerPage=10&hitsPerSite=0

This site was down when I tried to access it.

> Look at the top 3 results.
>
> Score of Hit 1 is 1.0188559
> Score of Hit 2 is 0.9934416
> Score of Hit 3 is 1.0188559
>
> I can't explain how score of hit 2 can be < hit 3. I thought the hits  
> that
> were returned were sorted.

Hits should be in descending score order by default.  Are you using the  
new Sort facility at all?  Are you walking through Hits properly (i.e.  
hits.doc(i), i is the i-th hit, not document id i)?   What version of  
Lucene are you using?

Sorry - figured I'd rattle off some standard troubleshooting questions  
:)

> FYI, the docs corresponding to hits 1,2 and 3 have exactly the same
> scoring fields(By scoring fields, I mean the fields used in the query).

Use the IndexSearcher.explain() feature to get the real scoop on why a  
score is computed the way it is.

	Erik


---------------------------------------------------------------------
To unsubscribe, e-mail: lucene-user-unsubscribe@jakarta.apache.org
For additional commands, e-mail: lucene-user-help@jakarta.apache.org


Hit 2 has score less than Hit 3

Posted by Vikas Gupta <vg...@cs.utexas.edu>.
I have come across a scenario where the hits returned are not sorted. Or
maybe they are sorted but the explanation is not correct.

Take a look at
http://cofferdam.cs.utexas.edu:8080/search.jsp?query=space+odyssey&hitsPerPage=10&hitsPerSite=0

Look at the top 3 results.

Score of Hit 1 is 1.0188559
Score of Hit 2 is 0.9934416
Score of Hit 3 is 1.0188559

I can't explain how score of hit 2 can be < hit 3. I thought the hits that
were returned were sorted.

An explanation is that the explanation of hit 2 is not correctly computed.
Has anyone encountered this before?

FYI, the docs corresponding to hits 1,2 and 3 have exactly the same
scoring fields(By scoring fields, I mean the fields used in the query).

Thanks for your time.

-Vikas

---------------------------------------------------------------------
To unsubscribe, e-mail: lucene-user-unsubscribe@jakarta.apache.org
For additional commands, e-mail: lucene-user-help@jakarta.apache.org