Metraipolis › archive › dc_8ee074caf0eb
Efficient discovery of unique column combinations on disk-resident data with limited memory — arXiv:2609.00783
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.00783
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T07:18:45.619Z
- SHA-256 of the archived text
e38d6f2e63fdda4a108703199c0b58f4cdf8048838678e87e12a82bedd7e3bcf- Stable URL of this page
https://metraipolis.com/documento/dc_8ee074caf0eb
How to cite
Efficient discovery of unique column combinations on disk-resident data with limited memory — arXiv:2609.00783 — arXiv (en), https://arxiv.org/abs/2609.00783 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8ee074caf0eb (Metraipolis archive dc_8ee074caf0eb, sha256 e38d6f2e63fdda4a108703199c0b58f4cdf8048838678e87e12a82bedd7e3bcf)
BibTeX
@misc{dc8ee074caf0eb,
title = {Efficient discovery of unique column combinations on disk-resident data with limited memory — arXiv:2609.00783},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.00783},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8ee074caf0eb; sha256 e38d6f2e63fdda4a108703199c0b58f4cdf8048838678e87e12a82bedd7e3bcf},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.00783. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The discovery of unique column combinations (UCCs) is a core task in data profiling, describing the key constraints of a table. The existing algorithms cannot deal with large-scale disk-resident data well due to high memory consumption and computational cost. In this paper, a novel DUD algorithm is developed to efficiently discover UCCs on disk-resident data with limited memory, which is inspired by the relationship between UCC discovery and transversal hypergraph. Rather than complete difference set generation of quadratic complexity, DUD only generates partial difference sets for hypergraph construction, followed by minimal hitting set enumeration to generate candidates and a validation process. DUD devises a strategy to generate full useful difference sets by pairwise comparisons of tuples having the same values with respect to some selected attributes. A novel theorem is developed and proved in this paper to report the candidates including the selected attributes as true UCCs directly without validation, which reduces the number of candidates to be validated significantly. A hash-based batch validation strategy is devised to validate a set of candidates on the relation instance, which only needs to maintain a small number of tuples in memory at a time. The extensive experimental results, conducted on synthetic and real-life data sets, show that DUD can discover UCCs on disk-resident data with high efficiency and low memory consumption. Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-02 in cs.DB). Categorie arXiv: Databases (cs.DB). Pagina del lavoro: https://arxiv.org/abs/2609.00783 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-17T07:06:49.783Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-09-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).