{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T08:14:53Z","timestamp":1768724093531,"version":"3.49.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>\n            We consider the problem of constructing decision trees for entity identification from a given relational table. The input is a table containing information about a set of entities over a fixed set of attributes and a probability distribution over the set of entities that specifies the likelihood of the occurrence of each entity. The goal is to construct a decision tree that identifies each entity unambiguously by testing the attribute values such that the average number of tests is minimized. This classical problem finds such diverse applications as efficient fault detection, species identification in biology, and efficient diagnosis in the field of medicine. Prior work mainly deals with the special case where the input table is binary and the probability distribution over the set of entities is uniform. We study the general problem involving arbitrary input tables and arbitrary probability distributions over the set of entities. We consider a natural greedy algorithm and prove an approximation guarantee of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>r<\/jats:italic>\n            <jats:sub>\n              <jats:italic>K<\/jats:italic>\n            <\/jats:sub>\n            \u22c5 log\n            <jats:italic>N<\/jats:italic>\n            ), where\n            <jats:italic>N<\/jats:italic>\n            is the number of entities and\n            <jats:italic>K<\/jats:italic>\n            is the maximum number of distinct values of an attribute. The value\n            <jats:italic>r<\/jats:italic>\n            <jats:sub>\n              <jats:italic>K<\/jats:italic>\n            <\/jats:sub>\n            is a suitably defined Ramsey number, which is at most log\n            <jats:italic>K<\/jats:italic>\n            . We show that it is NP-hard to approximate the problem within a factor of \u03a9(log\n            <jats:italic>N<\/jats:italic>\n            ), even for binary tables (i.e.,\n            <jats:italic>K<\/jats:italic>\n            =2). Thus, for the case of binary tables, our approximation algorithm is optimal up to constant factors (since\n            <jats:italic>r<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            =2). In addition, our analysis indicates a possible way of resolving a Ramsey-theoretic conjecture by Erd\u00f6s.\n          <\/jats:p>","DOI":"10.1145\/1921659.1921661","type":"journal-article","created":{"date-parts":[[2011,3,29]],"date-time":"2011-03-29T12:01:30Z","timestamp":1301400090000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Decision trees for entity identification"],"prefix":"10.1145","volume":"7","author":[{"given":"Venkatesan T.","family":"Chakaravarthy","sequence":"first","affiliation":[{"name":"IBM India Research Lab, Vasanth Kunj, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vinayaka","family":"Pandit","sequence":"additional","affiliation":[{"name":"IBM India Research Lab, Vasanth Kunj, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sambuddha","family":"Roy","sequence":"additional","affiliation":[{"name":"IBM India Research Lab, Vasanth Kunj, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranjal","family":"Awasthi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mukesh K.","family":"Mohania","sequence":"additional","affiliation":[{"name":"IBM India Research Lab, Vasanth Kunj, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,3,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265538"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_19"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190070105"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 17th Annual Conference on Neural Information Processing Systems. MIT Press","author":"Dasgupta S.","year":"2005","unstructured":"Dasgupta , S. 2005 . Analysis of a greedy active learning strategy . In Proceedings of the 17th Annual Conference on Neural Information Processing Systems. MIT Press , Cambridge, MA, 337--344. Dasgupta, S. 2005. Analysis of a greedy active learning strategy. In Proceedings of the 17th Annual Conference on Neural Information Processing Systems. MIT Press, Cambridge, MA, 337--344."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.37236\/1188"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1110-5"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0123019"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263588"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Graham R. Rothschild B. and Spencer J. 1990. Ramsey Theory. John Wiley &amp; Sons New York.  Graham R. Rothschild B. and Spencer J. 1990. Ramsey Theory. John Wiley &amp; Sons New York.","DOI":"10.1038\/scientificamerican0790-112"},{"key":"e_1_2_1_13_1","unstructured":"Heeringa B. and Adler M. 2005. Approximating optimal decision trees. Tech. rep. TR 05-25 University of Massachusetts Amherst.  Heeringa B. and Adler M. 2005. Approximating optimal decision trees. Tech. rep. TR 05-25 University of Massachusetts Amherst."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90095-8"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 5th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science","volume":"1272","author":"Kosaraju S.","unstructured":"Kosaraju , S. , Przytycka , M. , and Borgstrom , R . 1999. On an optimal split tree problem . In Proceedings of the 5th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science , vol. 1272 . Springer, Berlin, 69--92. Kosaraju, S., Przytycka, M., and Borgstrom, R. 1999. On an optimal split tree problem. In Proceedings of the 5th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 1272. Springer, Berlin, 69--92."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/356893.356898"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009744630224"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00208-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/13.2.145"},{"key":"e_1_2_1_20_1","first-page":"7","article-title":"Small Ramsey numbers","volume":"1","author":"Radziszowski S.","year":"1994","unstructured":"Radziszowski , S. 1994 . Small Ramsey numbers . Electron. J. Combin. 1 , 7 . Radziszowski, S. 1994. Small Ramsey numbers. Electron. J. Combin. 1, 7.","journal-title":"Electron. J. Combin."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_2_1_22_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of EvoWorkshops","author":"Reynolds A.","unstructured":"Reynolds , A. , Dicks , J. , Roberts , I. , Wesselink , J. , Iglesia , B. , Robert , V. , Boekhout , T. , and Rayward-Smith , V. 2003. Algorithms for identification key generation and optimization with application to yeast identification . In Proceedings of EvoWorkshops . Lecture Notes in Computer Science , vol. 2611 . Springer , Berlin , 107--118. Reynolds, A., Dicks, J., Roberts, I., Wesselink, J., Iglesia, B., Robert, V., Boekhout, T., and Rayward-Smith, V. 2003. Algorithms for identification key generation and optimization with application to yeast identification. In Proceedings of EvoWorkshops. Lecture Notes in Computer Science, vol. 2611. Springer, Berlin, 107--118."},{"key":"e_1_2_1_23_1","first-page":"114","article-title":"Uber die kongruenz xm+ym\u2261 zm (mod p)","volume":"25","author":"Schur I.","year":"1916","unstructured":"Schur , I. 1916 . Uber die kongruenz xm+ym\u2261 zm (mod p) . Jber. Deustsch. Math. Verein 25 , 114 -- 117 . Schur, I. 1916. Uber die kongruenz xm+ym\u2261 zm (mod p). Jber. Deustsch. Math. Verein 25, 114--117.","journal-title":"Jber. Deustsch. Math. Verein"},{"key":"e_1_2_1_24_1","volume-title":"Introduction to Graph Theory","author":"West D.","unstructured":"West , D. 2001. Introduction to Graph Theory . Prentice Hall . West, D. 2001. Introduction to Graph Theory. Prentice Hall."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-1605(97)00084-6"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921659.1921661","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1921659.1921661","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:08Z","timestamp":1750278368000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921659.1921661"}},"subtitle":["Approximation algorithms and hardness results"],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1145\/1921659.1921661"],"URL":"https:\/\/doi.org\/10.1145\/1921659.1921661","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3]]},"assertion":[{"value":"2008-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}