An Experimental Evaluation of Aggregation Algorithms for Processing Top-K Queries

For processing top-K queries with monotone aggregation functions, the threshold algorithm (TA) and its family are important methods in many scenarios. From 1996 to 2003, Fagin et al. proposed a variety of TA-like algorithms such as the FA, TA, TAz, NRA and CA algorithms for different access methods as well as various data resources, but they did not report the experimental results of the TA-like algorithms in their seminal papers. Since then, some of the original TA-like algorithms have been implemented, improved or adapted in different situations and/or applications, however, the original algorithms have not been thoroughly compared and analyzed under the same experimental framework. To address this problem, in this paper, we carry out extensive experiments to measure the performance of the original aggregation algorithms and the slight adaptations of TA, TAz and NRA, and then we provide comprehensive surveys on the natures of the TA-like algorithms based on our experimental results.