1. Finding the K highest-ranked answers in a distributed network
- Author
-
Zeinalipour-Yazdi, Constantinos D., Vagena, Zografoula, Kalogeraki, Vana, Gunopulos, Dimitrios, Tsotras, Vassilis J., Vlachos, Michail, Koudas, Nick, Srivastava, D., and Zeinalipour-Yazdi, Constantinos D. [0000-0002-8388-1549]
- Subjects
Sensor networks ,Ad hoc networks ,Theoretical computer science ,Query processing ,Computer Networks and Communications ,Computer science ,Join algorithms ,Peer-to-peer ,computer.software_genre ,Network topology ,Peer-to-peer networks ,P2P networks ,Electric network topology ,Information retrieval ,Test beds ,Distributed Top-K query processing ,Order of magnitudes ,Network architecture ,Vehicular ad hoc network ,Testbed ,Cost metric ,Local area network ,Arts computing ,Network topologies ,Shared resource ,Distributed networks ,Multi hops ,Experimental methodologies ,Non-uniform ,Efficient algorithms ,Metric (mathematics) ,Top-k queries ,Experimental evaluations ,Client server computer systems ,computer ,Algorithm ,Wireless sensor network ,Vehicular networks ,Algorithms - Abstract
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. © 2009 Elsevier B.V. All rights reserved. 53 9 1431 1449 Cited By :5
- Published
- 2009