Title :
Index recommendation tool for optimized information discovery over distributed hash tables
Author :
Memon, Faraz ; Dürr, Frank ; Rothermel, Kurt
Author_Institution :
IPVS - Distrib. Syst. Dept., Univ. Stuttgart, Stuttgart, Germany
Abstract :
Peer-to-peer (P2P) networks allow for efficient information discovery in large-scale distributed systems. Although point queries are well supported by current P2P systems - in particular systems based on distributed hash tables (DHTs) -, providing efficient support for more complex queries remains a challenge. Our research focuses on the efficient support for multiattribute range (MAR) queries over DHT-based information discovery systems. Traditionally, the support for MAR queries over DHTs has been provided either by creating an individual index for each data attribute or by creating a single index using the combination of all data attributes. In contrast to these approaches, we propose to create a set of indices over selected attribute combinations. In order to limit the overhead induced by index maintenance, the total number of created indices has to be limited. Thus, the resulting problem is to create a limited number of indices such that the overall system performance is optimal for MAR queries. In this paper, we propose an index recommendation tool that implements heuristic solutions to this NP-hard problem. Our evaluations show that these heuristics lead to a close-to-optimal system performance for MAR queries.
Keywords :
peer-to-peer computing; query processing; DHT-based information discovery systems; MAR queries; NP-hard problem; close-to-optimal system performance; distributed hash tables; index maintenance; index recommendation tool; large-scale distributed systems; multiattribute range queries; optimized information discovery; peer-to-peer networks; Complexity theory; Cost function; Distributed databases; Indexing; Merging; Distributed data structures; Distributed networks; Hash-table representations; Indexing methods;
Conference_Titel :
Local Computer Networks (LCN), 2010 IEEE 35th Conference on
Conference_Location :
Denver, CO
Print_ISBN :
978-1-4244-8387-7
DOI :
10.1109/LCN.2010.5735679