{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T11:21:43Z","timestamp":1763810503767,"version":"3.37.3"},"reference-count":63,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"2","license":[{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"am","delay-in-days":0,"URL":"http:\/\/www.ieee.org\/publications_standards\/publications\/rights\/ieeecopyrightform.pdf"},{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.ieee.org\/publications_standards\/publications\/rights\/ieeecopyrightform.pdf"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1563098","Graduate Research Fellowship"],"award-info":[{"award-number":["CCF-1563098","Graduate Research Fellowship"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Center for Science of Information","award":["CCF-0939370"],"award-info":[{"award-number":["CCF-0939370"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE J. Sel. Areas Inf. Theory"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1109\/jsait.2021.3076447","type":"journal-article","created":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T20:50:47Z","timestamp":1620075047000},"page":"599-610","source":"Crossref","is-referenced-by-count":4,"title":["Bandit-Based Monte Carlo Optimization for Nearest Neighbors"],"prefix":"10.1109","volume":"2","author":[{"given":"Vivek","family":"Bagaria","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8924-0243","authenticated-orcid":false,"given":"Tavor Z.","family":"Baharav","sequence":"additional","affiliation":[]},{"given":"Govinda M.","family":"Kamath","sequence":"additional","affiliation":[]},{"given":"David N.","family":"Tse","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"journal-title":"The simulator Understanding adaptive sampling in the moderate-confidence regime","year":"2017","author":"simchowitz","key":"ref39"},{"key":"ref38","first-page":"655","article-title":"PAC subset selection in stochastic multi-armed bandits","volume":"12","author":"kalyanakrishnan","year":"2012","journal-title":"Proc ICML"},{"journal-title":"Query complexity of k-NN based mode estimation","year":"2020","author":"singhal","key":"ref33"},{"key":"ref32","first-page":"7513","article-title":"Adaptive learning of rank-one models for efficient pairwise sequence alignment","author":"kamath","year":"2020","journal-title":"Proc Adv Neural Inf Process Syst"},{"journal-title":"Bandit-pam Almost linear time k-medoids clustering via multi-armed bandits","year":"2020","author":"tiwari","key":"ref31"},{"journal-title":"Adaptive Monte Carlo multiple testing via multi-armed bandits","year":"2019","author":"zhang","key":"ref30"},{"journal-title":"Nearly instance optimal sample complexity bounds for top-k arm selection","year":"2017","author":"chen","key":"ref37"},{"key":"ref36","first-page":"1","article-title":"On the complexity of best-arm identification in multi-armed bandit models","volume":"17","author":"kaufmann","year":"2016","journal-title":"J Mach Learn Res"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2014.6814096"},{"key":"ref34","first-page":"41","article-title":"Best arm identification in multi-armed bandits","author":"audibert","year":"2010","journal-title":"Proc 23th Conf Learn Theory"},{"key":"ref60","first-page":"6609","article-title":"Efficient pure exploration in adaptive round model","volume":"32","author":"jin","year":"2019","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1090\/S0094-9000-2013-00887-4"},{"journal-title":"Linear bandit algorithms with sublinear time complexity","year":"2021","author":"yang","key":"ref61"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-015-0816-y"},{"journal-title":"Learning nearest neighbor graphs from noisy distance samples","year":"2019","author":"mason","key":"ref28"},{"journal-title":"Adaptive estimation for approximate k-nearest-neighbor computations","year":"2019","author":"lejeune","key":"ref27"},{"journal-title":"Nearest neighbor search under uncertainty","year":"2021","author":"mason","key":"ref29"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/11871842_29"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1040.0145"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"article-title":"High-dimensional similarity search and sketching: Algorithms and hardness","year":"2017","author":"razenshteyn","key":"ref21"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2015.508"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939753"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089026"},{"journal-title":"1 3 Million Brain Cells From E18 Mice","year":"2017","key":"ref25"},{"journal-title":"Use of Variance Estimation in the Multi-Armed Bandit Problem","year":"2006","author":"audibert","key":"ref50"},{"key":"ref51","first-page":"5638","article-title":"Normal bandits of unknown means and variances","volume":"18","author":"cowan","year":"2017","journal-title":"J Mach Learn Res"},{"key":"ref59","first-page":"139","article-title":"Top arm identification in multi-armed bandits with batch arm pulls","author":"jun","year":"2016","journal-title":"Proc Artif Intell Stat"},{"key":"ref58","first-page":"2825","article-title":"Scikit-learn: Machine learning in Python","volume":"12","author":"pedregosa","year":"2011","journal-title":"J Mach Learn Res"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1137\/060673096"},{"journal-title":"Randomized algorithms for matrices and data","year":"2011","author":"mahoney","key":"ref55"},{"journal-title":"On Finding the Largest Mean among Many","year":"2013","author":"jamieson","key":"ref54"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1145\/502109.502111"},{"key":"ref52","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/3-540-45435-7_18","article-title":"Pac bounds for multi-armed bandit and Markov decision processes","author":"even-dar","year":"2002","journal-title":"Proc Int Conf Comput Learn Theory"},{"journal-title":"Nearest Neighbour Benchmarks","year":"2014","author":"bern","key":"ref10"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/4908.001.0001"},{"key":"ref40","first-page":"423","article-title":"lil’ UCB: An optimal exploration algorithm for multi-armed bandits","author":"jamieson","year":"2014","journal-title":"Proc Conf Learn Theory"},{"journal-title":"The Elements of Statistical Learning Data Mining Inference and Prediction","year":"2009","author":"hastie","key":"ref12"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1126\/science.290.5500.2319"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1126\/science.290.5500.2323"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1031596100"},{"journal-title":"Randomized near neighbor graphs giant components and applications in data science","year":"2017","author":"linderman","key":"ref16"},{"journal-title":"Billion-scale similarity search with GPUs","year":"2017","author":"johnson","key":"ref17"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"journal-title":"Five balltree construction algorithms","year":"1989","author":"omohundro","key":"ref19"},{"journal-title":"Hyperband A Novel Bandit-Based Approach to Hyperparameter Optimization","year":"2016","author":"li","key":"ref4"},{"key":"ref3","first-page":"240","article-title":"Non-stochastic best arm identification and hyperparameter optimization","author":"jamieson","year":"2016","journal-title":"Proc Artif Intell Stat"},{"key":"ref6","first-page":"3655","article-title":"Ultra fast medoid identification via correlated sequential halving","author":"baharav","year":"2019","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref5","first-page":"500","article-title":"Medoids in almost-linear time via multi-armed bandits","volume":"84","author":"bagaria","year":"2018","journal-title":"Proc Int Conf Artif Intell Statist"},{"journal-title":"Kgraph","year":"2014","author":"dong","key":"ref8"},{"key":"ref7","first-page":"1225","article-title":"Practical and optimal LSH for angular distance","author":"andoni","year":"2015","journal-title":"Proc Adv Neural Inf Process Syst"},{"journal-title":"Ordinal optimization — empirical large deviations rate estimators and stochastic multi-armed bandits","year":"2015","author":"glynn","key":"ref49"},{"journal-title":"Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data","year":"2018","author":"iwasaki","key":"ref9"},{"key":"ref46","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1016\/S0927-0507(06)13017-0","article-title":"Selecting the best system","volume":"13","author":"kim","year":"2006","journal-title":"Handbooks in Operations Research and Management Science"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1753"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0281"},{"key":"ref47","first-page":"162","article-title":"Recent advances in ranking and selection","author":"kim","year":"2007","journal-title":"Winter Simulation Conference Proceedings"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/BF01797280"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"ref44","first-page":"577","article-title":"A large deviations perspective on ordinal optimization","volume":"1","author":"glynn","year":"2004","journal-title":"Winter Simulation Conference Proceedings"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008349927281"}],"container-title":["IEEE Journal on Selected Areas in Information Theory"],"original-title":[],"link":[{"URL":"https:\/\/ieeexplore.ieee.org\/ielam\/8700143\/9459757\/9420755-aam.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/8700143\/9459757\/09420755.pdf?arnumber=9420755","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,8]],"date-time":"2021-11-08T22:37:02Z","timestamp":1636411022000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9420755\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6]]},"references-count":63,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.1109\/jsait.2021.3076447","relation":{},"ISSN":["2641-8770"],"issn-type":[{"type":"electronic","value":"2641-8770"}],"subject":[],"published":{"date-parts":[[2021,6]]}}}