SkipMard: A multi-attribute peer-to-peer resource discovery approach

Tao He, Jun Ni, Alberto M. Segre, Shaowen Wang, Boyd M. Knosp

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Resource discovery technologies for Grids and Peer-to-Peer (P2P) systems share some characteristics. However, some P2P systems such as Skip Graph cannot simply be applied to Grid resource discovery because complex grid resources need to be searched by using multi-attribute queries. This paper proposes a new multi-attribute P2P resource discovery approach (SkipMard) that extends Skip Graph structure to support multi-attribute queries. SkipMard provides a prefix matching resource routing algorithm to resolve multi-attribute queries, and introduces the concepts of "layer" and "crossing layer nearest neighbor" into the data structure. To decrease message passing numbers, an approximate closest-point method is addressed that can help routing a searching key to a node with a key value that has the minimum distance between two keys. Each node has O(m *l) neighbors for total m layers and l levels in SkipMard. The expected time for a multi-attribute query is O(log N) and the message passing number is O(log N)+O(k).

Original languageEnglish (US)
Title of host publicationProceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07
Pages266-273
Number of pages8
DOIs
StatePublished - Dec 1 2007
Event2nd International Multi-Symposiums on Computer and Computational Sciences 2007, IMSCCS'07 - Iowa City, IA, United States
Duration: Aug 13 2007Aug 15 2007

Publication series

NameProceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07

Other

Other2nd International Multi-Symposiums on Computer and Computational Sciences 2007, IMSCCS'07
CountryUnited States
CityIowa City, IA
Period8/13/078/15/07

Fingerprint

Resource Discovery
Message passing
Peer to Peer
Attribute
Query
Routing algorithms
P2P Systems
Data structures
Message Passing
Grid
Resources
Peer-to-peer Systems
Peer-to-peer (P2P)
Prefix
Routing Algorithm
Minimum Distance
Graph in graph theory
Vertex of a graph
Nearest Neighbor
Resolve

Keywords

  • DHT
  • Grid
  • Multi-attribute
  • Network
  • Peer-to-peer
  • Resource discovery
  • SkipMard

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Theoretical Computer Science

Cite this

He, T., Ni, J., Segre, A. M., Wang, S., & Knosp, B. M. (2007). SkipMard: A multi-attribute peer-to-peer resource discovery approach. In Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07 (pp. 266-273). [4392611] (Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07). https://doi.org/10.1109/IMSCCS.2007.4392611

SkipMard : A multi-attribute peer-to-peer resource discovery approach. / He, Tao; Ni, Jun; Segre, Alberto M.; Wang, Shaowen; Knosp, Boyd M.

Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07. 2007. p. 266-273 4392611 (Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

He, T, Ni, J, Segre, AM, Wang, S & Knosp, BM 2007, SkipMard: A multi-attribute peer-to-peer resource discovery approach. in Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07., 4392611, Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07, pp. 266-273, 2nd International Multi-Symposiums on Computer and Computational Sciences 2007, IMSCCS'07, Iowa City, IA, United States, 8/13/07. https://doi.org/10.1109/IMSCCS.2007.4392611
He T, Ni J, Segre AM, Wang S, Knosp BM. SkipMard: A multi-attribute peer-to-peer resource discovery approach. In Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07. 2007. p. 266-273. 4392611. (Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07). https://doi.org/10.1109/IMSCCS.2007.4392611
He, Tao ; Ni, Jun ; Segre, Alberto M. ; Wang, Shaowen ; Knosp, Boyd M. / SkipMard : A multi-attribute peer-to-peer resource discovery approach. Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07. 2007. pp. 266-273 (Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07).
@inproceedings{e251c780232143d7ad9d4180c45ab395,
title = "SkipMard: A multi-attribute peer-to-peer resource discovery approach",
abstract = "Resource discovery technologies for Grids and Peer-to-Peer (P2P) systems share some characteristics. However, some P2P systems such as Skip Graph cannot simply be applied to Grid resource discovery because complex grid resources need to be searched by using multi-attribute queries. This paper proposes a new multi-attribute P2P resource discovery approach (SkipMard) that extends Skip Graph structure to support multi-attribute queries. SkipMard provides a prefix matching resource routing algorithm to resolve multi-attribute queries, and introduces the concepts of {"}layer{"} and {"}crossing layer nearest neighbor{"} into the data structure. To decrease message passing numbers, an approximate closest-point method is addressed that can help routing a searching key to a node with a key value that has the minimum distance between two keys. Each node has O(m *l) neighbors for total m layers and l levels in SkipMard. The expected time for a multi-attribute query is O(log N) and the message passing number is O(log N)+O(k).",
keywords = "DHT, Grid, Multi-attribute, Network, Peer-to-peer, Resource discovery, SkipMard",
author = "Tao He and Jun Ni and Segre, {Alberto M.} and Shaowen Wang and Knosp, {Boyd M.}",
year = "2007",
month = "12",
day = "1",
doi = "10.1109/IMSCCS.2007.4392611",
language = "English (US)",
isbn = "0769530397",
series = "Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07",
pages = "266--273",
booktitle = "Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07",

}

TY - GEN

T1 - SkipMard

T2 - A multi-attribute peer-to-peer resource discovery approach

AU - He, Tao

AU - Ni, Jun

AU - Segre, Alberto M.

AU - Wang, Shaowen

AU - Knosp, Boyd M.

PY - 2007/12/1

Y1 - 2007/12/1

N2 - Resource discovery technologies for Grids and Peer-to-Peer (P2P) systems share some characteristics. However, some P2P systems such as Skip Graph cannot simply be applied to Grid resource discovery because complex grid resources need to be searched by using multi-attribute queries. This paper proposes a new multi-attribute P2P resource discovery approach (SkipMard) that extends Skip Graph structure to support multi-attribute queries. SkipMard provides a prefix matching resource routing algorithm to resolve multi-attribute queries, and introduces the concepts of "layer" and "crossing layer nearest neighbor" into the data structure. To decrease message passing numbers, an approximate closest-point method is addressed that can help routing a searching key to a node with a key value that has the minimum distance between two keys. Each node has O(m *l) neighbors for total m layers and l levels in SkipMard. The expected time for a multi-attribute query is O(log N) and the message passing number is O(log N)+O(k).

AB - Resource discovery technologies for Grids and Peer-to-Peer (P2P) systems share some characteristics. However, some P2P systems such as Skip Graph cannot simply be applied to Grid resource discovery because complex grid resources need to be searched by using multi-attribute queries. This paper proposes a new multi-attribute P2P resource discovery approach (SkipMard) that extends Skip Graph structure to support multi-attribute queries. SkipMard provides a prefix matching resource routing algorithm to resolve multi-attribute queries, and introduces the concepts of "layer" and "crossing layer nearest neighbor" into the data structure. To decrease message passing numbers, an approximate closest-point method is addressed that can help routing a searching key to a node with a key value that has the minimum distance between two keys. Each node has O(m *l) neighbors for total m layers and l levels in SkipMard. The expected time for a multi-attribute query is O(log N) and the message passing number is O(log N)+O(k).

KW - DHT

KW - Grid

KW - Multi-attribute

KW - Network

KW - Peer-to-peer

KW - Resource discovery

KW - SkipMard

UR - http://www.scopus.com/inward/record.url?scp=46449119174&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=46449119174&partnerID=8YFLogxK

U2 - 10.1109/IMSCCS.2007.4392611

DO - 10.1109/IMSCCS.2007.4392611

M3 - Conference contribution

AN - SCOPUS:46449119174

SN - 0769530397

SN - 9780769530390

T3 - Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07

SP - 266

EP - 273

BT - Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07

ER -