{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:52Z","timestamp":1750221292665,"version":"3.41.0"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,6,16]],"date-time":"2018-06-16T00:00:00Z","timestamp":1529107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council under the European Union's Seventh Framework Programme","award":["FP\/2007-2013"],"award-info":[{"award-number":["FP\/2007-2013"]}]},{"name":"ERC","award":["338077"],"award-info":[{"award-number":["338077"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,7,31]]},"abstract":"<jats:p>\n            We study the problem of detecting\n            <jats:italic>outlier pairs<\/jats:italic>\n            of strongly correlated variables among a collection of\n            <jats:italic>n<\/jats:italic>\n            variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of\n            <jats:italic>n<\/jats:italic>\n            vectors with unit Euclidean norm and dimension\n            <jats:italic>d<\/jats:italic>\n            , and for some constants 0&lt;\u03c4 &lt; \u03c1 &lt; 1, we are asked to find all the outlier pairs of vectors whose inner product is at least \u03c1 in absolute value, subject to the promise that all but at most\n            <jats:italic>q<\/jats:italic>\n            pairs of vectors have inner product at most \u03c4 in absolute value.\n          <\/jats:p>\n          <jats:p>\n            Improving on an algorithm of Valiant [FOCS\u00a02012; J.\u00a0ACM\u00a02015], we present a randomized algorithm that for Boolean inputs ({ \u22121,1}-valued data normalized to unit Euclidean length) runs in time \u00d5((\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              max,{ 1\u2212\u03b3 +\n              <jats:italic>M<\/jats:italic>\n              (\u0394 \u03b3 ,\u03b3),\n              <jats:italic>M<\/jats:italic>\n              (1\u2212\u03b3 ,2 \u0394 \u03b3)}\n            <\/jats:sup>\n            +\n            <jats:italic>qdn<\/jats:italic>\n            <jats:sup>2\u03b3<\/jats:sup>\n            ), where 0&lt;\u03b3 &lt; 1 is a constant tradeoff parameter and\n            <jats:italic>M<\/jats:italic>\n            (\u03bc, \u03bd) is the exponent to multiply an \u230a\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03bc<\/jats:sup>\n            \u230b \u00d7 \u230a\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03bd<\/jats:sup>\n            \u230b matrix with an \u230a\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03bd<\/jats:sup>\n            \u230b \u00d7 \u230a\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03bc<\/jats:sup>\n            \u230b matrix and \u0394 =1\/(1\u2212log\n            <jats:sub>\u03c4<\/jats:sub>\n            \u03c1). As corollaries we obtain randomized algorithms that run in time \u00d5( (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              2\/\u03c9 3\u2212log\n              <jats:sub>\u03c4<\/jats:sub>\n              \u03c1\n            <\/jats:sup>\n            +\n            <jats:italic>qdn<\/jats:italic>\n            <jats:sup>\n              2\/(1\u2212log\n              <jats:sub>\u03c4<\/jats:sub>\n              \u03c1)3=log\n              <jats:sub>\u03c4\u03c4<\/jats:sub>\n              \u03c1\n            <\/jats:sup>\n            ) and in time \u00f5( (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              4 \/ 2+\u03b1 (1\u2212log\n              <jats:sub>\u03c4<\/jats:sub>\n              \u03c1)\n            <\/jats:sup>\n            +\n            <jats:italic>qdn<\/jats:italic>\n            <jats:sup>\n              2\/\u03b1 (1\u2212log\n              <jats:sub>\u03c4<\/jats:sub>\n              \u03c1)2+\u03b1 (1\u2212log\n              <jats:sub>\u03c4<\/jats:sub>\n              \u03c1)\n            <\/jats:sup>\n            &gt;), where 2\u2264 \u03c9 &lt;2.38 is the exponent for square matrix multiplication and 0.3&lt;\u03b1 \u2264 1 is the exponent for\u00a0 rectangular matrix multiplication. The notation \u00d5(\u1e61) hides polylogarithmic factors in\n            <jats:italic>n<\/jats:italic>\n            and\n            <jats:italic>d<\/jats:italic>\n            whose degree may depend on \u03c1 and \u03c4. We present further corollaries for the light bulb problem and for learning sparse Boolean functions.\n          <\/jats:p>","DOI":"10.1145\/3174804","type":"journal-article","created":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T12:28:11Z","timestamp":1529324891000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A Faster Subquadratic Algorithm for Finding Outlier Correlations"],"prefix":"10.1145","volume":"14","author":[{"given":"Matti","family":"Karppa","sequence":"first","affiliation":[{"name":"Aalto University, Finland"}]},{"given":"Petteri","family":"Kaski","sequence":"additional","affiliation":[{"name":"Aalto University, Finland"}]},{"given":"Jukka","family":"Kohonen","sequence":"additional","affiliation":[{"name":"Aalto University, Finland"}]}],"member":"320","published-online":{"date-parts":[[2018,6,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722146"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020521"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902285"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.18"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.49"},{"volume-title":"Advances in Neural Information Processing Systems 28. Curran Associates","author":"Andoni Alexandr","key":"e_1_2_1_6_1","unstructured":"Alexandr Andoni , Piotr Indyk , Thijs Laarhoven , Ilya Razenshteyn , and Ludwig Schmidt . 2015. Practical and optimal LSH for angular distance . In Advances in Neural Information Processing Systems 28. Curran Associates , Inc., Red Hook, NY , 1225--1233. Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. 2015. Practical and optimal LSH for angular distance. In Advances in Neural Information Processing Systems 28. Curran Associates, Inc., Red Hook, NY, 1225--1233."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634150"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242591"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688513"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792543"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.908981"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242610"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442684"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2050814"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/070684914"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspl.1888.0082"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2013.12.009"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2050345.2050385"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2017.56"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.ch39"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745761"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Karppa Matti","year":"2016","unstructured":"Matti Karppa , Petteri Kaski , Jukka Kohonen , and Padraig \u00d3. Cath\u00e1in . 2016 . Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time . In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) . Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 52:1--52:17. Matti Karppa, Petteri Kaski, Jukka Kohonen, and Padraig \u00d3. Cath\u00e1in. 2016. Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 52:1--52:17."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396831"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276877"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.80"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1887568.1887611"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398574"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_32"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46800-5_9"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1057"},{"key":"e_1_2_1_40_1","volume-title":"Papert","author":"Minsky Marvin L.","year":"1969","unstructured":"Marvin L. Minsky and Seymour A . Papert . 1969 . Perceptrons : An Introduction to Computational Geometry. MIT Press , Boston, MA. Marvin L. Minsky and Seymour A. Papert. 1969. Perceptrons: An Introduction to Computational Geometry. MIT Press, Boston, MA."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.002"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646858"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 32nd International Conference on Machine Learning (ICML\u201915)","author":"Neyshabur Behnam","year":"2015","unstructured":"Behnam Neyshabur and Nathan Srebro . 2015 . On symmetric and asymmetric LSHs for inner product search . In Proceedings of the 32nd International Conference on Machine Learning (ICML\u201915) . Journal of Machine Learning Research , 1926--1934. Behnam Neyshabur and Nathan Srebro. 2015. On symmetric and asymmetric LSHs for inner product search. In Proceedings of the 32nd International Conference on Machine Learning (ICML\u201915). Journal of Machine Learning Research, 1926--1934."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2578221"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2493252.2493254"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884436"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/93335.93363"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/13.1.25"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339677"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS\u201914)","author":"Shrivastava Anshumali","year":"2014","unstructured":"Anshumali Shrivastava and Ping Li . 2014 . Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS) . In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS\u201914) . Curran Associates, Inc., Red Hook, NY, 2321--2329. Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS). In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS\u201914). Curran Associates, Inc., Red Hook, NY, 2321--2329."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741285"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447873"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177012580"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747647"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2728167"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/93025.93038"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767865"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213847"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487625"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/645924.671192"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634209"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316755"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000825"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/2567709.2567715"},{"volume-title":"Similarity Search. The Metric Space Approach. Advances in Database Systems","author":"Zezula Pavel","key":"e_1_2_1_66_1","unstructured":"Pavel Zezula , Giuseppe Amato , Vlastislav Dohnal , and Michal Batko . 2006. Similarity Search. The Metric Space Approach. Advances in Database Systems , Vol. 32 . Springer, New York , NY. Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, and Michal Batko. 2006. Similarity Search. The Metric Space Approach. Advances in Database Systems, Vol. 32. Springer, New York, NY."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3174804","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3174804","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:33Z","timestamp":1750212693000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3174804"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,16]]},"references-count":66,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7,31]]}},"alternative-id":["10.1145\/3174804"],"URL":"https:\/\/doi.org\/10.1145\/3174804","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,6,16]]},"assertion":[{"value":"2016-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}