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

This codebase is used in the ADCS 2017 paper "Early Termination Heuristics for Score-at-a-Time Index Traversal".

You first need to build ATIRE, and then point to the ATIRE directory in the GNUMakefile. The invocation is the same as with the regular Jass program, but you may wish to specify the number of threads to use when building the code.

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.