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
 threedimensional
 threeway merge sort
 threeway radix quicksort: see multikey Quicksort
 timeconstructible function
 time/space complexity
 topdown radix sort
 topdown 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
 TurboBM
 Turbo Reverse Factor
 Turing machine
 Turing reduction
 Turing transducer
 twin grid file
 2choice hashing
 twodimensional
 2left hashing
 twolevel grid file
 234 tree
 23 tree
 Two Way algorithm
 twoway linked list: see doubly linked list
 twoway 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 × 2^{nk}.
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 3way 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 ...)
kary 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 3639, 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 1126.
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 otherwiseempty left child link to refer to the node's inorder predecessor and an empty right child link to refer to its inorder 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
threedimensional
(definition)
Definition:
Dealing with or restricted to a space in which location can be completely described with exactly three orthogonal axes.
Author: PEB
threeway merge sort
(algorithm)
Definition:
A kway merge sort which uses three input and three output streams.
Author: ASK
timeconstructible 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 2721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
topdown 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 621, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 l1 whose union gives the vertex cluster the node represents.
Note:
From Algorithms and Theory of Computation Handbook, page 811, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2620, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 n1 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 singleelimination 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 8613, 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 223226.
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 2^{n}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 n1 disks from post A to C, 2) move the n^{th} disk from A to B, and 3) recursively move the n1 disks from C to B. A solution using iteration is: on oddnumbered moves, move the smallest disk clockwise. On evennumbered 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:131137, 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 selforganizing 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 d_{ik} > d_{ij} + d_{jk} for some i, j, k, there is no possible polynomial time algorithm which guarantees nearoptimal result (unless P=NP). If the triangle inequality holds, you can quickly get a nearoptimal solution by finding the minimum spanning tree. Convert the tree to a path by traversing the tree, say by depthfirst 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:464497 (1996). Also in 30th Annual Symposium on Foundations of Computer Science, pages 540545, Research Triangle Park, North Carolina, 30 October1 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, Btree, 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,CRCA
tree automaton
(definition)
Definition:
An extension of a finite state machine that operates on nary 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 topdown (starting from the root) or bottomup (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 0ary constructor, the end of the word. Nondeterministic topdown and bottomup automata, and deterministic bottomup automata are equivalent, but topdown 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 4739, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
treesort (1)
(algorithm)
Definition:
A sort algorithm that first builds a binary search tree of the keys, then accesses the keys with an inorder traversal.
Generalization (I am a kind of ...)
sort.
Aggregate child (... is a part of or used in me.)
binary search tree, inorder 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, inorder traversal, postorder traversal, levelorder traversal.
Author: PEB
More information
Demonstration of preorder, inorder, 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 edgeweighted graphs have better approximation algorithms if the problem is restricted to weights satisfying the triangle inequality. From Algorithms and Theory of Computation Handbook, page 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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:295298, March 1959. Edward Fredkin, Trie Memory, CACM, 3(9):490499, 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 readwrite 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 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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
2choice 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 averagecase cost of a successful search is O(2 + (m1)/n), where m is the number of keys and n is the size of the array. The most collisions is log_{2} 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 "2way 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 realtime 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 2left and 2choice hashing.
Author: PEB
More information
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal, Balanced Allocations, SIAM J. Comput. 29(1):180200, 1999. An earlier version appeared in STOC 1994.
twodimensional
(definition)
Definition:
Dealing with or restricted to a plane. An organization where location can be completely described with exactly two orthogonal axes.
Author: PEB
2left hashing
(data structure)
Definition:
A dictionary implemented with two hash tables of equal size, T_{1} and T_{2}, and two different hash functions, h_{1} and h_{2}. A new key is put in table 2 only if there are fewer (colliding) keys at T_{2}[h_{2}(key)] than at T_{1}[h_{1}(key)], otherwise it is put in table 1. With n keys and two tables of size n/2, the most collisions is 0.69... log_{2} 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 realtime 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 2choice hashing? Michael Mitzenmacher, who extensively studied and analyzed 2left and 2choice hashing, provides the intuition that no location increases the maximum number of collisions until both of the pair has the same number. But alwaysgoleft keeps one half more loaded.
Author: PEB
More information
Berthold Vöcking, How Asymmetry Helps Load Balancing, Journal of the ACM, 50(4):568589, July 2003. A preliminary version appeared in FOCS 1999.
twolevel 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
234 tree
(data structure)
Definition:
A Btree of order 4, that is, internal nodes have two, three, or four children.
Generalization (I am a kind of ...)
Btree with m=4.
Author: PEB
23 tree
(data structure)
Definition:
A Btree of order 3, that is, internal nodes have two or three children.
Generalization (I am a kind of ...)
Btree with m=3.
Author: PEB
Two Way algorithm
(algorithm)
Definition: Partition ("factor") the pattern, x, into left, x_{l}, and right, x_{r}, parts in such a way to optimize searching. Compare x_{r} left to right then, if it matches, compare x_{l} 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, Twoway stringmatching, Journal of the ACM, 38(3):651675, July 1991.
twoway merge sort
(algorithm)
Definition:
A kway 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
