{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:19:25Z","timestamp":1750306765510,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,7,1]],"date-time":"2013-07-01T00:00:00Z","timestamp":1372636800000},"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":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>\n            Although order statistics have been studied for several decades, most of the results are based on the assumption of independent and identically distributed (i.i.d.) random variables. In the literature, how to compute the\n            <jats:italic>m<\/jats:italic>\n            th order statistics of\n            <jats:italic>n<\/jats:italic>\n            correlated random variables is still a problem. This article proposes a recursive algorithm based on statistical min\/max operations to compute order statistics for general correlated and not necessarily identically distributed random variables. The algorithm has an O(\n            <jats:italic>mn<\/jats:italic>\n            ) time complexity and O(\n            <jats:italic>m + n<\/jats:italic>\n            ) space complexity. A binary tree-based data structure is further developed to allow selective update of the order statistics with O(\n            <jats:italic>\n              nm\n              <jats:sup>2<\/jats:sup>\n            <\/jats:italic>\n            ) time. As a vehicle to demonstrate the algorithm, we apply it to the path selection algorithm in at-speed testing. A novel metric\n            <jats:italic>multilayer process space coverage metric<\/jats:italic>\n            is proposed to quantitatively gauge the quality of path selection. We then show that such a metric is directly linked to the order statistics, and our recursive algorithm can thus be applied. By employing a branch-and-bound path selection algorithm with these techniques, this article shows that selecting an optimal set of paths for a multimillion-gate design can be performed efficiently. Compared to the state of the art, experimental results show both the efficiency of our algorithms and better quality of our path selection.\n          <\/jats:p>","DOI":"10.1145\/2491477.2491486","type":"journal-article","created":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T19:12:41Z","timestamp":1374779561000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Order statistics for correlated random variables and its application to at-speed testing"],"prefix":"10.1145","volume":"18","author":[{"given":"Yiyu","family":"Shi","sequence":"first","affiliation":[{"name":"Missouri University of Science and Technology, Rolla, MO"}]},{"given":"Jinjun","family":"Xiong","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Yorktown Heights, NY"}]},{"given":"Vladimir","family":"Zolotov","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Yorktown Heights, NY"}]},{"given":"Chandu","family":"Visweswariah","sequence":"additional","affiliation":[{"name":"IBM Microelectronics, Hopewell Junction, NY"}]}],"member":"320","published-online":{"date-parts":[[2013,7,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610929408831453"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9473(94)90172-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610929508831564"},{"key":"e_1_2_1_4_1","unstructured":"Bushnell M. L. and Agrawal V. D. 2000. Essentials of Electronic Testing for Digital Memory and Mixed-Signal VLSI Circuits. Kluwer Academic Publishers Norwell MA.  Bushnell M. L. and Agrawal V. D. 2000. Essentials of Electronic Testing for Digital Memory and Mixed-Signal VLSI Circuits. Kluwer Academic Publishers Norwell MA."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/68.3.609"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.238614"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Childs A. and Balakrishnan N. 1998. Generalized recurrence relations for moments of order statistics from non-identical pareto and truncated pareto random variables with applications to robustness. In Order Statistics: Theory and Methods Elsevier Amsterdam 403--438.  Childs A. and Balakrishnan N. 1998. Generalized recurrence relations for moments of order statistics from non-identical pareto and truncated pareto random variables with applications to robustness. In Order Statistics: Theory and Methods Elsevier Amsterdam 403--438.","DOI":"10.1016\/S0169-7161(98)16017-0"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jspi.2005.08.026"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.9.2.145"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"David H. A. and Nagaraja H. N. 2003. Order Statistic. John Wiley and Sons Hoboken NJ.  David H. A. and Nagaraja H. N. 2003. Order Statistic. John Wiley and Sons Hoboken NJ.","DOI":"10.1002\/0471722162"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Dudley R. M. 2002. Real Analysis and Probability. Cambridge University Press Cambridge U.K.  Dudley R. M. 2002. Real Analysis and Probability. Cambridge University Press Cambridge U.K.","DOI":"10.1017\/CBO9780511755347"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-3758(95)92781-5"},{"key":"e_1_2_1_13_1","first-page":"229","article-title":"Functions of non-i.i.d. random vectors expressed as functions of i.i.d. random vectors","volume":"9","author":"Guilbaud O.","year":"1982","journal-title":"Scand. J. Statist"},{"volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design. 405--412","author":"Iyengar V.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the International Test Conference.","author":"Iyengar V.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02868637"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/513918.514061"},{"key":"e_1_2_1_18_1","unstructured":"Nishii R. 2001. Box-Cox Transformation. Springer Berlin Heidelberg.  Nishii R. 2001. Box-Cox Transformation. Springer Berlin Heidelberg."},{"volume-title":"Proceedings of the International Test Conference. 592--601","author":"Qiu W.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Reiss R. D. 1989. Approximate Distributions of Order Statistics: With Applications to Nonparametric Statistics. Springer Berlin Heidelberg.  Reiss R. D. 1989. Approximate Distributions of Order Statistics: With Applications to Nonparametric Statistics. Springer Berlin Heidelberg.","DOI":"10.1007\/978-1-4613-9620-8"},{"volume-title":"Proceedings of the International Test Conference. 974--982","author":"Sharma M.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/996566.996663"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/996566.996663"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.835137"},{"key":"e_1_2_1_25_1","unstructured":"Weiss N. A. 2007. Introductory Statistics 8th Ed. Addison Wesley Boston MA.  Weiss N. A. 2007. Introductory Statistics 8th Ed. Addison Wesley Boston MA."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1630004"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.884403"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065579.1065606"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2043570"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2491477.2491486","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2491477.2491486","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:49Z","timestamp":1750231729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2491477.2491486"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["10.1145\/2491477.2491486"],"URL":"https:\/\/doi.org\/10.1145\/2491477.2491486","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2013,7]]},"assertion":[{"value":"2011-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}