Naslov
Distributed Processing of Continuous Sliding-Window k-NN Queries for Data Stream Filtering

Autori
Pripužić, Krešimir ; Podnar Žarko, Ivana ; Aberer, Karl

Izvornik
World wide web-internet and web information systems (1386-145X) 14 (2011), 5/6; 465-494

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
k nearest neighbor queries; sliding windows; data streams; peer-to-peer system

Sažetak
A sliding-window k-NN query (k-NN/w query) continuously monitors incoming data stream objects within a sliding window to identify k closest objects to a query. It enables effective filtering of data objects streaming in at high rates from potentially distributed sources, and offers means to control the rate of object insertions into result streams. Therefore k-NN/w processing systems may be regarded as one of the prospective solutions for the information overload problem in applications that require processing of structured data in real-time, such as the Sensor Web. Existing k- NN/w processing systems are mainly centralized and cannot cope with multiple data streams, where data sources are scattered over the Internet. In this paper, we propose a solution for distributed continuous k-NN/w processing of structured data from distributed streams. We define a k-NN/w processing model for such setting, and design a distributed k-NN/w processing system on top of the Content- Addressable Network (CAN) overlay. An extensive evaluation using both real and synthetic data sets demonstrates the feasibility of the proposed solution because it balances the load among the peers, while the messaging overhead within the P2P network remains reasonable. Moreover, our results clearly show the solution is scalable for an increasing number of queries and peers.

Izvorni jezik
Engleski

Znanstvena područja
Elektrotehnika, Računarstvo, Informacijske i komunikacijske znanosti

POVEZANOST RADA