[go: up one dir, main page]

Prezza, 2018 - Google Patents

In-place sparse suffix sorting

Prezza, 2018

View PDF
Document ID
16683163040035818688
Author
Prezza N
Publication year
Publication venue
Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms

External Links

Snippet

Suffix arrays encode the lexicographical order of all suffixes of a text and are often combined with the Longest Common Prefix array (LCP) to simulate navigational queries on the suffix tree in reduced space. In space-critical applications such as sparse and compressed text …
Continue reading at epubs.siam.org (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30949—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures hash tables
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30964—Querying
    • G06F17/30979—Query processing
    • G06F17/30985—Query processing by using string matching techniques
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30952—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures using directory or table look-up
    • G06F17/30955—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures using directory or table look-up using more than one table in sequence, i.e. systems with three or more layers
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F19/00—Digital computing or data processing equipment or methods, specially adapted for specific applications
    • G06F19/10—Bioinformatics, i.e. methods or systems for genetic or protein-related data processing in computational molecular biology
    • G06F19/22—Bioinformatics, i.e. methods or systems for genetic or protein-related data processing in computational molecular biology for sequence comparison involving nucleotides or amino acids, e.g. homology search, motif or SNP [Single-Nucleotide Polymorphism] discovery or sequence alignment

Similar Documents

Publication Publication Date Title
Kociumaka et al. Internal pattern matching queries in a text and applications
Gawrychowski et al. Optimal dynamic strings
Adjeroh et al. The burrows-wheeler transform: data compression, suffix arrays, and pattern matching
Czech et al. Perfect hashing
Kempa et al. Dynamic suffix array with polylogarithmic queries and updates
Gawrychowski Optimal pattern matching in LZW compressed strings
Boffa et al. A “Learned” Approach to Quicken and Compress Rank/Select Dictionaries∗
Prezza In-place sparse suffix sorting
Grossi et al. The wavelet trie: maintaining an indexed sequence of strings in compressed space
Gog et al. Large-scale pattern search using reduced-space on-disk suffix arrays
Gawrychowski et al. Sparse suffix tree construction in optimal time and space
Ferragina et al. Fast string searching in secondary storage: Theoretical developments and experimental results
Kim et al. A compact index for Cartesian tree matching
Salson et al. A four-stage algorithm for updating a Burrows–Wheeler transform
Kanda et al. Dynamic path-decomposed tries
Bertram et al. Move-r: Optimizing the r-index
Maniscalco et al. Faster lightweight suffix array construction
Li et al. Dynamic dictionary with subconstant wasted bits per key
Yu Nearly optimal static Las Vegas succinct dictionary
Frieze et al. Greedy algorithms for the shortest common superstring that are asymptotically optimal
Prezza Optimal substring equality queries with applications to sparse text indexing
Rubinchik et al. Palindromic k-factorization in pure linear time
Giancarlo et al. From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
Poyias et al. Compact dynamic rewritable (CDRW) arrays
Lehmann et al. Modern Minimal Perfect Hashing: A Survey