{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,5]],"date-time":"2024-06-05T15:41:27Z","timestamp":1717602087412},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>\n            The problem of identification of statistically significant patterns in a sequence of data has been applied to many domains such as intrusion detection systems, financial models, web-click records, automated monitoring systems, computational biology, cryptology, and text analysis. An observed pattern of events is deemed to be statistically significant if it is unlikely to have occurred due to randomness or chance alone. We use the\n            <jats:italic>chi-square statistic<\/jats:italic>\n            as a quantitative measure of statistical significance. Given a string of characters generated from a memoryless Bernoulli model, the problem is to identify the substring for which the empirical distribution of single letters deviates the most from the distribution expected from the generative Bernoulli model. This deviation is captured using the chi-square measure. The most significant substring (MSS) of a string is thus defined as the substring having the highest chi-square value. Till date, to the best of our knowledge, there does not exist any algorithm to find the MSS in better than\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time, where\n            <jats:italic>n<\/jats:italic>\n            denotes the length of the string. In this paper, we propose an algorithm to find the most significant substring, whose running time is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            ) with high probability. We also study some variants of this problem such as finding the top-t set, finding all substrings having chi-square greater than a fixed threshold and finding the MSS among substrings greater than a given length. We experimentally demonstrate the asymptotic behavior of the MSS on varying the string size and alphabet size. We also describe some applications of our algorithm on cryptology and real world data from finance and sports. Finally, we compare our technique with the existing heuristics for finding the MSS.\n          <\/jats:p>","DOI":"10.14778\/2336664.2336677","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1052-1063","source":"Crossref","is-referenced-by-count":7,"title":["Mining statistically significant substrings using the chi-square statistic"],"prefix":"10.14778","volume":"5","author":[{"given":"Mayank","family":"Sachan","sequence":"first","affiliation":[{"name":"Indian Institute of Technology, Kanpur, INDIA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnab","family":"Bhattacharya","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Kanpur, INDIA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Handbook of Mathematical Functions","author":"Abramowitz M.","year":"1964","unstructured":"M. Abramowitz and I. Stegun . Handbook of Mathematical Functions . Wiley , 1964 . M. Abramowitz and I. Stegun. Handbook of Mathematical Functions. Wiley, 1964."},{"key":"e_1_2_1_2_1","volume-title":"On finding the most statistically significant substring using the chi-square measure. Master's thesis","author":"Agarwal S.","year":"2009","unstructured":"S. Agarwal . On finding the most statistically significant substring using the chi-square measure. Master's thesis , Indian Institute of Technology , Kanpur , 2009 . S. Agarwal. On finding the most statistically significant substring using the chi-square measure. Master's thesis, Indian Institute of Technology, Kanpur, 2009."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1032649.1033431"},{"key":"e_1_2_1_4_1","volume-title":"Statistics for Experimenters","author":"Box G.","year":"1978","unstructured":"G. Box , W. Hunter , and J. Hunter . Statistics for Experimenters . Wiley , 1978 . G. Box, W. Hunter, and J. Hunter. Statistics for Experimenters. Wiley, 1978."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728726"},{"key":"e_1_2_1_6_1","volume-title":"MIT","author":"Cootner P.","year":"1964","unstructured":"P. Cootner . The Random Character of Stock Market Prices . MIT , 1964 . P. Cootner. The Random Character of Stock Market Prices. MIT, 1964."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/645906.673108"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511779398","volume-title":"Theory and Examples","author":"Durrett R.","year":"2010","unstructured":"R. Durrett . Probability : Theory and Examples . Cambridge University Press , 2010 . R. Durrett. Probability: Theory and Examples. Cambridge University Press, 2010."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13657-3_35"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4018\/978-1-61350-056-9.ch004"},{"key":"e_1_2_1_11_1","volume-title":"Red Sox vs Yankees: The Great Rivalry","author":"Frommer H.","year":"2004","unstructured":"H. Frommer and F. Frommer . Red Sox vs Yankees: The Great Rivalry . Sports Publishing LLC , 2004 . H. Frommer and F. Frommer. Red Sox vs Yankees: The Great Rivalry. Sports Publishing LLC, 2004."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/552556"},{"issue":"1","key":"e_1_2_1_13_1","first-page":"255","article-title":"Intrusion detection using the chi-square goodness-of-fit test for information assurance, network, forensics and software security","volume":"23","author":"Goonatilake R.","year":"2007","unstructured":"R. Goonatilake , A. Herath , S. Herath , S. Herath , and J. Herath . Intrusion detection using the chi-square goodness-of-fit test for information assurance, network, forensics and software security . J. Computing Sciences , 23 ( 1 ): 255 -- 263 , 2007 . R. Goonatilake, A. Herath, S. Herath, S. Herath, and J. Herath. Intrusion detection using the chi-square goodness-of-fit test for information assurance, network, forensics and software security. J. Computing Sciences, 23(1): 255--263, 2007.","journal-title":"J. Computing Sciences"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/262228"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-004-0174-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008768404046"},{"key":"e_1_2_1_18_1","first-page":"604","volume-title":"CSB","author":"Kuznetsov I.","year":"2003","unstructured":"I. Kuznetsov and S. Rackovsky . Identification of non-random patterns in structural and mutational data: the case of prion protein . In CSB , pages 604 -- 608 , 2003 . I. Kuznetsov and S. Rackovsky. Identification of non-random patterns in structural and mutational data: the case of prion protein. In CSB, pages 604--608, 2003."},{"key":"e_1_2_1_19_1","first-page":"210","volume-title":"KDD","author":"Mannila H.","year":"1995","unstructured":"H. Mannila , H. Toivonen , and A. Verkamo . Discovering frequent episodes in sequences . In KDD , pages 210 -- 215 , 1995 . H. Mannila, H. Toivonen, and A. Verkamo. Discovering frequent episodes in sequences. In KDD, pages 210--215, 1995."},{"key":"e_1_2_1_20_1","volume-title":"MIT Open Course Ware","author":"Panchenko D.","year":"2003","unstructured":"D. Panchenko . Lecture 23. In Statistics for Applications . MIT Open Course Ware , 2003 . D. Panchenko. Lecture 23. In Statistics for Applications. MIT Open Course Ware, 2003."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1973.10489014"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1185838"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39763-2_12"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4578-0"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720006002028"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/qre.392"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/3468.935043"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2336664.2336677","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:46:25Z","timestamp":1672224385000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2336664.2336677"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":27,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.14778\/2336664.2336677"],"URL":"https:\/\/doi.org\/10.14778\/2336664.2336677","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,6]]}}}