SWINN: Efficient nearest neighbor search in sliding windows using graphs

• Type: Article in International Scientific Journal
• Date: 2024

Authors

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

Journal

Title: Information Fusion

Vol. 101

ISSN: 1566-2535

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 2 Citations

Scopus - 2 Citations

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 17