A dynamic distributed data structure for top-\(k\) and \(k\)-select queries. (English) Zbl 1514.68046
Böckenhauer, Hans-Joachim (ed.) et al., Adventures between lower bounds and higher altitudes. Essays dedicated to Juraj Hromkovič on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 11011, 311-329 (2018).
Summary: We consider a scenario where \(n\) sensor nodes observe streams of data. The nodes are connected to a central server whose task it is to compute some function over all data items observed by the nodes. Extending the capabilities of the distributed monitoring model from [G. Cormode et al., SODA 2008, 1076–1085 (2008; Zbl 1192.68080)], we allow, in addition to sending messages from the sensor nodes to the server, also broadcasts from the server to the sensor nodes.
In this paper, we address the problem of answering Top-\(k\) queries (report the \(k\) largest data items currently observed) and approximate \(k\)-Select queries (report an element with rank close to \(k)\). We present a communication-efficient dynamic data structure that supports these queries under updates of the data items arriving at the sensor nodes.
For the entire collection see [Zbl 1398.68015].
In this paper, we address the problem of answering Top-\(k\) queries (report the \(k\) largest data items currently observed) and approximate \(k\)-Select queries (report an element with rank close to \(k)\). We present a communication-efficient dynamic data structure that supports these queries under updates of the data items arriving at the sensor nodes.
For the entire collection see [Zbl 1398.68015].
MSC:
| 68P05 | Data structures |
Citations:
Zbl 1192.68080References:
| [1] | 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-106. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02927-1_10 · Zbl 1248.68085 · doi:10.1007/978-3-642-02927-1_10 |
| [2] | Babcock, B., Olston, C.: Distributed Top-K monitoring. In: ACM SIGMOD International Conference on Management of Data, pp. 28-39. ACM (2003) |
| [3] | Bemmann, P., et al.: Monitoring of domain-related problems in distributed data streams. In: Das, S., Tixeuil, S. (eds.) SIROCCO 2017. LNCS, vol. 10641, pp. 212-226. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72050-0_13 · Zbl 1496.68045 · doi:10.1007/978-3-319-72050-0_13 |
| [4] | Biermeier, F., Feldkord, B., Malatyali, M., Meyer auf der Heide, F.: A communication-efficient distributed data structure for Top-\(k\) and \(k\)-select queries. In: Solis-Oba, R., Fleischer, R. (eds.) WAOA 2017. LNCS, vol. 10787, pp. 285-300. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89441-6_21 · Zbl 1504.68042 · doi:10.1007/978-3-319-89441-6_21 |
| [5] | Cormode, G., Korn, F., Muthukrishnan, S., Srivastava, D.: Space-and time-efficient deterministic algorithms for biased quantiles over data streams. In: 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 263-272. ACM (2006) |
| [6] | Cormode, G., Korn, F., Muthukrishnan, S., Srivastava, D.: Effective computation of biased quantiles over data streams. In: 21st International Conference on Data Engineering, pp. 20-31. IEEE (2005) |
| [7] | Cormode, G., Muthukrishnan, S., Yi, K.: Algorithms for distributed functional monitoring. ACM Trans. Algorithms 7(2), 21 (2011) · Zbl 1295.68204 · doi:10.1145/1921659.1921667 |
| [8] | Cormode, G., Muthukrishnan, S., Yi, K.: Algorithms for distributed functional monitoring. In: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1076-1085. Society for Industrial and Applied Mathematics (2008) · Zbl 1192.68080 |
| [9] | Mäcker, 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, pp. 357-364. IEEE (2015) |
| [10] | Mäcker, 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, pp. 700-709. IEEE (2016) |
| [11] | Madden, S., Franklin, M., Hellerstein, J., Hong, W.: The design of an acquisitional query processor for sensor networks. In: ACM SIGMOD International Conference on Management of Data, pp. 491-502. ACM (2003) |
| [12] | Marberg, J., Gafni, E.: An optimal shout-echo algorithm for selection in distributed sets. In: 23rd Allerton Conference on Communication, Control, and Computing (1985) |
| [13] | Muthukrishnan, S.: Data Streams: Algorithms and Applications. Now Publishers Inc. (2005) · Zbl 1128.68025 |
| [14] | Rotem, D., Santoro, N., Sidney, J.: Shout echo selection in distributed files. Networks 16(1), 77-86 (1986) · Zbl 0641.68030 · doi:10.1002/net.3230160108 |
| [15] | Yi, K., Zhang, Q.: Optimal tracking of distributed heavy hitters and quantiles. Algorithmica 65(1), 206-223 (2013) · Zbl 1259.68042 · doi:10.1007/s00453-011-9584-4 |
| [16] | Zengfeng, H., Yi, K., Zhang, Q.: Randomized algorithms for tracking distributed count, frequencies, and ranks. In: 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 295-306. ACM (2012) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
