Implementing range queries with a decentralized balanced tree over distributed hash tables

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2007

Autores

Lopes, N (Autor) Outra; Baquero, C (Autor) Outra

Ata de Conferência Internacional

Título: NETWORK-BASED INFORMATION SYSTEMS, PROCEEDINGS

Páginas: 197-206

1st International Conference on Network-Based Information Systems (NBiS 2007)

Regensburg, GERMANY, SEP 03-07, 2007

Indexação

ISI Web of Knowledge - 4 Citações

Scopus - 9 Citações

Outras Informações

ID Authenticus: P-004-E0G

DOI: 10.1007/978-3-540-74573-0_21

Abstract (EN): Range queries, retrieving all keys within a given range, is an important add-on for Distributed Hash Tables (DHTs), as they rely only on exact key matching lookup. In this paper we support range queries through a balanced tree algorithm, Decentralized Balanced Tree, that runs over any DHT system. Our algorithm is based on the B(+)-tree design that efficiently stores clustered data while maintaining a balanced load on hosts. The internal structure of the balanced tree is suited for range queries operations over many data distributions since it easily handles clustered data without losing performance. We analyzed, and evaluated our algorithm under a simulated environment, to show it's operation scalability for both insertions and queries. We will show that the system design. imposes a fixed penalty over the DHT access cost, and thus inherits the scalability properties of the chosen underlying DHT.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 10