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 {T₁, T₂, ..., T_m}, or conversely B can be an "approximation" of some "ground truth" G where the rankings {T₁, T₂, ..., T_m} 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 T_i 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 termed 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.

REFERENCES

• 1: Nir Ailon, Aggregation of partial rankings, p-ratings and top-m lists, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.415-424, January 07-09, 2007, New Orleans, Louisiana
• 2: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 3: Richard Bellman, On the approximation of curves by line segments using dynamic programming, Communications of the ACM, v.4 n.6, p.284, June 1961 [doi>10.1145/366573.366611]
• 4: William W. Cohen , Robert E. Schapire , Yoram Singer, Learning to order things, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.451-457, July 1998, Denver, Colorado, United States
• 5: Carmel Domshlak , Avigdor Gal , Haggai Roitman, Rank Aggregation for Automatic Schema Matching, IEEE Transactions on Knowledge and Data Engineering, v.19 n.4, p.538-553, April 2007 [doi>10.1109/TKDE.2007.1010]
• 6: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 7: Ronald Fagin , Ravi Kumar , Mohammad Mahdian , D. Sivakumar , Erik Vee, Comparing and aggregating rankings with ties, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055568]
• 8: Ronald Fagin , Ravi Kumar , D. Sivakumar, Efficient similarity search and classification via rank aggregation, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872795]
• 9: M. Fortelius, A. Gionis, J. Jernvall, and H. Mannila. Spectral ordering and biochronology of european fossil mammals. In Paleobiology, pages 206--214, 2006.
• 10: Aristides Gionis , Heikki Mannila , Kai Puolamäki , Antti Ukkonen, Algorithms for discovering bucket orders from data, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150468]
• 11: U. Halekoh and W. Vach. A bayesian approach to seriation problems in archeology. Computational Statistics and Data Analysis, 45(33):651--673, 2004.
• 12: Johan Himberg , Kalle Korpiaho , Heikki Mannila , Johanna Tikanmäki , Hannu Toivonen, Time Series Segmentation for Context Recognition in Mobile Devices, Proceedings of the 2001 IEEE International Conference on Data Mining, p.203-210, November 29-December 02, 2001
• 13: I. Miklos, I. Somodi, and J. Podani. Rearrangement of ecological data matrices via markov chain monte carlo simulation. Ecology, 86:3398--3410, 2005.
• 14: K. Puolamäki, M. Fortelius, and H. Mannila. Seriation in paleontological data using markov chain monte carlo methods. PLoS Computational Bioglogy, 2(2), 2006.
• 15: Deepak Rajan , Philip S. Yu, Discovering Partial Orders in Binary Data, Proceedings of the Sixth International Conference on Data Mining, p.510-521, December 18-22, 2006 [doi>10.1109/ICDM.2006.57]
• 16: E. Terzi and P. Tsaparas. Efficient algorithm for sequence segmentation. In SIAM SDM, 2006.
• 17: Antti Ukkonen , Mikael Fortelius , Heikki Mannila, Finding partial orders from unordered 0-1 data, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081904]
• 18: Anke van Zuylen , Rajneesh Hegde , Kamal Jain , David P. Williamson, Deterministic pivoting algorithms for constrained ranking and clustering problems, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.405-414, January 07-09, 2007, New Orleans, Louisiana

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation, Performance

Keywords:
bucket order, full ranking, ground truth, order discovering, quantile rank, rank gap, ranking aggregation