Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Distributed processing of continuous sliding-window k-NN queries for data stream filtering
 
research article

Distributed processing of continuous sliding-window k-NN queries for data stream filtering

Pripuzic, Kresimir
•
Podnar Zarko, Ivana
•
Aberer, Karl  
2011
World Wide Web

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.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1007/s11280-011-0125-5
Web of Science ID

WOS:000294558800002

Author(s)
Pripuzic, Kresimir
Podnar Zarko, Ivana
Aberer, Karl  
Date Issued

2011

Publisher

Springer Verlag

Published in
World Wide Web
Volume

14

Issue

5-6

Start page

465

End page

494

Subjects

k nearest neighbor queries – sliding windows – data streams – peer-to-peer system

•

NCCR-MICS

•

NCCR-MICS/ESDM

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LSIR  
Available on Infoscience
December 1, 2011
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/72939
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés