Online nearest neighbor search

• Grant number: 21/10488-7
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate
• Start date: February 25, 2022
• End date: September 08, 2022
• Field of knowledge: Physical Sciences and Mathematics - Computer Science
• Principal Investigator: André Carlos Ponce de Leon Ferreira de Carvalho
• Grantee: Saulo Martiello Mastelini
• Supervisor: João Manuel Portela da Gama
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Institution abroad: Universidade do Porto (UP), Portugal
• Associated to the scholarship: 18/07319-6 - Multi-target data stream mining, BP.DR

Abstract

Nearest Neighbor Search (NNS) is one of the pivotal research areas in computer science. Machine learning leverages efficient NNS algorithms to speed up distance-based algorithms. However, most online nearest neighbor-based learning algorithms still rely on brute-force search strategies to this day. This research project is primarily concerned with the sliding window-based online k-Nearest Neighbor (k-NN) algorithm. This family of learning algorithms has a low memory footprint, is simple in design, and has few hyper-parameters to adjust. Still, they are strong contenders in online learning scenarios and naturally robust against concept drift. One clear drawback of the current online k-NN implementation is that exhaustive searches must be performed in the sliding window-based buffer for each incoming new instance. Thus, depending on the buffer size, online k-NN might become impractical in terms of running time. We hypothesize that online clustering and batch-based NNS techniques can be leveraged to speed up online k-NN algorithms. We intend to obtain memory and time-efficient online k-NN algorithms without incurring significative accuracy loss by exploring such techniques. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

RIBEIRO, RITA P.; MASTELINI, SAULO MARTIELLO; DAVARI, NARJES; AMINIAN, EHSAN; VELOSO, BRUNO; GAMA, JOAO; KOPRINSKA, I; MIGNONE, P; GUIDOTTI, R; JAROSZEWICZ, S; et al. Online Anomaly Explanation: A Case Study on Predictive Maintenance. MACHINE LEARNING AND PRINCIPLES AND PRACTICE OF KNOWLEDGE DISCOVERY IN DATABASES, ECML PKDD 2022, PT II, v. 1753, p. 17-pg., 2023-01-01. (21/10488-7)