7
$\begingroup$

Modern papers on search indices often contain a statement that inverted indexes (posting lists) are categorically superior to signature files (bloom filters). Here are some examples from papers published in 2016:

While this [signature file] technique provides a relatively low computation overhead, studies by Zobel et al. [1998] have shown that inverted files significantly outperform signature files.

Inverted indexes have been benchmarked as the most generalisable, and well performing structure (Zobel et al., 1998)

Every paper seems to cite Zobel et al., Inverted files versus signature files for text indexing.

However, if I'm reading Zobel et al. correctly, the argument they make isn't fundamental (e.g., an asymptotic bound or an information theoretic limit). Rather, the argument seems to be, given signature files implemented with techniques X, Y, and Z compared to inverted indices implemented with techniques A, B, and C, and the current technology of the day (disks with very high seek/access overhead), inverted indices are superior because they require fewer seeks and there are faster.

Is there a more recent comparison that compares these techniques on SSD, NVMe, or RAM, or is there a more recent comparison that looks at "new" techniques that have been invented since 1998?

$\endgroup$
1
$\begingroup$

Don't know any fresh references.

Off the top of my head:

Signature files require candidate verification via forward files. This requires lots of random accesses, basically one per potential match. One random memory access is 100+ CPU cycles. You can do a lot of work in 100 CPU cycles (e.g., you can decompress more than 100 IDs single core http://boytsov.info/pubs/simdcompressionarxiv.pdf).

Random access speed is even worse in the case of HDD or even SSD. There is in fact a growing gap between random and sequential access speed.

Before making this random access you cannot do pruning, early-termination, etc... BTW, for the most fancy recent data structure, you should probably check partitioned Elias-Fano indices: http://pages.di.unipi.it/rossano/wp-content/uploads/sites/7/2015/11/sigir14.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.