Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 130 for “"Binary Search"”.
-
Lock-free Self-adjusting Binary Search Tree
A binary search tree (BST) is a fundamental data structure for maintaining data in a way to allow fast search. As multi-core processors are widely used nowadays, such data structures require the ability to handle concurrent accesses to exploit the concurrent hardware. There are several algorithms …
-
Self-stabilizing binary search tree maintenance algorithm
Binary search tree is one of the most studied data structures. The main application of the binary search tree is in implementing efficient search operations. A binary search tree is a special binary tree which satisfies the property that for every processor p in the binary tree, the values of all …
-
Group Operations for Concurrent Binary Search Trees
… operation might look up 10 different keys in a binary search tree, returning 10 results. Chen et al introduced group prefetching, an optimization for group operations on linked data structures that improves throughput by overlapping memory access latencies for independent traversals. …
-
Formal verification of a concurrent binary search tree
… version of the non-blocking linearizable binary search tree of Ellen et al., which appeared in the Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing (pages 131-140), using the PVS specification and verification system. The algorithm and its specification …
-
New Analytical Methods for Online Binary Search Trees
This thesis aims to analyze the costs of various binary search tree (BST) algorithms. BST is one of the most fundamental data structures. The long-standing dynamic optimality conjecture states that there exists an online self-adjusting BST algorithm such that, starting with any initial tree, its …
-
An Investigation of Self-Organizing Binary Search Trees
… computational cost of retrieving records from a binary search tree.</p> <p> No knowledge of the probabilities with which these records are requested is assumed. The aim of each method is to gradually restructure an initial, arbitrary (and perhaps costly) tree into one which has minimal search …
-
Data discretization simplified: Randomized binary search trees for data preprocessing.
… discretization method based upon a randomized binary search tree that provides the sorting routine as one of the properties of inserting into the data structure. We then provide an experimental design to compare our simple discretization method against common methods used prior to learning with …
-
An Investigation and Implementation of Some Binary Search Tree Algorithms
… documents the results of an investigation into binary search trees. Because of their favourable characteristics binary search trees have become popular for information storage and retrieval applications in a one level store. The trees may be of two types, weighted and unweighted. Various …
-
Self Adjusting Contention Friendly Concurrent Binary Search Tree by Lazy Splaying
… a partial blocking implementation of concurrent binary search tree data structure that is contention friendly, fast and scales well. It uses a technique, called lazy splaying to move frequently accessed items close to the root without making the root of the tree a sequential bottleneck. Most of …
-
A study of a modified binary search for use in sensitivity testing
A modified binary search routine was developed by Tysver to provide inputs (estimates of parameters of threshold stimulus distributions) to the Probit and Staircase techniques for sensitivity testing. A high speed digital computer was used to provide simulated sensitivity data in order to test the …
-
Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts
… permute a sorted array into the level-order binary search tree (BST), level-order B-tree (B-tree), and van Emde Boas (vEB) layouts in-place. We analytically determine the complexity of our algorithms and empirically measure their performance. Given N elements and P processors, our fastest …
-
An evaluation of a modified binary search procedure for use with the Bruceton method in sensitivity testing
… procedure while the second used a modified binary search routine with a portion of the sample in order to obtain maximum likelihood estimates of the input parameters for use in a follow-on Bruceton test. The results showed both methods to be effective in estimating the mean but with slightly …
-
DEVELOPING A GAME FOR UNDERGRADUATE CS STUDENTS TO LEARN DATA STRUCTURES
… exhibited by the fundamental concepts. The Binary Search Tree is cited as one of<br/>the most challenging data structures to learn.<br/>To address the challenges faced by students, this research proposes the use of gamification in education, which involves incorporating game elements into …
-
Tail behaviour and martingale convergence of random recursive structures and algorithms
… for the profile of a class of trees, including binary search trees and random recursive trees, is proven. This result is obtained by embedding these discrete-time trees in a continuous-time weighted tree model and by using corresponding martingales. The third part is concerned with the proof of …
-
Converting circle-packing algorithms to work on the MasPar-2
… author explores three different algorithms, a binary search, a monotone binary search and a Newton's method algorithm. Two variables within the algorithms, factor and iterations, are adjusted to attempt to find the most efficient combination of variable for a particular algorithm. To best …
-
Vyhledání nejdelšího shodného prefixu
… síťový protokol verze 6. Jsou vybrány algoritmy Binary Trie, Level Compressed Trie, Lulea Compressed Trie a Binary Search on Intervals, které jsou nejdříve popsány a poté testovány s cílem najít nejvhodnější algoritmus z hlediska pamětových nároků a rychlosti vyhledání.
-
Approximately Optimum Search Trees in External Memory Models
… and near optimal solutions to the classic binary search tree problem of Knuth. We are given a set of n keys (originally known as words), B_1, B_2, ..., B_n and 2n+1 frequencies. {p_1, p_2, ..., p_n} represent the probabilities of searching for each given key, and {q_0, q_1, ..., q_n} …
-
The enhanced binary single machine equivalent method for transient stability limit searching
This thesis proposes the novel Enhanced Binary Single-Machine Equivalent Method (EBSIME) to provide a fast, robust and systematic approach to search for the transient stability limits (TSLs) of multi-machine power systems. The algorithm is an extension of the SIME method [1] and provides an …
-
An Investigation of Some New Tree Structures
… of the above tree structures and the well known binary search tree is presented for exact match queries.</p> <p>An implementation of the insertion algorithms for each tree structure and a generalization of Aldon Walker's (9) display algorithm are given.</p>
Page 1 of 7