2017/07/28 by Bob Goodwin, Michael Hopcroft, Dan Luu +4 · 2 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Caching and Content Delivery #Web Data Mining and Analysis #Inverted index #Search engine indexing #Computer science #Signature (topology) #Index (typography) #Field (mathematics) #Block (permutation group theory) #Data mining #Cloud computing #Algorithm #Information retrieval #Mathematics #Operating system #World Wide Web
paper · pdf · doi:10.1145/3077136.3080789
openalex publication_date 2017/07/28 · openalex created_date 2017/08/08 · openalex updated_date 2026/07/29
Since the mid-90s there has been a widely-held belief that signature files are inferior to inverted files for text indexing. In recent years the Bing search engine has developed and deployed an index based on bit-sliced signatures. This index, known as BitFunnel, replaced an existing production system based on an inverted index. The driving factor behind the shift away from the inverted index was operational cost savings. This paper describes algorithmic innovations and changes in the cloud computing landscape that led us to reconsider and eventually field a technology that was once considered unusable. The BitFunnel algorithm directly addresses four fundamental limitations in bit-sliced block signatures. At the same time, our mapping of the algorithm onto a cluster offers opportunities to avoid other costs associated with signatures. We show these innovations yield a significant efficiency gain versus classic bit-sliced signatures and then compare BitFunnel with Partitioned Elias-Fano Indexes, MG4J, and Lucene.