Searching off the RAM

Search engines are a lot about precision, recall and speed. These three factors pretty much define the quality of a search engine. I'd only talk about the last point here, speed. The time taken to search for a search engine is such a critical factor that an improvement of a few hundred milliseconds is of extreme importance to anyone associated with developing/designing search engines.
More often than not, as a short term gain, all of us look at putting in more money on the hardware to improve a system's performance. Though this might look like a solution, its bound to fail if you try to run away from actually fixing the application architecture, which happens to be the root cause for poorly performing applications generally.
For those who have already done whatever it takes to optimize the search process, here are a few ways that are generally used to host the search index on the RAM, in order to improve the search speed.
You may mount a tmpfs/ramfs on your machine and copy the index on it. You may then open index reader/searcher on this copy of the index. This would help in reducing the I/O latency and improve the search speed.
The difference between using tmpfs vs ramfs are:

• ramfs will grow dynamically unlike tmpfs which is static and initialized with a fixed size.
• tmpfs uses swap memory whereas ramfs doesn't.

I have personally used tmpfs and it works rather efficiently.
One thing to remember is that both tmpfs and ramfs are volatile. They both get erased on a system restart and hence you'd need to re-mount and copy the index on system startup.

Mounting tmpfs: 
mkdir -p /mnt/tmp 
mount -t tmpfs -o size=20m tmpfs /mnt/tmp

Mounting ramfs:
mkdir -p /mnt/ram 
mount -t ramfs -o size=20m ramfs /mnt/ram

The other approach in case you're using lucene is to have the IndexReader use a Ram Directory. In this case you'd need a JVM instance with enough memory to load all of the index contents into memory and have more for processing search queries.
Also, that may translate to 'requiring'a 64-bit JVM so that it could use pseudo unlimited address space.

--Snip--

NIOFSDirectory nDir = new NIOFSDirectory(new File(indexDir));
RAMDirectory directory = new RAMDirectory(nDir);
IndexReader ir = IndexReader.open(directory);
IndexSearcher indexSearcher = new IndexSearcher(ir);

--Snip--

I haven't been really fond of using this approach as it forces a 64-bit architecture to be used but it may surely work as there's no overhead of using and manipulating the data manually as in the case of maintaining a tmpfs. The cleanups etc...

These are the basic 2 techniques to be used if you want your index to be fed off the RAM. It is a frequent question on the lucene users mailing list, so perhaps people can now stop asking that question... well.. almost...
All said and done.. don't stop optimizing the engine/app if your search is slow.. 99% of the times.. that is where it has to be handled.

Dealing with High Dimensional Data

I believe that data is best represented as a vector. For those who haven't heard this before, well let me start with a very basic example of 'how' this is done.

Lets assume a corpus of documents which have only 2 unique words(A,B) in its dictionary (If that was hard to follow, comment and I shall follow up with what that means). Now a document containing only 'A' is a unit vector along the direction of 'A' and so with a document containing only a single occurrence of 'B'. Documents with 'x' As and 'y' Bs can hence be represented as :

x a + y b (a and b are unit vectors along A and B).

When the corpus comprises of documents wherein there are a lot of terms with a very low document frequency, it is referred to as high dimensional data. An example would be a list of proper nouns e.g. hotel names.

High dimensional data, poses a lot of issues primarily due to its sparseness in the vector space. The sparseness of data makes a lot of tasks like clustering and tagging challenging. In order to process this data, more often than not, there is a need for reducing the dimension of the documents (sparseness). I'll discuss a relatively easy way to reduce the dimension of such data.

Given a corpus of high dimensional data, create document vectors for each of them. Create a term frequency matrix for the corpus and follow it up with dropping off all terms that occur in less than 10% (might vary as per the corpus/dataset) documents. Statistically this should remove around 60% of the documents

Also, removing the terms that occur in more than 80% of the documents would lead to removing a considerable ratio of terms that are redundant and too frequent. Such terms are generally tagged as stop-words and removed under all normal data/text processing algorithms.

The residue that remains now is of a considerably reduced dimension. This is a straightforward way of projecting the original data on a multi dimensional plane. A plane comprising of all dimensions that were reduced.

This data can now be consumed for any processing viz. clustering, classification etc..

Posts on how to cluster and various clustering techniques would soon follow.. unlike this one which took ages!

Lucene Vs Sphinx - A Showdown on a large dataset

There has long existed a battle among the "pro java" and "pro c" developer community. Not that I'd want to strictly be associated with one, but would always say the robustness/exception handling/stability vector have a better cosine value with java as compared to c [With all respect to C, for being the progenitor for Java]. Let me not move off on the tangent and rather more towards the core here. Last few weeks were spent trying to benchmark 'java' lucene as a search engine with 'C' sphinx. Though not exactly in their vanilla form, and a lot of modifications to both, we finally ran a lot of tests on both the engines.

Keeping a common playground with the following specifications:
Processor(s) : Intel Quad Core X 2
RAM : 24G
Operating System : RHEL 32 Bit
Document Corpus : 18 million+ Documents
Source Size : 90G [RDBMS Table]


On a corpus of approximately 18 million records, indexed and not all of them stored. Multiple field queries with varying boost values and some good level of complexity. Here is the result sheet:

Lucene
Index Size : 20G

Concurrency : 30 [5*6 Daemons, 2G each]
Total Searches : 64931
Slow Query Count (>=10 secs) : 3803 ( 5.86%)
Total Duration (secs) : 238094.574
Mean Duration : 3.667
Mode Duration : 0.835
Minimum Duration : 0.001
Maximum Duration : 1174.757
Duration Standard Deviation : 15.441
Search Time (secs) Distribution :-
[0,0.25) : 2770 ( 4.27%)
[0.25,0.5) : 5666 ( 8.73%)
[0.5,1) : 13515 (20.81%)
[1,1.5) : 10928 (16.83%)
[1.5,2) : 7330 (11.29%)
[2,3) : 8476 (13.05%)
[3,5) : 7222 (11.12%)
[5,10) : 5221 ( 8.04%)
[10,20) : 2335 ( 3.60%)
[20,+inf) : 1468 ( 2.26%)

Concurrency : 5 [1 Daemon * 2G]
Total Searches : 225906
Slow Query Count (>=10 secs) : 972 ( 0.43%)
Total Duration (secs) : 186700.646
Mean Duration : 0.826
Mode Duration : 0.003
Minimum Duration : 0.001
Maximum Duration : 467.647
Duration Standard Deviation : 2.864
Duration (secs) Bins :-
[0,0.25) : 64621 (28.61%)
[0.25,0.5) : 58947 (26.09%)
[0.5,1) : 56894 (25.18%)
[1,1.5) : 19836 ( 8.78%)
[1.5,2) : 9397 ( 4.16%)
[2,3) : 7941 ( 3.52%)
[3,5) : 4810 ( 2.13%)
[5,10) : 2488 ( 1.10%)
[10,20) : 684 ( 0.30%)
[20,+inf) : 288 ( 0.13%)



Sphinx
Index Size: 60G

Concurrency: 30
Total Searches : 244431
Slow Query Count (>=10 secs) : 27479 (11.24%)
Total Duration (secs) : 1243474.213
Mean Duration : 5.087
Mode Duration : 0.007
Minimum Duration : 0.001
Maximum Duration : 1869.063
Duration Standard Deviation : 17.833
Average Queries : 2.783
Duration (secs) Bins :-
[0,0.25) : 51186 (20.94%)
[0.25,0.5) : 27798 (11.37%)
[0.5,1) : 32372 (13.24%)
[1,1.5) : 20490 ( 8.38%)
[1.5,2) : 16915 ( 6.92%)
[2,3) : 21833 ( 8.93%)
[3,5) : 23550 ( 9.63%)
[5,10) : 22808 ( 9.33%)
[10,20) : 14540 ( 5.95%)
[20,+inf) : 12939 ( 5.29%)

Concurrency: 5
Total Searches : 226528
Slow Query Count (>=10 secs) : 9895 ( 4.37%)
Total Duration (secs) : 453296.517
Mean Duration : 2.001
Mode Duration : 0.007
Minimum Duration : 0.001
Maximum Duration : 164.713
Duration Standard Deviation : 4.543
Average Queries : 2.773
Duration (secs) Bins :-
[0,0.25) : 71001 (31.34%)
[0.25,0.5) : 36500 (16.11%)
[0.5,1) : 32799 (14.48%)
[1,1.5) : 20416 ( 9.01%)
[1.5,2) : 16385 ( 7.23%)
[2,3) : 13951 ( 6.16%)
[3,5) : 13330 ( 5.88%)
[5,10) : 12251 ( 5.41%)
[10,20) : 7563 ( 3.34%)
[20,+inf) : 2332 ( 1.03%)

As per the analysis, for the dataset analyzed, Lucene was found to win convincingly over its rival.
More details on the same to come soon!

P.S: Though lucene works great for a lot of cases, so does sphinx. Here, lucene seemed to have an upper hand