upload
National Institute of Standards and Technology
Branche: Technology
Number of terms: 2742
Number of blossaries: 0
Company Profile:
The National Institute of Standards and Technology (NIST) — known between 1901 and 1988 as the National Bureau of Standards (NBS) — is a measurement standards laboratory and a non-regulatory agency of the United States Department of Commerce. The institute's official mission is to promote U.S. ...
A graph whose vertices and edges are subsets of another graph. Formal Definition: A graph G'&#61;(V', E') is a subgraph of another graph G&#61;(V, E) iff <ul> <li> V'⊆ V, and <li> E'⊆ E &and; ( (v<sub>1</sub>, v<sub>2</sub>)∈ E' → v<sub>1</sub>, v<sub>2</sub>∈ V'). </ul>
Industry:Computer science
A graph with no path that starts and ends at the same vertex.
Industry:Computer science
A group of analytical approaches having mathematically precise foundation which can serve as a framework or adjunct for human engineering and design skills and experience.
Industry:Computer science
A hash function that maps each different key to a distinct integer. Usually all possible keys must be known beforehand. A hash table that uses a perfect hash has no collisions. Formal Definition: A function f is perfect for a set of keys K iff ∀ j, k ∈ K f(j) &#61; f(k) → j &#61; k.
Industry:Computer science
A hash function that uses an auxiliary array, but no shift or exclusive-or (xor) operations.
Industry:Computer science
A hash function that uses the first p bits of the key times an irrational number. Formal Definition: h(k) &#61; ⌊ m(k A (mod 1))⌋, where m is usually an integer 2<sup>p</sup> and A is an irrational number (or an approximation thereto) 0 < A < 1. The modulo 1 operation removes the integer part of k × A.
Industry:Computer science
A hash table in which a collision is resolved by putting the item in the next empty place in the array following the occupied place. Even with a moderate load factor, primary clustering tends to slow retrieval.
Industry:Computer science
A hash table in which the hash function is the last few bits of the key and the table refers to buckets. Table entries with the same final bits may use the same bucket. If a bucket overflows, it splits, and if only one entry referred to it, the table doubles in size. If a bucket is emptied by deletion, entries using it are changed to refer to an adjoining bucket, and the table may be halved.
Industry:Computer science
A hash table that grows to handle more items. The associated hash function must change as the table grows. Some schemes may shrink the table to save space when items are deleted.
Industry:Computer science
A heap made of a forest of binomial trees with the heap property numbered k&#61;0, 1, 2, ..., n, each containing either 0 or 2<sup>k</sup> nodes. Each tree is formed by linking two of its predecessors, by joining one at the root of the other. The operations of insert a value, decrease a value, delete a value, and merge or join (meld) two queues take O(log n) time. The find minimum operation is a constant Θ(1).
Industry:Computer science