Synopses for Summarizing Spatial Data Streams

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)

Abstract

In today’s data-driven landscape, geospatial streams are pivotal in diverse fields, ranging from sociology to network engineering
and to meteorology. A key challenge in utilizing these streams is to efficiently compute aggregates over ad-hoc spatial ranges,
possibly with additional predicates on the stream items. For each application scenario, different aggregates become relevant, such
as the number of distinct items, the frequency of each item, or even the variance of the frequencies of the items that fall within
a spatial range.
Storing the entire stream for computing these aggregates is impractical in scenarios that involve fast-paced and unbounded
streams, due to prohibitive storage costs and query execution delays. To address this, we propose two sketches, SpatialSketch
and DynSketch, that support aggregate queries with different types of aggregates. Both sketches require small space, and they
can summarize fast-paced streams and estimate the aggregates, with accuracy guarantees. Importantly, they support new diverse
functionalities, in a plug-and-play manner, without requiring novel theoretical analysis. In addition to the theoretical contribution,
we evaluate SpatialSketch and DynSketch experimentally. Our experiments demonstrate that the two sketches outperform the
state of the art, and that they can be used for addressing novel functionalities for which there exist no small-space solutions to
date.
Original languageEnglish
Title of host publicationProceedings 28th International Conference on Extending Database Technology, Proceedings, EDBT 2025
Subtitle of host publicationBarcelona, Spain, March 25-March 28
PublisherOpenProceedings.org
Pages284-296
Number of pages13
ISBN (Electronic)978-3-89318-098-1
DOIs
Publication statusPublished - 11 Nov 2024
Event28th International Conference on Extending Database Technology, EDBT 2025 - Barcelona, Spain
Duration: 25 Mar 202528 Mar 2025

Publication series

NameAdvances in Database Technology
Number2
Volume28
ISSN (Electronic)2367-2005

Conference

Conference28th International Conference on Extending Database Technology, EDBT 2025
Abbreviated titleEDBT 2025
Country/TerritorySpain
CityBarcelona
Period25/03/2528/03/25

Funding

This work was partially funded by the European Commission under the STELAR (HORIZON-EUROPE - Grant No. 101070122) project.

Keywords

  • databases
  • Streaming data
  • Sketches
  • approximation algorithm
  • spatial analysis

Fingerprint

Dive into the research topics of 'Synopses for Summarizing Spatial Data Streams'. Together they form a unique fingerprint.

Cite this