Beefy Boxes and Bandwidth Generously Provided by pair Networks Frank
Perl Monk, Perl Meditation
 
PerlMonks  

OT: Vector based search engine

by Ryszard (Priest)
on May 14, 2004 at 08:15 UTC ( #353299=perlmeditation: print w/ replies, xml ) Need Help??

I've recently decided it would be a cool thing to add a search engine to my website.

Sure you can get ready made options, but i'm interested in the guts and the theory on how it all works. I had a look at just a couple of techniques, and discounted an Inverted Index seach because, well, its just too simple.

I wanted something that i could learn something new from, and came across the Vector space search algorithm.

My question is, does anyone have any links that could go further to explain in a little more detail the theory and maths behind this? The article is all spelled out well, but i'm after a little more meat.

Comment on OT: Vector based search engine
Re: OT: Vector based search engine
by Enlil (Parson) on May 14, 2004 at 08:30 UTC
    Have you tried the ready made options? I noticed a lot of good articles near the top of all those searches (granted many point back to the perl.com article).

    update:citeseer tends to have articles about this type of thing that also tend to have more meat.

    -enlil

Re: OT: Vector based search engine
by kvale (Monsignor) on May 14, 2004 at 08:31 UTC
    The general field that includes techniques such as vector space algorithms is termed 'Information Retrieval'. A good book on this is "Information Retrieval: Data Structures and Algorithms" by William Frakes and Ricardo Baeza-Yates.

    If you are interested in this stuff, a fun package for playing around with IR is the SMART system developed at Cornell.

    -Mark

Re: OT: Vector based search engine
by DrHyde (Prior) on May 14, 2004 at 09:13 UTC
    I implemented this at work. Sadly, I can't (yet) share the code, but I can certainly explain how it works.

    As the article explains, you grovel over your corpus and extract a list of all the unique words from that corpus (after stemming and removing stopwords, of course). Each of those words will be represented by a dimension in an N-dimensional space. So, for example, if your list of words is "beer", "pie", "ninja" (the three best things ever), then you will be working with a three dimensional space whose axes are labelled "beer", "pie" and "ninja" instead of x, y and z.

    Once you have the list of words, you construct a vector in your N-dimensional space for each document. You simply go through each document, stemming all the words and removing stopwords again, and each time a word appears, you add one to the relevant dimension.

    The document "ninjas like pie" would therefore become:

    [0, 1, 1]

    and the document "I'll have beer, beer, more beer and a pie please" would be:

    [3, 1, 0]

    Those look exactly like co-ordinates in the N-dimensional space, which they are. However, because of what we do with them later, it is better to think of them as vectors - that is, they are directions from the [0, 0, 0] point, the "origin". [0, 1, 1] represents the direction "due east and up at an angle of 45 degrees", for example.

    So now we have reduced each document to a vector, which we can store in a nice compact index. To search the index, we take the user's search terms and reduce them to a vector just like we did with the documents. Any words which don't appear in the index - ie for which we don't have a dimension - are ignored.

    Now we need to see how close this vector is to all of the vectors in the index. Seeing that all the vectors are lines which cross at the origin, we can define their closeness as the angle between them. The smaller the angle, the closer the vectors. You need to do this for *all* document vectors.

    You will note that there is an angle between all possible vectors, so you need to choose a cut-off angle so that you only return results which are reasonably close. What that angle is will depend on your data and your usage patterns.

    The advantages of a vector search are:

    • You get document ranking for free - smaller angle == better match;
    • Users get sane results without having to learn about ANDs and ORs which is often beyond their poor little branes;

    The disadvantages are:

    • Needs lots of tuning - what weight to give to different parts of the document, how to weight words which appear many times, what angle to start throwing results away;
    • Can't search for phrases;
    • Have to compare the search to all documents and perform a calculation, so won't scale to huge data sets
      Hey, this is good stuff, thanks. When possible, i'd love to see your code.. ;-)

      Here is also a good link that explains some of the theory in Laymans terms.

Re: OT: Vector based search engine
by Fletch (Chancellor) on May 15, 2004 at 04:24 UTC

    Carp, I was trying to remember the url for the LSI paper you linked to; but then again you're apparently familiar with it :). You might also check out Search::ContextGraph by the same author for another interesting technique.

Re: OT: Vector based search engine
by tachyon (Chancellor) on May 15, 2004 at 05:42 UTC

    If you just want a good efficient seach engine I would recommend Swish-e We use it. So does apache.org and many other open source websites. The index code is in C of course but there is a Perl XS Swish::API module that ships with it. There is also a Perl front end. It is stable free and fast. Under mod perl (which gives you a persistent search object) searching a reasonable sized website it is blindingly fast ie sub millisecond. The result highlighting code takes about 4 times longer to run than the search.

    cheers

    tachyon

Re: OT: Vector based search engine
by sri (Vicar) on May 15, 2004 at 07:41 UTC
      One warning about Plucene: it's slow. I'm working on mailbox indexer (to be released real soon now) which can use swish-e or Plucene as index, and as far as real-life examples go, Plucene is just too slow.

      If your document collection isn't tiny (e.g. couple of hundred documents) you might want to use swish-e. On the other hand, Plucene query syntax and ability to add documents to index on the fly are good reasons to use it anyway.

      2share!2flame...
Re: OT: Vector based search engine
by Ryszard (Priest) on May 18, 2004 at 06:31 UTC
    After looking at various algorithms and what not, I've settled on a (sigh) ready made solution, swish-e.

    Its pretty cool, and while written in c, has a perl API which is quite nice. Its extremely fast for filesystem index scans and terribly slow for web spidering (not surprising really), (props tachyon).

    My site is a dynamic photo album site, not static html pages. As the content I want to index is stored on the FS, the scan takes less than a second (as opposed to 33hrs spidering) with swish-e.

    I've learned (not heaps) but a little more about search engine's, and know a bit more about the different algorithms and the advantages/disadvantages of them.

    Again, unfort, the Vector Space alorithm referenced above did not meet my needs, with completely irrelevant results, YMMV. I've not delved into the nitty gritty of how/why, but its on my list of things to do.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://353299]
Approved by rob_au
Front-paged by broquaint
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (11)
As of 2014-04-18 00:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (460 votes), past polls