惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

N
Netflix TechBlog - Medium
J
Java Code Geeks
爱范儿
爱范儿
雷峰网
雷峰网
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
博客园 - 三生石上(FineUI控件)
H
Hackread – Cybersecurity News, Data Breaches, AI and More
B
Blog RSS Feed
Google DeepMind News
Google DeepMind News
Jina AI
Jina AI
The GitHub Blog
The GitHub Blog
I
InfoQ
月光博客
月光博客
博客园 - 聂微东
博客园 - Franky
The Cloudflare Blog
阮一峰的网络日志
阮一峰的网络日志
博客园_首页
G
Google Developers Blog
Blog — PlanetScale
Blog — PlanetScale
L
LangChain Blog
罗磊的独立博客
Apple Machine Learning Research
Apple Machine Learning Research

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
Explaining the Inherent Tradeoffs for Suffix Array Functi...
Dominik Kempa, Tomasz Kociumaka · 2025-10-23 · via cs.DS updates on arXiv.org

We study the fundamental question of how efficiently suffix array entries can be accessed when the array cannot be stored explicitly. The suffix array $SA_T[1..n]$ of a text $T$ of length $n$ encodes the lexicographic order of its suffixes and underlies numerous applications in pattern matching, data compression, and bioinformatics. Previous work established one-way reductions showing how suffix array queries can be answered using, for example, rank queries on the Burrows-Wheeler Transform. More recently, a new class of prefix queries was introduced, together with reductions that, among others, transform a simple tradeoff for prefix-select queries into a suffix array tradeoff matching state-of-the-art space and query-time bounds, while achieving sublinear construction time. For binary texts, the resulting data structure achieves space $O(n)$ bits, preprocessing time $O(n / \sqrt{\log n})$, preprocessing space of $O(n)$ bits, and query time $O(\log^ε n)$ for any constant $ε> 0$. However, whether these bounds could be improved using different techniques has remained open. We resolve this question by presenting the first bidirectional reduction showing that suffix array queries are, up to an additive $O(\log\log n)$ term in query time, equivalent to prefix-select queries in all parameters. This result unifies prior approaches and shows that essentially all efficient suffix array representations can be expressed via prefix-select structures. Moreover, we prove analogous equivalences for inverse suffix array queries, pattern ranking, lexicographic range, and SA-interval queries, identifying six core problem pairs that connect string and prefix query models. Our framework thus provides a unified foundation for analyzing and improving the efficiency of fundamental string-processing problems through the lens of prefix queries.