Institutional Repository
Technical University of Crete
EN  |  EL



My Space

Monitoring distributed fragmented skylines

Papapetrou Odysseas, Garofalakis Minos

Simple record

Extent41 pagesen
TitleMonitoring distributed fragmented skylinesen
CreatorPapapetrou Odysseasen
CreatorΠαπαπετρου Οδυσσεαςel
CreatorGarofalakis Minosen
CreatorΓαροφαλακης Μινωςel
PublisherSpringer Nature [academic journals on]en
Content SummaryDistributed skyline computation is important for a wide range of domains, from distributed and web-based systems to ISP-network monitoring and distributed databases. The problem is particularly challenging in dynamic distributed settings, where the goal is to efficiently monitor a continuous skyline query over a collection of distributed streams. All existing work relies on the assumption of a single point of reference for object attributes/dimensions: objects may be vertically or horizontally partitioned, but the accurate value of each dimension for each object is always maintained by a single site. This assumption is unrealistic for several distributed applications, where object information is fragmented over a set of distributed streams (each monitored by a different site) and needs to be aggregated (e.g., averaged) across several sites. Furthermore, it is frequently useful to define skyline dimensions through complex functions over the aggregated objects, which raises further challenges for dealing with distribution and object fragmentation. We present the first known distributed algorithms for continuous monitoring of skylines over complex functions of fragmented multi-dimensional objects. Our algorithms rely on decomposition of the skyline monitoring problem to a select set of distributed threshold-crossing queries, which can be monitored locally at each site. We propose several optimizations, including: (a) a technique for adaptively determining the most efficient monitoring strategy for each object, (b) an approximate monitoring technique, and (c) a strategy that reduces communication overhead by grouping together threshold-crossing queries. Furthermore, we discuss how our proposed algorithms can be used to address other continuous query types. A thorough experimental study with synthetic and real-life data sets verifies the effectiveness of our schemes and demonstrates order-of-magnitude improvements in communication costs compared to the only alternative centralized solution.en
Type of ItemPeer-Reviewed Journal Publicationen
Type of ItemΔημοσίευση σε Περιοδικό με Κριτέςel
Date of Item2019-05-23-
Date of Publication2018-
SubjectDistributed skylinesen
SubjectFragmented skylinesen
SubjectGeometric methoden
SubjectC (programming language)en
SubjectComplex networksen
SubjectDistributed database systemsen
SubjectQuery processingen
Bibliographic CitationO. Papapetrou and M. Garofalakis, "Monitoring distributed fragmented skylines," Distrib. Parallel Databases, vol. 36, no. 4, pp. 675-715, Dec. 2018. doi: 10.1007/s10619-018-7223-7en