{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T02:46:37Z","timestamp":1777689997752,"version":"3.51.4"},"reference-count":46,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"6","license":[{"start":{"date-parts":[[2018,6,1]],"date-time":"2018-06-01T00:00:00Z","timestamp":1527811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["755\/15"],"award-info":[{"award-number":["755\/15"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1141\/12"],"award-info":[{"award-number":["1141\/12"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["755\/15"],"award-info":[{"award-number":["755\/15"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Yahoo Faculty Award"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1109\/tit.2018.2822267","type":"journal-article","created":{"date-parts":[[2018,4,2]],"date-time":"2018-04-02T18:05:15Z","timestamp":1522692315000},"page":"4120-4128","source":"Crossref","is-referenced-by-count":12,"title":["Near-Optimal Sample Compression for Nearest Neighbors"],"prefix":"10.1109","volume":"64","author":[{"given":"Lee-Ad","family":"Gottlieb","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8038-8671","authenticated-orcid":false,"given":"Aryeh","family":"Kontorovich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pinhas","family":"Nisnevitch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055464"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-009-5137-3"},{"key":"ref32","first-page":"791","article-title":"Navigating nets: Simple algorithms for proximity search","author":"krauthgamer","year":"2004","journal-title":"Proc 15th Annu ACM-SIAM Symp Discrete Algorithms"},{"key":"ref31","article-title":"A Bayes consistent 1-NN classifier","author":"kontorovich","year":"2015","journal-title":"Proc 14th Int Conf Artif Intell Statist (AISTATS)"},{"key":"ref30","first-page":"892","article-title":"Maximum margin multiclass nearest neighbors","author":"kontorovich","year":"2014","journal-title":"Proc ICML"},{"key":"ref37","author":"mohri","year":"2012","journal-title":"Foundations of Machine Learning"},{"key":"ref36","first-page":"723","article-title":"The set covering machine","volume":"3","author":"marchand","year":"2002","journal-title":"J Mach Learn Res"},{"key":"ref35","article-title":"Relating data compression and learnability","volume":"1986","author":"littlestone","year":"0"},{"key":"ref34","first-page":"889","article-title":"Learnability and the doubling dimension","author":"li","year":"2006","journal-title":"Neural Information Processing Systems"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1967.1053964"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1024691080"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176325633"},{"key":"ref12","article-title":"A probabilistic theory of pattern recognition","volume":"31","author":"devroye","year":"1996","journal-title":"Applications of Mathematics"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.11.007"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.2307\/1403797"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1972.1054809"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.10.040"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2339840"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2713820"},{"key":"ref19","first-page":"370","article-title":"Near-optimal sample compression for nearest neighbors","author":"gottlieb","year":"2014","journal-title":"Proc Adv 27th Annu Conf Neural Inf Process Syst (NIPS)"},{"key":"ref28","first-page":"856","article-title":"Active nearest-neighbor learning in metric spaces","author":"kontorovich","year":"2016","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref4","first-page":"43","author":"bartlett","year":"1999","journal-title":"Generalization performance of support vector machines and other pattern classifiers"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2002.804315"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366815"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.01.003"},{"key":"ref29","first-page":"1572","article-title":"Nearest-neighbor sample compression: Efficiency, consistency, infinite dimensions","author":"kontorovich","year":"2017","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/177424.177609"},{"key":"ref7","first-page":"3437","article-title":"Rates of convergence for nearest neighbor classification","author":"chaudhuri","year":"2014","journal-title":"Proc 27th Annu Adv Neural Inf Process Syst"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102355"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132599"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263927"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1134\/S1054661810040097"},{"key":"ref20","first-page":"1","article-title":"Nearly optimal classification for semimetrics","volume":"18","author":"gottlieb","year":"2017","journal-title":"J Mach Learn Res"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007626913721"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-005-0462-7"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/120874242"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-44400-8_29"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1145\/109648.109673"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(88)90002-1"},{"key":"ref43","first-page":"669","article-title":"Distance-based classification with Lipschitz functions","volume":"5","author":"von luxburg","year":"2004","journal-title":"J Mach Learn Res"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054155"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/8361085\/08329535.pdf?arnumber=8329535","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,26]],"date-time":"2022-01-26T04:55:55Z","timestamp":1643172955000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/8329535\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":46,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.1109\/tit.2018.2822267","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}