Extended Skip Graphs for Efficient Key Search in P2P Environment

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Satoshi Fujita Articles by Akira Ohtsubo Articles by Masaya Mito

8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05)

Las Vegas, Nevada, USA

December 07-December 09

ISBN: 0-7695-2509-1

	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

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.45

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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.