Algorithms and Data Structures Glossary
(Starting with "T")
By
www.nist.gov,
Gaithersburg, Maryland, U.S.A.
paul
. black [at] nist . gov
http://www.nist.gov/dads
Become a member of TranslationDirectory.com at just
$12 per month (paid per year)
Advertisements:
Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously
T
- taco sort
- tail
- tail recursion
- target
- temporal logic
- terminal
- terminal node: see leaf
- ternary search tree
- text
- text searching: see string matching
- theta: see Θ
- threaded binary tree
- threaded tree
- three-dimensional
- three-way merge sort
- three-way radix quicksort: see multikey Quicksort
- time-constructible function
- time/space complexity
- top-down radix sort
- top-down tree automaton
- topological order
- topological sort
- topology tree
- total function
- totally decidable language: see decidable language
- totally decidable problem: see decidable problem
- totally undecidable problem
- total order
- tour: see Hamiltonian cycle
- tournament
- tournament sort
- towers of Hanoi
- tractable
- transition
- transition function
- transitive
- transitive closure
- transitive reduction
- transpose sequential search
- traveling salesman
- treap
- tree
- tree automaton
- tree contraction
- tree editing problem
- treesort (1)
- treesort (2)
- tree traversal
- triangle inequality
- triconnected graph
- trie
- trinary function
- tripartition
- TSP: see traveling salesman
- TST: see ternary search tree
- Turbo-BM
- Turbo Reverse Factor
- Turing machine
- Turing reduction
- Turing transducer
- twin grid file
- 2-choice hashing
- two-dimensional
- 2-left hashing
- two-level grid file
- 2-3-4 tree
- 2-3 tree
- Two Way algorithm
- two-way linked list: see doubly linked list
- two-way merge sort
taco sort
(algorithm)
Definition:
A terribly inefficient sort algorithm that repeatedly changes a random item by a random amount until a sorted permutation occurs. For an array of n elements of k bits each, the expected run time is n × 2nk.
Generalization (I am a kind of ...)
Las Vegas algorithm.
Note:
Michael Bernard "came up with tacosort while trying to create an algorithm that is even less efficient than bogosort." The run time is the same as exhaustive search.
Author: PEB
tail
(definition)
Definition:
(1) The last item of a list. (2) All but the first item of a list; the list following the head.
Note:
The first definition is common when building lists from other language constructs, such as C pointers. The second definition occurs in languages with primitive list types, such as ML or Lisp.
Author: PEB
tail recursion
(algorithmic technique)
Definition:
A special form of recursion where the last operation of a function is a recursive call. The recursion may be optimized away by executing the call in the current stack frame and returning its result rather than creating a new stack frame.
Note:
Although it may not save a lot of run time, it can save a lot of memory. The following finds the maximum value in a list. int max_list(list l, int max_so_far)
{
if (null == l) {
return max_so_far;
}
if (max_so_far < head(l)) {
return max_list(tail(l), head(l));
} else {
return max_list(tail(l), max_so_far);
}
} The return value of the current invocation is just the return value of the recursive call. A compiler could optimize it something like the following so it doesn't allocate new space for l and max_so_far on each invocation or tear down the stack on the returns.
int max_list(list l, int max_so_far)
{
for (;;) {
if (null == l) {
return max_so_far;
}
if (max_so_far < head(l)) {
max_so_far = head(l);
l = tail(l);
} else {
max_so_far = max_so_far;
l = tail(l);
}
}
} Now there is no need to allocate new memory for the parameters or get rid of it during the returns, so this will run faster. This code transformation is simple enough to do by hand in this example, but it is much harder for complex recursive data structures, such as trees.
Of course, if a compiler is good enough to find and rewrite tail recursion, it will also collapse the loop test, eliminate the assignment of max_so_far to itself, and hoist the assignment of l after the test giving the following:
int max_list(list l, int max_so_far)
{
while (null != l) {
if (max_so_far < head(l)) {
max_so_far = head(l);
}
l = tail(l);
}
return max_so_far;
}
Author: PEB
target
(definition)
Definition:
The vertex which an edge of a directed graph enters.
Note:
That is, an edge goes from the source to the target.
Author: PEB
temporal logic
(definition)
Definition:
A logic with a notion of time included. The formulas can express facts about past, present, and future states. The formulas are interpreted over Kripke structures, which can model computation; hence temporal logic is very useful in formal verification.
Author: SKS
terminal
(definition)
Definition:
The set of points in a plane or vertices in a graph defining endpoints of a Steiner tree.
Author: PEB
ternary search tree
(data structure)
Definition:
A 3-way tree where every node's left subtree has keys less than the node's key, every middle subtree has keys equal to the node's key, and every right subtree has keys greater than the node's key. If the key is a multikey (string, array, list, etc.), the middle subtree organizes by the next subkey (character, array or list item, etc.)
Also known as TST.
Generalization (I am a kind of ...)
k-ary tree with k=3, search tree.
Author: PEB
More information
Although not named, ternary search trees are described in
Jon Louis Bentley and James B. Saxe, Algorithms on Vector Sets, SIGACT News, pages 36-39, Fall 1979. Jon Bentley and Robert Sedgewick, Ternary Search Trees, Dr. Dobb's Journal, April 1998.
text
(definition)
Definition:
A list of characters, usually thought of as a list of words separated by spaces.
Note:
The term string usually refers to a small sequence of characters, such as a name or a sentence. The term text usually refers to a large sequence of characters, such as an article or a book.
See definition relating to string matching in Algorithms and Theory of Computation Handbook, page 11-26.
Author: PEB
threaded binary tree
(data structure)
Definition:
See threaded tree.
Note:
Although Knuth defines a threaded tree and a threaded binary tree in [Knuth97, 1:320, Sect. 2.3.1], the first term might refer to a threaded multiway tree.
Author: PEB
threaded tree
(data structure)
Definition:
A binary search tree in which each node uses an otherwise-empty left child link to refer to the node's in-order predecessor and an empty right child link to refer to its in-order successor.
Note:
See [Knuth97, 1:320, Sect. 2.3.1]. Although the definition could refer to a multiway tree, Knuth defines a threaded tree as a binary tree.
Author: PEB
three-dimensional
(definition)
Definition:
Dealing with or restricted to a space in which location can be completely described with exactly three orthogonal axes.
Author: PEB
three-way merge sort
(algorithm)
Definition:
A k-way merge sort which uses three input and three output streams.
Author: ASK
time-constructible function
(definition)
Definition:
A function t(n) that gives the actual running time of some Turing machine on all inputs of length n.
Note:
From Algorithms and Theory of Computation Handbook, page 27-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
time/space complexity
(definition)
Definition:
The maximum time or space required by a Turing machine on any input of length n.
Note:
From Algorithms and Theory of Computation Handbook, page 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
top-down radix sort
(algorithm)
Definition:
A recursive bucket sort where elements are distributed based on succeeding pieces (characters) of the key.
Generalization (I am a kind of ...)
bucket sort.
Specialization (... is a kind of me.)
postman's sort.
Aggregate child (... is a part of or used in me.)
recursion.
Note:
For the first pass, elements are distributed according to the first character. In the first recursive call, the elements in each bucket are distributed to new "subbuckets" according to the second character. Succeeding deeper recursions use corresponding succeeding characters. This is similar to radix sort, but works "top down" or "most significant digit first" while radix sort works "bottom up" or "least significant digit first". Also radix sort merges distributed items while this does not.
Author: PEB
topological order
(definition)
Definition:
A numbering of the vertices of a directed acyclic graph such that every edge from a vertex numbered i to a vertex numbered j satisfies i<j.
Note:
From Algorithms and Theory of Computation Handbook, page 6-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
topological sort
(definition)
Definition:
To arrange items when some pairs of items have no comparison, that is, according to a partial order.
Generalization (I am a kind of ...)
sort.
Aggregate child (... is a part of or used in me.)
partial order.
Note:
After [Leda98].
Author: PEB
topology tree
(definition)
Definition:
Tree that describes a balanced decomposition of another tree, according to its topology. More precisely, given a restricted multilevel partition for a tree T, a topology tree satisfies the following: (1) A topology tree node at level l represents a vertex cluster at level l in the restricted multilevel partition, and (2) A node at level l ≥ 1 has at most two children, representing the vertex clusters at level l-1 whose union gives the vertex cluster the node represents.
Note:
From Algorithms and Theory of Computation Handbook, page 8-11, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
total function
(definition)
Definition:
A function which is defined for all inputs of the right type, that is, for all of a domain.
Note:
Square (x²) is a total function. Reciprocal (1/x) is not, since 0 is a real number, but has no reciprocal.
Author: PEB
totally undecidable problem
(definition)
Definition:
A problem that cannot be solved by a Turing machine.
Note:
From Algorithms and Theory of Computation Handbook, page 26-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
total order
(definition)
Definition:
An order defined for all pairs of items of a set. For instance, ≤ (less than or equal to) is a total order on integers, that is, for any two integers, one of them is less than or equal to the other.
Formal Definition: A total order is a relation that is reflexive, transitive, antisymmetric, and total.
Also known as linear order.
Note:
Subset (⊆) is partial not total, since {a} is not a subset of {b}, nor is {b} a subset of {a}. The sets {a} and {b} are incomparable. How could an order be total, but not transitive? If it is cyclic, like in the game Paper, Scissors, Rock.
Authors: PEB,PJT
tournament
(algorithm)
Definition:
Find the maximum of a set of n elements in  log n "rounds" (passes) by "playing" (comparing) pairs of elements and advancing the winner (greater) of each pair to the next round. It takes n-1 comparisons, like linear search, but may be parallelized, extended to also find the second greatest element, etc.
Note:
The second greatest element can be found with log n - 1 additional comparisons.
Author: GS
tournament sort
(algorithm)
Definition:
(no definition here)
Note:Heapsort is sometimes called tournament sort. Consider the tree of matches in a single-elimination sports tournament, where players' abilities are a total order. The tournament tree has the heap property. When a winner is found (the least element is chosen), the winner is removed and the appropriate matches replayed. In Using Tournament Trees to Sort, Center for Advanced Technology in Telecommunications, Polytechnic University, Brooklyn, New York, C.A.T.T Technical Report 86-13, Alexander Stepanov and Aaron Kershenbaum extend the observation that a tournament can find the winner in N comparisons and the 2nd in log N more comparisons. An algorithm written up in 2002 also called a tournament sort.
More information
Kenneth E. Iverson, A Programming Language, John Wiley and Sons, 1962, pages 223-226.
towers of Hanoi
(classic problem)
Definition:
Given three posts (towers) and n disks of decreasing sizes, move the disks from one post to another one at a time without putting a larger disk on a smaller one. The minimum is 2n-1 moves. The "ancient legend" was invented by De Parville in 1884.
Note:
A solution using recursion is: to move n disks from post A to post B 1) recursively move the top n-1 disks from post A to C, 2) move the nth disk from A to B, and 3) recursively move the n-1 disks from C to B. A solution using iteration is: on odd-numbered moves, move the smallest disk clockwise. On even-numbered moves, make the single other move which is possible. [GCG92] gives generalizations of the puzzle, algorithms, and proofs.
Author: PEB
tractable
(definition)
Definition:
A problem which has an algorithm which computes all instances of it in polynomial time.
Author: PEB
transition
(definition)
Definition:
The change from one state to another in a finite state machine. Analogously, an edge in a directed graph.
Also known as state transition, move.
Author: PEB
transition function
(definition)
Definition:
A function of the current state and input giving the next state of a finite state machine or Turing machine.
Note:
This defines the set of transitions.
Author: PEB
transitive
(definition)
Definition:
A binary relation R for which a R b and b R c implies a R c.
Note:
The relation "less than" is transitive: if a < b and b < c, then a < c. The relation "is an ancestor of" is also transitive: if Reuben is an ancestor of Bill and Bill is an ancestor of Patrick, Reuben is an ancestor of Patrick. However "likes" is not transitive since someone I like may like someone that I don't like.
Author: PEB
transitive closure
(definition)
Definition:
An extension or superset of a binary relation such that whenever (a,b) and (b,c) are in the extension, (a,c) is also in the extension.
Author: SKS
transitive reduction
(definition)
Definition:
The transitive reduction of a directed graph G is the directed graph G' with the smallest number of edges such that for every path between vertices in G, G' has a path between those vertices.
Note:
Informally G' is the minimal graph with the same connectivity as G. After abstract of A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph. SIAM Journal on Computing, 1:131--137, 1972.
Author: PEB
transpose sequential search
(algorithm)
Definition:
Search an array or list by checking items one at a time. If the value is found, swap it with its predecessor so it is found faster next time.
Also known as self-organizing sequential search.
Note:
This moves more frequently searched items to the front. If a few items are sought much more often than the rest, this can save time. A binary search or hash table is almost always faster, though.
Author: PEB
traveling salesman
(classic problem)
Definition:
Find a path through a weighted graph which starts and ends at the same vertex, includes every other vertex exactly once, and minimizes the total cost of edges.
Also known as TSP.
Note:
Less formally, find a path for a salesman to visit every listed city at the lowest total cost. The above described path is always a Hamiltonian cycle, or tour, however a Hamiltonian cycle need not be optimal. The problem is an optimization problem, that is, to find the shortest tour. The corresponding decision problem asks if there is a tour with a cost less than some given amount. See [CLR90, page 969]. If the triangle inequality does not hold, that is dik > dij + djk for some i, j, k, there is no possible polynomial time algorithm which guarantees near-optimal result (unless P=NP). If the triangle inequality holds, you can quickly get a near-optimal solution by finding the minimum spanning tree. Convert the tree to a path by traversing the tree, say by depth-first search, but go directly to the next unvisited node, rather than repeating nodes. Christofides algorithm starts with a minimum spanning tree, but is more careful about converting the tree to a path with results closer to optimal.
Author: PEB
treap
(data structure)
Definition:
A binary search tree in which nodes have another key, called the priority. Operations also keep the nodes heap ordered with regard to the priority.
Generalization (I am a kind of ...)
binary search tree.
Specialization (... is a kind of me.)
randomized binary search tree.
Note:
The name comes from "tree" and "heap". Some call "randomized binary search trees" treaps, but strictly a treap does not define how priorities are assigned.
Author: PEB
More information
Raimund G. Seidel and Cecilia R. Aragon, Randomized Search Trees, Algorithmica, 16:464-497 (1996). Also in 30th Annual Symposium on Foundations of Computer Science, pages 540-545, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
tree
(data structure)
Definition:
(1) A data structure accessed beginning at the root node. Each node is either a leaf or an internal node. An internal node has one or more child nodes and is called the parent of its child nodes. All children of the same node are siblings. Contrary to a physical tree, the root is usually depicted at the top of the structure, and the leaves are depicted at the bottom. (2) A connected, undirected, acyclic graph. It is rooted and ordered unless otherwise specified.
Thanks to Joshua O'Madadhain (jmadden@ics.uci.edu) for the figure, 6 October 2005.
Formal Definition: (1) A tree is either - empty (no nodes), or
- a root and zero or more subtrees.
The subtrees are ordered.
Specialization (... is a kind of me.)
heap, B-tree, binary tree, balanced tree, multiway tree, complete tree, search tree, digital tree.
Note:
Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC. A tree in the data structure sense (1) is not the same as a tree in the graph sense (2). Consider possible binary trees with two nodes. There are two possible data structures: a root and a left subtree or a root and a right subtree. However there is only one possible graph: a root and a subtree. The graph definition doesn't allow for "the subtree is the right subtree and the left subtree is empty". Also there is no "empty" graph tree. Thanks to Sharat Chandran (sharat@cs.umd.edu) for clarifying the difference between these two senses. The formal definition is after [CLR90, page 94].
Authors: PEB,CRC-A
tree automaton
(definition)
Definition:
An extension of a finite state machine that operates on n-ary constructors. Where a finite state automaton reaches a new state with a single state and character, a tree automaton takes n states and constructors. Tree automata may be top-down (starting from the root) or bottom-up (starting from the leaves), and deterministic or nondeterministic.
Note:
Words for finite state automata can be seen as composed of unary constructors, the alphabet, and a 0-ary constructor, the end of the word. Nondeterministic top-down and bottom-up automata, and deterministic bottom-up automata are equivalent, but top-down automata are weaker.
Author: DM
tree contraction
(definition)
Definition:
Contracting a tree by removing some of the nodes.
Note:
From Algorithms and Theory of Computation Handbook, page 47-39, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
tree editing problem
(definition)
Definition:
The problem of finding an edit script of minimum cost which transforms a given tree into another given tree.
Note:
From Algorithms and Theory of Computation Handbook, page 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
treesort (1)
(algorithm)
Definition:
A sort algorithm that first builds a binary search tree of the keys, then accesses the keys with an in-order traversal.
Generalization (I am a kind of ...)
sort.
Aggregate child (... is a part of or used in me.)
binary search tree, in-order traversal.
Note:
For good performance, use a balanced binary search tree.
Author: PEB
treesort (2)
(algorithm)
Definition:
Variants of heapsort.
Generalization (I am a kind of ...)
heapsort.
Aggregate child (... is a part of or used in me.)
balanced binary search tree, heap.
Note:
The algorithms Floyd named treesort can be seen as developments leading to what we now call heapsort.
Author: PEB
More information
Robert W. Floyd, Algorithm 245 Treesort 3, CACM, 7(12):701, December 1964.
Robert W. Floyd, Algorithm 113 Treesort, CACM, 5(8):434, August 1962.
tree traversal
(definition)
Definition:
A technique for processing the nodes of a tree in some order.
Specialization (... is a kind of me.)
preorder traversal, in-order traversal, postorder traversal, level-order traversal.
Author: PEB
More information
Demonstration of preorder, in-order, and postorder traversal on a binary tree.
triangle inequality
(definition)
Definition:
The property that a complete weighted graph satisfies weight(u,v) ≤ weight(u,w) + weight(w,v) for all vertices u, v, w. Informally, the graph has no short cuts.
Note:
This holds for any graph representing points in a metric space. Many problems involving edge-weighted graphs have better approximation algorithms if the problem is restricted to weights satisfying the triangle inequality. From Algorithms and Theory of Computation Handbook, page 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
triconnected graph
(definition)
Definition:
A connected graph such that deleting any two vertices (and incident edges) results in a graph that is still connected.
Note:
After Tomas Rokicki <rokicki@instantis.com>, 24 December 2002. Informally, there are at least three independent paths from any vertex to any other vertex. After Paul M. Sant, 6 Sep 2000.
Author: PEB
trie
(data structure)
Definition:
A tree for storing strings in which there is one node for every common prefix. The strings are stored in extra leaf nodes.
Generalization (I am a kind of ...)
tree.
Specialization (... is a kind of me.)
bucket trie, Patricia tree, compact trie.
Note:
The name comes from reTRIEval and is pronounced, "tree." See the historical note.
There are many who, in an attempt to verbally distinguish a trie from the more general tree and in contrast to typical English pronunciation (of which calorie, eerie, and reverie are examples, but die, lie, and pie are not), pronounce the name "try".
Author: PEB
More information
Renee de la Briandais, File Searching Using Variable Length Keys, Proc. AFIPS Western Joint Computer Conference, San Francisco, California, USA, 15:295-298, March 1959. Edward Fredkin, Trie Memory, CACM, 3(9):490-499, September 1960.
Historical Note
On 31 July 2008 Edward Fredkin wrote As defined by me, nearly 50 years ago, it is properly pronounced "tree" as in the word "retrieval". At least that was my intent when I gave it the name "Trie". The idea behind the name was to combine reference to both the structure (a tree structure) and a major purpose (data storage and retrieval). Ed Fredkin
trinary function
(definition)
Definition:
A function with three arguments.
Author: PEB
tripartition
(algorithm)
Definition:
To partition array elements into three groups.
Author: PEB
Turing machine
(definition)
Definition:
A model of computation consisting of a finite state machine controller, a read-write head, and an unbounded sequential tape. Depending on the current state and symbol read on the tape, the machine can change its state and move the head to the left or right. Unless otherwise specified, a Turing machine is deterministic.
Note:
From Algorithms and Theory of Computation Handbook, page 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
More information
An article in the Stanford Encyclopedia of Philosophy.
Turing reduction
(definition)
Definition:
A reduction computable by an oracle Turing machine that halts for all inputs.
Note:
From Algorithms and Theory of Computation Handbook, page 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
twin grid file
(data structure)
Definition:
A point access method which is two simultaneous grid files. Points are shuffled between the primary and secondary file to minimize the total size.
Note:
After [GG98].
Author: PEB
2-choice hashing
(data structure)
Definition:
A variant of a hash table in which keys are added by hashing with two hash functions. The key is put in the array position with the fewer (colliding) keys. Some collision resolution scheme is needed, unless keys are kept in buckets. The average-case cost of a successful search is O(2 + (m-1)/n), where m is the number of keys and n is the size of the array. The most collisions is log2 ln n + Θ(m/n) with high probability.
Generalization (I am a kind of ...)
hash table.
Aggregate parent (I am a part of or used in ...)
dictionary.
Aggregate child (... is a part of or used in me.)
array, hash function.
Note:
Called "2-way chaining" in the paper.
Although the average lookup time is similar to a table with a single hash function, the maximum number of collisions is exponentially smaller. This make using buckets or use in real-time systems far more practical. Additional hash functions only decrease the maximum by a constant factor.
Buckets or lists can be searched in parallel. Michael Mitzenmacher extensively studied and analyzed 2-left and 2-choice hashing.
Author: PEB
More information
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal, Balanced Allocations, SIAM J. Comput. 29(1):180-200, 1999.
An earlier version appeared in STOC 1994.
two-dimensional
(definition)
Definition:
Dealing with or restricted to a plane. An organization where location can be completely described with exactly two orthogonal axes.
Author: PEB
2-left hashing
(data structure)
Definition:
A dictionary implemented with two hash tables of equal size, T1 and T2, and two different hash functions, h1 and h2. A new key is put in table 2 only if there are fewer (colliding) keys at T2[h2(key)] than at T1[h1(key)], otherwise it is put in table 1. With n keys and two tables of size n/2, the most collisions is 0.69... log2 ln n + O(1) with high probability.
Generalization (I am a kind of ...)
hash table.
Aggregate parent (I am a part of or used in ...)
dictionary.
Aggregate child (... is a part of or used in me.)
array, hash function.
Note:
The name comes from the notion of dividing a single hash table in two, left and right halves of equal sizes, and always putting the key in the left half on ties.
Although the average lookup time is similar to a table with a single hash function, the maximum number of collisions is exponentially smaller. This make using buckets or use in real-time systems far more practical. Additional hash functions only decrease the maximum by a constant factor.
Buckets or lists can be searched in parallel. Why would breaking a single hash table into two pieces and asymmetrically resolving ties keep the maximum number of collisions lower than the single table of 2-choice hashing? Michael Mitzenmacher, who extensively studied and analyzed 2-left and 2-choice hashing, provides the intuition that no location increases the maximum number of collisions until both of the pair has the same number. But always-go-left keeps one half more loaded.
Author: PEB
More information
Berthold Vöcking, How Asymmetry Helps Load Balancing, Journal of the ACM, 50(4):568-589, July 2003.
A preliminary version appeared in FOCS 1999.
two-level grid file
(data structure)
Definition:
A point access method which is two levels of grid files. The first level addresses second level grid files.
Note:
After [GG98].
Author: PEB
2-3-4 tree
(data structure)
Definition:
A B-tree of order 4, that is, internal nodes have two, three, or four children.
Generalization (I am a kind of ...)
B-tree with m=4.
Author: PEB
2-3 tree
(data structure)
Definition:
A B-tree of order 3, that is, internal nodes have two or three children.
Generalization (I am a kind of ...)
B-tree with m=3.
Author: PEB
Two Way algorithm
(algorithm)
Definition: Partition ("factor") the pattern, x, into left, xl, and right, xr, parts in such a way to optimize searching. Compare xr left to right then, if it matches, compare xl right to left.
Generalization (I am a kind of ...)
string matchingalgorithm.
Note:
[It] "can be viewed as an intermediate between the classical algorithms of Knuth, Morris, and Pratt on the one hand and Boyer and Moore, on the other hand."
Author: PEB
More information
Maxime Crochemore and Dominique Perrin, Two-way string-matching, Journal of the ACM, 38(3):651-675, July 1991.
two-way merge sort
(algorithm)
Definition:
A k-way merge sort that sorts a data stream using repeated merges. It distributes the input into two streams by repeatedly reading a block of input that fits in memory, a run, sorting it, then writing it to the next stream. It merges runs from the two streams into an output stream. It then repeatedly distributes the runs in the output stream to the two streams and merges them until there is a single sorted output.
Note:
This is an external sort.
Author: ASK
Published - April 2009
Find free glossaries at TranslationDirectory.com
Find free dictionaries at TranslationDirectory.com
Subscribe to free TranslationDirectory.com newsletter
Need more translation jobs from translation agencies? Click here!
Translation agencies are welcome to register here - Free!
Freelance translators are welcome to register here - Free!
Submit your glossary or dictionary for publishing at TranslationDirectory.com
|
