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 14 of 14 for “"succinct data structures"”.

  1. Succinct Data Structures

    The world is drowning in data. The recent explosion of web publishing, XML data, bioinformation, scientific data, image data, geographical map data, and even email communications has put a strain on our ability to manage the information contained there. In general, the influx of massive data sets …

    duke Repository record for Succinct Data Structures (opens in a new tab)

  2. Succinct Data Structures for Chordal Graphs

    … graphs and give a n log n + o(n log n) bit data structure to answer the approximate distance query to within an additive constant of 1 in O(1) time. We study the problem of succinctly storing a static chordal graph to answer adjacency, degree, neighbourhood and shortest path queries. Let G …

    waterloo Repository record for Succinct Data Structures for Chordal Graphs (opens in a new tab)

  3. Succinct Data Structures for Parameterized Pattern Matching and Related Problems

    … size sigma <= n. Suffix tree is the ubiquitous data structure for answering a pattern matching query: report all the positions i in T such that T[i + k - 1] = P[k], 1 <= k <= |P|. Compressed data structures support pattern matching queries, using much lesser space than the suffix tree, mainly by …

    lsu-thes Repository record for Succinct Data Structures for Parameterized Pattern Matching and Related Problems (opens in a new tab)

  4. Space Efficient Data Structures and Algorithms in the Word-RAM Model

    In modern computation 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 …

    waterloo Repository record for Space Efficient Data Structures and Algorithms in the Word-RAM Model (opens in a new tab)

  5. In-Memory Storage for Labeled Tree-Structured Data

    In this thesis, we design in-memory data structures for labeled and weights trees, so that various types of path queries or operations can be supported 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 …

    waterloo Repository record for In-Memory Storage for Labeled Tree-Structured Data (opens in a new tab)

  6. Succinct and Compact Data Structures for Intersection Graphs

    This thesis designs space efficient data structures for several classes of intersection graphs, including interval graphs, path graphs and chordal graphs. Our goal is to support navigational operations such as adjacent and neighbourhood and distance operations such as distance efficiently while …

    waterloo Repository record for Succinct and Compact Data Structures for Intersection Graphs (opens in a new tab)

  7. On the Succinct Representation of Equivalence Classes

    … Lewenstein et al. showed that with no auxiliary data structure, a label space of size nlg(n) is necessary and sufficient to represent the equivalence relation. They also showed that if the labels were to be assigned from the set [n], a data structure of square root of n bits is necessary and …

    waterloo Repository record for On the Succinct Representation of Equivalence Classes (opens in a new tab)

  8. Space-efficient data structures for string searching and retrieval

    … document retrieval problem is to maintain D as a data structure, such that when ever a query Q=(P, k) comes, we can report (the identifiers of) those k documents that are most relevant to the pattern P (of p characters). The relevance of a document d_r with respect to a pattern P is captured by …

    lsu-thes Repository record for Space-efficient data structures for string searching and retrieval (opens in a new tab)

  9. Enhancing space and time efficiency of genomics in practice through sophisticated applications of the FM-Index

    Genomic sequence data has become so easy to get that the computation to process it has become a bottleneck in the advancement of biological science. A data structure known as the FM-Index both compresses data and allows efficient querying, thus can be used to implement more efficient processing …

    colostate Repository record for Enhancing space and time efficiency of genomics in practice through sophisticated applications of the FM-Index (opens in a new tab)

  10. Space-efficient data sketching algorithms for network applications

    … applications. Sketching algorithms “encode” data into succinct data structures that can later be accessed and “decoded” for various purposes, such as network measurement, accounting, anomaly detection and etc. Bloom filters and counter braids are two well-known representatives in this …

    gatech Repository record for Space-efficient data sketching algorithms for network applications (opens in a new tab)

  11. Succinct Indexes

    This thesis defines and designs succinct indexes for several abstract data types (ADTs). The concept is to design auxiliary data structures that ideally occupy asymptotically less space than the information-theoretic lower bound on the space required to encode the given data, and support an …

    waterloo Repository record for Succinct Indexes (opens in a new tab)

  12. Algorithms for efficient sensitive search and sample comparison on petabase-scale genomics data

    … communities of microorganisms. Much of these data are deposited in data banks in the form of short inexact sequence fragments which traditionally needed to be assembled into longer genome fragments before they could be analysed. Due to both the limited computational capacity to assemble …

    ethz Repository record for Algorithms for efficient sensitive search and sample comparison on petabase-scale genomics data (opens in a new tab)

  13. Compact Routing on Planar Graphs

    … emphasis on the utilization of space-efficient data structures. Our investigation primarily targets connected, undirected, static pointer planar graphs, focusing on scenarios where queries predominantly start or end at a select subset of nodes. The shortest path problem, central to our study, …

    waterloo Repository record for Compact Routing on Planar Graphs (opens in a new tab)