期刊
INFORMATION FUSION
卷 101, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.inffus.2023.101979
关键词
Nearest neighbor search; Sliding window; FIFO; Proximity query; Graph
This paper proposes a graph-based online search index algorithm called SWINN for speeding up nearest neighbor search (NNS) in potentially never-ending and dynamic data stream tasks. SWINN significantly outperforms a naive complete scan of the data buffer while maintaining competitive search recall values. It also proves to be effective against popular online machine learning algorithms when applied to online classification and regression tasks.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据