Algorithms for discovering bucket orders from data
- 20 August 2006
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '06
- p. 561-566
- https://doi.org/10.1145/1150402.1150468
Abstract
Ordering and ranking items of different types are important tasks in various applications, such as query processing and scientific data mining. A total order for the items can be misleading, since there are groups of items that have practically equal ranks.We consider bucket orders, i.e., total orders with ties. They can be used to capture the essential order information without overfitting the data: they form a useful concept class between total orders and arbitrary partial orders. We address the question of finding a bucket order for a set of items, given pairwise precedence information between the items. We also discuss methods for computing the pairwise precedence data.We describe simple and efficient algorithms for finding good bucket orders. Several of the algorithms have a provable approximation guarantee, and they scale well to large datasets. We provide experimental results on artificial and a real data that show the usefulness of bucket orders and demonstrate the accuracy and efficiency of the algorithms.Keywords
This publication has 17 references indexed in Scilit:
- Seriation in Paleontological Data Using Markov Chain Monte Carlo MethodsPLoS Computational Biology, 2006
- Ranking TournamentsSIAM Journal on Discrete Mathematics, 2006
- RankSQLPublished by Association for Computing Machinery (ACM) ,2005
- Aggregating inconsistent informationPublished by Association for Computing Machinery (ACM) ,2005
- Link analysis ranking: algorithms, theory, and experimentsACM Transactions on Internet Technology, 2005
- Pairwise Preference Learning and RankingLecture Notes in Computer Science, 2003
- Topic-sensitive PageRankPublished by Association for Computing Machinery (ACM) ,2002
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- On removing a vertex from the assignment polytopeLinear Algebra and its Applications, 1979