SWINN: Efficient nearest neighbor search in sliding windows using graphs

• Tipo: Artigo em Revista Científica Internacional
• Data: 2024

Autores

Mastelini, SM (Autor) Outra; Veloso, B (Autor) FEP; Halford, M (Autor) Outra; de Carvalho, ACPDF (Autor) Outra; João Gama (Autor) FEP

Revista

Título: Information Fusion

Vol. 101

ISSN: 1566-2535

Editora: Elsevier

Indexação

ISI Web of Knowledge - 5 Citações

Scopus - 7 Citações

Outras Informações

ID Authenticus: P-00Z-0VQ

DOI: 10.1016/j.inffus.2023.101979

Abstract (EN): Nearest neighbor search (NNS) is one of the main concerns in data stream applications since similarity queries can be used in multiple scenarios. Online NNS is usually performed on a sliding window by lazily scanning every element currently stored in the window. This paper proposes Sliding Window-based Incremental Nearest Neighbors (SWINN), a graph-based online search index algorithm for speeding up NNS in potentially never-ending and dynamic data stream tasks. Our proposal broadens the application of online NNS-based solutions, as even moderately large data buffers become impractical to handle when a naive NNS strategy is selected. SWINN enables efficient handling of large data buffers by using an incremental strategy to build and update a search graph supporting any distance metric. Vertices can be added and removed from the search graph. To keep the graph reliable for search queries, lightweight graph maintenance routines are run. According to experimental results, SWINN is significantly faster than performing a naive complete scan of the data buffer while keeping competitive search recall values. We also apply SWINN to online classification and regression tasks and show that our proposal is effective against popular online machine learning algorithms.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 17