Article in Proceedings INPROC-2010-60

BibliographyMemon, Faraz; Dürr, Frank; Rothermel, Kurt: Index Recommendation Tool for Optimized Information Discovery Over Distributed Hash Tables.
In: Proceedings of the 35th International Conference on Local Computer Networks (LCN '10).
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology.
pp. 1-8, english.
Dever, CO, USA: IEEE Computer Society, October 11, 2010.
Article in Proceedings (Conference Paper).
CR-SchemaC.2.1 (Network Architecture and Design)
E.1 (Data Structures)
E.2 (Data Storage Representations)
H.3.1 (Content Analysis and Indexing)

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 multi-attribute 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.

Full text and
other links
PDF (863651 Bytes)
CopyrightThis material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE (contact By choosing to view this document, you agree to all provisions of the copyright laws protecting it.
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Project(s)Optimized Information Discovery
Entry dateJuly 5, 2010
   Publ. Department   Publ. Institute   Publ. Computer Science