Internal masked prefix sums and its connection to fully internal measurement queries

DOI10.1007/978-3-031-20643-6_16zbMath1525.68038MaRDI QIDQ6111587

J. Ian Munro, Eitan Kondratovsky, Kaiyu Wu, Meng He, Rathish Das

Publication date: 4 August 2023

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Algorithms on strings (68W32)

Cites Work

• Fast set intersection and two-patterns matching
• Surpassing the information theoretic bound with fusion trees
• An improved combinatorial algorithm for Boolean matrix multiplication
• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Approximate string matching for music analysis
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Optimal bounds for the predecessor problem and related problems
• Generalized substring compression
• Towards polynomial lower bounds for dynamic problems
• The vectorization of ITPACK 2C
• Upper and Lower Bounds for Dynamic Data Structures on Strings
• Dynamic Set Intersection
• Higher Lower Bounds from the 3SUM Conjecture
• Internal Pattern Matching Queries in a Text and Applications
• Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
• Multiplying matrices faster than coppersmith-winograd
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Internal masked prefix sums and its connection to fully internal measurement queries