Scalable Methods for Calculating Term Co-Occurrence Frequencies
This work addresses a specific bottleneck in search and information retrieval systems by providing scalable exact computation methods, which is incremental over existing approaches.
The paper tackles the challenge of efficiently computing exact term co-occurrence frequencies, which is computationally intensive due to the vast number of term pairs. It proposes methods based on inverted indexes and linear scanning, achieving processing speeds of over several hundred thousand documents per hour.
Search techniques make use of elementary information such as term frequencies and document lengths in computation of similarity weighting. They can also exploit richer statistics, in particular the number of documents in which any two terms co-occur. In this paper we propose alternative methods for computing this statistic, a challenging task because the number of distinct pairs of terms is vast -- around 100,000 in a typical 1000-word news article, for example. In contrast, we do not employ approximation algorithms, as we want to be able to find exact counts. We explore their efficiency, finding that a naïve approach based on a dictionary is indeed very slow, while methods based on a combination of inverted indexes and linear scanning provide both massive speed-ups and better observed asymptotic behaviour. Our careful implementation shows that, with our novel list-pairs approach it is possible to process over several hundred thousand documents per hour.