{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T12:39:55Z","timestamp":1765888795834,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:00:00Z","timestamp":1641513600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:00:00Z","timestamp":1641513600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1948133"],"award-info":[{"award-number":["1948133"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s10994-021-06124-1","type":"journal-article","created":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:03:47Z","timestamp":1641513827000},"page":"2297-2322","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast spectral analysis for approximate nearest neighbor search"],"prefix":"10.1007","volume":"111","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2065-1102","authenticated-orcid":false,"given":"Jing","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Shen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,7]]},"reference":[{"key":"6124_CR1","doi-asserted-by":"crossref","unstructured":"Abdullah, A., Andoni, A., Kannan, R. & Krauthgamer, R. (2014). Spectral approaches to nearest neighbor search. In Annual symposium on foundations of computer science (pp. 581\u2013590).","DOI":"10.1109\/FOCS.2014.68"},{"key":"6124_CR2","unstructured":"Alaoui, A., & Mahoney, M. W. (2015). Fast randomized kernel ridge regression with statistical guarantees. In Advances in neural information processing systems (pp. 775\u2013783)."},{"issue":"1","key":"6124_CR3","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1145\/1327452.1327494","volume":"51","author":"A Andoni","year":"2008","unstructured":"Andoni, A., & Indyk, P. (2008). Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Communications of the ACM, 51(1), 117\u2013122.","journal-title":"Communications of the ACM"},{"key":"6124_CR4","doi-asserted-by":"crossref","unstructured":"Andoni, A., Indyk, P., Nguyen, H.L. & Razenshteyn, I. (2014). Beyond locality-sensitive hashing. In Proceedings of the 2014 ACM-SIAM symposium on discrete algorithms, SIAM (pp. 1018\u20131028).","DOI":"10.1137\/1.9781611973402.76"},{"key":"6124_CR5","doi-asserted-by":"crossref","unstructured":"Andoni, A., Naor, A., Nikolov, A., Razenshteyn, I., & Waingarten, E. (2018). Data-dependent hashing via nonlinear spectral gaps. In Annual ACM SIGACT symposium on theory of computing. ACM (pp. 787\u2013800).","DOI":"10.1145\/3188745.3188846"},{"key":"6124_CR6","doi-asserted-by":"crossref","unstructured":"Andoni, A,. Nikolov, A., Razenshteyn, I., & Waingarten, E. (2021). Approximate nearest neighbors beyond space partitions. In Proceedings of the 2021 ACM-SIAM symposium on discrete algorithms (pp. 1171\u20131190) SIAM.","DOI":"10.1137\/1.9781611976465.72"},{"key":"6124_CR7","unstructured":"Arya, S., & Mount, D.M. (1993). Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the fourth annual ACM\/SIGACT-SIAM symposium on discrete algorithms (pp. 271\u2013280)."},{"key":"6124_CR8","doi-asserted-by":"crossref","unstructured":"Arya, S., Mount, D. M., & Narayan, O. (1995). Accounting for boundary effects in nearest neighbor searching. In Proceedings of the eleventh annual symposium on computational geometry, Vancouver (pp. 336\u2013344).","DOI":"10.1145\/220279.220315"},{"issue":"9","key":"6124_CR9","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM 18(9), 509\u2013517.","journal-title":"Commun ACM"},{"key":"6124_CR10","doi-asserted-by":"crossref","unstructured":"\u00c7akir, F., He, K., Sclaroff, S. (2018). Hashing with binary matrix pursuit. In European conference on computer vision (pp. 344\u2013361).","DOI":"10.1007\/978-3-030-01228-1_21"},{"key":"6124_CR11","unstructured":"Cohen, M.B., Musco, C., & Pachocki, J.W. (2016). Online row sampling. In Approximation, randomization, and combinatorial optimization. algorithms and techniques, APPROX\/RANDOM (pp 7:1\u20137:18)."},{"issue":"2","key":"6124_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"DP Dobkin","year":"1976","unstructured":"Dobkin, D. P., & Lipton, R. J. (1976). Multidimensional searching problems. SIAM Journal on Computing 5(2), 181\u2013186.","journal-title":"SIAM J Comput"},{"key":"6124_CR13","unstructured":"Dolan, W.B., & Brockett, C. (2005). Automatically constructing a corpus of sentential paraphrases. In Proceedings of the third international workshop on paraphrasing."},{"key":"6124_CR14","doi-asserted-by":"crossref","unstructured":"Erin\u00a0Liong, V., Lu, J., Wang, G., Moulin, P., Zhou, J. (2015). Deep hashing for compact binary codes learning. In IEEE conference on computer vision and pattern recognition (pp. 2475\u20132483).","DOI":"10.1109\/CVPR.2015.7298862"},{"key":"6124_CR15","unstructured":"Gersho, A., & Gray, R. M. (2012). Vector quantization and signal compression, vol 159. Springer."},{"key":"6124_CR16","first-page":"518","volume":"99","author":"A Gionis","year":"1999","unstructured":"Gionis, A., Indyk, P., & Motwani, R. (1999). Similarity search in high dimensions via hashing. International Conference on Very Large Data Bases, 99, 518\u2013529.","journal-title":"International Conference on Very Large Data Bases"},{"key":"6124_CR17","unstructured":"Gittens, A. (2011). The spectral norm error of the naive nystrom extension. arXiv preprint arXiv:11105305"},{"issue":"1","key":"6124_CR18","first-page":"3977","volume":"17","author":"A Gittens","year":"2016","unstructured":"Gittens, A., & Mahoney, M. W. (2016). Revisiting the nystr\u00f6m method for improved large-scale machine learning. The Journal of Machine Learning Research, 17(1), 3977\u20134041.","journal-title":"The Journal of Machine Learning Research"},{"key":"6124_CR19","doi-asserted-by":"crossref","unstructured":"Gong, Y., & Lazebnik, S. (2011). Iterative quantization: A procrustean approach to learning binary codes. In IEEE conference on computer vision and pattern recognition (pp. 817\u2013824).","DOI":"10.1109\/CVPR.2011.5995432"},{"key":"6124_CR20","doi-asserted-by":"crossref","unstructured":"Gong, Y., Kumar, S., Rowley, H. A., & Lazebnik, S. (2013). Learning binary codes for high-dimensional data using bilinear projections. In IEEE conference on computer vision and pattern recognition (pp. 484\u2013491).","DOI":"10.1109\/CVPR.2013.69"},{"key":"6124_CR21","unstructured":"Han, X., Leung, T., Jia, Y., Sukthankar, R., & Berg, A. C. (2015). Matchnet: Unifying feature and metric learning for patch-based matching. In The 28th IEEE conference on computer vision and pattern recognition (pp. 3279\u20133286)."},{"key":"6124_CR22","doi-asserted-by":"crossref","unstructured":"Indyk, P., & Motwani, R. (1998). Approximate nearest neighbors: Towards removing the curse of dimensionality. In Annual ACM symposium on theory of computing, ACM (pp. 604\u2013613).","DOI":"10.1145\/276698.276876"},{"issue":"1","key":"6124_CR23","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TPAMI.2010.57","volume":"33","author":"H Jegou","year":"2011","unstructured":"Jegou, H., Douze, M., & Schmid, C. (2011). Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1), 117\u2013128.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"6124_CR24","unstructured":"Jiang, Q., &Li, W. (2015). Scalable graph hashing with feature transformation. In International joint conference on artificial intelligence (pp. 2248\u20132254)."},{"key":"6124_CR25","unstructured":"Knuth, D. E. (1973). Sorting and searching. The art of computer programming 3:Ch\u20136."},{"key":"6124_CR26","unstructured":"Kong, W., & Li, W. J. (2012). Isotropic hashing. In Annual conference on neural information processing systems (pp. 1646\u20131654)."},{"key":"6124_CR27","unstructured":"Kulis, B., & Darrell, T. (2009). Learning to hash with binary reconstructive embeddings. In Annual conference on neural information processing systems (pp. 1042\u20131050)."},{"key":"6124_CR28","doi-asserted-by":"crossref","unstructured":"Liu, H., Wang, R., Shan, S., & Chen, X. (2016). Deep supervised hashing for fast image retrieval. In IEEE conference on computer vision and pattern recognition (pp. 2064\u20132072).","DOI":"10.1109\/CVPR.2016.227"},{"key":"6124_CR29","unstructured":"Liu, W., Wang, J., Kumar, S., & Chang, S. F. (2011). Hashing with graphs. In International conference on machine learning (pp. 1\u20138)."},{"key":"6124_CR30","unstructured":"Liu, W., Mu, C., Kumar, S., & Chang, S. (2014). Discrete graph hashing. In Annual conference on neural information processing systems (pp. 3419\u20133427)."},{"issue":"11","key":"6124_CR31","doi-asserted-by":"publisher","first-page":"1551","DOI":"10.1109\/PROC.1985.13340","volume":"73","author":"J Makhoul","year":"1985","unstructured":"Makhoul, J., Roucos, S., & Gish, H. (1985). Vector quantization in speech coding. Proceedings of the IEEE, 73(11), 1551\u20131588.","journal-title":"Proceedings of the IEEE"},{"key":"6124_CR32","unstructured":"Mitzenmacher, M., & Upfal, E. (2017). Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge University Press"},{"key":"6124_CR33","unstructured":"Musco, C., & Musco, C. (2015). Randomized block krylov methods for stronger and faster approximate singular value decomposition. In Annual conference on neural information processing systems (pp. 1396\u20131404)."},{"key":"6124_CR34","unstructured":"Musco, C., & Musco, C. (2017). Recursive sampling for the nystrom method. In Advances in neural information processing systems (pp. 3836\u20133848)."},{"key":"6124_CR100","doi-asserted-by":"crossref","unstructured":"Pennington J., Socher R., & Manning C. D. (2014). GloVe: Global Vectors for Word Representation. In Proceedings of the 2014\nConference on Empirical Methods in Natural Language Processing (pp. 1532\u20131543).","DOI":"10.3115\/v1\/D14-1162"},{"key":"6124_CR35","doi-asserted-by":"crossref","unstructured":"Rajpurkar, P., Zhang, J., Lopyrev, K., & Liang, P. (2016). Squad: 100, 000+ questions for machine comprehension of text. In J. Su, X. Carreras, K. Duh (Eds.) Proceedings of the 2016 conference on empirical methods in natural language processing (pp. 2383\u20132392).","DOI":"10.18653\/v1\/D16-1264"},{"key":"6124_CR36","doi-asserted-by":"crossref","unstructured":"Reimers, N., & Gurevych, I. (2019). Sentence-bert: Sentence embeddings using siamese bert-networks. In: K. Inui, J. Jiang, V. Ng, X. Wan (Eds.) Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing, (pp. 3980\u20133990).","DOI":"10.18653\/v1\/D19-1410"},{"key":"6124_CR37","unstructured":"Rudi, A., Camoriano, R., & Rosasco, L. (2015). Less is more: Nystr\u00f6m computational regularization. In Annual conference on neural information processing systems (pp. 1648\u20131656)."},{"key":"6124_CR38","doi-asserted-by":"crossref","unstructured":"Samet, H. (1990). The design and analysis of spatial data structures (Vol. 85). Addison-Wesley.","DOI":"10.1007\/3-540-52208-5_28"},{"key":"6124_CR39","unstructured":"Samet, H. (2006). Foundations of multidimensional and metric data structures"},{"key":"6124_CR40","unstructured":"Sellis, T. K., Roussopoulos, N., & Faloutsos, C. (1997). Multidimensional access methods: Trees have grown everywhere. In Proceedings of 23rd international conference on very large data bases (pp. 13\u201314)."},{"key":"6124_CR41","doi-asserted-by":"crossref","unstructured":"Shen, F., Shen, C., Liu, W., & Shen, H. T. (2015). Supervised discrete hashing. In IEEE conference on computer vision and pattern recognition (pp. 37\u201345).","DOI":"10.1109\/CVPR.2015.7298598"},{"key":"6124_CR42","unstructured":"Socher, R., Perelygin, A., Wu, J., Chuang, J., Manning, C.D., Ng, A.Y., & Potts, C. (2013). Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language processing (pp. 1631\u20131642)."},{"key":"6124_CR43","doi-asserted-by":"crossref","unstructured":"Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., & Bowman, S. R. (2019). GLUE: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 7th international conference on learning representations.","DOI":"10.18653\/v1\/W18-5446"},{"key":"6124_CR44","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1162\/tacl_a_00290","volume":"7","author":"A Warstadt","year":"2019","unstructured":"Warstadt, A., Singh, A., & Bowman, S. R. (2019). Neural network acceptability judgments. Trans Assoc Comput Linguistics, 7, 625\u2013641.","journal-title":"Trans Assoc Comput Linguistics"},{"key":"6124_CR45","unstructured":"Weiss, Y., Torralba, A., & Fergus, R. (2009). Spectral hashing. In Annual conference on neural information processing systems (pp. 1753\u20131760)."},{"key":"6124_CR46","doi-asserted-by":"crossref","unstructured":"Weiss, Y., Fergus, R., & Torralba, A. (2012). Multidimensional spectral hashing. In European conference on computer vision (pp. 340\u2013353).","DOI":"10.1007\/978-3-642-33715-4_25"},{"issue":"1\u20132","key":"6124_CR47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000060","volume":"10","author":"DP Woodruff","year":"2014","unstructured":"Woodruff, D. P., et al. (2014). Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1\u20132), 1\u2013157.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"6124_CR48","unstructured":"Xia, Y., He, K., Kohli, P., & Sun, J. (2015). Sparse projections for high-dimensional binary codes. In IEEE conference on computer vision and pattern recognition (pp. 3332\u20133339)."},{"key":"6124_CR49","unstructured":"Yu, F. X., Kumar, S., Gong, Y., & Chang, S. (2014). Circulant binary embedding. In Proceedings of the 31th international conference on machine learning (pp. 946\u2013954)."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06124-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-06124-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06124-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T01:06:15Z","timestamp":1673053575000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-06124-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,7]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["6124"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-06124-1","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2022,1,7]]},"assertion":[{"value":"4 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Jie Shen is supported by NSF-IIS-1948133 and the startup funding of Stevens Institute of Technology.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest\/competing interests"}},{"value":"All the data sets used in the paper are publicly available, and have been cited in the main text.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Availability of data and material"}},{"value":"All the codes will be release on the authors\u2019 personal websites after acceptance.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}},{"value":"All authors contributed to the work. The paper was written together by Jie Shen and Jing Wang. Jing Wang designed and ran the experiments and Jie Shen commented on ways for improvements.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Authors\u2019 contributions"}},{"value":"Not applicable.","order":7,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable.","order":8,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":9,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication."}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}