{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T17:12:09Z","timestamp":1769879529288,"version":"3.49.0"},"reference-count":87,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,10,26]],"date-time":"2020-10-26T00:00:00Z","timestamp":1603670400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,10,26]],"date-time":"2020-10-26T00:00:00Z","timestamp":1603670400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1447943"],"award-info":[{"award-number":["1447943"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["1759980"],"award-info":[{"award-number":["1759980"]}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["P41GM103484"],"award-info":[{"award-number":["P41GM103484"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R24GM127667"],"award-info":[{"award-number":["R24GM127667"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s00224-020-10009-6","type":"journal-article","created":{"date-parts":[[2020,10,26]],"date-time":"2020-10-26T08:03:05Z","timestamp":1603699385000},"page":"42-83","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Index-based, High-dimensional, Cosine Threshold Querying with Optimality Guarantees"],"prefix":"10.1007","volume":"65","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0602-149X","authenticated-orcid":false,"given":"Yuliang","family":"Li","sequence":"first","affiliation":[]},{"given":"Jianguo","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Pullman","sequence":"additional","affiliation":[]},{"given":"Nuno","family":"Bandeira","sequence":"additional","affiliation":[]},{"given":"Yannis","family":"Papakonstantinou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,10,26]]},"reference":[{"key":"10009_CR1","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1038\/nature19949","volume":"537","author":"R Aebersold","year":"2016","unstructured":"Aebersold, R., Mann, M.: Mass-spectrometric exploration of proteome structure and function. Nature 537, 347\u2013355 (2016)","journal-title":"Nature"},{"key":"10009_CR2","doi-asserted-by":"crossref","unstructured":"Ahle, T.D., Pagh, R., Razenshteyn, I., Silvestri, F.: On the complexity of inner product similarity join. In: PODS, pp 151\u2013164 (2016)","DOI":"10.1145\/2902251.2902285"},{"key":"10009_CR3","unstructured":"Akbarinia, R., Pacitti, E., Valduriez, P.: Best position algorithms for top-k queries. In: VLDB, pp 495\u2013506 (2007)"},{"key":"10009_CR4","doi-asserted-by":"crossref","unstructured":"Anastasiu, D.C., Karypis, G.: L2AP: Fast cosine similarity search with prefix L-2 norm bounds. In: ICDE, pp 784\u2013795 (2014)","DOI":"10.1109\/ICDE.2014.6816700"},{"key":"10009_CR5","doi-asserted-by":"crossref","unstructured":"Anastasiu, D.C., Karypis, G.: PL2AP: Fast parallel cosine similarity search. In: IA3, pp 8:1\u20138:8 (2015)","DOI":"10.1145\/2833179.2833182"},{"key":"10009_CR6","unstructured":"Andoni, A., Indyk, P., Laarhoven, T., Razenshteyn, I., Schmidt, L.: Practical and optimal lsh for angular distance. In: NIPS, pp 1225\u20131233 (2015)"},{"issue":"4","key":"10009_CR7","first-page":"288","volume":"9","author":"F Andr\u00e9","year":"2015","unstructured":"Andr\u00e9, F., Kermarrec, A.-M., Scouarnec, N.L.: Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. PVLDB 9(4), 288\u2013299 (2015)","journal-title":"PVLDB"},{"issue":"8","key":"10009_CR8","first-page":"906","volume":"11","author":"A Arora","year":"2018","unstructured":"Arora, A., Sinha, S., Kumar, P., Bhattacharya, A.: HD-Index: Pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces. PVLDB 11(8), 906\u2013919 (2018)","journal-title":"PVLDB"},{"key":"10009_CR9","unstructured":"Bast, H., Majumdar, D., Schenkel, R., Theobald, M., Weikum, G.: Io-top-k: Index-access optimized top-k query processing. In: VLDB, pp 475\u2013486 (2006)"},{"key":"10009_CR10","doi-asserted-by":"crossref","unstructured":"Bayardo, R.J., Ma, Y., Srikant, R.: Scaling up all pairs similarity search. In: WWW, pp 131\u2013140 (2007)","DOI":"10.1145\/1242572.1242591"},{"key":"10009_CR11","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: ICML, pp 97\u2013104 (2006)","DOI":"10.1145\/1143844.1143857"},{"issue":"3","key":"10009_CR12","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/502807.502809","volume":"33","author":"C B\u00f6hm","year":"2001","unstructured":"B\u00f6hm, C., Berchtold, S., Keim, D.A.: Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. CSUR 33(3), 322\u2013373 (2001)","journal-title":"CSUR"},{"key":"10009_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge University Press, Cambridge (2004)"},{"key":"10009_CR14","doi-asserted-by":"crossref","unstructured":"Broder, A.Z., Carmel, D., Herscovici, M., Soffer, A., Zien, J.: Efficient query evaluation using a two-level retrieval process. In: CIKM, pp 426\u2013434 (2003)","DOI":"10.1145\/956863.956944"},{"key":"10009_CR15","unstructured":"Bruno, N., Gravano, L., Marian, A.: Evaluating top-k queries over web-accessible databases. In: ICDE, pp 369\u2013380 (2002)"},{"key":"10009_CR16","doi-asserted-by":"crossref","unstructured":"Chakrabarti, K., Chaudhuri, S., Ganti, V.: Interval-based pruning for top-k processing over compressed lists. In: ICDE, pp 709\u2013720 (2011)","DOI":"10.1109\/ICDE.2011.5767855"},{"issue":"10","key":"10009_CR17","first-page":"1058","volume":"10","author":"L Chen","year":"2017","unstructured":"Chen, L., Gao, Y., Zheng, B., Jensen, C.S., Yang, H., Yang, K.: Pivot-based metric indexing. PVLDB 10(10), 1058\u20131069 (2017)","journal-title":"PVLDB"},{"issue":"8","key":"10009_CR18","doi-asserted-by":"publisher","first-page":"1843","DOI":"10.1021\/pr0602085","volume":"5","author":"R Craig","year":"2006","unstructured":"Craig, R., Cortens, J.C, Fenyo, D., Beavis, R.C.: Using annotated peptide mass spectrum libraries for protein identification. J. Proteome Res. 5 (8), 1843\u20131849 (2006)","journal-title":"J. Proteome Res."},{"key":"10009_CR19","doi-asserted-by":"crossref","unstructured":"Cui, B., Zhao, J., Cong, G.: ISIS: A new approach for efficient similarity search in sparse databases. In: DASFAA, pp 231\u2013245 (2010)","DOI":"10.1007\/978-3-642-12098-5_18"},{"key":"10009_CR20","doi-asserted-by":"crossref","unstructured":"Curtin, R.R., Gray, A.G., Ram, P.: Fast exact max-kernel search. In: SDM, pp 1\u20139 (2013)","DOI":"10.1137\/1.9781611972832.1"},{"issue":"3","key":"10009_CR21","doi-asserted-by":"publisher","first-page":"1686","DOI":"10.1021\/pr200874e","volume":"11","author":"S Dasari","year":"2012","unstructured":"Dasari, S., Chambers, M.C., Martinez, M.A., Carpenter, K.L., Ham, A.-J.L., Vega-Montoto, L.J., Tabb, D.L.: Pepitome: Evaluating improved spectral library search for identification complementarity and quality assessment. J. Proteome Res. 11(3), 1686\u201395 (2012)","journal-title":"J. Proteome Res."},{"key":"10009_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Introduction","author":"M De Berg","year":"2008","unstructured":"De Berg, M., Cheong, O., Van Kreveld, M., Overmars, M.: Computational Geometry: Introduction. Springer, Berlin (2008)"},{"key":"10009_CR23","doi-asserted-by":"crossref","unstructured":"Deshpande, P.M., Deepak, P., Kummamuru, K.: Efficient online top-k retrieval with arbitrary similarity measures. In: EDBT, pp 356\u2013367 (2008)","DOI":"10.1145\/1353343.1353388"},{"key":"10009_CR24","doi-asserted-by":"crossref","unstructured":"Ding, S., Suel, T.: Faster top-k document retrieval using block-max indexes. In: SIGIR, pp 993\u20131002 (2011)","DOI":"10.1145\/2009916.2010048"},{"key":"10009_CR25","unstructured":"Doc2Vec. https:\/\/radimrehurek.com\/gensim\/models\/doc2vec.html"},{"key":"10009_CR26","doi-asserted-by":"crossref","unstructured":"Dong, W., Moses, C., Li, K.: Efficient k-nearest neighbor graph construction for generic similarity measures. In: WWW, pp 577\u2013586 (2011)","DOI":"10.1145\/1963405.1963487"},{"issue":"5","key":"10009_CR27","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1093\/bioinformatics\/btl645","volume":"23","author":"D Dutta","year":"2007","unstructured":"Dutta, D., Chen, T.: Speeding up tandem mass spectrometry database search: metric embeddings and fast near neighbor search. Bioinformatics 23(5), 612\u2013618 (2007)","journal-title":"Bioinformatics"},{"key":"10009_CR28","unstructured":"Eghbali, S., Tahvildari, L.: Cosine similarity search with multi index hashing. arXiv:1610.00574"},{"issue":"11","key":"10009_CR29","doi-asserted-by":"publisher","first-page":"976","DOI":"10.1016\/1044-0305(94)80016-2","volume":"5","author":"JK Eng","year":"1994","unstructured":"Eng, J.K., McCormack, A.L., Yates, J.R.: An approach to correlate tandem mass spectral data of peptides with amino acid sequences in a protein database. J. Am. Soc. Mass Spectrom. 5(11), 976\u2013989 (1994)","journal-title":"J. Am. Soc. Mass Spectrom."},{"key":"10009_CR30","doi-asserted-by":"crossref","unstructured":"Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. In: PODS, pp 102\u2013113 (2001)","DOI":"10.1145\/375551.375567"},{"issue":"4","key":"10009_CR31","first-page":"614","volume":"66","author":"R Fagin","year":"2003","unstructured":"Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. JCSS 66(4), 614\u2013656 (2003)","journal-title":"JCSS"},{"key":"10009_CR32","doi-asserted-by":"crossref","unstructured":"Fraccaro, M., Paquet, U., Winther, O.: Indexable probabilistic matrix factorization for maximum inner product search. In: AAAI, pp 1554\u20131560 (2016)","DOI":"10.1609\/aaai.v30i1.10234"},{"key":"10009_CR33","unstructured":"Fu, C., Wang, C., Cai, D.: Fast approximate nearest neighbor search with navigating spreading-out graphs. arXiv:1707.00143 (2017)"},{"key":"10009_CR34","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"RL Graham","year":"1972","unstructured":"Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Info. Pro. Lett. 1, 132\u2013133 (1972)","journal-title":"Info. Pro. Lett."},{"key":"10009_CR35","unstructured":"G\u00fcntzer, U., Balke, W.-T., Kiebling, W.: Optimizing multi-feature queries for image databases. In: VLDB, pp 419\u2013428 (2000)"},{"issue":"1","key":"10009_CR36","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1109\/TPAMI.2014.2343223","volume":"37","author":"ME Houle","year":"2015","unstructured":"Houle, M.E., Nett, M.: Rank-based similarity search: Reducing the dimensional dependence. PAMI 37(1), 136\u2013150 (2015)","journal-title":"PAMI"},{"key":"10009_CR37","doi-asserted-by":"crossref","unstructured":"Hristidis, V., Koudas, N., Papakonstantinou, Y: PREFER: A system for the efficient execution of multi-parametric ranked queries. In: SIGMOD, pp 259\u2013270 (2001)","DOI":"10.1145\/376284.375690"},{"key":"10009_CR38","doi-asserted-by":"crossref","unstructured":"Hu, X., Tao, Y., Yi, K.: Output-optimal parallel algorithms for similarity joins. In: PODS, pp 79\u201390 (2017)","DOI":"10.1145\/3034786.3056110"},{"issue":"4","key":"10009_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1391729.1391730","volume":"40","author":"IF Ilyas","year":"2008","unstructured":"Ilyas, I.F., Beskales, G., Soliman, M.A.: A survey of top-k query processing techniques in relational database systems. CSUR 40(4), 1\u201358 (2008)","journal-title":"CSUR"},{"key":"10009_CR40","unstructured":"Img2Vec. https:\/\/github.com\/christiansafka\/img2vec"},{"key":"10009_CR41","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: ICDT, pp 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"issue":"1","key":"10009_CR42","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.: Product quantization for nearest neighbor search. PAMI 33(1), 117\u2013128 (2011)","journal-title":"PAMI"},{"key":"10009_CR43","doi-asserted-by":"crossref","unstructured":"Jin, W., Patel, J.M.: Efficient and generic evaluation of ranked queries. In: SIGMOD, pp 601\u2013612 (2011)","DOI":"10.1145\/1989323.1989386"},{"issue":"2","key":"10009_CR44","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF02764938","volume":"54","author":"WB Johnson","year":"1986","unstructured":"Johnson, W.B., Lindenstrauss, J., Schechtman, G.: Extensions of lipschitz maps into banach spaces. Israel J. Math. 54(2), 129\u2013138 (1986)","journal-title":"Israel J. Math."},{"key":"10009_CR45","doi-asserted-by":"crossref","unstructured":"Keivani, O., Sinha, K., Ram, P.: Improved maximum inner product search with better theoretical guarantees. In: IJCNN, pp 2927\u20132934 (2017)","DOI":"10.1109\/IJCNN.2017.7966218"},{"key":"10009_CR46","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1038\/nmeth.4256","volume":"14","author":"AT Kong","year":"2017","unstructured":"Kong, A.T., Leprevost, F.V., Avtonomov, D.M., Mellacheruvu, D., Nesvizhskii, A.I.: Msfragger: Ultrafast and comprehensive peptide identification in mass spectrometry-based proteomics. Nat. Methods 14, 513\u2013520 (2017)","journal-title":"Nat. Methods"},{"key":"10009_CR47","doi-asserted-by":"crossref","unstructured":"Kuhn, H.W., Tucker, A.W.: Nonlinear programming. In: Traces and Emergence of Nonlinear Programming, pp 247\u2013258 (2014)","DOI":"10.1007\/978-3-0348-0439-4_11"},{"key":"10009_CR48","doi-asserted-by":"crossref","unstructured":"Kulis, B., Grauman, K.: Kernelized locality-sensitive hashing for scalable image search. In: ICCV, pp 2130\u20132137 (2009)","DOI":"10.1109\/ICCV.2009.5459466"},{"key":"10009_CR49","doi-asserted-by":"crossref","unstructured":"Lam, H., Deutsch, E.W., Eddes, J.S., Eng, J.K., King, N., Stein, S.E., Aebersold, R.: Development and validation of a spectral library searching method for peptide identification from ms\/ms. Proteomics 7(5) (2007)","DOI":"10.1002\/pmic.200600625"},{"key":"10009_CR50","doi-asserted-by":"crossref","unstructured":"Learned-Miller, E., Huang, G.B., RoyChowdhury, A., Li, H., Hua, G.: Labeled faces in the wild: A survey. In: Advances in face detection and facial image analysis, pp 189\u2013248. Springer (2016)","DOI":"10.1007\/978-3-319-25958-1_8"},{"key":"10009_CR51","doi-asserted-by":"crossref","unstructured":"Lee, J., Cho, H., Hwang, S.-W.: Efficient dual-resolution layer indexing for top-k queries. In: ICDE, pp 1084\u20131095 (2012)","DOI":"10.1109\/ICDE.2012.73"},{"key":"10009_CR52","unstructured":"Lempitsky, V.: The inverted multi-index. In: CVPR, pp 3069\u20133076 (2012)"},{"issue":"4","key":"10009_CR53","first-page":"792","volume":"14","author":"C Li","year":"2002","unstructured":"Li, C., Chang, E., Garcia-Molina, H., Wiederhold, G.: Clustering for approximate similarity search in high-dimensional spaces. TKDE 14(4), 792\u2013808 (2002)","journal-title":"TKDE"},{"key":"10009_CR54","doi-asserted-by":"crossref","unstructured":"Li, H, Chan, T.N., Yiu, M.L., Mamoulis, N.: Fexipro: Fast and exact inner product retrieval in recommender systems. In: SIGMOD, pp 835\u2013850 (2017)","DOI":"10.1145\/3035918.3064009"},{"key":"10009_CR55","doi-asserted-by":"crossref","unstructured":"Li, W., Deng, L., Li, Y., Li, C.: Zigzag: Supporting similarity queries on vector space models. In: SIGMOD (2018)","DOI":"10.1145\/3183713.3196936"},{"key":"10009_CR56","unstructured":"Li, Y., Wang, J., Pullman, B., Bandeira, N., Papakonstantinou, Y.: Index-Based High-Dimensional, Cosine Threshold Querying with Optimality Guarantees. In: ICDT, vol. 127, pp 11:1\u201311:20 (2019)"},{"issue":"10","key":"10009_CR57","first-page":"1447","volume":"21","author":"X Lian","year":"2009","unstructured":"Lian, X., Chen, L.: General cost models for evaluating dimensionality reduction in high-dimensional spaces. TKDE 21(10), 1447\u20131460 (2009)","journal-title":"TKDE"},{"issue":"6","key":"10009_CR58","first-page":"2351","volume":"43","author":"Y-C Liaw","year":"2010","unstructured":"Liaw, Y.-C., Leou, M.-L., Wu, C.-M.: Fast exact k nearest neighbors search using an orthogonal search tree. PR 43(6), 2351\u20132358 (2010)","journal-title":"PR"},{"key":"10009_CR59","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809071","volume-title":"Introduction to Information Retrieval","author":"CD Manning","year":"2008","unstructured":"Manning, C.D., Raghavan, P., Schtze, H.: Introduction to Information Retrieval. Cambridge University Press, Cambridge (2008)"},{"issue":"11","key":"10009_CR60","doi-asserted-by":"publisher","first-page":"2227","DOI":"10.1109\/TPAMI.2014.2321376","volume":"36","author":"M Muja","year":"2014","unstructured":"Muja, M., Lowe, D.G.: Scalable nearest neighbor algorithms for high dimensional data. PAMI 36(11), 2227\u20132240 (2014)","journal-title":"PAMI"},{"key":"10009_CR61","unstructured":"Mussmann, S., Ermon, S.: Learning and inference via maximum inner product search. In: ICML, pp 2587\u20132596 (2016)"},{"key":"10009_CR62","doi-asserted-by":"crossref","unstructured":"Qin, J., Wang, Y., Xiao, C., Wang, W., Lin, X., Ishikawa, Y.: GPH: Similarity search in hamming space. In: ICDE (2018)","DOI":"10.1109\/ICDE.2018.00013"},{"key":"10009_CR63","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139058452","volume-title":"Mining of Massive Datasets","author":"A Rajaraman","year":"2011","unstructured":"Rajaraman, A., Ullman, J.D.: Mining of Massive Datasets. Cambridge University Press, Cambridge (2011)"},{"key":"10009_CR64","doi-asserted-by":"crossref","unstructured":"Ram, P., Gray, A.G.: Maximum inner-product search using cone trees. In: SIGKDD, pp 931\u2013939 (2012)","DOI":"10.1145\/2339530.2339677"},{"issue":"6","key":"10009_CR65","first-page":"815","volume":"23","author":"S Ramaswamy","year":"2011","unstructured":"Ramaswamy, S., Rose, K.: Adaptive cluster distance bounding for high-dimensional indexing. TKDE 23(6), 815\u2013830 (2011)","journal-title":"TKDE"},{"key":"10009_CR66","volume-title":"Foundations of Multidimensional and Metric Data Structures","author":"H Samet","year":"2005","unstructured":"Samet, H.: Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann Publishers Inc., San Francisco (2005)"},{"key":"10009_CR67","unstructured":"Savage, J.E.: Models of computation\u2013exploring the power of computing (1998)"},{"key":"10009_CR68","doi-asserted-by":"crossref","unstructured":"Shen, F., Liu, W., Zhang, S., Yang, Y., Shen, H.T.: Learning binary codes for maximum inner product search. In: ICCV, pp 4148\u20134156 (2015)","DOI":"10.1109\/ICCV.2015.472"},{"key":"10009_CR69","doi-asserted-by":"crossref","unstructured":"Silpa-Anan, C., Hartley, R.: Optimised kd-trees for fast image descriptor matching. In: CVPR, pp 1\u20138 (2008)","DOI":"10.1109\/CVPR.2008.4587638"},{"issue":"13","key":"10009_CR70","doi-asserted-by":"publisher","first-page":"3931","DOI":"10.1021\/ac0481046","volume":"77","author":"WH Tang","year":"2005","unstructured":"Tang, W.H., Halpern, B.R., Shilov, I.V., Seymour, S.L., Keating, S.P., Loboda, A., Patel, A.A., Schaeffer, D.A., Nuwaysir, L.M.: Discovering known and unanticipated protein modifications using ms\/ms database searching. Anal. Chem. 77(13), 3931\u20133946 (2005)","journal-title":"Anal. Chem."},{"key":"10009_CR71","doi-asserted-by":"crossref","unstructured":"Tao, Y., Yi, K., Sheng, C., Kalnis, P.: Quality and efficiency in high dimensional nearest neighbor search. In: SIGMOD, pp 563\u2013576 (2009)","DOI":"10.1145\/1559845.1559905"},{"issue":"1","key":"10009_CR72","first-page":"5:1","volume":"42","author":"C Teflioudi","year":"2016","unstructured":"Teflioudi, C., Gemulla, R.: Exact and approximate maximum inner product search with lemp. TODS 42(1), 5:1\u20135:49 (2016)","journal-title":"TODS"},{"key":"10009_CR73","doi-asserted-by":"crossref","unstructured":"Teflioudi, C., Gemulla, R., Mykytiuk, O.: Lemp: Fast retrieval of large entries in a matrix product. In: SIGMOD, pp 107\u2013122 (2015)","DOI":"10.1145\/2723372.2747647"},{"key":"10009_CR74","unstructured":"The Booking.com Dataset. https:\/\/www.kaggle.com\/jiashenliu\/515k-hotel-reviews-data-in-europe"},{"issue":"7","key":"10009_CR75","first-page":"1476","volume":"9","author":"J Wang","year":"2010","unstructured":"Wang, J., P\u00e9rez-Santiago, J., Katz, J.E., Mallick, P., Bandeira, N.: Peptide identification from mixture tandem mass spectra. MCP 9(7), 1476\u20131485 (2010)","journal-title":"MCP"},{"key":"10009_CR76","volume-title":"Query Processing of Sorted Lists on Modern Hardware","author":"J Wang","year":"2019","unstructured":"Wang, J.: Query Processing of Sorted Lists on Modern Hardware. University of California, San Diego (2019)"},{"issue":"8","key":"10009_CR77","first-page":"853","volume":"10","author":"J Wang","year":"2017","unstructured":"Wang, J., Lin, C., He, R., Chae, M., Papakonstantinou, Y., Swanson, S.: MILC: Inverted list compression in memory. PVLDB 10(8), 853\u2013864 (2017)","journal-title":"PVLDB"},{"issue":"9","key":"10009_CR78","doi-asserted-by":"publisher","first-page":"3944","DOI":"10.1021\/pr400230p","volume":"12","author":"M Wang","year":"2013","unstructured":"Wang, M., Bandeira, N.: Spectral library generating function for assessing spectrum-spectrum match significance. J. Proteome Res. 12 (9), 3944\u20133951 (2013)","journal-title":"J. Proteome Res."},{"issue":"8","key":"10009_CR79","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1038\/nbt.3597","volume":"34","author":"M Wang","year":"2016","unstructured":"Wang, M., Carver, J.J., Bandeira, N.: Sharing and community curation of mass spectrometry data with global natural products social molecular networking. Nat. Biotechnol. 34(8), 828\u2013837 (2016)","journal-title":"Nat. Biotechnol."},{"key":"10009_CR80","doi-asserted-by":"crossref","unstructured":"Wang, Y., Shrivastava, A., Wang, J., Ryu, J.: Randomized algorithms accelerated over cpu-gpu for ultra-high dimensional similarity search. In: SIGMOD (2018)","DOI":"10.1145\/3183713.3196925"},{"key":"10009_CR81","unstructured":"Weber, R., Schek, H.-J., Blott, S.: A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In: VLDB, pp 194\u2013205 (1998)"},{"key":"10009_CR82","doi-asserted-by":"crossref","unstructured":"Wu, Y., Jin, R., Zhang, X.: Fast and unified local search for random walk based k-nearest-neighbor query in large graphs. In: SIGMOD, pp 1139\u20131150 (2014)","DOI":"10.1145\/2588555.2610500"},{"key":"10009_CR83","doi-asserted-by":"crossref","unstructured":"Xin, D., Han, J., Chang, K.C.: Progressive and selective merge: Computing top-k with ad-hoc ranking functions. In: SIGMOD, pp 103\u2013114 (2007)","DOI":"10.1145\/1247480.1247494"},{"issue":"17","key":"10009_CR84","doi-asserted-by":"publisher","first-page":"3557","DOI":"10.1021\/ac980122y","volume":"70","author":"JR Yates","year":"1998","unstructured":"Yates, J.R., Morgan, S.F., Gatlin, C.L., Griffin, P.R., Eng, J.K.: Method to compare collision-induced dissociation spectra of peptides: Potential for library searching and subtractive analysis. Anal. Chem. 70(17), 3557\u20133565 (1998)","journal-title":"Anal. Chem."},{"key":"10009_CR85","doi-asserted-by":"crossref","unstructured":"Yu, A., Agarwal, P.K., Yang, J.: Top-k preferences in high dimensions. In: ICDE, pp 748\u2013759 (2014)","DOI":"10.1109\/ICDE.2014.6816697"},{"key":"10009_CR86","doi-asserted-by":"crossref","unstructured":"Zhang, S., Sun, C., He, Z.: Listmerge: Accelerating top-k aggregation queries over large number of lists. In: DASFAA, pp 67\u201381 (2016)","DOI":"10.1007\/978-3-319-32049-6_5"},{"key":"10009_CR87","doi-asserted-by":"crossref","unstructured":"Zhang, Z., Hwang, S.-W., Chang, K.C.-C., Wang, M., Lang, C.A., Chang, Y.-C.: Boolean + ranking: Querying a database by k-constrained optimization. In: SIGMOD, pp 359\u2013370 (2006)","DOI":"10.1145\/1142473.1142515"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10009-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-10009-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10009-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T18:58:49Z","timestamp":1669316329000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-10009-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,26]]},"references-count":87,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10009"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-10009-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,26]]},"assertion":[{"value":"19 September 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}