{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T19:19:49Z","timestamp":1771960789357,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T00:00:00Z","timestamp":1653264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["OAC-1755464, OAC-2106461 and DGE-1723250"],"award-info":[{"award-number":["OAC-1755464, OAC-2106461 and DGE-1723250"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62136002 and 61972155"],"award-info":[{"award-number":["62136002 and 61972155"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003399","name":"Science and Technology Commission of Shanghai Municipality","doi-asserted-by":"crossref","award":["20DZ1100300"],"award-info":[{"award-number":["20DZ1100300"]}],"id":[{"id":"10.13039\/501100003399","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Shanghai Knowledge Service Platform","award":["ZF1213"],"award-info":[{"award-number":["ZF1213"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>Given a data matrix<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( D \\)<\/jats:tex-math><\/jats:inline-formula>, a submatrix<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( S \\)<\/jats:tex-math><\/jats:inline-formula>of<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( D \\)<\/jats:tex-math><\/jats:inline-formula>is an order-preserving submatrix (OPSM) if there is a permutation of the columns of<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( S \\)<\/jats:tex-math><\/jats:inline-formula>, under which the entry values of each row in<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( S \\)<\/jats:tex-math><\/jats:inline-formula>are strictly increasing. OPSM mining is widely used in real-life applications such as identifying coexpressed genes and finding customers with similar preference. However, noise is ubiquitous in real data matrices due to variable experimental conditions and measurement errors, which makes conventional OPSM mining algorithms inapplicable. No previous work on OPSM has ever considered uncertain value intervals using the well-established possible world semantics.<\/jats:p><jats:p>We establish two different definitions of significant OPSMs based on the<jats:italic>possible world semantics<\/jats:italic>: (1)\u00a0expected support-based and (2)\u00a0probabilistic frequentness-based. An optimized dynamic programming approach is proposed to compute the probability that a row supports a particular column permutation, with a closed-form formula derived to efficiently handle the special case of uniform value distribution and an accurate cubic spline approximation approach that works well with any uncertain value distributions. To efficiently check the probabilistic frequentness, several effective pruning rules are designed to efficiently prune insignificant OPSMs; two approximation techniques based on the Poisson and Gaussian distributions, respectively, are proposed for further speedup. These techniques are integrated into our two OPSM mining algorithms, based on prefix-projection and Apriori, respectively. We further parallelize our prefix-projection-based mining algorithm using PrefixFPM, a recently proposed framework for parallel frequent pattern mining, and we achieve a good speedup with the number of CPU cores. Extensive experiments on real microarray data demonstrate that the OPSMs found by our algorithms have a much higher quality than those found by existing approaches.<\/jats:p>","DOI":"10.1145\/3524915","type":"journal-article","created":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T12:09:07Z","timestamp":1648728547000},"page":"1-57","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Mining Order-preserving Submatrices under Data Uncertainty: A Possible-world Approach and Efficient Approximation Methods"],"prefix":"10.1145","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3120-8966","authenticated-orcid":false,"given":"Ji","family":"Cheng","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, HKUST, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4653-0408","authenticated-orcid":false,"given":"Da","family":"Yan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Alabama at Birmingham, AL, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6390-6940","authenticated-orcid":false,"given":"Wenwen","family":"Qu","sequence":"additional","affiliation":[{"name":"Shanghai Key Laboratory of Trustworthy Computing, ECNU, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8758-494X","authenticated-orcid":false,"given":"Xiaotian","family":"Hao","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, HKUST, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6806-8405","authenticated-orcid":false,"given":"Cheng","family":"Long","sequence":"additional","affiliation":[{"name":"School of Comput. Sci. and Engineering, Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6639-0521","authenticated-orcid":false,"given":"Wilfred","family":"Ng","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, HKUST, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4594-6946","authenticated-orcid":false,"given":"Xiaoling","family":"Wang","sequence":"additional","affiliation":[{"name":"Software Engineering Institute, East China Normal University China, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,5,23]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"29","volume-title":"SIGKDD","author":"Aggarwal Charu C.","year":"2009","unstructured":"Charu C. Aggarwal, Yan Li, Jianyong Wang, and Jing Wang. 2009. Frequent pattern mining with uncertain data. In SIGKDD. 29\u201338."},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1145\/276304.276314","volume-title":"SIGMOD","author":"Agrawal Rakesh","year":"1998","unstructured":"Rakesh Agrawal, Johannes Gehrke, Dimitrios Gunopulos, and Prabhakar Raghavan. 1998. Automatic subspace clustering of high dimensional data for data mining applications. In SIGMOD. 94\u2013105."},{"issue":"1","key":"e_1_3_3_4_2","first-page":"D885\u2013D890","article-title":"NCBI GEO: Archive for high-throughput functional genomic data","volume":"37","author":"Barrett Tanya","year":"2009","unstructured":"Tanya Barrett, Dennis B. Troup, Stephen E. Wilhite, Pierre Ledoux, Dmitry Rudnev, Carlos Evangelista, Irene F. Kim, Alexandra Soboleva, Maxim Tomashevsky, Kimberly A. Marshall, et\u00a0al. 2009. NCBI GEO: Archive for high-throughput functional genomic data. Nucleic Acids Res. 37, suppl 1 (2009), D885\u2013D890.","journal-title":"Nucleic Acids Res."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1089\/10665270360688075"},{"key":"e_1_3_3_6_2","first-page":"119","volume-title":"SIGKDD","author":"Bernecker Thomas","year":"2009","unstructured":"Thomas Bernecker, Hans-Peter Kriegel, Matthias Renz, Florian Verhein, and Andreas Z\u00fcfle. 2009. Probabilistic frequent itemset mining in uncertain databases. In SIGKDD. 119\u2013128."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1504\/IJBRA.2007.011834"},{"key":"e_1_3_3_8_2","first-page":"47","volume-title":"PAKDD","author":"Chui Chun Kit","year":"2007","unstructured":"Chun Kit Chui, Ben Kao, and Edward Hung. 2007. Mining frequent itemsets from uncertain data. In PAKDD. 47\u201358."},{"key":"e_1_3_3_9_2","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen et\u00a0al. 2009. Introduction to Algorithms. The MIT Press."},{"key":"e_1_3_3_10_2","first-page":"305","volume-title":"ICDE","author":"Cormode Graham","year":"2009","unstructured":"Graham Cormode, Feifei Li, and Ke Yi. 2009. Semantics of ranking queries for probabilistic data and expected ranks. In ICDE. 305\u2013316."},{"key":"e_1_3_3_11_2","first-page":"864","volume-title":"VLDB","author":"Dalvi Nilesh N.","year":"2004","unstructured":"Nilesh N. Dalvi and Dan Suciu. 2004. Efficient query evaluation on probabilistic databases. In VLDB. Morgan Kaufmann, 864\u2013875."},{"key":"e_1_3_3_12_2","first-page":"433","volume-title":"SIGKDD","author":"Fang Qiong","year":"2010","unstructured":"Qiong Fang, Wilfred Ng, and Jianlin Feng. 2010. Discovering significant relaxed order-preserving submatrices. In SIGKDD. 433\u2013442."},{"issue":"1","key":"e_1_3_3_13_2","first-page":"6:1\u20136:43","article-title":"Mining order-preserving submatrices from probabilistic matrices","volume":"39","author":"Fang Qiong","year":"2014","unstructured":"Qiong Fang, Wilfred Ng, Jianlin Feng, and Yuliang Li. 2014. Mining order-preserving submatrices from probabilistic matrices. ACM Trans. Datab. Syst. 39, 1 (2014), 6:1\u20136:43.","journal-title":"ACM Trans. Datab. Syst."},{"key":"e_1_3_3_14_2","first-page":"922","volume-title":"SIGKDD","author":"Gao Byron J.","year":"2006","unstructured":"Byron J. Gao, Obi L. Griffith, Martin Ester, and Steven J. M. Jones. 2006. Discovering significant OPSM subspace clusters in massive gene expression data. In SIGKDD. 922\u2013928."},{"key":"e_1_3_3_15_2","first-page":"375","volume-title":"SIGMOD","author":"Ge Tingjian","year":"2009","unstructured":"Tingjian Ge, Stanley B. Zdonik, and Samuel Madden. 2009. Top-k queries on uncertain data: On score distribution and typical answers. In SIGMOD. 375\u2013388."},{"key":"e_1_3_3_16_2","first-page":"1","volume-title":"SIGMOD","author":"Han Jiawei","year":"2000","unstructured":"Jiawei Han, Jian Pei, and Yiwen Yin. 2000. Mining frequent patterns without candidate generation. In SIGMOD. 1\u201312."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2827872"},{"key":"e_1_3_3_18_2","first-page":"673","volume-title":"SIGMOD","author":"Hua Ming","year":"2008","unstructured":"Ming Hua, Jian Pei, Wenjie Zhang, and Xuemin Lin. 2008. Ranking queries on uncertain data: A probabilistic threshold approach. In SIGMOD. 673\u2013686."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1960.10.1181"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920923"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687685"},{"key":"e_1_3_3_22_2","first-page":"187","volume-title":"ICDM","author":"Liu Jinze","year":"2003","unstructured":"Jinze Liu and Wei Wang. 2003. OP-cluster: Clustering by tendency in high dimensional space. In ICDM. 187\u2013194."},{"key":"e_1_3_3_23_2","first-page":"210","volume-title":"PAKDD","author":"Muzammal Muhammad","year":"2011","unstructured":"Muhammad Muzammal and Rajeev Raman. 2011. Mining sequential patterns from probabilistic databases. In PAKDD. 210\u2013221."},{"key":"e_1_3_3_24_2","first-page":"317","volume-title":"ICDE","author":"Soliman Mohamed A.","year":"2009","unstructured":"Mohamed A. Soliman and Ihab F. Ilyas. 2009. Ranking with uncertain scores. In ICDE. 317\u2013328."},{"key":"e_1_3_3_25_2","first-page":"896","volume-title":"ICDE","author":"Soliman Mohamed A.","year":"2007","unstructured":"Mohamed A. Soliman, Ihab F. Ilyas, and Kevin Chen-Chuan Chang. 2007. Top-k query processing in uncertain databases. In ICDE. 896\u2013905."},{"key":"e_1_3_3_26_2","first-page":"273","volume-title":"SIGKDD","author":"Sun Liwen","year":"2010","unstructured":"Liwen Sun, Reynold Cheng, David W. Cheung, and Jiefeng Cheng. 2010. Mining uncertain data with probabilistic guarantees. In SIGKDD. 273\u2013282."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350277"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1140093"},{"key":"e_1_3_3_29_2","first-page":"254","volume-title":"DASFAA","author":"Yan Da","year":"2011","unstructured":"Da Yan and Wilfred Ng. 2011. Robust ranking of uncertain data. In DASFAA. 254\u2013268."},{"key":"e_1_3_3_30_2","first-page":"1938","volume-title":"ICDE","author":"Yan Da","year":"2020","unstructured":"Da Yan, Wenwen Qu, Guimu Guo, and Xiaoling Wang. 2020. PrefixFPM: A parallel framework for general-purpose frequent pattern mining. In ICDE. IEEE, 1938\u20131941."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00687-0"},{"key":"e_1_3_3_32_2","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1145\/564691.564738","volume-title":"SIGMOD","author":"Yang Jiong","year":"2002","unstructured":"Jiong Yang, Wei Wang, Philip S. Yu, and Jiawei Han. 2002. Mining long sequential patterns in a noisy environment. In SIGMOD. 406\u2013417."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2003-4-5-r34"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.167"},{"key":"e_1_3_3_35_2","first-page":"160","volume-title":"ICDE","author":"Zhang Mengsheng","year":"2008","unstructured":"Mengsheng Zhang, Wei Wang, and Jinze Liu. 2008. Mining approximate order preserving clusters in the presence of noise. In ICDE. 160\u2013168."},{"key":"e_1_3_3_36_2","first-page":"819","volume-title":"SIGMOD","author":"Zhang Qin","year":"2008","unstructured":"Qin Zhang, Feifei Li, and Ke Yi. 2008. Finding frequent items in probabilistic data. In SIGMOD. 819\u2013832."},{"key":"e_1_3_3_37_2","first-page":"556","volume-title":"DBRank","author":"Zhang Xi","year":"2008","unstructured":"Xi Zhang and Jan Chomicki. 2008. On the semantics and evaluation of top-k queries in probabilistic databases. In DBRank. 556\u2013563."},{"key":"e_1_3_3_38_2","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/2247596.2247606","volume-title":"EDBT","author":"Zhao Zhou","year":"2012","unstructured":"Zhou Zhao, Da Yan, and Wilfred Ng. 2012. Mining probabilistically frequent sequential patterns in uncertain databases. In EDBT. 74\u201385."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3524915","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3524915","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3524915","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:20Z","timestamp":1750183760000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3524915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,23]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3524915"],"URL":"https:\/\/doi.org\/10.1145\/3524915","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,23]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}