Continuous fragmented skylines over distributed streams

Odysseas Papapetrou, Minos Garofalakis

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

16 Citations (Scopus)

Abstract

Distributed skyline computation is important for a wide range of application 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, i.e., 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 monitoring 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 object fragmentation. In this paper, we present the first known distributed approach for continuous fragmented skylines, namely distributed monitoring of skylines over complex functions of fragmented multi-dimensional objects. We also propose several optimizations, including a new technique based on random-walk models for adaptively determining the most efficient monitoring strategy for each object. A thorough experimental study with synthetic and real-life data sets verifies the effectiveness of our approach, demonstrating order-of-magnitude improvements in communication costs compared to the only available centralized solution.

Original languageEnglish
Title of host publication2014 IEEE 30th International Conference on Data Engineering, ICDE 2014
Place of PublicationPiscataway
PublisherIEEE Computer Society
Pages124-135
Number of pages12
ISBN (Print)9781479925544
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event30th IEEE International Conference on Data Engineering, ICDE 2014 - Chicago, IL, United States
Duration: 31 Mar 20144 Apr 2014

Conference

Conference30th IEEE International Conference on Data Engineering, ICDE 2014
CountryUnited States
CityChicago, IL
Period31/03/144/04/14

Fingerprint

Monitoring
Communication
Costs

Cite this

Papapetrou, O., & Garofalakis, M. (2014). Continuous fragmented skylines over distributed streams. In 2014 IEEE 30th International Conference on Data Engineering, ICDE 2014 (pp. 124-135). [6816645] Piscataway: IEEE Computer Society. https://doi.org/10.1109/ICDE.2014.6816645
Papapetrou, Odysseas ; Garofalakis, Minos. / Continuous fragmented skylines over distributed streams. 2014 IEEE 30th International Conference on Data Engineering, ICDE 2014. Piscataway : IEEE Computer Society, 2014. pp. 124-135
@inproceedings{56136fabc3dd4a97bb94512f36bb955f,
title = "Continuous fragmented skylines over distributed streams",
abstract = "Distributed skyline computation is important for a wide range of application 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, i.e., 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 monitoring 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 object fragmentation. In this paper, we present the first known distributed approach for continuous fragmented skylines, namely distributed monitoring of skylines over complex functions of fragmented multi-dimensional objects. We also propose several optimizations, including a new technique based on random-walk models for adaptively determining the most efficient monitoring strategy for each object. A thorough experimental study with synthetic and real-life data sets verifies the effectiveness of our approach, demonstrating order-of-magnitude improvements in communication costs compared to the only available centralized solution.",
author = "Odysseas Papapetrou and Minos Garofalakis",
year = "2014",
month = "1",
day = "1",
doi = "10.1109/ICDE.2014.6816645",
language = "English",
isbn = "9781479925544",
pages = "124--135",
booktitle = "2014 IEEE 30th International Conference on Data Engineering, ICDE 2014",
publisher = "IEEE Computer Society",
address = "United States",

}

Papapetrou, O & Garofalakis, M 2014, Continuous fragmented skylines over distributed streams. in 2014 IEEE 30th International Conference on Data Engineering, ICDE 2014., 6816645, IEEE Computer Society, Piscataway, pp. 124-135, 30th IEEE International Conference on Data Engineering, ICDE 2014, Chicago, IL, United States, 31/03/14. https://doi.org/10.1109/ICDE.2014.6816645

Continuous fragmented skylines over distributed streams. / Papapetrou, Odysseas; Garofalakis, Minos.

2014 IEEE 30th International Conference on Data Engineering, ICDE 2014. Piscataway : IEEE Computer Society, 2014. p. 124-135 6816645.

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

TY - GEN

T1 - Continuous fragmented skylines over distributed streams

AU - Papapetrou, Odysseas

AU - Garofalakis, Minos

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Distributed skyline computation is important for a wide range of application 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, i.e., 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 monitoring 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 object fragmentation. In this paper, we present the first known distributed approach for continuous fragmented skylines, namely distributed monitoring of skylines over complex functions of fragmented multi-dimensional objects. We also propose several optimizations, including a new technique based on random-walk models for adaptively determining the most efficient monitoring strategy for each object. A thorough experimental study with synthetic and real-life data sets verifies the effectiveness of our approach, demonstrating order-of-magnitude improvements in communication costs compared to the only available centralized solution.

AB - Distributed skyline computation is important for a wide range of application 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, i.e., 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 monitoring 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 object fragmentation. In this paper, we present the first known distributed approach for continuous fragmented skylines, namely distributed monitoring of skylines over complex functions of fragmented multi-dimensional objects. We also propose several optimizations, including a new technique based on random-walk models for adaptively determining the most efficient monitoring strategy for each object. A thorough experimental study with synthetic and real-life data sets verifies the effectiveness of our approach, demonstrating order-of-magnitude improvements in communication costs compared to the only available centralized solution.

UR - http://www.scopus.com/inward/record.url?scp=84901790084&partnerID=8YFLogxK

U2 - 10.1109/ICDE.2014.6816645

DO - 10.1109/ICDE.2014.6816645

M3 - Conference contribution

AN - SCOPUS:84901790084

SN - 9781479925544

SP - 124

EP - 135

BT - 2014 IEEE 30th International Conference on Data Engineering, ICDE 2014

PB - IEEE Computer Society

CY - Piscataway

ER -

Papapetrou O, Garofalakis M. Continuous fragmented skylines over distributed streams. In 2014 IEEE 30th International Conference on Data Engineering, ICDE 2014. Piscataway: IEEE Computer Society. 2014. p. 124-135. 6816645 https://doi.org/10.1109/ICDE.2014.6816645