Notes

Writing

Plain-language summaries of my research - the key idea behind each paper, without the notation.

  1. Measuring a social network without learning who knows whomVLDB 2025
  2. Spending a privacy budget wisely when you can guess what’s comingICML 2026
  3. Finding passages that mean the same thing across millions of textsVLDB 2026
  4. Finding the most similar datasets - exactly, and fastICDE 2023
  5. Discovering the hidden structure inside messy tablesSIGMOD 2020
  6. Answering questions over data that’s full of holesHILDA 2023
VLDB 2025

Measuring a social network without learning who knows whom

On Practical and Accurate Local Edge Differentially Private Graph Algorithms

Platforms often want aggregate facts about a network - how tightly knit its communities are (k-core decomposition), or how many mutual-friend triangles it contains. But every edge is itself a private fact: that two specific people are connected. Differential privacy hides individual edges by injecting random noise, and at the scale of billion-edge graphs that noise usually swamps the real signal, leaving answers that are technically private but practically useless.

We work under local edge differential privacy, the strong version where each participant perturbs their own connections before anything is pooled - and show you don't have to trade that protection for garbage accuracy. Real graphs have exploitable structure: they're "shallow" in a precise sense (low degeneracy) and most nodes have bounded degree. By calibrating the noise to those structural properties instead of to the worst case, and running the whole thing across many machines, the algorithms stay accurate at scale.

The payoff is concrete: on billion-edge graphs, k-core estimates land within about 3× of the truth where prior methods were off by 131×, and triangle-counting error drops by up to six orders of magnitude - strong privacy and usable numbers at the same time.

ICML 2026

Spending a privacy budget wisely when you can guess what’s coming

On LAPRAS: Learning-Augmented Private Online Analytics (paper forthcoming)

When you answer a stream of questions about sensitive data, differential privacy gives you a fixed "budget" of privacy to spend. Every answer costs some of it, and once it's gone you're left returning pure noise. Spend the budget evenly and you waste it on questions nobody cares about; spend it greedily and you may have nothing left for the ones that matter later.

In practice we often have a rough forecast of what will be asked - which queries, and how often. LAPRAS is learning-augmented: it takes such a prediction and uses it to allocate the budget adaptively, leaning on the classic Matrix Mechanism to answer correlated queries efficiently. The design goal is a clean guarantee - when the prediction is good, accuracy approaches what you could achieve if you'd known the whole workload in advance; when it's bad, privacy is never compromised and quality only degrades gently.

That turns a brittle, all-or-nothing budgeting problem into one that gracefully exploits whatever foresight you have: the upside of planning ahead, without the downside of being wrong.

VLDB 2026

Finding passages that mean the same thing across millions of texts

On SeDa: Bridging the Gap between Efficient Syntactic and Precise Semantic Search of Similar Passages in Large Text Corpora

Suppose you want to find, across a massive collection of text, the passages that say the same thing as a given one - even when the wording differs through paraphrase, translation, or historical drift. Fast keyword-style (syntactic) search misses meaning; precise semantic comparison captures meaning but is far too slow to run over an entire corpus.

SeDa bridges the two. It first uses cheap syntactic signals to quickly narrow the corpus down to a small set of plausible candidates, then applies precise semantic verification only to those. The filtering step is built so it never discards a genuine match, so the final results keep the accuracy of semantic search at close to the speed of syntactic search.

The result is scalable, accurate similar-passage search - useful anywhere meaning matters more than exact words, from deduplicating large corpora to comparing texts across languages and eras.

ICDE 2023

Finding the most similar datasets - exactly, and fast

On KOIOS: Top-K Semantic Overlap Set Search

Given a set - say, the values in a column - you often want the top-k most similar sets in a huge repository, where "similar" means real semantic overlap rather than identical items. The precise notion of similarity requires solving a matching problem between the two sets' elements: accurate, but expensive to compute for every candidate in a large data lake.

KOIOS uses a filter-verification strategy. Instead of fully scoring every candidate, it computes cheap upper and lower bounds on the true similarity using bipartite-matching arguments, and uses those bounds to prune the vast majority of candidates that provably can't make the top-k. Only the few survivors get the expensive exact check.

Because the bounds are sound, the answers are exact - no approximation - while running about 5.5× faster than prior methods, which makes semantic set search practical over large collections.

SIGMOD 2020

Discovering the hidden structure inside messy tables

On Mining Approximate Acyclic Schemas from Relations

Real tables hide structure: some columns effectively determine others, and that structure tells you how to clean, normalize, and query the data. Finding it exactly is combinatorially expensive - and real data is noisy enough that exact dependencies rarely hold in the first place.

This work looks instead for approximate multivalued dependencies and the acyclic schema they imply, using information theory to measure how strongly one set of columns predicts another and to prune the search. Framing dependency discovery in information-theoretic terms lets it tolerate noise and skip huge parts of the search space.

The result is a practical way to recover the approximate relational structure of messy data - a building block for data cleaning, schema design, and simply understanding an unfamiliar dataset.

HILDA 2023

Answering questions over data that’s full of holes

On Approximate Query Answering over Open Data

Open datasets and knowledge graphs are incomplete and noisy - facts are missing, inconsistent, or uncertain. Ask an aggregate question ("how many …?") and an exact answer is impossible, because the data simply doesn't contain the whole truth.

Rather than pretend the data is complete, this work estimates aggregate answers over open knowledge, reasoning about what's missing to produce useful approximate results instead of misleadingly precise ones.

That lets analysts get meaningful, appropriately hedged answers from the kind of imperfect open data that's increasingly common - instead of being blocked by the gaps.