Papers for

database system engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Index performance changes when application work affects cache and memory

Revisiting Index Performance under High Cache-Miss Penalties

Abstract: Modern data-intensive applications often query very large datasets, making index performance critical. Recent index structures exploit the fine-grained access capabilities of emerging storage devices such as DCPMM and CXL. However, existing benchmarks typically evaluate indexes in isolation using saturated, closed-loop workloads that emphasize maximum throughput. Such workloads favor highly concurrent designs while overlooking the application work that follows an index lookup and competes for cache, memory bandwidth, and CPU resources. We present AuxBench - a microbenchmark that evaluates indexes as auxiliary access paths within larger application workloads. Using AuxBench, we evaluate four byte-addressable indexes under controlled post-lookup memory activity, concurrency, and request arrival patterns. Our experiments show that post-lookup memory activity can change the relative performance of competing indexes, that concurrency-oriented designs may lose their advantages when substantial application work is introduced, and that time-varying request arrivals can produce severe tail latency near saturation. These findings demonstrate why index-only benchmarks may not adequately predict performance in larger application workloads

Mon 16 NovDatabases
The gist
Large data applications rely on indexes to quickly find information, but how well indexes work depends on what happens after the lookup. The authors show that testing indexes by themselves can be misleading because real applications use memory and CPU after looking up data. They created a new test called AuxBench to see how indexes perform alongside other work and found that some designs that do well alone struggle when used with more application activity. They also discovered that request patterns can cause unexpected delays near peak usage.
Open → 2611.21835v1

Seeing future data improves greedy set selection for limited memory

Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead

Abstract: Elements arrive one at a time, and after each arrival an algorithm holds a set of at most $k$ arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that $k$ arrived elements can achieve. The recourse of an update is the number of elements inserted into or removed from the held set, and we require it to be bounded independently of $k$ and of the number $n$ of arrivals. With evaluations only on sets of arrived elements and polynomially many of them, the best ratio a randomized algorithm can achieve is $2-\sqrt{2}\approx0.5858$. We show that seeing future arrivals raises the best ratio for polynomially many evaluations to $1-1/e\approx0.6321$, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds $1-1/e$, even when all elements are available at once. For every $\varepsilon>0$, a deterministic algorithm that sees the next $\lceil\varepsilon k/3\rceil$ arrivals keeps a set of value at least $1-1/e-\varepsilon$ times the optimum at every time, changes $O(\varepsilon^{-3})$ elements per arrival and makes $(n+1)^{O(\varepsilon^{-2})}$ evaluations. With the whole arrival sequence known in advance, a deterministic algorithm attains the same ratio with $O(\varepsilon^{-2})$ changes per arrival. A randomized algorithm with the same short lookahead makes $O(n^2k)$ evaluations, changes $O(\varepsilon^{-2})$ elements per arrival, and attains the same ratio in expectation at each fixed time. The main tool is a greedy algorithm with an explicit guarantee for each of its partial solutions combined with each initial segment of the known future arrivals. A second tool moves between two such solutions one element at a time while keeping the value high, and the deterministic algorithm times each move using upper bounds on the optimum from failed searches.

Sun 8 NovData Structures and AlgorithmsMachine Learning
The gist
The paper studies how to keep a small group of items that maximizes value as new items arrive one by one. Normally, without knowing what's coming next, the best you can do is about 58.6% as good as the perfect choice after seeing all items. The authors show that if the algorithm can look a little bit into the future, it can do about 63.2% as well, which is the best possible. They also give specific algorithms that balance how many items are changed at each step and how many future items are seen, offering a clearer understanding of this trade-off.
Open → 2611.11124v1

Combinatorial boolean matrix multiplication runs faster than before

Combinatorial Boolean Matrix Multiplication in $n^3 / 2^{Ω(\sqrt{\log n})}$ Time

Abstract: For over fifty years, combinatorial algorithms for Boolean matrix multiplication (BMM) and triangle detection saved only polylogarithmic factors over cubic time. At STOC 2024, Abboud, Fischer, Kelley, Lovett, and Meka broke this barrier with a deterministic $O(n^3 / 2^{Ω((\log n)^{1/7})})$-time algorithm, and asked whether $n^3 / 2^{Ω(\sqrt{\log n})}$ time is achievable. We answer this question in the affirmative, giving deterministic combinatorial algorithms for both BMM and triangle detection running in $O(n^3 / 2^{Ω(\sqrt{\log n})})$ time. Following Abboud et al., we decompose $(A,B)$ into pairs of submatrices $(A_k,B_k)$, called \emph{pieces}, each of which is either sparse or pseudorandom in a sense that forces $A_k\star B_k$ to be nearly all-ones on its vertex sets. Whereas their decomposition produces $2^{O(d^7)}$ pieces at regularity parameter $d$, we obtain $2^{O(d^2)}$ pieces, directly improving the runtime exponent from $(\log n)^{1/7}$ to $\sqrt{\log n}$. Prior work found pseudorandom pieces by repeatedly restricting to denser submatrices, paying worst-case vertex losses at each step that compounded across nested recursion levels, together with an expensive derandomization step. We eliminate the extra powers of $d$ by matching the vertex loss at each step to the size of its density jump so losses telescope across scales, derandomizing witness search via $L_d$-norm estimation so the sampler length stays $2^{O(d)}$, and bounding overlap across the recursion with a fractional density-weighted volume budget rather than raw submatrix volume.

Wed 4 NovData Structures and Algorithms
The gist
Boolean matrix multiplication is a way to combine two grids of true/false values to find connections, important in many computer problems like detecting triangles in graphs. For decades, the fastest step-by-step (combinatorial) methods only improved speed slightly over the basic cubic time. The authors build on recent advances to create a new deterministic algorithm that cuts down the running time more significantly. They achieve this by better breaking down the problem into manageable parts that are either sparse or highly structured, carefully managing how much information is lost at each step. Their method leads to a faster algorithm that improves on the previous complexity bound.
Open → 2611.06717v1

Complexity limits for finding key sets in special hypergraphs

Lower Bounds for Minimal-Transversal Enumeration of Bounded-Dimension Hypergraphs and the maximum Minimal Hitting Set Problem

Abstract: We present lower bounds for the maximum minimal hitting set problem and for the problem of enumeration of minimal transversals in bounded-dimension hypergraphs. Our starting point is the recent reduction of Kobayashi, Kurita, and Wasa (2026), developed to establish ETH-based hardness of hypergraph dualization. Adapting their construction, we show that, under ETH, deciding whether a hypergraph $\mathcal{G}$ with $n$ vertices and $m$ hyperedges has a minimal transversal of size at least $k$ cannot be done in time $n^{f(k)}m^{o(k)}$, for an arbitrary computable $f$. We transfer this bound to the following decision problem: given a dimension-at-most-$r$ hypergraph and a family of $s$ of its minimal transversals, decide whether another exists. Under ETH, this problem admits no uniform algorithm with running time $n^{f(r)}(s+1)^{o(r)}$. Under SETH, for every fixed $t \geq 2$, it admits no algorithm with running time $\poly(|\mathcal{G}|)(s+1)^c$ for dimension at most $2t$ and any $c<t$. As corollaries, the same exponent obstructions hold for the total time of any output-polynomial enumeration algorithm, with $s$ replaced by the total number of minimal transversals. In particular, polynomial delay is excluded under SETH already for dimension at most four.

Tue 20 OctComputational Complexity
The gist
Some mathematical problems involve finding small sets that intersect certain groups, which mathematicians call minimal hitting sets or transversals in hypergraphs. This paper shows that even for hypergraphs with limited group sizes, it is very hard to decide or list these special sets quickly. The authors build on earlier research to prove that there are fundamental time limits for solving these problems efficiently, assuming widely believed computational assumptions. Their results suggest that no fast, general algorithm exists for these tasks in many cases.
Open → 2610.28012v1

Conditional sampling reveals new limits in estimating hypergraph edges

Power of Conditional Sampling on Hypergraphs

Abstract: Let $G=(V,E)$ be a $d$-uniform hypergraph with $|V|=n$ and $|E|=m$. Estimating $m$ from uniformly random hyperedge samples requires $Θ(\sqrt{m})$ samples by a birthday-paradox argument. We investigate the power of conditional sampling through a hierarchy of oracles: for an integer $1\le s\le d$, given pairwise disjoint subsets $X_1,\ldots,X_s\subseteq V$, the $s$-colorful oracle returns a hyperedge chosen uniformly at random from all hyperedges contained in $X_1\cup\cdots\cup X_s$ that intersect every $X_i$, provided one exists. For $s=1$, this samples a uniformly random hyperedge induced by $X_1$. For every $1\le s\le d$, we give a randomized algorithm that outputs $\widehat{m}\in[(1-\varepsilon)m,(1+\varepsilon)m]$ with probability at least $2/3$ using $O_{s,d}(\operatorname{poly}(1/\varepsilon,\log n))$ conditional samples, where the exponent of $\log n$ is an absolute constant independent of both $s$ and $d$. Conditional sampling thus yields an exponential separation over uniform hyperedge sampling. We also study the decision version, in which the oracle only reports whether a qualifying hyperedge exists. For every $1\le s<d$, we prove that any algorithm using the $s$-colorful decision oracle requires $\widetildeΩ_{s,d}(n^{\frac{d-s}{d-s+1}})$ queries. Hence, for $s<d$, access to uniformly random witness hyperedges (random certificates) is exponentially more powerful than existence queries. For $s=d$, decision queries alone achieve $\operatorname{poly}(1/\varepsilon,\log n)$ query complexity, but the exponent of $\log n$ is known to be $Θ(d)$. The colorful hierarchy thus exhibits a phase transition at $s=d$: for $s<d$, random certificates are essential for polylogarithmic-query estimation, whereas at $s=d$ decision queries suffice, yet random certificates still provably reduce the exponent of $\log n$ from $Θ(d)$ to an absolute constant.

Fri 16 OctData Structures and Algorithms
The gist
Counting connections in complex networks called hypergraphs is usually hard when you pick those connections randomly. The authors studied smarter ways to sample parts of the network, called conditional sampling, which makes the count much easier and more accurate. They showed that using these special queries can dramatically reduce how many samples you need, sometimes exponentially fewer. They also found a clear divide in difficulty depending on how much information the sampling can provide.
Open → 2610.23364v1

Binary rank limits found for matrices with fixed real rank

On the Binary Rank of Matrices with Constant Real Rank

Abstract: We continue the study initiated by Parnas and Shraibman~\cite{PARNAS2026264} who gave upper bounds on the binary rank of $0,1$ matrices which have a small rank over the reals. We give alternative completely mathematical proofs of results proved in~\cite{PARNAS2026264} with the assistance of a computer program, and also solve one of the open problems presented there regarding the maximal binary rank of a matrix with real rank $5$. Moreover, our techniques provide a general method for giving non-trivial upper bounds on the maximal binary rank of a matrix with constant real rank. Our results also imply bounds on the equivalent problem of finding the minimum number of bicliques needed to partition the edges of a bipartite graph whose reduced adjacency matrix has real rank at most $d$.

Thu 24 SeptDiscrete Mathematics
The gist
Some math researchers studied a special kind of matrix that contains only zeros and ones but also has a fixed rank when using normal real numbers. They found new ways to show upper limits on the ‘binary rank’, which measures how complex the matrix is in a different way. They solved an open problem for matrices with real rank 5 and created general methods that work for other fixed ranks too. Their work also relates to how we can break down connections in certain graphs efficiently.
Open → 2609.30203v1