{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T06:10:05Z","timestamp":1751523005552,"version":"3.41.0"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319894409"},{"type":"electronic","value":"9783319894416"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-89441-6_21","type":"book-chapter","created":{"date-parts":[[2018,3,30]],"date-time":"2018-03-30T09:43:23Z","timestamp":1522403003000},"page":"285-300","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries"],"prefix":"10.1007","author":[{"given":"Felix","family":"Biermeier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bj\u00f6rn","family":"Feldkord","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":[[2018,3,31]]},"reference":[{"key":"21_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-642-02927-1_10","volume-title":"Automata, Languages and Programming","author":"C Arackaparambil","year":"2009","unstructured":"Arackaparambil, C., Brody, J., Chakrabarti, A.: Functional monitoring without monotonicity. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 95\u2013106. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02927-1_10"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Babcock, B., Olston, C.: Distributed Top-K monitoring. In: International Conference on Management of Data, pp. 28\u201339. ACM (2003)","DOI":"10.1145\/872757.872764"},{"key":"21_CR3","unstructured":"Bemmann, P., Biermeier, F., B\u00fcrmann, J., Kemper, A., Knollmann, T., Knorr, S., Kothe, N., M\u00e4cker, A., Malatyali, M., Meyer auf der Heide, F., Riechers, S., Schaefer, J., Sundermeier, J.: Monitoring of domain-related problems in distributed data streams. In: 24th International Colloquium on Structural Information and Communication Complexity (to appear)"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Biermeier, F., Feldkord, B., Malatyali, M., Meyer auf der Heide, F.: A communication-efficient distributed data structure for top-k and k-select queries. arXiv preprint arXiv:1709.07259 (2017)","DOI":"10.1007\/978-3-319-89441-6_21"},{"issue":"1","key":"21_CR5","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0020-0190(94)00171-T","volume":"53","author":"R Canetti","year":"1995","unstructured":"Canetti, R., Even, G., Goldreich, O.: Lower bounds for sampling algorithms for estimating the average. Inf. Process. Lett. 53(1), 17\u201325 (1995)","journal-title":"Inf. Process. Lett."},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Cormode, G., Korn, F., Muthukrishnan, S., Srivastava, D.: Space-and time-efficient deterministic algorithms for biased quantiles over data streams. In: Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 263\u2013272. ACM","DOI":"10.1145\/1142351.1142389"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Cormode, G., Korn, F., Muthukrishnan, S., Srivastava, D.: Effective computation of biased quantiles over data streams. In: 21st International Conference on Data Engineering, ICDE 2005 Proceedings, pp. 20\u201331. IEEE (2005)","DOI":"10.1109\/ICDE.2005.55"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/1921659.1921667","volume":"7","author":"G Cormode","year":"2011","unstructured":"Cormode, G., Muthukrishnan, S., Yi, K.: Algorithms for distributed functional monitoring. ACM Trans. Algorithms 7, 21 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"21_CR9","unstructured":"Cormode, G., Muthukrishnan, S., Yi, K.: Algorithms for distributed functional monitoring. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete algorithms, SODA 2008. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2008)"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"M\u00e4cker, A., Malatyali, M., Meyer auf der Heide, F.: Online Top-k-position monitoring of distributed data streams. In: 29th International Parallel and Distributed Processing Symposium. IEEE (2015)","DOI":"10.1109\/IPDPS.2015.40"},{"key":"21_CR11","doi-asserted-by":"crossref","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: 30th International Parallel and Distributed Processing Symposium. IEEE (2016)","DOI":"10.1109\/IPDPS.2016.91"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Madden, S., Franklin, M., Hellerstein, J., Hong, W.: The design of an acquisitional query processor for sensor networks. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of data, pp. 491\u2013502 (2003)","DOI":"10.1145\/872757.872817"},{"key":"21_CR13","unstructured":"Marberg, J.: An optimal shout-echo algorithm for selection in distributed sets. UCLA (1985)"},{"key":"21_CR14","doi-asserted-by":"crossref","DOI":"10.1561\/9781933019604","volume-title":"Data Streams: Algorithms and Applications","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data Streams: Algorithms and Applications. Now Publishers Inc., Breda (2005)"},{"key":"21_CR15","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1002\/net.3230160108","volume":"16","author":"D Rotem","year":"1986","unstructured":"Rotem, D., Santoro, N., Sidney, J.: Shout echo selection in distributed files. Networks 16, 77\u201386 (1986)","journal-title":"Networks"},{"issue":"1","key":"21_CR16","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/s00453-011-9584-4","volume":"65","author":"K Yi","year":"2013","unstructured":"Yi, K., Zhang, Q.: Optimal tracking of distributed heavy hitters and quantiles. Algorithmica 65(1), 206\u2013223 (2013)","journal-title":"Algorithmica"},{"key":"21_CR17","unstructured":"Zengfeng, H., Yi, K., Zhang, Q.: Randomized algorithms for tracking distributed count, frequencies, and ranks. In: Proceedings of the 31st Symposium on Principles of Database Systems (2012)"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"Zhang, Z., Cheng, R., Papadias, D., Tung, A.K.H.: Minimizing the communication cost for continuous skyline maintenance. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 495\u2013508. ACM, New York (2009)","DOI":"10.1145\/1559845.1559898"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Zhang, Q.: Communication-efficient computation on distributed noisy datasets. In: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 313\u2013322. ACM (2015)","DOI":"10.1145\/2755573.2755575"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-89441-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T05:32:11Z","timestamp":1751520731000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-89441-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319894409","9783319894416"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-89441-6_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"31 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vienna","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 September 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 September 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo2017.ac.tuwien.ac.at\/waoa","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}