{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T13:12:17Z","timestamp":1791897137652,"version":"4.3.4"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2003,1]]},"abstract":"<jats:p>Motivated by several applications, we introduce various distance measures between \"top k lists.\" Some of these distance measures are metrics, while others are not. For each of these latter distance measures, we show that they are \"almost\" a metric in the following two seemingly unrelated aspects:<\/jats:p>\n                  <jats:p>(i) they satisfy a relaxed version of the polygonal (hence, triangle) inequality, and<\/jats:p>\n                  <jats:p>(ii) there is a metric with positive constant multiples that bound our measure above and below.<\/jats:p>\n                  <jats:p>This is not a coincidence---we show that these two notions of almost being a metric are the same. Based on the second notion, we define two distance measures to be equivalent if they are bounded above and below by constant multiples of each other. We thereby identify a large and robust equivalence class of distance measures.<\/jats:p>\n                  <jats:p>Besides the applications to the task of identifying good notions of (dis)similarity between two top k lists, our results imply polynomial-time constant-factor approximation algorithms for the rank aggregation problem with respect to a large class of distance measures. (A correction for this article has been appended to the pdf file.)<\/jats:p>","DOI":"10.1137\/s0895480102412856","type":"journal-article","created":{"date-parts":[[2003,11,17]],"date-time":"2003-11-17T21:00:45Z","timestamp":1069102845000},"page":"134-160","source":"Crossref","is-referenced-by-count":552,"title":["Comparing Top\n                    <i>k<\/i>\n                    Lists"],"prefix":"10.1137","volume":"17","author":[{"given":"Ronald","family":"Fagin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D.","family":"Sivakumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192240226"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00160-X"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"01]Haifa D. Carmel, D. Cohen, R. Fagin, E. Farchi, M. Herscovici, Y. Maarek, and A. Soffer,\n                      Static index pruning for information retrieval systems\n                      , in Proceedings of the 24th ACM SIGIR Conference on Research and Development in Information Retrieval, 2001, pp. 43\u201350.","DOI":"10.1145\/383952.383958"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. Charikar, K. Chen, and M. Farach\u2010Colton,\n                      Finding frequent items in data streams\n                      , in Proceedings of the 29th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Comput. Sci. 2380, Springer\u2010Verlag, Berlin, 2002, pp. 693\u2013703.","DOI":"10.1007\/3-540-45465-9_59"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1106-8"},{"key":"R6","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1111\/j.2517-6161.1977.tb01624.x","volume":"39","author":"Diaconis Persi","year":"1977","journal-title":"J. Roy. Statist. Soc. Ser. B"},{"key":"R7","unstructured":"P. Diaconis,\n                      Group Representation in Probability and Statistics\n                      , IMS Lecture Notes Monogr. Ser. 11, Institute of Mathematical Statistics, Hayward, CA, 1988."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"C. Dwork, R. Kumar, M. Naor, and D. Sivakumar,\n                      Rank aggregation methods for the web\n                      , in Proceedings of the 10th International World Wide Web Conference, ACM, New York, 2001, pp. 613\u2013622.","DOI":"10.1145\/371920.372165"},{"key":"R9","volume-title":"Topology","author":"Dugundji James","year":"1966"},{"key":"R10","unstructured":"RonaldFagin, RaviKumar, D.Sivakumar, Comparing topklists, ACM, New York, 2003, 28\u2013361974898"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008023416823"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-9995-0"},{"key":"R13","volume-title":"Rank correlation methods","author":"Kendall Maurice","year":"1990"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"S. Kamvar, T. Haveliwala, C. Manning, and G. Golub,\n                      Extrapolation methods for accelerating PageRank computations\n                      , in Proceedings of the 12th International World Wide Web Conference, ACM, New York, 2003, pp. 261\u2013270.","DOI":"10.1145\/775152.775190"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"J. H. Lee,\n                      Combining multiple evidence from different properties of weighting schemes\n                      , in Proceedings of the 18th ACM SIGIR Conference on Research and Development in Information Retrieval, 1995, pp. 180\u2013188.","DOI":"10.1145\/215206.215358"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"J. H. Lee,\n                      Combining multiple evidence from different relevant feedback methods\n                      , in Database Systems for Advanced Applications \u201997, World Scientific, Singapore, 1997, pp. 421\u2013430.","DOI":"10.1142\/9789812819536_0044"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480102412856","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:32:21Z","timestamp":1787322741000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480102412856"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["10.1137\/S0895480102412856"],"URL":"https:\/\/doi.org\/10.1137\/s0895480102412856","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}