General Methods for Parallel Searching |
Contents
VALUEINDEPENDENT PARALLEL SEARCH | 10 |
III | 38 |
GENERATION OF INDEPENDENT MRELATIONS ON KEYS | 86 |
2 other sections not shown
Common terms and phrases
Algorithm 2a terminates application assume average cost average number b₁ b₂ balanced M-dimensional tree binary relation binary tree search bits centered binary search Chapter comparing the search completes the proof cost of Algorithm CP,k data structure defined efficient equal example expected value external node external path length hash function hash table implement initial eligible set k₁ k₂ key is contained key k keys chosen keys k₁ log₂ N)/M lower bound M-relation minpep number of items number of probes number of processors optimal search parallel processors parallel scatter table parallel search algorithm parallel sequential search partial order proof of Theorem scatter table search search key search policy search-sort M-tree second order clustering sequence function set of keys sorted list sorted partial-list statistically independent storage requirements subsets subtree terminates successfully Theorem 2.5 threaded M-tree total ordering totally-ordered Typical unimodal function universal set