A communication-efficient distributed data structure for top-k and k-select queries

DOI10.1007/978-3-319-89441-6_21zbMATH Open1504.68042arXiv1709.07259OpenAlexW2964294520MaRDI QIDQ1644951FDOQ1644951

Authors: Felix Biermeier, Björn Feldkord, Manuel Malatyali, Friedhelm Meyer auf der Heide 

Publication date: 22 June 2018

Abstract: We consider the scenario of $n$ sensor nodes observing 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. In our case, there exists a total order on the data items observed by the nodes. Our goal is to compute the $k$ currently lowest observed values or a value with rank in $[(1-varepsilon)k,(1+varepsilon)k]$ with probability $(1-delta)$. We propose solutions for these problems in an extension of the distributed monitoring model where the server can send broadcast messages to all nodes for unit cost. We want to minimize communication over multiple time steps where there are $m$ updates to a node's value in between queries. The result is composed of two main parts, which each may be of independent interest: (1) Protocols which answer Top-k and k-Select queries. These protocols are memoryless in the sense that they gather all information at the time of the request. (2) A dynamic data structure which tracks for every $k$ an element close to $k$. We describe how to combine the two parts to receive a protocol answering the stated queries over multiple time steps. Overall, for Top-$k$ queries we use $O(k+logm+loglogn)$ and for $k$-Select queries $O(frac1varepsilo{n}^{2}logfrac1delta+logm+lo{g}^{2}logn)$ messages in expectation. These results are shown to be asymptotically tight if $m$ is not too small.

Full work available at URL: https://arxiv.org/abs/1709.07259

Recommendations

• A Dynamic Distributed Data Structure for Top-k and k-Select Queries
• Approximate Top-k Queries in Sensor Networks
• Approximate distributed top-\(k\) queries
• Efficient top-\(k\) query calculation in distributed networks
• A note on efficient aggregate queries in sensor networks

Mathematics Subject Classification ID

Data structures (68P05) Distributed systems (68M14)

Cited In (7)

• A Dynamic Distributed Data Structure for Top-k and k-Select Queries
• Efficient top-\(k\) query calculation in distributed networks
• A note on efficient aggregate queries in sensor networks
• Title not available (Why is that?)
• Approximate distributed top-\(k\) queries
• Top-\(k\) vectorial aggregation queries in a distributed environment
• Approximate Top-k Queries in Sensor Networks

This page was built for publication: A communication-efficient distributed data structure for top-\(k\) and \(k\)-select queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1644951)