Repeatability Corner Cases in Document Ranking: The Impact of Score Ties
This addresses a repeatability issue in information retrieval experiments, particularly for researchers using Lucene, but it is incremental as it focuses on a specific corner case.
The paper tackles the problem of non-deterministic document rankings due to score ties in multi-threaded indexing, showing that this can cause variability in effectiveness metrics, with efficiency costs when using external document ids to ensure repeatability.
Document ranking experiments should be repeatable. However, the interaction between multi-threaded indexing and score ties during retrieval may yield non-deterministic rankings, making repeatability not as trivial as one might imagine. In the context of the open-source Lucene search engine, score ties are broken by internal document ids, which are assigned at index time. Due to multi-threaded indexing, which makes experimentation with large modern document collections practical, internal document ids are not assigned consistently between different index instances of the same collection, and thus score ties are broken unpredictably. This short paper examines the effectiveness impact of such score ties, quantifying the variability that can be attributed to this phenomenon. The obvious solution to this non-determinism and to ensure repeatable document ranking is to break score ties using external collection document ids. This approach, however, comes with measurable efficiency costs due to the necessity of consulting external identifiers during query evaluation.