Supporting early pruning in top-k query processing on massive data

This paper analyzes the execution behavior of “No Random Accesses” (NRA) and determines the depths to which each sorted file is scanned in growing phase and shrinking phase of NRA respectively. The analysis shows that NRA needs to maintain a large quantity of candidate tuples in growing phase on massive data. Based on the analysis, this paper proposes a novel top-k algorithm Top-K with Early Pruning (TKEP) which performs early pruning in growing phase. General rule and mathematical analysis for early pruning are presented in this paper. The theoretical analysis shows that early pruning can prune most of the candidate tuples. Although TKEP is an approximate method to obtain the top-k result, the probability for correctness is extremely high. Extensive experiments show that TKEP has a significant advantage over NRA.

► We find that NRA needs to maintain lots of candidate tuples on massive data.
► We propose an algorithm to prune most of candidate tuples.
► We provide a mathematical analysis for the pruning rule.