Discovering bucket orders from full rankings

Abstract

Discovering a bucket order B from a collection of possibly noisy full rankings is a fundamental problem that relates to various applications involving rankings. Informally, a bucket order is a total order that allows "ties" between items in a bucket. A bucket order B can be viewed as a "representative" that summarizes a given set of full rankings {7 1, T2, . . ., Tm}, or conversely B can be an "approximation" of some "ground truth" G where the rankings {T1, T2,.. ., Tm} are the "linear extensions" of G. Current work of finding bucket orders such as the dynamic programming algorithm is mainly developed from the "representative" perspective, which maximizes items' Intra-bucket similarity when forming a bucket. The underlying idea of maximizing intra-bucket similarity is realized via minimizing the sum of the deviations of median ranks within a bucket. In contrast, from the "approximation" perspective, since each observed full ranking Ti is simply a linear extension of the given "ground truth" bucket order G, items in a big bucket b in G are forced to have different median ranks, and as a result b will have a big sum of deviations. Thus, minimizing the sum of deviations may result in an undesirable scenario that big buckets are mostly decomposed into small ones. In this paper, we propose a novel heuristic called Abnormal Rank Gap to capture the inter-bucket dissimilarity for better bucket forming. In addition, we propose to use the "closeness" on multiple quantile ranks to determine if two items should be put into the same bucket. We develop a novel bucket order discovering method called the Bucket Gap algorithm. Our extensive experiments demonstrate that the Bucket Gap algorithm significantly outperforms the major related work, i.e., the Bucket Pivot algorithm. In particular, the error distance of the generated bucket order can be reduced by about 30% on a real paleontological dataset and the noise tolerance can be increased from 30% to 50% in the synthetic dataset. © Copyright 2008 ACM