loading...
Extended Skip Graphs for Efficient Key Search in P2P Environment
Las Vegas, Nevada, USA December 07-December 09
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.458th International Symposium on Parall ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Satoshi Fujita, Akira Ohtsubo, Masaya Mito, "Extended Skip Graphs for Efficient Key Search in P2P Environment," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 256-261, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005.
 
 
BibTex
x
 
@article{ 10.1109/ISPAN.2005.45,
author = {Satoshi Fujita and Akira Ohtsubo and Masaya Mito},
title = {Extended Skip Graphs for Efficient Key Search in P2P Environment},
journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on},
volume = {0},
year = {2005},
issn = {1087-4089},
pages = {256-261},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.45},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel Architectures, Algorithms, and Networks, International Symposium on
TI - Extended Skip Graphs for Efficient Key Search in P2P Environment
SN - 1087-4089
SP256
EP261
A1 - Satoshi Fujita,
A1 - Akira Ohtsubo,
A1 - Masaya Mito,
PY - 2005
KW - null
VL - 0
JA - Parallel Architectures, Algorithms, and Networks, International Symposium on
ER -
 
Satoshi Fujita, Graduate School of Engineering, Hiroshima University
Akira Ohtsubo, Graduate School of Engineering, Hiroshima University
Masaya Mito, Graduate School of Engineering, Hiroshima University
In this paper, we propose three techniques to improve the cost/performance of the skip graph that was recently proposed by Aspnes and Shah in 2003. More concretely, the skip graph, in which each node is connected with exactly log2 N neighbors among N nodes contained in the system, is extended in the following two directions: 1) proposal of a subgraph of the skip graph which realizes a graceful degradation of the routing performance when the number of neighbors reduces from log2N, and 2) proposal of a supergraph of the skip graph which realizes a significant performance improvement when the number of neighbors increases from log2N. The performance of those extended graphs will be evaluated analytically with concrete numerical results.
Citation:
Satoshi Fujita, Akira Ohtsubo, Masaya Mito, "Extended Skip Graphs for Efficient Key Search in P2P Environment," ispan, pp.256-261, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.