{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T11:50:47Z","timestamp":1787313047147,"version":"build-2736575974"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T00:00:00Z","timestamp":1713916800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T00:00:00Z","timestamp":1713916800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002969","name":"Technologick\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["CZ.01.1.02\/0.0\/0.0\/20_321\/0024988"],"award-info":[{"award-number":["CZ.01.1.02\/0.0\/0.0\/20_321\/0024988"]}],"id":[{"id":"10.13039\/501100002969","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007655","name":"Czech Technical University in Prague","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007655","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The intuitive approach of comparing like with like, forms the basis of the so-called nearest neighbor analysis, which is central to many machine learning algorithms. Nearest neighbor analysis is easy to interpret, analyze, and reason about. It is widely used in advanced techniques such as uncertainty estimation in regression models, as well as the renowned\n                    <jats:italic>k<\/jats:italic>\n                    -nearest neighbor-based algorithms. Nevertheless, its high inference time complexity, which is dataset size dependent even in the case of its faster approximated version, restricts its applications and can considerably inflate the application cost. In this paper, we address the problem of high inference time complexity. By using gradient-boosted regression trees as a predictor of the labels obtained from nearest neighbor analysis, we demonstrate a significant increase in inference speed, improving by several orders of magnitude. We validate the effectiveness of our approach on a real-world European Car Pricing Dataset with approximately\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$4.2 \\times 10^6$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mn>4.2<\/mml:mn>\n                            <mml:mo>\u00d7<\/mml:mo>\n                            <mml:msup>\n                              <mml:mn>10<\/mml:mn>\n                              <mml:mn>6<\/mml:mn>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    rows for both residual cost and price uncertainty prediction. Moreover, we assess our method\u2019s performance on the most commonly used tabular benchmark datasets to demonstrate its scalability. The link is to github repository where the code is available:\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/koutefra\/uncertainty_experiments\">https:\/\/github.com\/koutefra\/uncertainty_experiments<\/jats:ext-link>\n                    .\n                  <\/jats:p>","DOI":"10.1007\/s42979-024-02670-2","type":"journal-article","created":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T11:01:56Z","timestamp":1713956516000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Overcoming Long Inference Time of Nearest Neighbors Analysis in Regression and Uncertainty Prediction"],"prefix":"10.1007","volume":"5","author":[{"given":"Franti\u0161ek","family":"Koutensk\u00fd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr","family":"\u0160im\u00e1nek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Miroslav","family":"\u010cepek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7194-1874","authenticated-orcid":false,"given":"Alexander","family":"Kovalenko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,4,24]]},"reference":[{"key":"2670_CR1","unstructured":"Bhatia N, et al. Survey of nearest neighbor techniques. arXiv preprint arXiv:1007.0085. 2010"},{"issue":"3","key":"2670_CR2","doi-asserted-by":"publisher","first-page":"525","DOI":"10.3390\/make3030027","volume":"3","author":"MR Zafar","year":"2021","unstructured":"Zafar MR, Khan N. Deterministic local interpretable model-agnostic explanations for stable explainability. Mach Learn Knowl Extr. 2021;3(3):525\u201341.","journal-title":"Mach Learn Knowl Extr"},{"issue":"4","key":"2670_CR3","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1080\/10926488.2013.826529","volume":"28","author":"B Winter","year":"2013","unstructured":"Winter B, Matlock T. Making judgments based on similarity and proximity. Metaphor Symb. 2013;28(4):219\u201332.","journal-title":"Metaphor Symb"},{"issue":"57","key":"2670_CR4","first-page":"233","volume":"3","author":"E Fix","year":"1951","unstructured":"Fix E, Hodges J. An important contribution to nonparametric discriminant analysis and density estimation. Int Stat Rev. 1951;3(57):233\u20138.","journal-title":"Int Stat Rev"},{"key":"2670_CR5","doi-asserted-by":"crossref","unstructured":"Mukhlishin MF, Saputra R, Wibowo A, Predicting house sale price using fuzzy logic, artificial neural network and k-nearest neighbor. In: 2017 1st international conference on informatics and computational sciences (ICICoS). IEEE, 2017; p. 171\u20136.","DOI":"10.1109\/ICICOS.2017.8276357"},{"key":"2670_CR6","unstructured":"Brophy J, Lowd D, Instance-based uncertainty estimation for gradient-boosted regression trees. arXiv preprint arXiv:2205.11412. 2022"},{"issue":"8","key":"2670_CR7","doi-asserted-by":"publisher","first-page":"6469","DOI":"10.1109\/JIOT.2020.3043716","volume":"8","author":"L Liu","year":"2020","unstructured":"Liu L, Lu S, Zhong R, Wu B, Yao Y, Zhang Q, Shi W. Computing systems for autonomous driving: state of the art and challenges. IEEE Internet Things J. 2020;8(8):6469\u201386.","journal-title":"IEEE Internet Things J"},{"key":"2670_CR8","unstructured":"Liu T, Moore A, Yang K, Gray A, An investigation of practical approximate nearest neighbor algorithms. Adv Neural Inf Process Syst 2004;17"},{"key":"2670_CR9","unstructured":"Omohundro SM, Five Balltree Construction Algorithms. International Computer Science Institute Berkeley, 1989"},{"key":"2670_CR10","doi-asserted-by":"crossref","unstructured":"Clarkson KL, et al. Nearest-neighbor searching and metric space dimensions. Nearest-neighbor methods for learning and vision: theory and practice, 2006;15\u201359","DOI":"10.7551\/mitpress\/4908.003.0005"},{"key":"2670_CR11","doi-asserted-by":"crossref","unstructured":"Chen T, Guestrin C. Xgboost: A scalable tree boosting system. In: Proceedings of the 22nd Acm Sigkdd international conference on knowledge discovery and data mining, 2016; p. 785\u201394","DOI":"10.1145\/2939672.2939785"},{"key":"2670_CR12","unstructured":"Dorogush AV, Ershov V, Gulin A, Catboost: gradient boosting with categorical features support. arXiv preprint arXiv:1810.11363. 2018"},{"issue":"1\u20132","key":"2670_CR13","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/s11146-019-09712-0","volume":"60","author":"AN Bogin","year":"2020","unstructured":"Bogin AN, Shui J. Appraisal accuracy and automated valuation models in rural areas. J Real Estate Financ Econ. 2020;60(1\u20132):40\u201352.","journal-title":"J Real Estate Financ Econ"},{"key":"2670_CR14","doi-asserted-by":"crossref","unstructured":"Bloom K, Argamon S, Automated learning of appraisal extraction patterns. In: Corpus-linguistic applications. Brill; 2010, p. 249\u201360.","DOI":"10.1163\/9789042028012_017"},{"issue":"4","key":"2670_CR15","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1108\/JPIF-05-2018-0033","volume":"36","author":"N French","year":"2018","unstructured":"French N, Gabrielli L. Pricing to market: property valuation revisited: the hierarchy of valuation approaches, methods and models. J Prop Invest Financ. 2018;36(4):391\u20136.","journal-title":"J Prop Invest Financ"},{"key":"2670_CR16","unstructured":"Brunauer WA, Weberndorfer RS, Feilmayr W, et al. A statistically founded sales comparison approach. Technical report, European Real Estate Society (ERES), 2017."},{"issue":"14","key":"2670_CR17","doi-asserted-by":"publisher","first-page":"5679","DOI":"10.3390\/su12145679","volume":"12","author":"Y Kim","year":"2020","unstructured":"Kim Y, Choi S, Yi MY. Applying comparable sales method to the automated estimation of real estate prices. Sustainability. 2020;12(14):5679.","journal-title":"Sustainability"},{"issue":"6","key":"2670_CR18","doi-asserted-by":"publisher","first-page":"1712","DOI":"10.1177\/2399808320947729","volume":"48","author":"B Larraz","year":"2021","unstructured":"Larraz B, Alfaro-Navarro J-L, Cano LE, Alfaro-Cortes E, Garcia N, Gamez M. A computer-assisted expert algorithm for real estate valuation in spanish cities. Environ Plan B Urban Anal City Sci. 2021;48(6):1712\u201327.","journal-title":"Environ Plan B Urban Anal City Sci"},{"key":"2670_CR19","doi-asserted-by":"crossref","unstructured":"Chen Z, Goh HS, Sin KL, Lim K, Chung NKH, Liew XY. Automated agriculture commodity price prediction system with machine learning techniques; 2021","DOI":"10.25046\/aj060442"},{"key":"2670_CR20","doi-asserted-by":"crossref","unstructured":"Ashfaq T, Javaid N. Short-term electricity load and price forecasting using enhanced knn. In: 2019 International conference on frontiers of information technology (FIT). IEEE; 2019, p. 266\u2013266.","DOI":"10.1109\/FIT47737.2019.00057"},{"issue":"1","key":"2670_CR21","first-page":"19","volume":"1","author":"E G\u00fcven\u00e7","year":"2021","unstructured":"G\u00fcven\u00e7 E, \u00c7etin G, Ko\u00e7ak H. Comparison of knn and dnn classifiers performance in predicting mobile phone price ranges. Adv Artif Intell Res. 2021;1(1):19\u201328.","journal-title":"Adv Artif Intell Res"},{"issue":"17","key":"2670_CR22","doi-asserted-by":"publisher","first-page":"1978","DOI":"10.1080\/00036846.2017.1383596","volume":"50","author":"D Li","year":"2018","unstructured":"Li D, Li Z, Li R. Automate the identification of technical patterns: a k-nearest-neighbour model approach. Appl Econ. 2018;50(17):1978\u201391.","journal-title":"Appl Econ"},{"issue":"3","key":"2670_CR23","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/j.rse.2006.04.009","volume":"104","author":"H-J Kim","year":"2006","unstructured":"Kim H-J, Tomppo E. Model-based prediction error uncertainty estimation for k-nn method. Remote Sens Environ. 2006;104(3):257\u201363.","journal-title":"Remote Sens Environ"},{"key":"2670_CR24","doi-asserted-by":"publisher","DOI":"10.1016\/j.scitotenv.2021.151760","volume":"818","author":"A Fathabadi","year":"2022","unstructured":"Fathabadi A, Seyedian SM, Malekian A. Comparison of bayesian, k-nearest neighbor and gaussian process regression methods for quantifying uncertainty of suspended sediment concentration prediction. Sci Total Environ. 2022;818: 151760.","journal-title":"Sci Total Environ"},{"issue":"11","key":"2670_CR25","first-page":"13","volume":"105","author":"R Agrawal","year":"2014","unstructured":"Agrawal R. K-nearest neighbor for uncertain data. Int J Comput Appl. 2014;105(11):13\u20136.","journal-title":"Int J Comput Appl"},{"issue":"8","key":"2670_CR26","doi-asserted-by":"publisher","first-page":"4021","DOI":"10.5194\/hess-21-4021-2017","volume":"21","author":"O Wani","year":"2017","unstructured":"Wani O, Beckers JV, Weerts AH, Solomatine DP. Residual uncertainty estimation using instance-based learning with applications to hydrologic forecasting. Hydrol Earth Syst Sci. 2017;21(8):4021\u201336.","journal-title":"Hydrol Earth Syst Sci"},{"key":"2670_CR27","first-page":"20073","volume":"33","author":"A Zaoui","year":"2020","unstructured":"Zaoui A, Denis C, Hebiri M. Regression with reject option and application to knn. Adv Neural Inf Process Syst. 2020;33:20073\u201382.","journal-title":"Adv Neural Inf Process Syst"},{"key":"2670_CR28","unstructured":"Zong Y. Maintenance cost and residual value prediction of heavy construction equipment; 2017"},{"issue":"3","key":"2670_CR29","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1109\/TBDATA.2019.2921572","volume":"7","author":"J Johnson","year":"2019","unstructured":"Johnson J, Douze M, J\u00e9gou H. Billion-scale similarity search with gpus. IEEE Trans Big Data. 2019;7(3):535\u201347.","journal-title":"IEEE Trans Big Data"},{"key":"2670_CR30","unstructured":"Ke G, Meng Q, Finley T, Wang T, Chen W, Ma W, Ye Q, Liu T-Y, Lightgbm: a highly efficient gradient boosting decision tree. Adv Neural Inf Process Syst 2017;30"},{"key":"2670_CR31","doi-asserted-by":"crossref","unstructured":"Shapley LS, et al. A value for n-person games; 1953","DOI":"10.1515\/9781400881970-018"},{"key":"2670_CR32","unstructured":"Kadra A, Lindauer M, Hutter F, Grabocka J. Regularization is all you need: simple neural nets can excel on tabular data. arXiv preprint arXiv:2106.11189. 2021;536"},{"key":"2670_CR33","unstructured":"Tweedie MC, An index which distinguishes between some important exponential families. In: Statistics: applications and new directions: Proc. Indian Statistical Institute Golden Jubilee International Conference, 1984; vol. 579, p. 579\u2013604"},{"key":"2670_CR34","unstructured":"Prokhorenkova L, Gusev G, Vorobev A, Dorogush AV, Gulin A, Catboost: unbiased boosting with categorical features. Adv Neural Inf Process Syst 2018;31"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-024-02670-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-024-02670-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-024-02670-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T11:29:42Z","timestamp":1713958182000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-024-02670-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,24]]},"references-count":34,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2024,6]]}},"alternative-id":["2670"],"URL":"https:\/\/doi.org\/10.1007\/s42979-024-02670-2","relation":{},"ISSN":["2661-8907"],"issn-type":[{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,24]]},"assertion":[{"value":"24 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflicts of interest or competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}},{"value":"The data utilized in this study were collected and processed following strict ethical guidelines. Informed consent was obtained from all participants, ensuring that they were fully aware of the purpose, methods, potential risks, benefits, and consequences of the data collection. All personal and sensitive information was anonymized to safeguard participants\u2019 identities. Furthermore, the data were used solely for the purpose of this research, respecting the privacy and rights of the individuals involved. The approach taken for data collection and usage aligns with the standard ethical guidelines and legal requirements, thereby maintaining the trust and integrity of the research process.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}],"article-number":"486"}}