{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:40:08Z","timestamp":1750297208014,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T00:00:00Z","timestamp":1738886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"crossref","award":["CCF-2153723"],"award-info":[{"award-number":["CCF-2153723"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"<jats:p>\n            Given a weighted, ordered query set\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(Q\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and a partition of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(Q\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            into classes, we study the problem of computing a minimum-cost decision tree that, given any query\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(q\\in Q\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , uses equality tests and less-than tests to determine\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(q\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            's class. Such a tree can be faster and smaller than a conventional search tree and smaller than a lookup table (both of which must identify\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(q\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , not just its class). We give the first polynomial-time algorithm for the problem. The algorithm extends naturally to the setting where each query has multiple allowed classes.\n          <\/jats:p>","DOI":"10.1145\/3709361","type":"journal-article","created":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T15:34:11Z","timestamp":1734968051000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Classification via Two-Way Comparisons"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8673-2709","authenticated-orcid":false,"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[{"name":"University of California Riverside, Riverside, CA, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8144-3345","authenticated-orcid":false,"given":"Neal E.","family":"Young","sequence":"additional","affiliation":[{"name":"University of California Riverside, Riverside, CA, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2","DOI":"10.1016\/S0196-6774(02)00203-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_2","DOI":"10.1007\/s10994-017-5633-9"},{"doi-asserted-by":"publisher","key":"e_1_3_2_4_2","DOI":"10.1145\/320384.320407"},{"doi-asserted-by":"publisher","key":"e_1_3_2_5_2","DOI":"10.1145\/320385.320407"},{"doi-asserted-by":"publisher","key":"e_1_3_2_6_2","DOI":"10.1145\/3477910"},{"doi-asserted-by":"publisher","key":"e_1_3_2_7_2","DOI":"10.1007\/s00236-021-00411-z"},{"doi-asserted-by":"publisher","key":"e_1_3_2_8_2","DOI":"10.1007\/978-3-031-38906-1_19"},{"key":"e_1_3_2_9_2","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2022","unstructured":"Thomas H. Cormen, Charles Eric Leiserson, Ronald L. Rivest, and Clifford Stein. 2022. Introduction to Algorithms (fourth ed.). The MIT Press, Cambridge, MA."},{"doi-asserted-by":"publisher","key":"e_1_3_2_10_2","DOI":"10.1145\/3055399.3055422"},{"doi-asserted-by":"publisher","key":"e_1_3_2_11_2","DOI":"10.1002\/j.1538-7305.1959.tb01583.x"},{"doi-asserted-by":"publisher","key":"e_1_3_2_12_2","DOI":"10.1016\/0196-6774(86)90031-3"},{"doi-asserted-by":"publisher","key":"e_1_3_2_13_2","DOI":"10.1007\/BF00289143"},{"doi-asserted-by":"publisher","key":"e_1_3_2_14_2","DOI":"10.1016\/0196-6774(84)90041-5"},{"doi-asserted-by":"publisher","key":"e_1_3_2_15_2","DOI":"10.1016\/0020-0190(76)90095-8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_16_2","DOI":"10.1016\/j.tcs.2011.08.042"},{"doi-asserted-by":"publisher","key":"e_1_3_2_17_2","DOI":"10.1007\/BF00264289"},{"key":"e_1_3_2_18_2","volume-title":"The Art of Computer ProgrammingSorting and Searching","author":"Knuth D. E.","year":"1998","unstructured":"D. E. Knuth. 1998. The Art of Computer Programming, Vol. 3. Sorting and Searching (nd ed.). Addison-Wesley Publishing Company, Redwood City, CA."},{"doi-asserted-by":"publisher","key":"e_1_3_2_19_2","DOI":"10.1016\/0196-6774(84)90017-8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_20_2","DOI":"10.1145\/359642.359653"},{"doi-asserted-by":"publisher","key":"e_1_3_2_21_2","DOI":"10.1007\/BF01178732"},{"key":"e_1_3_2_22_2","volume-title":"Optimal Search Trees using Two-Way Key Comparisons","author":"Spuler D. A.","year":"1994","unstructured":"D. A. Spuler. 1994. Optimal Search Trees using Two-Way Key Comparisons. Ph.D. Dissertation. James Cook University."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709361","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709361","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709361","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:20Z","timestamp":1750295840000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,7]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3709361"],"URL":"https:\/\/doi.org\/10.1145\/3709361","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,2,7]]},"assertion":[{"value":"2023-05-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-08","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}