New Algorithms for Monotone Classification

Summary: Active model: exact optimal needs Ω(n) label probes even for d=1; randomized (1+ε)-approximation uses Õ(w/ε^2) probes (w = dominance width), matching lower bounds up to polylog factors. Passive model: optimal monotone classifier found in poly(n,d) time. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1851
Venue: PODS
Year: 2021
Pagerank: 5.093636e-05
Overall Rank: 11,636 | 20.17%
DOI: 10.1145/3452021.3458324

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yufei Tao (Chinese University of Hong Kong)
2. Yu Wang (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{tao_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{New Algorithms for Monotone Classification}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458324},
        doi = {10.1145/3452021.3458324},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Tao, Yufei and Wang, Yu},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
248	Evaluation of entity resolution approaches on real-world match problems	2010	VLDB	0.00023278354
439	Corleone: Hands-Off Crowdsourcing for Entity Matching	2014	SIGMOD	0.00018464913
528	On Active Learning of Record Matching Packages	2010	SIGMOD	0.00017100838
529	Magellan: Toward Building Entity Matching Management Systems	2016	VLDB	0.00017096361
2,463	A Comprehensive Benchmark Framework for Active Learning Methods in Entity Matching	2020	SIGMOD	8.5486912e-05
2,893	Distributed Data Deduplication	2016	VLDB	7.983961e-05
3,568	MOMA - A Mapping-based Object Matching System	2007	CIDR	7.3021209e-05
11,898	Entity Matching with Active Monotone Classification	2018	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,835	From Discrepancy to Declustering: Near-optimal multidimensional declustering strategies for range queries [Extended Abstract]	2002	PODS
2	962	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD
3	6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
4	9,899	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS
5	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS
6	5,103	Deciding Monotone Duality and Identifying Frequent Itemsets in Quadratic Logspace	2013	PODS
7	690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
8	9,073	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS
9	11,790	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD
10	11,898	Entity Matching with Active Monotone Classification	2018	PODS