{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T18:30:53Z","timestamp":1743100253216,"version":"3.40.3"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031215339"},{"type":"electronic","value":"9783031215346"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T00:00:00Z","timestamp":1674000000000},"content-version":"vor","delay-in-days":382,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a scenario where a server is wirelessly connected to countless sensor nodes that continuously measure data. The task of the server is to monitor the sensors\u2019 data. More precisely, at each time step the server calculates a function defined over the current measurements of the sensors. Since the sensors only have small computational power and tight battery constraints, the communication between the server and the sensors should be as small as possible, i.e., we aim at minimizing the total number of messages that is transferred.<\/jats:p><jats:p>There are various conceivable problems for the setting above. We demonstrate our approaches on the following three: In the Top-<jats:italic>k<\/jats:italic>-Value Monitoring Problem, the server aims at identifying the <jats:italic>k<\/jats:italic> largest values. The Top-<jats:italic>k<\/jats:italic>-Position Monitoring Problem shifts the task to identify the sensors observing these values. Finally, the Count Distinct Monitoring Problem obliges the server to determine the number of distinct values currently observed.<\/jats:p><jats:p>For all three problems, we not only present communication-efficient protocols for one time step, we also show how it can be exploited if the input at sensors is similar between consecutive time steps to reduce the total communication on the long term. Thereby, we utilize different techniques \u2013 involving sampling, dynamic data structures, filter-based approaches, and combinations of them \u2013 to demonstrate their potential and their limits in the broad setting described above.<\/jats:p>","DOI":"10.1007\/978-3-031-21534-6_10","type":"book-chapter","created":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:02:53Z","timestamp":1673985773000},"page":"179-195","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Distributed Data Streams"],"prefix":"10.1007","author":[{"given":"Jannik","family":"Castenow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bj\u00f6rn","family":"Feldkord","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonas","family":"Hanselle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Till","family":"Knollmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Malatyali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedhelm","family":"Meyer auf der Heide","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,18]]},"reference":[{"key":"10_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-319-72050-0_13","volume-title":"Structural Information and Communication Complexity","author":"P Bemmann","year":"2017","unstructured":"Bemmann, P., et al.: Monitoring of domain-related problems in\u00a0distributed data streams. In: Das, S., Tixeuil, S. (eds.) SIROCCO 2017. LNCS, vol. 10641, pp. 212\u2013226. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-72050-0_13"},{"key":"10_CR2","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"1","key":"10_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/2481528.2481530","volume":"42","author":"G Cormode","year":"2013","unstructured":"Cormode, G.: The continuous distributed monitoring model. SIGMOD Rec. 42(1), 5\u201314 (2013). https:\/\/doi.org\/10.1145\/2481528.2481530","journal-title":"SIGMOD Rec."},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-319-98355-4_18","volume-title":"Adventures Between Lower Bounds and Higher Altitudes","author":"B Feldkord","year":"2018","unstructured":"Feldkord, B., Malatyali, M., Meyer auf der Heide, F.: A dynamic distributed data structure for top-k and k-select queries. In: B\u00f6ckenhauer, H.-J., Komm, D., Unger, W. (eds.) Adventures Between Lower Bounds and Higher Altitudes. LNCS, vol. 11011, pp. 311\u2013329. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98355-4_18"},{"key":"10_CR5","doi-asserted-by":"publisher","unstructured":"Jain, A., Chang, E.Y., Wang, Y.: Adaptive stream resource management using kalman filters. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, 13\u201318 June 2004, pp. 11\u201322 (2004). https:\/\/doi.org\/10.1145\/1007568.1007573","DOI":"10.1145\/1007568.1007573"},{"issue":"1","key":"10_CR6","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica 3(1), 77\u2013119 (1988). https:\/\/doi.org\/10.1007\/BF01762111","journal-title":"Algorithmica"},{"issue":"1","key":"10_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s000370050018","volume":"8","author":"I Kremer","year":"1999","unstructured":"Kremer, I., Nisan, N., Ron, D.: On randomized one-round communication complexity. Comput. Complex. 8(1), 21\u201349 (1999). https:\/\/doi.org\/10.1007\/s000370050018","journal-title":"Comput. Complex."},{"key":"10_CR8","doi-asserted-by":"publisher","unstructured":"M\u00e4cker, A., Malatyali, M., Meyer auf der Heide, F.: Online top-k-position monitoring of distributed data streams. In: IPDPS, pp. 357\u2013364. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/IPDPS.2015.40","DOI":"10.1109\/IPDPS.2015.40"},{"key":"10_CR9","doi-asserted-by":"publisher","unstructured":"M\u00e4cker, A., Malatyali, M., Meyer auf der Heide, F.: On competitive algorithms for approximations of top-k-position monitoring of distributed streams. In: IPDPS, pp. 700\u2013709. IEEE Computer Society (2016). https:\/\/doi.org\/10.1109\/IPDPS.2016.91","DOI":"10.1109\/IPDPS.2016.91"},{"key":"10_CR10","unstructured":"Malatyali, M.: Big data: sublinear algorithms for distributed data streams. Ph.D. thesis, University of Paderborn, Germany (2019)"},{"key":"10_CR11","unstructured":"Osipov, V.: Algorithm Engineering for fundamental Sorting and Graph Problems. Ph.D. thesis, Karlsruhe Institute of Technology (2014). http:\/\/digbib.ubka.uni-karlsruhe.de\/volltexte\/1000042377"},{"key":"10_CR12","doi-asserted-by":"publisher","unstructured":"Osipov, V., Sanders, P., Singler, J.: The filter-kruskal minimum spanning tree algorithm. In: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, ALENEX 2009, New York, New York, USA, 3 January 2009, pp. 52\u201361 (2009). https:\/\/doi.org\/10.1137\/1.9781611972894.5","DOI":"10.1137\/1.9781611972894.5"},{"issue":"2","key":"10_CR13","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985). https:\/\/doi.org\/10.1145\/2786.2793","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms for Big Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-21534-6_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:04:14Z","timestamp":1673985854000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-21534-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031215339","9783031215346"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-21534-6_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"18 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}