Early Termination Heuristics for Score-at-a-Time Index Traversal

Abstract

Score-at-a-Time index traversal is a query processing approach which supports early termination in order to balance efficiency and effectiveness trade-offs. In this work, we explore new techniques which extend a modern Score-at-a-Time traversal algorithm to allow for parallel postings traversal. We show that careful integration of parallel traversal can improve both efficiency and effectiveness when compared with current single threaded early termination approaches. In addition, we explore the various trade-offs for differing early termination heuristics, and propose hybrid systems which parallelize long running queries, while processing short running queries with only a single thread.

Publication
Proceedings of the 22nd Australasian Document Computing Symposium (ADCS 2017)
Note
Runner up best paper award
Date
Links