%0 Conference Paper %1 1376625 %A Feng, Jianlin %A Fang, Qiong %A Ng, Wilfred %B SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data %C New York, NY, USA %D 2008 %I ACM %K clickdata label order ranking search %P 55--66 %R 10.1145/1376616.1376625 %T Discovering bucket orders from full rankings %U http://portal.acm.org/citation.cfm?id=1376625 %X 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 T1, T2, ..., Tm, or conversely B can be an äpproximation" of some "ground truth" G where the rankings T1, T2, ..., Tm are simply 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 äpproximation" 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. %@ 978-1-60558-102-6

@inproceedings{1376625, 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 {T1, T2, ..., Tm}, or conversely B can be an "approximation" of some "ground truth" G where the rankings {T1, T2, ..., Tm} are simply 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.}, added-at = {2010-08-11T11:18:01.000+0200}, address = {New York, NY, USA}, author = {Feng, Jianlin and Fang, Qiong and Ng, Wilfred}, biburl = {https://www.bibsonomy.org/bibtex/2e836b438b06577afe33ccb589d893ca0/beate}, booktitle = {SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data}, description = {Discovering bucket orders from full rankings}, doi = {10.1145/1376616.1376625}, interhash = {eed6fbd01ea08cb4f0cb4f97828fc8fb}, intrahash = {e836b438b06577afe33ccb589d893ca0}, isbn = {978-1-60558-102-6}, keywords = {clickdata label order ranking search}, location = {Vancouver, Canada}, pages = {55--66}, publisher = {ACM}, timestamp = {2010-08-11T11:18:01.000+0200}, title = {Discovering bucket orders from full rankings}, url = {http://portal.acm.org/citation.cfm?id=1376625}, year = 2008 }