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.

PropertyValue
dbpprop: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 based on a similar idea in range searching data structures of Lueker (1978) and Willard (1978), handled static data only. 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 gleichgroße bzw. größere Schlüsselwerte in den beiden Sohnarrays. Durch Verfolgen dieser Verweise kann in O(1+k) in dem Baum gesucht werden.
dbpprop:hasPhotoCollection
dbpprop:reference
dbpprop:relatedInstance
rdf:type
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.
  • 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 gleichgroße bzw. größere Schlüsselwerte in den beiden Sohnarrays. Durch Verfolgen dieser Verweise kann in O(1+k) in dem Baum gesucht werden.
rdfs:label
  • Fractional cascading
  • Fractional Cascading
owl:sameAs
skos:subject
foaf:page
is owl:sameAs of