This HTML5 document contains 70 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n8http://dbpedia.org/resource/File:
n14https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n18http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Pointer_jumping
rdf:type
yago:Act100030358 dbo:TopicalConcept yago:YagoPermanentlyLocatedEntity yago:Procedure101023820 yago:Rule105846932 yago:Event100029378 yago:Algorithm105847438 yago:PsychologicalFeature100023100 yago:WikicatAlgorithms yago:Abstraction100002137 yago:Activity100407535
rdfs:label
Pointer jumping
rdfs:comment
Pointer jumping or path doubling is a design technique for parallel algorithms that operate on pointer structures, such as linked lists and directed graphs. Pointer jumping allows an algorithm to follow paths with a time complexity that is logarithmic with respect to the length of the longest path. It does this by "jumping" to the end of the path computed by neighbors. Pointer jumping is best understood by looking at simple examples such as and .
foaf:depiction
n18:PointerJumpingListRanking.svg n18:Pointer_Jumping_Example.svg
dcterms:subject
dbc:Algorithms dbc:Parallel_computing
dbo:wikiPageID
41026219
dbo:wikiPageRevisionID
1092466795
dbo:wikiPageWikiLink
dbr:Parallel_random_access_machine dbr:Forest_(graph_theory) dbr:Software_design_pattern dbr:Image_compression dbr:Linked_list n8:PointerJumpingListRanking.svg n8:Pointer_Jumping_Example.svg dbr:Time_complexity dbr:List_ranking dbr:Connected_component_(graph_theory) dbr:Null_pointer dbr:Computer_vision dbc:Algorithms dbr:Path_(graph_theory) dbr:Textbook dbr:Bayesian_inference dbr:Logarithmic_time dbr:Recursive_data_type dbr:Graph_(discrete_mathematics) dbc:Parallel_computing dbr:Minimum_spanning_trees dbr:Directed_graph dbr:Pseudocode dbr:Graph_algorithm dbr:Biconnected_components dbr:Vertex_(graph_theory) dbr:Parallel_algorithm dbr:Rooted_tree dbr:Algorithm_design
owl:sameAs
wikidata:Q17131051 yago-res:Pointer_jumping n14:fy9w freebase:m.0z2q89p
dbp:wikiPageUsesTemplate
dbt:Unreferenced_section dbt:R dbt:Mono dbt:= dbt:Parallel_computing dbt:Moresources dbt:Framebox dbt:Reflist dbt:Frame-footer dbt:Rp dbt:Mvar dbt:Math
dbo:thumbnail
n18:PointerJumpingListRanking.svg?width=300
dbo:abstract
Pointer jumping or path doubling is a design technique for parallel algorithms that operate on pointer structures, such as linked lists and directed graphs. Pointer jumping allows an algorithm to follow paths with a time complexity that is logarithmic with respect to the length of the longest path. It does this by "jumping" to the end of the path computed by neighbors. The basic operation of pointer jumping is to replace each neighbor in a pointer structure with its neighbor's neighbor. In each step of the algorithm, this replacement is done for all nodes in the data structure, which can be done independently in parallel. In the next step when a neighbor's neighbor is followed, the neighbor's path already followed in the previous step is added to the node's followed path in a single step. Thus, each step effectively doubles the distance traversed by the explored paths. Pointer jumping is best understood by looking at simple examples such as and .
gold:hypernym
dbr:Technique
prov:wasDerivedFrom
wikipedia-en:Pointer_jumping?oldid=1092466795&ns=0
dbo:wikiPageLength
11421
foaf:isPrimaryTopicOf
wikipedia-en:Pointer_jumping