Fractional cascading (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (es) 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. (de) 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. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Convex_layers_halfspace.svg?width=300 |
| dbo:wikiPageExternalLink | https://www3.cs.stonybrook.edu/~jgao/paper/fractional_cascading_IPSN.pdf https://archive.org/details/DTIC_ADA110139 http://www.cs.princeton.edu/~chazelle/pubs/ConvexLayers.pdf http://www.cs.princeton.edu/~chazelle/pubs/FClowerbounds.pdf http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading1.pdf http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading2.pdf https://www.acsu.buffalo.edu/~mblanton/publications/wads07.pdf https://graphics.stanford.edu/courses/cs268-11-spring/manuals/monotone-point-loc.pdf http://www.cccg.ca/proceedings/2001/yap-56333.ps.gz http://www1.bell-labs.com/user/mbuddhikot/psdocs/pfhsn99.pdf https://web.archive.org/web/20041020183845/http:/www.bell-labs.com/user/mbuddhikot/psdocs/pfhsn99.pdf http://www.umiacs.umd.edu/~joseph/ffc-and-apps-tr.pdf https://www.cs.princeton.edu/~chazelle/pubs/FilteringSearch.pdf |
| dbo:wikiPageID | 7543270 (xsd:integer) |
| dbo:wikiPageLength | 24881 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1044892323 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bernard_Chazelle dbr:Van_Emde_Boas_tree dbc:Search_algorithms dbr:Convex_hull dbr:Convex_layers dbr:Convex_polygon dbr:Computational_geometry dbr:Computer_science dbr:Leonidas_J._Guibas dbr:Path_(graph_theory) dbr:B-tree dbc:Geometric_data_structures dbr:Packet_filter dbr:Directed_graph dbr:Range_searching dbc:Graph_data_structures dbr:Half-plane dbr:Vertex_(graph_theory) dbr:Point_location dbr:Range_reporting dbr:Internet_router dbr:Range_search dbr:Binary_search dbr:Sensor_network dbr:Sequential_search dbr:File:Convex_layers_halfspace.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Refbegin dbt:Refend dbt:Harvid dbt:Harvnb |
| dct:subject | dbc:Search_algorithms dbc:Geometric_data_structures dbc:Graph_data_structures |
| gold:hypernym | dbr:Technique |
| rdf:type | dbo:TopicalConcept yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricDataStructures yago:WikicatGraphDataStructures yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Structure105726345 |
| rdfs:comment | 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. (de) 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. (en) 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 (es) |
| rdfs:label | Fractional Cascading (de) Algoritmo Fractional Cascading (es) Fractional cascading (en) |
| owl:sameAs | freebase:Fractional cascading yago-res:Fractional cascading wikidata:Fractional cascading dbpedia-de:Fractional cascading dbpedia-es:Fractional cascading dbpedia-fa:Fractional cascading https://global.dbpedia.org/id/SWHT |
| prov:wasDerivedFrom | wikipedia-en:Fractional_cascading?oldid=1044892323&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Convex_layers_halfspace.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Fractional_cascading |
| is dbo:wikiPageWikiLink of | dbr:Binary_search_algorithm dbr:Persistent_data_structure dbr:Vijay_Vaishnavi dbr:Range_tree dbr:Convex_layers dbr:Dan_Willard dbr:Range_query_(data_structures) dbr:Leonidas_J._Guibas dbr:Herbert_Edelsbrunner dbr:Range_searching dbr:Segment_tree dbr:Point_location |
| is foaf:primaryTopic of | wikipedia-en:Fractional_cascading |
