Skip graph (original) (raw)
Skip graphs are a kind of distributed data structure based on skip lists. They were invented in 2003 by James Aspnes and Gauri Shah. A nearly identical data structure called SkipNet was independently invented by Nicholas Harvey, Michael Jones, Stefan Saroiu, Marvin Theimer and Alec Wolman, also in 2003.
| Property | Value |
|---|---|
| dbo:abstract | Skip graphs are a kind of distributed data structure based on skip lists. They were invented in 2003 by James Aspnes and Gauri Shah. A nearly identical data structure called SkipNet was independently invented by Nicholas Harvey, Michael Jones, Stefan Saroiu, Marvin Theimer and Alec Wolman, also in 2003. Skip graphs have the full functionality of a balanced tree in a distributed system. Skip graphs are mostly used in searching peer-to-peer networks. As they provide the ability to query by , they improve over search tools based on the hash table functionality only. In contrast to skip lists and other tree data structures, they are very resilient and can tolerate a large fraction of node failures. In addition, constructing, inserting, searching, and repairing a skip graph that was disturbed by failing nodes can be done by straightforward algorithms. (en) |
| dbo:wikiPageID | 31169226 (xsd:integer) |
| dbo:wikiPageLength | 11662 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1096460567 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Peer-to-peer_network dbr:Doubly_linked_list dbr:Chord_(peer-to-peer) dbr:Tapestry_(DHT) dbr:Tree_(data_structure) dbr:Data_structure dbr:Distributed_computing dbr:Expander_graph dbr:Query_(complexity) dbr:Hash_table dbc:Graph_data_structures dbr:Adversary_model dbr:Skip_lists dbr:Distributed_hash_table dbr:Skip_list dbr:Search_tree dbr:Distributed_system dbr:Balanced_tree dbr:Node_(graph_theory) dbr:Key_ordering |
| dbp:wikiPageUsesTemplate | dbt:Code dbt:Math dbt:Mvar dbt:Reflist dbt:Tmath dbt:Var |
| dct:subject | dbc:Graph_data_structures |
| gold:hypernym | dbr:Kind |
| rdf:type | yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:PsychologicalFeature100023100 yago:WikicatGraphDataStructures yago:Structure105726345 |
| rdfs:comment | Skip graphs are a kind of distributed data structure based on skip lists. They were invented in 2003 by James Aspnes and Gauri Shah. A nearly identical data structure called SkipNet was independently invented by Nicholas Harvey, Michael Jones, Stefan Saroiu, Marvin Theimer and Alec Wolman, also in 2003. (en) |
| rdfs:label | Skip graph (en) |
| owl:sameAs | freebase:Skip graph yago-res:Skip graph wikidata:Skip graph https://global.dbpedia.org/id/4uin7 |
| prov:wasDerivedFrom | wikipedia-en:Skip_graph?oldid=1096460567&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Skip_graph |
| is dbo:wikiPageWikiLink of | dbr:Distributed_hash_table dbr:Skip_list |
| is foaf:primaryTopic of | wikipedia-en:Skip_graph |