{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,17]],"date-time":"2026-10-17T20:59:08Z","timestamp":1792270748216,"version":"4.4.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>The discovery of all unique (and non-unique) column combinations in a given dataset is at the core of any data profiling effort. The results are useful for a large number of areas of data management, such as anomaly detection, data integration, data modeling, duplicate detection, indexing, and query optimization. However, discovering all unique and non-unique column combinations is an NP-hard problem, which in principle requires to verify an exponential number of column combinations for uniqueness on all data values. Thus, achieving efficiency and scalability in this context is a tremendous challenge by itself.<\/jats:p>\n          <jats:p>\n            In this paper, we devise Ducc, a scalable and efficient approach to the problem of finding all unique\n            <jats:italic>and<\/jats:italic>\n            non-unique column combinations in big datasets. We first model the problem as a graph coloring problem and analyze the pruning effect of individual combinations. We then present our hybrid column-based pruning technique, which traverses the lattice in a depth-first and random walk combination. This strategy allows Ducc to typically depend on the solution set size and hence to prune large swaths of the lattice. Ducc also incorporates row-based pruning to run uniqueness checks in just few milliseconds. To achieve even higher scalability, Ducc runs on several CPU cores (scale-up) and compute nodes (scale-out) with a very low overhead. We exhaustively evaluate Ducc using three datasets (two real and one synthetic) with several millions rows and hundreds of attributes. We compare Ducc with related work: Gordian and HCA. The results show that Ducc is up to more than 2 orders of magnitude faster than Gordian and HCA (631x faster than Gordian and 398x faster than HCA). Finally, a series of scalability experiments shows the efficiency of Ducc to scale up and out.\n          <\/jats:p>","DOI":"10.14778\/2732240.2732248","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"301-312","source":"Crossref","is-referenced-by-count":63,"title":["Scalable discovery of unique column combinations"],"prefix":"10.14778","volume":"7","author":[{"given":"Arvid","family":"Heise","sequence":"first","affiliation":[{"name":"Hasso Plattner Institute (HPI), Postdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jorge-Arnulfo","family":"Quian\u00e9-Ruiz","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute (QCRI), Doha, Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ziawasch","family":"Abedjan","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute (HPI), Postdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anja","family":"Jentzsch","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute (HPI), Postdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Felix","family":"Naumann","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute (HPI), Postdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063801"},{"key":"e_1_2_1_2_1","first-page":"487","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB)","author":"Agrawal R.","year":"1994"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398580"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.369032"},{"key":"e_1_2_1_5_1","first-page":"243","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB)","author":"Bravo L.","year":"2007"},{"key":"e_1_2_1_6_1","first-page":"668","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB)","author":"Brown P. G.","year":"2003"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559895"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376940"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.154"},{"key":"e_1_2_1_10_1","volume-title":"Finding minimal keys in a relation instance","author":"Giannella C."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jbi.2008.01.008"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453900"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/584792.584867"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/777943.777945"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/645483.656220"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_1_17_1","unstructured":"IBM InfoSphere Information Analyzer. http:\/\/www-01.ibm.com\/software\/data\/infosphere\/information-analyzer.  IBM InfoSphere Information Analyzer. http:\/\/www-01.ibm.com\/software\/data\/infosphere\/information-analyzer."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007641"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/int.4550070703"},{"key":"e_1_2_1_20_1","volume-title":"Morgan Kaufmann","author":"Lacroix Z.","year":"2003"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-007-0048-x"},{"key":"e_1_2_1_22_1","unstructured":"Microsoft Data Profiling Task 03\/2013. http:\/\/msdn.microsoft.com\/en-us\/library\/bb895263.aspx.  Microsoft Data Profiling Task 03\/2013. http:\/\/msdn.microsoft.com\/en-us\/library\/bb895263.aspx."},{"key":"e_1_2_1_23_1","unstructured":"Oracle 11g Data Profiling. http:\/\/www.oracle.com\/technetwork\/middleware\/data-integration\/index-082810.html.  Oracle 11g Data Profiling. http:\/\/www.oracle.com\/technetwork\/middleware\/data-integration\/index-082810.html."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/39.2.124"},{"key":"e_1_2_1_25_1","first-page":"691","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB)","author":"Sismanis Y.","year":"2006"},{"key":"e_1_2_1_26_1","first-page":"1150","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB)","author":"Stonebraker M.","year":"2007"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920944"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732240.2732248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:47:19Z","timestamp":1672224439000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732240.2732248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.14778\/2732240.2732248"],"URL":"https:\/\/doi.org\/10.14778\/2732240.2732248","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}