::MG4J: Managing Gigabytes for Java™
From the webpage:
Release 5.0 has several source and binary incompatibilities, and introduces quasi-succinct indices[broken link]. Benchmarks on the performance of quasi-succinct indices can be found here; for instance, this table shows the number of seconds to answer 1000 multi-term queries on a document collection of 130 million web pages:
MG4J MG4J* Lucene 3.6.2
Terms 70.9 132.1 130.6
And 27.5 36.7 108.8
Phrase 78.2 — 127.2
Proximity 106.5 — 347.6
Both engines were set to just enumerate the results without scoring. The column labelled MG4J* gives the timings of an artificially modified version in which counts for each retrieved document have been read (MG4J now stores document pointers and counts in separate files, but Lucene interleaves them, so it has to read counts compulsorily). Proximity queries are conjunctive queries that must be satisfied within a window of 16 words. The row labelled “Terms” gives the timings for enumerating the posting lists of all terms appearing in the queries.
I tried the link for “quasi-succinct indices” and it consistently returns a 404.
In lieu of that reference, see: Quasi-Succinct Indices by Sebastiano Vigna.
Abstract:
Compressed inverted indices in use today are based on the idea of gap compression: documents pointers are stored in increasing order, and the gaps between successive document pointers are stored using suitable codes which represent smaller gaps using less bits. Additional data such as counts and positions is stored using similar techniques. A large body of research has been built in the last 30 years around gap compression, including theoretical modeling of the gap distribution, specialized instantaneous codes suitable for gap encoding, and ad hoc document reorderings which increase the efficiency of instantaneous codes. This paper proposes to represent an index using a different architecture based on quasi-succinct representation of monotone sequences. We show that, besides being theoretically elegant and simple, the new index provides expected constant-time operations and, in practice, significant performance improvements on conjunctive, phrasal and proximity queries.
Heavy sledding but with search results as shown from the benchmark, well worth the time to master.