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

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

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
n30http://www.cs.princeton.edu/~chazelle/pubs/
dbohttp://dbpedia.org/ontology/
n25http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n26https://www.cs.princeton.edu/~chazelle/pubs/
n24http://www1.bell-labs.com/user/mbuddhikot/psdocs/
n29https://web.archive.org/web/20041020183845/http:/www.bell-labs.com/user/mbuddhikot/psdocs/
dbpedia-eshttp://es.dbpedia.org/resource/
n19https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
n9https://www.acsu.buffalo.edu/~mblanton/publications/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n5https://graphics.stanford.edu/courses/cs268-11-spring/manuals/
freebasehttp://rdf.freebase.com/ns/
n28http://www.umiacs.umd.edu/~joseph/
n7http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
n23http://www.cccg.ca/proceedings/2001/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n12https://www3.cs.stonybrook.edu/~jgao/paper/
n31https://archive.org/details/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
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:Binary_search_algorithm
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
dbr:Persistent_data_structure
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
dbr:Vijay_Vaishnavi
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
dbr:Range_tree
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
dbr:Convex_layers
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
dbr:Dan_Willard
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
dbr:Range_query_(data_structures)
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
dbr:Leonidas_J._Guibas
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
dbr:Fractional_cascading
rdf:type
yago:Act100030358 yago:Cognition100023271 yago:PsychologicalFeature100023100 yago:DataStructure105728493 yago:Abstraction100002137 dbo:TopicalConcept yago:Procedure101023820 yago:Arrangement105726596 yago:WikicatGeometricDataStructures yago:Activity100407535 yago:Structure105726345 yago:WikicatGraphDataStructures yago:YagoPermanentlyLocatedEntity yago:WikicatSearchAlgorithms yago:Event100029378 yago:Algorithm105847438 yago:Rule105846932
rdfs:label
Fractional cascading Algoritmo Fractional Cascading Fractional Cascading
rdfs:comment
In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standard for binary searches, but successive searches in the sequence are faster. The original version of fractional cascading, introduced in two papers by Chazelle and Guibas in 1986 , combined the idea of cascading, originating in range searching data structures of and , with the idea of fractional sampling, which originated in . Later authors introduced more complex forms of fractional cascading that allow the data structure to be maintained as the data changes by a sequence of discrete insertion and deletion events. Fractional Cascading bietet die Möglichkeit, die Bereichssuche in einem Bereichsbaum schneller zu gestalten. Dabei wird der jeweils höchstdimensionale assoziierte Baum nicht als Baum, sondern als Array gespeichert. Von jedem Element des Arrays gehen Verweise auf gleich große bzw. größere Schlüsselwerte in den beiden Sohnarrays. Durch Verfolgen dieser Verweise kann in O(1+k) in dem Baum gesucht werden. En ciencias de la computación , el algoritmo Fractional Cascading es una técnica para acelerar una secuencia de búsquedas binarias para el mismo valor en una secuencia de estructuras de datos relacionados. La primera búsqueda binaria en la secuencia toma una cantidad logarítmica de tiempo, como es estándar para las búsquedas binarias, pero las búsquedas sucesivas en la secuencia son más rápidas. La versión original de Fractional Cascading, presentada en dos artículos por Chazelle y Guibas en 1986 ( Chazelle y Guibas 1986a ; Chazelle y Guibas 1986b ), combinó la idea de la cascada, surgida de las estructuras de datos para búsquedas de rango de Lueker (1978) y Willard (1978), con la idea de muestreo fraccionado, que se originó en Chazelle (1983). Más tarde autores introdujeron formas más com
foaf:depiction
n7:Convex_layers_halfspace.svg
dct:subject
dbc:Search_algorithms dbc:Geometric_data_structures dbc:Graph_data_structures
dbo:wikiPageID
7543270
dbo:wikiPageRevisionID
1044892323
dbo:wikiPageWikiLink
dbc:Search_algorithms dbr:Point_location dbr:Packet_filter dbr:Directed_graph dbr:Computer_science dbr:Internet_router dbr:Computational_geometry dbc:Geometric_data_structures dbr:Range_search dbr:Sequential_search dbr:Bernard_Chazelle dbr:Binary_search dbc:Graph_data_structures dbr:Convex_hull dbr:Convex_layers n25:Convex_layers_halfspace.svg dbr:Convex_polygon dbr:B-tree dbr:Van_Emde_Boas_tree dbr:Range_searching dbr:Path_(graph_theory) dbr:Half-plane dbr:Range_reporting dbr:Leonidas_J._Guibas dbr:Vertex_(graph_theory) dbr:Sensor_network
dbo:wikiPageExternalLink
n5:monotone-point-loc.pdf n9:wads07.pdf n12:fractional_cascading_IPSN.pdf n23:yap-56333.ps.gz n24:pfhsn99.pdf n26:FilteringSearch.pdf n28:ffc-and-apps-tr.pdf n29:pfhsn99.pdf n30:FClowerbounds.pdf n30:FractionalCascading1.pdf n31:DTIC_ADA110139 n30:FractionalCascading2.pdf n30:ConvexLayers.pdf
owl:sameAs
freebase:m.0264yr4 dbpedia-fa:آبشاره‌سازی_جزءبه‌جزء dbpedia-es:Algoritmo_Fractional_Cascading n19:SWHT dbpedia-de:Fractional_Cascading wikidata:Q1440360 yago-res:Fractional_cascading
dbp:wikiPageUsesTemplate
dbt:Harvtxt dbt:Citation dbt:Harvnb dbt:Harvid dbt:Refend dbt:Refbegin
dbo:thumbnail
n7:Convex_layers_halfspace.svg?width=300
dbo:abstract
In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standard for binary searches, but successive searches in the sequence are faster. The original version of fractional cascading, introduced in two papers by Chazelle and Guibas in 1986 , combined the idea of cascading, originating in range searching data structures of and , with the idea of fractional sampling, which originated in . Later authors introduced more complex forms of fractional cascading that allow the data structure to be maintained as the data changes by a sequence of discrete insertion and deletion events. Fractional Cascading bietet die Möglichkeit, die Bereichssuche in einem Bereichsbaum schneller zu gestalten. Dabei wird der jeweils höchstdimensionale assoziierte Baum nicht als Baum, sondern als Array gespeichert. Von jedem Element des Arrays gehen Verweise auf gleich große bzw. größere Schlüsselwerte in den beiden Sohnarrays. Durch Verfolgen dieser Verweise kann in O(1+k) in dem Baum gesucht werden. En ciencias de la computación , el algoritmo Fractional Cascading es una técnica para acelerar una secuencia de búsquedas binarias para el mismo valor en una secuencia de estructuras de datos relacionados. La primera búsqueda binaria en la secuencia toma una cantidad logarítmica de tiempo, como es estándar para las búsquedas binarias, pero las búsquedas sucesivas en la secuencia son más rápidas. La versión original de Fractional Cascading, presentada en dos artículos por Chazelle y Guibas en 1986 ( Chazelle y Guibas 1986a ; Chazelle y Guibas 1986b ), combinó la idea de la cascada, surgida de las estructuras de datos para búsquedas de rango de Lueker (1978) y Willard (1978), con la idea de muestreo fraccionado, que se originó en Chazelle (1983). Más tarde autores introdujeron formas más complejas de Fractional Cascading que permiten que la estructura de datos se mantenga, como los cambios en los datos por una secuencia de eventos de inserción y eliminación discretos.
gold:hypernym
dbr:Technique
prov:wasDerivedFrom
wikipedia-en:Fractional_cascading?oldid=1044892323&ns=0
dbo:wikiPageLength
24881
foaf:isPrimaryTopicOf
wikipedia-en:Fractional_cascading
Subject Item
dbr:Herbert_Edelsbrunner
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
dbr:Range_searching
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
dbr:Segment_tree
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
dbr:Point_location
dbo:wikiPageWikiLink
dbr:Fractional_cascading
Subject Item
wikipedia-en:Fractional_cascading
foaf:primaryTopic
dbr:Fractional_cascading