{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T16:18:12Z","timestamp":1759940292592,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,9,25]],"date-time":"2014-09-25T00:00:00Z","timestamp":1411603200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGKDD Explor. Newsl."],"published-print":{"date-parts":[[2014,9,25]]},"abstract":"<jats:p>In many of the large-scale physical and social complex systems phenomena fat-tailed distributions occur, for which different generating mechanisms have been proposed. In this paper, we study models of generating power law distributions in the evolution of large-scale taxonomies such as Open Directory Project, which consist of websites assigned to one of tens of thousands of categories. The categories in such taxonomies are arranged in tree or DAG structured configurations having parent-child relations among them. We first quantitatively analyse the formation process of such taxonomies, which leads to power law distribution as the stationary distributions. In the context of designing classifiers for large-scale taxonomies, which automatically assign unseen documents to leaf-level categories, we highlight how the fat-tailed nature of these distributions can be leveraged to analytically study the space complexity of such classifiers. Empirical evaluation of the space complexity on publicly available datasets demonstrates the applicability of our approach.<\/jats:p>","DOI":"10.1145\/2674026.2674033","type":"journal-article","created":{"date-parts":[[2014,10,1]],"date-time":"2014-10-01T13:34:59Z","timestamp":1412170499000},"page":"47-56","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["On power law distributions in large-scale taxonomies"],"prefix":"10.1145","volume":"16","author":[{"given":"Rohit","family":"Babbar","sequence":"first","affiliation":[{"name":"Universit\u00e9 Grenoble Alpes, CNRS, Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cornelia","family":"Metzig","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Grenoble Alpes, CNRS, Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioannis","family":"Partalas","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Grenoble Alpes, CNRS, Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Gaussier","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Grenoble Alpes, CNRS, Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Massih-Reza","family":"Amini","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Grenoble Alpes, CNRS, Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,9,25]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"European Semantic Web Conference","author":"Babbar R.","year":"2013","unstructured":"R. Babbar , I. Partalas , C. Metzig , E. Gaussier , and M.-R. Amini . Comparative classifier evaluation for webscale taxonomies using power law . In European Semantic Web Conference , 2013 . R. Babbar, I. Partalas, C. Metzig, E. Gaussier, and M.-R. Amini. Comparative classifier evaluation for webscale taxonomies using power law. In European Semantic Web Conference, 2013."},{"key":"e_1_2_1_2_1","volume-title":"Emergence of scaling in random networks. science, 286(5439):509--512","author":"Barab\u00e1si A.-L.","year":"1999","unstructured":"A.-L. Barab\u00e1si and R. Albert . Emergence of scaling in random networks. science, 286(5439):509--512 , 1999 . A.-L. Barab\u00e1si and R. Albert. Emergence of scaling in random networks. science, 286(5439):509--512, 1999."},{"key":"e_1_2_1_3_1","first-page":"163","volume-title":"Neural Information Processing Systems","author":"Bengio S.","year":"2010","unstructured":"S. Bengio , J. Weston , and D. Grangier . Label embedding trees for large multi-class tasks . In Neural Information Processing Systems , pages 163 -- 171 , 2010 . S. Bengio, J. Weston, and D. Grangier. Label embedding trees for large multi-class tasks. In Neural Information Processing Systems, pages 163--171, 2010."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1571941.1571946"},{"key":"e_1_2_1_5_1","first-page":"161","volume-title":"Advances In Neural Information Processing Systems","author":"Bottou L.","year":"2008","unstructured":"L. Bottou and O. Bousquet . The tradeoffs of large scale learning . In Advances In Neural Information Processing Systems , pages 161 -- 168 , 2008 . L. Bottou and O. Bousquet. The tradeoffs of large scale learning. In Advances In Neural Information Processing Systems, pages 161--168, 2008."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031171.1031186"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036116"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015330.1015374"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.62.1842"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v58:5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316229"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1390681.1442794"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2011.6126481"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2009-00302-5"},{"key":"e_1_2_1_15_1","volume-title":"Neural Information Processing Systems","author":"Gopal S.","year":"2012","unstructured":"S. Gopal , Y. Yang , B. Bai , and A. Niculescu-Mizil . Bayesian models for large-scale hierarchical classification . In Neural Information Processing Systems , 2012 . S. Gopal, Y. Yang, B. Bai, and A. Niculescu-Mizil. Bayesian models for large-scale hierarchical classification. In Neural Information Processing Systems, 2012."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0370-1573(01)00042-4"},{"key":"e_1_2_1_17_1","volume-title":"Scaling in the structure of directory trees in a computer cluster. Physical review letters, 95(12):128701","author":"Klemm K.","year":"2005","unstructured":"K. Klemm , V. M. Egu\u00edluz , and M. San Miguel . Scaling in the structure of directory trees in a computer cluster. Physical review letters, 95(12):128701 , 2005 . K. Klemm, V. M. Egu\u00edluz, and M. San Miguel. Scaling in the structure of directory trees in a computer cluster. Physical review letters, 95(12):128701, 2005."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645526.657130"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089815.1089821"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(59)90098-1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2013.11.027"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1080\/00107510500052444"},{"key":"e_1_2_1_23_1","volume-title":"Contemporary Physics","author":"Newman M. E. J.","year":"2005","unstructured":"M. E. J. Newman . Power laws, Pareto distributions and Zipf's law . Contemporary Physics , 2005 . M. E. J. Newman. Power laws, Pareto distributions and Zipf's law. Contemporary Physics, 2005."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34487-9_74"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129183101001754"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2307\/2333389"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03248"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.79.966"},{"key":"e_1_2_1_29_1","volume-title":"Sustainable growth in complex networks. EPL (Europhysics Letters), 96(5):58005","author":"Tessone C. J.","year":"2011","unstructured":"C. J. Tessone , M. M. Geipel , and F. Schweitzer . Sustainable growth in complex networks. EPL (Europhysics Letters), 96(5):58005 , 2011 . C. J. Tessone, M. M. Geipel, and F. Schweitzer. Sustainable growth in complex networks. EPL (Europhysics Letters), 96(5):58005, 2011."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0370-1573(74)90023-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390440"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/860435.860455"},{"key":"e_1_2_1_33_1","volume-title":"Containing Papers of a Biological Character, 213:21--87","author":"Yule G. U.","year":"1925","unstructured":"G. U. Yule . A mathematical theory of evolution, based on the conclusions of dr. jc willis, frs. Philosophical Transactions of the Royal Society of London. Series B , Containing Papers of a Biological Character, 213:21--87 , 1925 . G. U. Yule. A mathematical theory of evolution, based on the conclusions of dr. jc willis, frs. Philosophical Transactions of the Royal Society of London. Series B, Containing Papers of a Biological Character, 213:21--87, 1925."}],"container-title":["ACM SIGKDD Explorations Newsletter"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2674026.2674033","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2674026.2674033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:38Z","timestamp":1750227218000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2674026.2674033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,25]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,9,25]]}},"alternative-id":["10.1145\/2674026.2674033"],"URL":"https:\/\/doi.org\/10.1145\/2674026.2674033","relation":{},"ISSN":["1931-0145","1931-0153"],"issn-type":[{"type":"print","value":"1931-0145"},{"type":"electronic","value":"1931-0153"}],"subject":[],"published":{"date-parts":[[2014,9,25]]},"assertion":[{"value":"2014-09-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}