Space-efficient substring occurrence estimation

DOI10.1007/S00453-014-9936-YMaRDI QIDQ261345zbMATH OpenOpenAlexFDO

Authors Alessio Orlandi, Rossano Venturini

Publication date 23 March 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-014-9936-y

zbMATH Keywords

data structurescompressed full-text indexingfull-text indexingpattern matching

Mathematics Subject Classification ID

Data structures (68P05) Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Recommendations

• Generalized substring selectivity estimation
• Combinatorial Pattern Matching
• Position-Restricted Substring Searching
• Indexing compressed text
• One-dimensional and multi-dimensional substring selectivity estimation

Cites work

• scientific article; zbMATH DE number 1688373 (Why is no real title available?)
• scientific article; zbMATH DE number 756768 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• Alphabet partitioning for compressed rank/select and applications
• An analysis of the Burrows-Wheeler transform
• Cache-oblivious algorithms
• Compressed Cache-Oblivious String B-tree
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressed representations of sequences and full-text indexes
• Compressed text indexes, from theory to practice
• Efficient Storage and Retrieval by Content and Address of Static Files
• Fast prefix search in little space, with applications
• Fully-Compressed Suffix Trees
• Indexing compressed text
• New lower and upper bounds for representing sequences
• Space-efficient substring occurrence estimation
• Stronger Lempel-Ziv based compressed text indexing
• The compressed permuterm index
• The string B-tree

Cited in

(5)

• Space-efficient substring occurrence estimation
• Generalized substring selectivity estimation
• One-dimensional and multi-dimensional substring selectivity estimation
• Discovering subword associations in strings in time linear in the output size
• An encoding for order-preserving matching

Describes a project that uses

Uses Software

• PATRICIA

This page was built for publication: Space-efficient substring occurrence estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q261345)