
In this paper, we present an algorithm for finding the k highest-ranked (or Top-k) answers in a distributed network. A Top-K query returns the subset of most relevant answers, in place of all answers, for two reasons: (i) to minimize the cost metric that is associated with the retrieval of all answers; and (ii) to improve the recall and the precision of the answer-set, such that the user is not overwhelmed with irrelevant results. Our study focuses on multi-hop distributed networks in which the data is accessible by traversing a network of nodes. Such a setting captures very well the computation framework of emerging Sensor Networks, Peer-to-Peer Networks and Vehicular Networks. We present the Threshold Join Algorithm (TJA), an efficient algorithm that utilizes a non-uniform threshold on the queried attribute in order to minimize the transfer of data when a query is executed. Additionally, TJA resolves queries in the network rather than in a centralized fashion which further minimizes the consumption of bandwidth and delay. We performed an extensive experimental evaluation of our algorithm using a real testbed of 75 workstations along with a trace-driven experimental methodology. Our results indicate that TJA requires an order of magnitude less communication than the state-of-the-art, scales well with respect to the parameter k and the network topology.
Sensor networks, Ad hoc networks, Query processing, Cost metric, Arts computing, Join algorithms, Peer-to-peer networks, P2P networks, Network topologies, Distributed networks, Multi hops, Experimental methodologies, Non-uniform, Electric network topology, Efficient algorithms, Top-k queries, Information retrieval, Test beds, Experimental evaluations, Client server computer systems, Distributed Top-K query processing, Vehicular networks, Algorithms, Order of magnitudes
Sensor networks, Ad hoc networks, Query processing, Cost metric, Arts computing, Join algorithms, Peer-to-peer networks, P2P networks, Network topologies, Distributed networks, Multi hops, Experimental methodologies, Non-uniform, Electric network topology, Efficient algorithms, Top-k queries, Information retrieval, Test beds, Experimental evaluations, Client server computer systems, Distributed Top-K query processing, Vehicular networks, Algorithms, Order of magnitudes
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
