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 53 for “"Search Trees"”.
-
Search trees on graphs
Search trees on graphs (STGs) are a far-reaching generalization of binary search trees (BSTs), where the key space is a graph instead of a totally ordered set. Intuitively, instead of comparing keys, we compare vertices, which tells us their relative position in the graph. STGs can alternatively be …
-
Group Operations for Concurrent Binary Search Trees
… 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. Constructing code …
-
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} represent the …
-
Bulk updates and cache sensitivity in search trees
This thesis examines two topics related to binary search trees: cache-sensitive memory layouts and AVL-tree bulk-update operations. Bulk updates are also applied to adaptive sorting. Cache-sensitive data structures are tailored to the hardware caches in modern computers. The thesis presents a …
-
New Analytical Methods for Online Binary Search Trees
… 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 access …
-
An Investigation of Self-Organizing Binary Search Trees
… 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 cost, on …
-
Selectable Heaps and Their Application to Lazy Search Trees
… Kaplan et al. can be applied on the heap-ordered trees of the classic Fibonacci heap to support the extraction in O(k \log(n/k)) amortized time. We then show selection is possible in a priority queue with optimal worst-case guarantees by applying heap-ordered tree selection on Brodal queues, …
-
An examination of fast similarity search trees with gating
… that are both generic and efficient. Traditional search algorithms that only check specified fields and keys are no longer effective. Tree-structured indexing techniques based on metric spaces are widely used to solve this problem. Unfortunately, these data structures can be slow as the …
-
Data discretization simplified: Randomized binary search trees for data preprocessing.
… 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 Na¨ıve …
-
Concurrency techniques for implementing efficient search trees in multicore systems
Concurrent search trees are one of the most popular and widely used family of data structures. They are used in applications where it is necessary to store a large volume of sorted data with the ability to efficiently search, insert, remove, as well as more advanced operations, such as range …
-
Adaptive long-range UAV flight planning using Monte Carlo search trees
An adaptive Monte Carlo tree search (MCTS) framework is presented for long-range, energy-aware trajectory planning and online re-planning of fixed-wing uncrewed aerial vehicles in dynamic environments. Mission planning is posed as a finite-horizon Markov decision process with a …
-
Performance Study of Concurrent Search Trees and Hash Algorithms on Multiprocessors Systems
… the performance of concurrent algorithms for B-trees and linear hashing. B-trees are widely used as an access method for large, single key, database files, stored in lexicographic order on secondary storage devices. Linear hashing is a fast and reliable hash algorithm, suitable for accessing …
-
A Study of Concurrent Data Structures
… tree data structures, in particular concurrent search trees. We have studied two concurrent search trees - concurrent AVL tree and concurrent counting-based tree (CBTree) and two concurrent queues - lock-free concurrent queue and two-lock concurrent queue. We implemented two variants of …
-
An Investigation and Implementation of Some Binary Search Tree Algorithms
… 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 algorithms are …
-
Tail behaviour and martingale convergence of random recursive structures and algorithms
… limit theorem 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 …
-
DEVELOPING A GAME FOR UNDERGRADUATE CS STUDENTS TO LEARN DATA STRUCTURES
… 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 non-game …
-
Potentials and limitations of visual methods for the exploration of complex data structures
… <br>Similarly, visualization can be a helpful research tool for the analysis of complex data structures and the algorithms operating on them. For a formal mathematical analysis, the right approach to the problem is often the most decisive step. A suitable visual representation of the structure …
-
Multi-way self-adjusting data structures: a general theory and some limitations
In Chapter 1, “Introduction: The Searching Problem,” we present a concise history of the searching problem, from the original divide-and-conquer, known intuitevely even to children, up to the formulation of contemporary concepts such as amortized analysis and competitiveness. Our own work focuses …
Page 1 of 3