How Much Can a Query Budget Buy? Converse Bounds for Multi-Source Harvesting Under Schema Mismatch

Many valuable datasets sit behind search forms and rate-limited APIs: the "deep web," which ordinary link-following crawlers cannot reach. Pulling records out of several such sources for several downstream users raises two problems. Each source answers only a limited number of queries. Each source also labels its fields differently from what the users want, a mismatch called semantic heterogeneity. Today's systems handle the two problems separately. Harvesters learn which queries return new records, and schema matchers learn which source column corresponds to which target column. Neither kind of system can tell an operator how far it is from the best any strategy could do, or whether the next hundred queries should go toward fetching more records or toward figuring out what the fields mean.

We propose to borrow the converse-bound machinery of network information theory, which proves upper limits on what any coding scheme can deliver. We apply it to a harvesting network with many sources and many receivers. The bound is computable from a small pilot sample. It treats an imperfect schema mapping as a noisy channel that wastes part of every query's payload. It also accounts for one query's response serving several receivers at once. Its practical use is as a planner: the gap between the bound and achieved harvest says where the next query is worth most.

Core Claim

Model each source as returning at most $k$ records per query under its own schema. Model each receiver as wanting a set of entity–attribute values under its own target schema. We claim three things.

First, the number of values a receiver can recover correctly is limited by the budget times the information a single response carries about that receiver's targets, after passing through the current schema mapping. Second, the joint limits across groups of receivers form a region, not a single number. The right converse is a combination of cuts built from entropy submodularity: $H(A\cup B)+H(A\cap B)\le H(A)+H(B)$, which says that adding information to a larger collection helps less than adding it to a smaller one. Third, this region is tight enough on realistic fragmented web tables to steer budget allocation. In particular it tells the planner when spending queries to improve alignment raises every receiver's ceiling more than spending them on harvesting.

Concretely, let $b_s$ be the queries spent on source $s$. Let $Y_s$ be one response projected through the current mapping into target attributes. Let $W_T$ be the target values demanded by a set $T$ of receivers, and let $n_r$ be the number of values receiver $r$ wants, recovered with error rate $P_{e,r}$. Fano's inequality, which links a small error rate to little remaining uncertainty, gives

$$\sum_{r\in T} n_r(1-P_{e,r}) - \sum_{r \in T} 1 \;\lesssim\; \frac{1}{\log|\mathcal{V}|}\sum_s b_s\, I(Y_s; W_T),$$

where $|\mathcal{V}|$ is the size of a value domain. The novelty is not this single-cut inequality. It is the claim that intersecting such cuts over receiver subsets, in the style of the generalized cut-set bounds for broadcast networks, yields a strictly smaller region. That reduction is what makes the bound useful for allocation.

Grounding in Prior Work

The bounding tools come from multi-flow network information theory.

Shomorony and Avestimehr chain copies of a deterministic network end to end. This yields nested-cut outer bounds that are tighter than simple cuts when several flows share links. Salimi, Liu and Cui use entropy submodularity to combine cuts, and characterize exact capacity regions for three-sink combination networks. Both methods supply our technique. Both also assume abstract message bits that carry no semantics. Salimi et al. further restrict to a single source, and we must lift that restriction.

Two papers constrain the design. The Two-Unicast Problem shows that exact multi-flow capacity is computationally hard even for two flows. We therefore aim for computable outer bounds, not exact capacity. Cut-Set Bound is Loose for Gaussian Relay Networks warns that plain cuts can be arbitrarily loose. That is why we insist on measuring tightness empirically rather than assuming it.

On the harvesting side, two papers motivate the gap. Learning to Surface Deep Web Content chooses keyword queries with reinforcement learning to maximize new records. Distributed query sampling allocates samples across sources using Heaps' law, a power-law fit of how fast new vocabulary appears. Both report only empirical harvest curves and give no ceiling to compare against. ActiveDeeper uses search endpoints as active labelers when overlap with local data is low. It enriches only one categorical attribute.

On the alignment side, SMARTINT mines approximate functional dependencies to rebuild entities split across web tables without join keys. It explicitly assumes attribute names already agree. Magneto retrieves candidate matches with a small language model and reranks them with a large one. It needs column value samples, which behind a form exist only after queries are spent. NAVI uses column entropy to decide which attributes to align globally. It treats entropy as a training heuristic, not as a bound.

Our proposal differs from all of these in one way. It puts harvesting and alignment into a single information budget and bounds that budget from above.

Research Program

The first piece is theory. We formalize the harvesting network as a bipartite graph. Sources have per-source rate limits $c_s$ and a total budget $B$. Receivers have demand sets over their own schemas. The schema mapping of source $s$ is a stochastic map whose confusion matrix is estimated from a pilot sample. We will prove the single-cut Fano bound above. We will then extend the submodular combination of cuts from the single-source broadcast case to many sources. Many sources make the problem harder because receivers' demands overlap: two receivers may want the same vehicle's engine type under different names. We expect the combination step to require only Shannon-type inequalities in this bipartite setting, because there are no relay nodes. If it does not, that negative result is itself worth reporting.

The second piece is estimation. The bound needs $I(Y_s; W_T)$, which we estimate from a pilot of a few hundred records per source. We reuse the observation from Caverlee et al. that vocabulary statistics stabilize within 100–200 documents. Their schemes are called Proportional Document and Proportional Vocabulary. Alignment noise enters through the matcher's calibrated scores. We will run Magneto-style retrieval and reranking on pilot values to get a soft mapping. We will give confidence intervals on the bound, propagated from the pilot sample.

The third piece is a planner. At each step it computes the gradient of the bound region. It compares two actions. One is a harvesting query on source $s$, which adds roughly one unit of $I(Y_s;W_T)$. The other is an alignment probe on source $s$: a query chosen to disambiguate the columns the matcher is least sure about, which raises $I(Y_s;W_T)$ for all future queries on $s$. Because a better mapping for a shared source raises the ceiling of every receiver that draws on it, the planner should favor alignment on hub sources early. This is the testable behavioral prediction.

Baselines

The naive reference allocates the budget uniformly across sources. It uses frequency-ranked keyword queries and exact header-name matching. Caverlee et al. report that uniform allocation loses on every metric they measure, so beating it is necessary but not interesting.

The strongest harvesting competitor is the reinforcement-learning surfacer of Wu et al.. Its output is passed through Magneto for alignment after harvesting. This is the obvious "best of both worlds" pipeline. No reported numeric result was found on Lacuna for its harvest rate on Baidu Baike or AbeBooks. We will rerun it on our simulated interfaces with the same query budget, the same per-source rate limits, and the same matcher. Its hyperparameters get the same tuning budget, measured in pilot queries, that our planner spends on estimation.

For enrichment, the strongest number in the file is ActiveDeeper. It accurately enriched 83% of 1,599 business names at a budget of 200 queries, and achieved four times the accuracy of Deeper across 100 to 800 queries. If the Local Business DB can be replayed offline, we compare against it at 200 queries in its single-receiver, single-attribute setting.

We also run greedy submodular coverage: pick the query with the largest expected count of new demanded values per receiver, with the classical $(1-1/e)$ guarantee. This baseline matters because it isolates whether our gains come from the information-theoretic accounting or merely from greedy diminishing-returns allocation.

Two ablations isolate the key ingredients. The first is our planner with alignment probes disabled. The second is our planner using only per-receiver single cuts instead of combined cuts.

Beating the field means two things on at least two of the three testbeds below, at matched budgets. Our planner must achieve higher total correctly-aligned values across receivers than both RL-then-Magneto and greedy coverage. The ablation without alignment probes must lose most of that margin.

Why not just…?

Why not just use the counting bound of budget times page size? The trivial ceiling $Bk\cdot(\text{attributes})$ is valid and costs nothing to compute. Our claim is worthless unless our bound is materially tighter. We therefore report, as a headline number, the ratio of each bound to the best achieved harvest. If the combined-cut bound is not tighter than the counting bound by a clear margin on fragmented Google Base data, where overlap and mismatch are heavy, the theory contributes nothing practical. We will say so.

Why not just estimate source size with Heaps' law or capture–recapture and stop when you approach it? Extrapolation estimates how much exists. It does not say how much is recoverable under a given mapping, and it gives one number rather than a per-receiver trade-off. It is still a real threat as a planning signal. We include a Heaps-law stopping-and-allocation baseline built on Proportional Vocabulary. If it matches our planner's harvest, the contribution shrinks to the alignment-versus-harvest decision alone.

Why not just run greedy submodular coverage with post-hoc LLM alignment? This is the most serious alternative. Greedy coverage already exploits diminishing returns, and Magneto already scales to schemas with more than 700 target attributes. Our bet is that greedy coverage over unaligned responses counts values it cannot yet map correctly, and so never chooses to spend a query improving the mapping. The probe ablation tests this directly. If greedy with oracle-free alignment matches us, the bound has diagnostic value only, and we will reframe the work as a certification tool.

Why not just prompt a large model end to end? Magneto reports that a competing matcher, ISResMat, failed to finish the GDC task beyond 100 columns, while its own two-stage pipeline ran in minutes. Pure prompting also does not decide which query to send next. We keep the language model inside the alignment channel rather than as the planner.

Proposed Experiments

We build three simulated deep web testbeds with form-like interfaces. Each returns the top $k$ records for a keyword or attribute-value query, with per-source rate limits.

The first uses the Google Base vehicles data from SMARTINT: about 350,000 records and 18 attributes split into five overlapping child tables. We rename, split and merge headers in each child table, using the distortion types of the ISLab Instance Matching Benchmark. Three receivers each get a different target schema. The second uses GDC-SM, with biomedical source tables placed behind interfaces and the GDC target schema as one receiver. Two coarser derived schemas serve as the other receivers. The third uses the movie and product WebTables from NAVI, split by source site.

The metrics are three. The first is correctly-aligned demanded values per receiver as a function of budget. The second is the tightness ratio, meaning achieved harvest over bound, for the counting bound, the sum of single cuts, and the combined cuts. The third is calibration: whether the bound's pilot-based confidence interval covers the best achieved harvest of every method we run.

Three outcomes would settle the proposal. The bound must never be violated by any method, including an oracle harvester given true mappings. It must be tighter than the counting bound and than single cuts on the multi-receiver testbeds. The planner must prefer alignment probes on sources shared by several receivers, and it must gain over greedy coverage exactly in those cases.

The vehicles testbed allows a final falsifiable check. With one receiver, the gap between single and combined cuts should vanish. As receivers whose demands overlap are added, the gap should grow. Failure of the gap to grow would refute the central claim.