Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/95D97471-3CCA-4DE5-A9E7-49709A8FCB75 | - |
| Αναγνωριστικό | https://doi.org/10.1007/s10619-018-7223-7 | - |
| Αναγνωριστικό | https://link.springer.com/article/10.1007/s10619-018-7223-7 | - |
| Γλώσσα | en | - |
| Μέγεθος | 41 pages | en |
| Τίτλος | Monitoring distributed fragmented skylines | en |
| Δημιουργός | Papapetrou Odysseas | en |
| Δημιουργός | Παπαπετρου Οδυσσεας | el |
| Δημιουργός | Garofalakis Minos | en |
| Δημιουργός | Γαροφαλακης Μινως | el |
| Εκδότης | Springer Nature [academic journals on nature.com] | en |
| Περίληψη | Distributed 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 |
| Τύπος | Peer-Reviewed Journal Publication | en |
| Τύπος | Δημοσίευση σε Περιοδικό με Κριτές | el |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2019-05-23 | - |
| Ημερομηνία Δημοσίευσης | 2018 | - |
| Θεματική Κατηγορία | Distributed skylines | en |
| Θεματική Κατηγορία | Fragmented skylines | en |
| Θεματική Κατηγορία | Geometric method | en |
| Θεματική Κατηγορία | Skylines | en |
| Θεματική Κατηγορία | C (programming language) | en |
| Θεματική Κατηγορία | Complex networks | en |
| Θεματική Κατηγορία | Distributed database systems | en |
| Θεματική Κατηγορία | Monitoring | en |
| Θεματική Κατηγορία | Query processing | en |
| Βιβλιογραφική Αναφορά | O. 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-7 | en |
Copyright © DIAS 2013
