2018/04/02 by Yu-Hsuan Kuo, Kuo, Yu-Hsuan, Cho-Chun Chiu +7 · 1 citation
Computer Science · #Databases (cs.DB) #FOS: Computer and information sciences #cs.DB
paper · pdf · doi:10.48550/arxiv.1804.00370
13 pages
arxiv created 2018/09/13 · arxiv updated 2018/09/17
We consider the problem of privately releasing a class of queries that we call hierarchical count-of-counts histograms. Count-of-counts histograms partition the rows of an input table into groups (e.g., group of people in the same household), and for every integer j report the number of groups of size j. Hierarchical count-of-counts queries report count-of-counts histograms at different granularities as per hierarchy defined on an attribute in the input data (e.g., geographical location of a household at the national, state and county levels). In this paper, we introduce this problem, along with appropriate error metrics and propose a differentially private solution that generates count-of-counts histograms that are consistent across all levels of the hierarchy.