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

DOI10.1007/978-3-319-89441-6_21MaRDI QIDQ1644951zbMATH OpenOpenAlexFDO

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

Publication date 22 June 2018

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(7)

• Approximate Top-k Queries in Sensor Networks
• Efficient top-\(k\) query calculation in distributed networks
• A Dynamic Distributed Data Structure for Top-k and k-Select Queries
• A note on efficient aggregate queries in sensor networks
• Approximate distributed top-\(k\) queries
• scientific article; zbMATH DE number 2080920 (Why is no real title available?)
• Top-\(k\) vectorial aggregation queries in a distributed environment

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)