Index-Faithful Synthetic Data for Benchmarking Disjoint Spatial Partitions

Many spatial databases split space into regions that never overlap. Examples are the R+-tree, the KDB-tree, quadtrees, and grids of Geohash cells. Because the regions are disjoint, a point lookup follows exactly one path down the index. The price is paid by objects with extent, such as road segments, trips, and parcels. Whenever one of these crosses a region boundary, it has to be cut and stored more than once. As a result, the cost of these indexes is set by a few geometric facts about the data: how density varies at the scale of the partition cells, and how often objects cross cell boundaries.

The best real data for measuring those facts, such as GPS traces and enterprise location logs, usually cannot be released. Systems papers therefore fall back on synthetic data, either simple uniform, Gaussian, and clustered point clouds or the output of privacy-preserving generative models. Nobody has checked whether an index comparison run on synthetic data reaches the same conclusion it would reach on the real data. This proposal tests that directly. We treat public datasets as if they were private, so the true answer is known. We then ask which kinds of synthetic data preserve the ranking and cost profile of disjoint partitioning methods. Our hypothesis is that a small, privately released set of "index-sufficient" statistics, together with a cheap generator conditioned on them, preserves these conclusions better than either parametric toy distributions or deep generative models tuned for distributional similarity.

Core Claim

We claim that, for disjoint partitioning, whether a synthetic benchmark can be trusted depends mainly on two things. The first is the density spectrum at the cell sizes the index will actually use. The second is the object-extent distribution measured relative to those cells. Overall resemblance to the real point cloud matters much less.

The second ingredient can be made precise with a Buffon-needle argument. A straight segment of length $L$ with uniformly random orientation, placed on a grid of square cells of side $s$, touches on average

$$ \mathbb{E}[\text{cells}] = 1 + \frac{4}{\pi}\,\frac{L}{s} $$

cells. The derivation is short: the expected number of vertical grid lines crossed is $L\,\mathbb{E}|\cos\theta|/s = 2L/(\pi s)$, and the same holds for horizontal lines. Duplication in an R+-tree or Geohash index therefore grows linearly in the ratio of object length to cell size.

This has a direct consequence for existing generators. Synthetic location trajectory generation using categorical diffusion models generates mobility traces with a diffusion model, a generator that learns by gradually denoising random noise into samples. The authors report that it overestimates travel distances. If so, any disjoint index benchmarked on its output will show inflated fragmentation, and that inflation can reorder methods that trade fragmentation against fanout.

Similarity scores such as Chamfer distance and Earth Mover's Distance are what generators like GeoPointGAN are evaluated on. Neither score is sensitive to this length-to-cell ratio. We therefore predict that these scores will correlate weakly with index-level fidelity, while a differentially private release of multi-scale density and crossing statistics will correlate strongly.

Research Program

The work has three parts.

An index-fidelity measurement harness. We run the same set of disjoint partitioners on real data and on synthetic stand-ins, sweeping each method's main parameter. The partitioners are an R+-tree, a KDB-tree, a quadtree, a Geohash-cell index with degree $D$ swept in the style of the HQ-sLSM+ tree, and, on one dataset, the reinforcement-learning partitioner from Learned spatial data partitioning. A classic overlapping R-tree serves as a reference.

Fidelity is not measured by how similar the data look. It is measured by whether the decisions a researcher would draw agree. We compute three quantities. The first is Kendall rank correlation between the real and synthetic orderings of method-and-parameter configurations, by page accesses and by query runtime. The second is the relative error of reported speedup ratios. The third is the error in the measured duplicate-key ratio.

Index-sufficient statistics and a matching generator. The data owner releases, under differential privacy, two things:

  1. a multi-resolution density histogram over a quadtree pyramid;
  2. a joint histogram of object length and orientation bucketed by resolution level, which captures the crossing behavior in the equation above.

Differential privacy here means a formal guarantee that the release barely changes if any one record is removed. A simple sampler then draws points and segments consistent with these statistics.

The release is cheap, and auditing it means auditing a few thousand counts rather than a neural network. It also gives other groups something concrete to cite: a reported benchmark number can be re-run by anyone on the released statistics.

Testing two tensions in the literature. The first concerns privacy noise:

  1. GeoPointGAN finds that moderate label-flipping privacy ($\epsilon \approx 1$) acts as a regularizer and improves downstream utility.
  2. PateGAIL++ treats uniform privacy noise as a tax on utility that has to be offset with sensitivity-aware budgets.

We sweep $\epsilon$ and measure which effect dominates for index fidelity, where partition lines depend on fine-grained density.

The second tension is about how much realism a benchmark needs:

  1. On the Equivalency, Substitutability, and Flexibility of Synthetic Data finds that behavioral complexity in synthetic tracking data mattered more than photorealism, and that simple synthetic data hurt performance.
  2. The HQ-sLSM+ tree work, in contrast, treated uniform, Gaussian, and cluster distributions as adequate evidence for a 50% I/O reduction.

We test which view holds for spatial joins.

Prior work. The papers above play different roles. The HQ-sLSM+ evaluation and the categorical-diffusion distance bias motivate the gap. The substitutability study supplies the evaluation concept, which we adapt from model accuracy to systems decisions. The R+-tree paper (The R+-Tree) and the surveys Spatial Indexing: Past and Future and Multidimensional Access Methods: Trees Have Grown Everywhere supply the fragmentation mechanism we model. None of these works measures how synthetic data changes index behavior. The generative papers measure statistical similarity or task utility, and the index papers take their test data as given.

Baselines

Naive reference: fitted parametric data. The do-nothing benchmark is the practice of the HQ-sLSM+ tree paper:

  1. uniform, Gaussian, and clustered point and box distributions;
  2. clusters fitted to the real data by maximum likelihood;
  3. box sizes capped as in that paper, at 1.5% of the space.

It is the strongest naive competitor because it costs nothing, is perfectly reproducible, and is what most of the field actually uses. To beat it, the summary-based generator needs a clearly higher rank correlation across all real datasets. We fix a gap of at least 0.2 in Kendall's tau in advance as meaningful.

Strongest learned generator for points: GeoPointGAN. It is trained with its published architecture on the Porto, Beijing, and NYC 311 data it was designed for. We run it at matched privacy budgets and give it the same wall-clock tuning budget as our generator plus a factor-of-ten allowance, since it is the more expensive method. The paper reports up to a 10-fold improvement in Chamfer distance and Earth Mover's Distance over r-GAN and tree-GAN. No reported result was found on Lacuna for any index-level metric (page accesses, duplication, or rank agreement) on GeoPointGAN output.

Strongest learned generators for trajectories. We use PateGAIL++ and the categorical diffusion model, both evaluated on Geolife. PateGAIL++ reports roughly a 29% reduction in DailyLoc error, the error in the number of distinct locations a user visits per day, relative to PateGAIL. It also reports membership-inference attack accuracy near chance (about 0.51, versus about 0.66 for PateGAIL). No reported result was found on Lacuna for the travel-distance error of the diffusion model, beyond the qualitative statement that distances are overestimated.

Coordinate-perturbation baseline. We add Laplace noise directly to coordinates of the open data, calibrated to the same $\epsilon$.

Key ablation. We run our generator with only the density pyramid, dropping the length and orientation component. If this ablation matches the full version on trajectories and road segments, the crossing statistics are unnecessary and the core claim is wrong.

All generators are trained on the same 80% of records. Fidelity is measured on indexes built from full real data, and query workloads are generated identically for every condition.

Why not just…?

Why not just use uniform, Gaussian, and clustered distributions as the field already does? This is a real threat for point data. A partitioner that balances density may rank the same on any reasonably clustered cloud. We expect the approach to fail on extended objects, because these distributions carry no length-to-cell information. The fragmentation equation implies that duplication, and with it the R+-tree versus quadtree tradeoff, depends mainly on the length distribution. The experiment settles the question per object type: if parametric data reach rank agreement comparable to ours on segments drawn from OSM+ and Geolife, we will report that simple benchmarks are adequate.

Why not just evaluate generators with Chamfer distance and Earth Mover's Distance and assume good scores carry over to indexing? If these scores predicted index fidelity, no new evaluation would be needed. We test this directly. Across all generators and privacy budgets, we compute the correlation between each similarity score and index rank agreement. A correlation above 0.8 would undercut the proposal's motivation, and we would say so.

Why not just release a privatized density histogram and skip generators entirely? This is close to our proposal. The density-only ablation is exactly this alternative. The idea we defend is narrower: density alone is enough for points but not for lines and trajectories, so the release must include a length and orientation component. If the ablation matches the full method everywhere, the contribution shrinks to the finding that density histograms suffice, which is still a useful negative result for the deep-generator line of work.

Why not just benchmark on OSM+, which is open and huge? OSM+ (code) provides about 1.9 billion vertices of static road geometry. It contains no individual trips or query workloads. Those are exactly what learned partitioners optimize for, and they remain private. We use OSM+ as real ground truth for road-segment geometry, not as a substitute for mobility data.

Proposed Experiments

Datasets. Real ground truth comes from public data treated as private:

  1. Porto and Beijing taxi points and NYC 311 calls, as used by GeoPointGAN;
  2. Geolife trajectories, segmented into polylines;
  3. OSM+ road segments for selected cities;
  4. 100,000-point samples of OSM-US, OSM-SA, and Imis, following Learned spatial data partitioning.

Workloads. Range queries, point queries, and distance joins, run in Apache Sedona for the runtime results.

First decisive check: rank agreement. On each real dataset, for each generator and $\epsilon$ in {0.1, 1, 10, ∞}, we compute Kendall's tau over the configuration ranking. The prediction is that the summary-based generator beats GeoPointGAN and parametric data on segments, and ties them on points.

Second decisive check: re-running the 50% join-filter claim. We re-measure the HQ-sLSM+ tree result that its spatial join filter cuts disk I/O by up to 50%. We compare its synthetic cluster data against real OSM+ polylines and parcels at matched object counts (500K to 5M). The outcome tells us whether the gain depends on idealized empty space in the synthetic data.

Third decisive check: substitutability for the learned partitioner. We train it on synthetic OSM-US stand-ins at a fixed partition count and deploy it on the real data. We report the fraction of its reported runtime reduction of up to 59.4% that is retained. Training is expensive (about 65.5 hours reported), so we run this check only for the best two generators.

Fourth decisive check: the privacy-noise tension. We plot index fidelity against $\epsilon$. A U-shaped curve would extend GeoPointGAN's regularization finding to systems metrics. A monotone decline would side with the PateGAIL++ view that privacy noise taxes utility.

Falsification. The proposal fails if parametric data or Chamfer-matched GAN output preserve index rankings on extended objects as well as the crossing-aware release does.