2025/04/01 by Xianghong Xu, Xiao He, Tieying Zhang +3 · 1 voice · 1 citation
Computer Science · Decision Sciences · #Column (typography) #Computer science #Data Management and Algorithms #Data Quality and Management #Data access #Data mining #Database #Information retrieval #Schema (genetic algorithms) #Time Series Analysis and Forecasting #cs.AI #cs.DB
paper · pdf · doi:10.1145/3725336
published in Proceedings of the ACM on Management of Data 3(3), 1-28 (Association for Computing Machinery)
arxiv published 2025/04/01 · arxiv updated 2025/04/01 · openalex publication_date 2025/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Number of Distinct Values (NDV) estimation of a multiset/column is a basis for many data management tasks, especially within databases. Despite decades of research, most existing methods require either a significant amount of samples through uniform random sampling or access to the entire column to produce estimates, leading to substantial data access costs and potentially ineffective estimations in scenarios with limited data access. In this paper, we propose leveraging semantic information, i.e., schema, to address these challenges. The schema contains rich semantic information that can benefit the NDV estimation. To this end, we propose PLM4NDV, a learned method incorporating Pre-trained Language Models (PLMs) to extract semantic schema information for NDV estimation. Specifically, PLM4NDV leverages the semantics of the target column and the corresponding table to gain a comprehensive understanding of the column's meaning. By using the semantics, PLM4NDV reduces data access costs, provides accurate NDV estimation, and can even operate effectively without any data access. Extensive experiments on a large-scale real-world dataset demonstrate the superiority of PLM4NDV over baseline methods. Our code is available at https://github.com/bytedance/plm4ndv.