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 9 of 9 for “"word RAM"”.
-
Space Efficient Data Structures and Algorithms in the Word-RAM Model
… the volume of data-sets has increased dramatically. Since the majority of these data-sets are stored in internal memory, reducing their storage requirement is an important research topic. One way of reducing storage is using succinct and compact data structures which maintain the data in …
-
Space-Efficient Data Structures in the Word-RAM and Bitprobe Models
This thesis studies data structures in the word-RAM and bitprobe models, with an emphasis on space efficiency. In the word-RAM model of computation the space cost of a data structure is measured in terms of the number of w-bit words stored in memory, and the cost of answering a query is measured in …
-
Adaptive Algorithms for Weighted Queries on Weighted Binary Relations and Labeled Trees
Keyword queries are extremely easy for a user to write. They have become a standard way to query for information in web search engines and most other information retrieval systems whose users are usually laypersons and might not have knowledge about the database schema or contained data. As keyword …
-
Performance of the Ultra-Wide Word Model
The Ultra-wide word model of computation (UWRAM) is an extension of the Word-RAM model which has an ALU that can operate on w^2 bits at a time, where w is the size in bits of a cell in memory. The purpose of this thesis is to explore the applicability of the UWRAM model, particularly when compared …
-
Path Queries in Weighted Trees
… that answers queries in O(lg σ) time under the word RAM model. This greatly improves previous results on the same problem, as previous data structures achieving O(lg n) query time use O(n lg^2 n) space, and previous linear space data structures require O(n^ε) time to answer a query for any …
-
Algorithms and Data Structures for Geometric Intersection Query Problems
… are built for the internal memory model (word-RAM or pointer machine model), but in some settings they are generic enough to be efficient in the I/O-model as well.
-
Models for Parallel Computation in Multi-Core, Heterogeneous, and Ultra Wide-Word Architectures
… the decreasing costs and increasing programmability of Graphic Processing Units (GPUs) have made these an accessible source of parallel processing power in general purpose computing. Among the many research challenges that this scenario has raised are the fundamental problems related to …
-
Adaptive Range Counting and Other Frequency-Based Range Query Problems
… range counting problem under the w-bit word RAM model. The query time of an adaptive range counting data structure is sensitive to k, the number of points being counted. We give an adaptive data structure that requires O(n loglog n) space and O(loglog n + log_w k) query time. …
-
In-Memory Storage for Labeled Tree-Structured Data
… with efficient query time. We assume the word RAM model with word size w, which permits random accesses to w-bit memory cells. Our data structures are space-efficient and many of them are even succinct. These succinct data structures occupy space close to the information theoretic lower …