Not logged in.

Contribution Details

Type Conference or Workshop Paper
Scope Discipline-based scholarship
Published in Proceedings Yes
Title Planning Ahead: Stream-Driven Linked-Data Access under Update-Budget Constraints
Organization Unit
  • Shen Gao
  • Daniele Dell'Aglio
  • Soheila Dehghanzadeh
  • Abraham Bernstein
  • Emanuele Della Valle
  • Alessandra Mileo
Presentation Type paper
Item Subtype Original Work
Refereed Yes
Status Published in final form
  • English
Event Title The 15th International Semantic Web Conference
Event Type conference
Event Location Kobe, Japan
Event Start Date October 17 - 2016
Event End Date October 21 - 2016
Place of Publication Heidelberg
Abstract Text Data stream applications are becoming increasingly popular on the web. In these applications, one query pattern is especially prominent: a join between a continuous data stream and some background data (BGD). Oftentimes, the target BGD is large, maintained externally, changing slowly, and costly to query (both in terms of time and money). Hence, practical applications usually maintain a local (cached) view of the relevant BGD. Given that these caches are not updated as the original BGD, they should be refreshed under realistic budget constraints (in terms of latency, computation time, and possibly financial cost) to avoid stale data leading to wrong answers. This paper proposes to model the join between streams and the BGD as a bipartite graph. By exploiting the graph structure, we keep the quality of results good enough without refreshing the entire cache for each evaluation. We also introduce two extensions to this method: first, we consider a continuous join between recent portions of a data stream and some BGD to focus on updates that have the longest effect. Second, we consider the future impact of a query to the BGD by proposing to delay some updates to provide fresher answers in future. By extending an existing stream processor with the proposed policies, we empirically show that we can improve result freshness by 93% over baseline algorithms such as Random Selection or Least Recently Updated.
PDF File Download
Export BibTeX