Abstract
Ordering and ranking items of different types (observations, web pages, etc.) are important tasks in various applications, such as query processing and scientific data mining. We consider different problems of inferring total or partial orders from data, with special emphasis on applications to the seriation problem in paleontology. Seriation can be viewed as the task of ordering rows of a 0-1 matrix so that certain conditions hold. We review different approaches to this task, including spectral ordering methods, techniques for finding partial orders, and probabilistic models using MCMC methods.
Joint work with Antti Ukkonen, Aris Gionis, Mikael Fortelius, Kai Puolamäki, and Jukka Jernvall.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, S., Chaudhuri, S., Das, G., Gionis, A.: Automated ranking of database query results. In: CIDR (2003)
Chaudhuri, S., Das, G., Hristidis, V., Weikum, G.: Probabilistic ranking of database query results. In: Proceedings of the 30th International Conference on Very Large Data Bases (VLDB) (2004)
Fagin, R., Kumar, R., Mahdian, M., Sivakumar, D., Vee, E.: Comparing and aggregating rankings with ties. In: Proceedings of the 23rd ACM Symposium on Principles of Database Systems (PODS) (2004)
Fagin, R., Kumar, R., Sivakumar, D.: Comparing top k lists. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) (2003)
Fagin, R., Kumar, R., Sivakumar, D.: Efficient similarity search and classification via rank aggregation. In: Proceedings of the ACM Conference on Management of Data (SIGMOD) (2003)
Ilyas, I.F., Shah, R., Aref, W.G., Vitter, J.S., Elmagarmid, A.K.: Rank-aware query optimization. In: Proceedings of the ACM Conference on Management of Data (SIGMOD) (2004)
Li, C., Chang, K., Ilyas, I., Song, S.: Query algebra and optimization for relational top-k queries. In: Proceedings of the ACM Conference on Management of Data (SIGMOD) (2005)
Borodin, A., Roberts, G.O., Rosenthal, J.S., Tsaparas, P.: Link analysis ranking: Algorithms, theory, and experiments. ACM Transactions on Internet Technology 5(1) (2005)
Brin, S., Page, L.: The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems 30(1–7), 107–117 (1998)
Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: Proceedings of the 10th International World Wide Web Conference (WWW) (2001)
Haveliwala, T.: Topic-sensitive pagerank. In: Proceedings of the 11th International World Wide Web Conference (WWW) (2002)
Kleinberg, J.M.: Authoritative sources in a hyperlinked environment. Journal of the ACM 46(5) (1999)
Cohen, W.W., Schapire, R.E., Singer, Y.: Learning to order things. Journal of Artificial Intelligence Research 10, 243–270 (1999)
Crammer, K., Singer, Y.: Pranking with ranking. In: Conference on Neural Information Processing Systems (NIPS) (2001)
Fürnkranz, J., Hüllermeier, E.: Pairwise preference learning and ranking. In: Lavrač, N., Gamberger, D., Todorovski, L., Blockeel, H. (eds.) ECML 2003. LNCS (LNAI), vol. 2837. Springer, Heidelberg (2003)
Lebanon, G., Lafferty, J.D.: Cranking: Combining rankings using conditional probability models on permutations. In: ICML (2002)
Gionis, A., Kujala, T., Mannila, H.: Fragments of order. In: KDD 2003 (2003)
Puolamäki, K., Fortelius, M., Mannila, H.: Seriation in paleontological data using Markov Chain Monte Carlo methods. PLoS Computational Biology 2(2) (February 2006)
Gionis, A., Mannila, H., Puolamaki, K., Ukkonen, A.: Algorithms for discovering bucket orders from data. In: KDD (2006)
Fortelius, M., Gionis, A., Jernvall, J., Mannila, H.: Spectral ordering and biochronology of european fossil mammals. Paleobiology 32(2), 206–214 (2006)
Ukkonen, A.: Algorithms for Finding Orders and Analyzing Sets of Chains. PhD thesis, Helsinki University of Technology (2008)
Ukkonen, A., Mannila, H.: Finding outlying items in sets of partial rankings. In: Kok, J.N., Koronacki, J., López de Mántaras, R., Matwin, S., Mladenič, D., Skowron, A. (eds.) PKDD 2007. LNCS (LNAI), vol. 4702. Springer, Heidelberg (2007)
Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using P-Q tree algorithms. J. of Comp. and Syst. Sci. 13, 335–379 (1976)
Hsu, W.L.: A simple test for the consecutive ones property. Journal of Algorithms 43 (2002)
Brower, J., Kile, K.: Seriation of an original data matrix as applied to palaeoecology. Lethaia 21, 79–93 (1988)
Atkins, J.E., Boman, E.G., Hendrickson, B.: A spectral algorithm for seriation and the consecutive ones problem. SIAM Journal on Computing 28(1), 297–310 (1999)
Ng, A., Jordan, M., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: Advances in Neural Information Processing Systems (2001)
Azar, Y., Fiat, A., Karlin, A.R., McSherry, F., Saia, J.: Spectral analysis of data. In: ACM Symposium on Theory of Computing (2000)
Chung, F.R.K.: Spectral Graph Theory. CBMS Regional Conference Series in Mathematics (1997)
Hill, M.: Correspondence analysis: A neglected multivariate method. Applied Statistics 23, 340–354 (1974)
Kendall, D.G.: Abundance matrices and seriation in archaeology. Z. Wahscheinlichkeitstheorie verw. Geb. 17, 104–112 (1971)
Fortelius, M.: Neogene of the old world database of fossil mammals (NOW) (2006), http://www.helsinki.fi/science/now/
Ukkonen, A., Fortelius, M., Mannila, H.: Finding partial orders from unordered 0-1 data. In: Proceedings of the 11th ACM Conference on Knowledge Discovery and Data Mining (KDD) (2005)
Mannila, H., Meek, C.: Global partial orders from sequential data. In: KDD (2000)
Wilf, H.S.: Generatingfunctionology. Academic Press, London (1994), http://www.math.upenn.edu/~wilf/DownldGF.html
Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC) (2005)
Coppersmith, D., Fleischer, L., Rudra, A.: Ordering by weighted number of wins gives a good ranking for weighted tournaments. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 776–782 (2006)
van Zuylen, A., Hegde, R., Jain, K., Williamson, D.P.: Deterministic pivoting algorithms for constrained ranking and clustering problems. In: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 405–414 (2007)
Kempe, D., Kleinberg, J.M., Tardos, E.: Maximizing the spread of influence through a social network. In: KDD, pp. 137–146 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer Berlin Heidelberg
About this paper
Cite this paper
Mannila, H. (2008). Finding Total and Partial Orders from Data for Seriation. In: Jean-Fran, JF., Berthold, M.R., Horváth, T. (eds) Discovery Science. DS 2008. Lecture Notes in Computer Science(), vol 5255. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88411-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-88411-8_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88410-1
Online ISBN: 978-3-540-88411-8
eBook Packages: Computer ScienceComputer Science (R0)