Decision Trees for Entity Identification: Approximation Algorithms and Hardness Results

Summary: Extends entity-identification decision trees beyond binary/uniform inputs to arbitrary attribute alphabets and priors, minimizing expected test cost. Greedy yields O(r_K·log N) (r_K≤log K); Ω(log N) hardness even for K=2 so greedy is binary-optimal up to constants; connects to an Erdős Ramsey conjecture. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1414
Venue: PODS
Year: 2007
Pagerank: -
Overall Rank: 13,784 | 5.43%
DOI: 10.1145/1265530.1265538

Incoming Non-self Citations Over Time

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

Authors

BibTeX Citation

@inproceedings{chakravarthy_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Decision Trees for Entity Identification: Approximation Algorithms and Hardness Results}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265538},
        doi = {10.1145/1265530.1265538},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chakravarthy, Venkatesan T. and Pandit, Vinayaka and Roy, Sambuddha and Awasthi, Pranjal and Mohania, Mukesh},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,561	Helping Satisfy Multiple Objectives During a Service Desk Conversation	2008	SIGMOD	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	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS
2	8,103	The Computation of Optimal Subset Repairs	2020	VLDB
3	7,923	Ranked Enumeration of Minimal Triangulations	2019	PODS
4	11,641	Approximation Algorithms for Large Scale Data Analysis	2021	PODS
5	11,790	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD
6	6,554	Approximate Algorithms for k-Anonymity	2007	SIGMOD
7	11,463	Approximating Probabilistic Group Steiner Trees in Graphs	2023	VLDB
8	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
9	9,036	Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations	2022	PODS
10	3,553	On the Complexity of Approximate Query Optimization	2002	PODS