Auditing Boolean Attributes

Summary: Audits sum-query databases with Boolean-sensitive attributes; proves continuous-attribute techniques fail and auditing is hard (NP-hard in 2D), so no general efficient solution. Provides an exact 1D range algorithm, a conservative approximate auditor, and methods for max-aggregate variants. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1197
Venue: PODS
Year: 2000
Pagerank: 9.3006188e-05
Overall Rank: 2,017 | 86.17%
DOI: 10.1145/335168.335210

Incoming Non-self Citations Over Time

Authors

1. Jon Kleinberg (Cornell University)
2. Christos Papadimitriou (University of California Berkeley)
3. Prabhakar Raghavan (IBM)

BibTeX Citation

@inproceedings{kleinberg_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{Auditing Boolean Attributes}},
        url = {https://dl.acm.org/doi/10.1145/335168.335210},
        doi = {10.1145/335168.335210},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kleinberg, Jon and Papadimitriou, Christos and Raghavan, Prabhakar},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
123	Revealing Information while Preserving Privacy	2003	PODS	0.00031082693
384	On the Complexity of Optimal K-Anonymity	2004	PODS	0.00019510305
2,133	Two Can Keep a Secret: A Distributed Architecture for Secure Database Services	2005	CIDR	9.1164075e-05
7,875	Privacy-Enhancing k-Anonymization of Customer Data	2005	PODS	5.5253531e-05
12,545	Publishing Naive Bayesian Classifiers: Privacy without Accuracy Loss	2009	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,403	Minimal Data Upgrading to Prevent Inference and Association Attacks	1999	PODS
2	8,673	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS
3	7,115	Efficient Secure Query Evaluation over Encrypted XML Databases	2006	VLDB
4	123	Revealing Information while Preserving Privacy	2003	PODS
5	2,436	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD
6	8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
7	12,291	On Scaling Up Sensitive Data Auditing	2013	VLDB
8	2,401	Simulatable Auditing	2005	PODS
9	6,705	Efficient Auditing For Complex SQL queries	2011	SIGMOD
10	3,296	Towards Robustness in Query Auditing	2006	VLDB