acceptodds
Under review as a conference paper at ICLR 2027

Segment-Delta: Exact and Scalable Replacement Refinement for Trajectory Simplification

Abstract

Fixed-budget trajectory simplifiers produce compact anchor subsequences, but reconstruction quality depends jointly on all anchors, so their outputs may still admit beneficial same-budget replacements. Exhaustively finding the best such replacement requires evaluating delete–insert pairs at every refinement round. We introduce Segment-Delta, an exact compiler for this complete neighborhood under segment-local reconstruction objectives. Deleting an anchor merges two adjacent intervals, whereas inserting a point splits one; the effects compose when their supports are disjoint, and only a linear number of pairs overlap. Segment-Delta summarizes the disjoint pairs and evaluates the exceptions, reducing candidate comparison in each scan to values. Direct deltas handle additive costs, while a two-pass value–witness procedure handles bottleneck objectives. In exact arithmetic, both recover the same tie-broken move, refinement path, and terminal subset as exhaustive search. After refinement restricted to overlapping edit supports, a complete-neighborhood audit finds a further improving move in 59.7% of 144 terminal states. Across GeoLife and Porto, complete refinement improves classical and learned simplifications and closes 94.2–99.9% of the aggregate Linear dynamic-programming gap for learned constructors. Segment-Delta gives 1.10–1.54 complete-refinement speedups on published length-1,000 low-retention outputs and 2.11–5.55 on nested-length complete-path tests (). With a frozen global Transformer, structurally ranked proposals retain 91.3–98.3% of complete-refinement gain, and every accepted move is verified on the full objective.

Primary area:
optimization
Keywords:
trajectory simplification, structured inference, combinatorial optimization, local search, exact algorithms

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_FHhYOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Segment-Delta, a method for improving trajectory simplification by replacing selected points while keeping the same number of points. For segment-local reconstruction objectives, it finds the same best replacement as exhaustive search with fewer candidate comparisons. It also uses the edit structure to rank proposals for a frozen Transformer, checking each accepted change against the full objective. Experiments on GeoLife and Porto show lower reconstruction errors for classical and learned simplifiers, with faster refinement than exhaustive search.

Critical strengths

S1. For segment-local objectives, the method finds the same best replacement as exhaustive search while reducing candidate comparisons to (O(n+k) per round.

S2. The proposed method achieves near-optimal results under linear interpolation.

Critical weaknesses

W1. The paper only tests one recent published method, MLSimp. It would be useful to test more recent methods, such as S3 and RL4QDS where applicable, to see whether the improvements also hold for other existing simplifiers.

W2. Being faster than exhaustive refinement does not show whether the post-processing is worth its extra cost. Trajectory simplification needs to balance runtime and quality, so the paper should compare each original method with its refined version using total runtime, including both initial simplification and refinement.

W3. Scalability with longer trajectories is not clear. An experiment with large and increasing k should be added.

Questions for authors

Please address the weaknesses

4 comments
AuthorsOpenReview ↗

Response to Reviewer FHhY

Thank you for these suggestions.

W1. Additional learned simplifiers. We added S3 NoGraph and an RL4QDTS-derived selector to test Segment-Delta (SD) on outputs from additional learned simplifiers. For every method, budget and seed, SD yields lower mean error than the unrefined output and near-only refinement. Both selectors use fixed sample-index Linear reconstruction during training and evaluation. S3 retains its straight-through selector and learned temperature, replacing neural reconstruction with Linear during training and evaluation. RL4-derived retains INB/OUB policies, with its environment and rewards adapted to Linear reconstruction.

Both use the same 2,000 length-1,000 GeoLife trajectories and total budgets of 24,000/44,000 points: 1%/2% interior budgets, or 1.2%/2.2% including endpoints. Allocation may differ between upstreams. The unrefined output (Original), near-only refinement (Near) and SD are paired within each frozen output, preserving its point count and endpoints. S3's selector uses token candidates; SD can refine over the original samples.

Upstream / interior budgetOriginalNearSD
RL4-derived / 1%127.8766.1152.78
RL4-derived / 2%73.9335.7826.90
S3 / 1%256.8669.7648.08
S3 / 2%147.1136.1422.45

Entries are mean non-anchor Euclidean errors in meters, averaged over three training seeds. Validation selects one checkpoint per seed jointly across budgets; every selected checkpoint improves over initialization on validation at both budgets. Training curves, checkpoint selection and matched controls are in Appendix L: S3 improves over candidate/quota-matched random subsets on test; RL4-derived improves over matched random-action policies on validation.

W2. Quality versus total cost. The same-cohort experiment measures the entire simplification-plus-refinement pipeline. A strong, inexpensive Greedy initializer remains substantially improvable:

Interior budgetOriginal: error / total timeGreedy+NearGreedy+SD
1%75.65 m / 1.06 s56.20 m / 4.48 s50.30 m / 5.50 s
2%34.77 m / 1.75 s26.34 m / 6.64 s22.95 m / 8.30 s

Times cover the full 2,000-trajectory batch. SD reduces Greedy error by 33.5%/34.0%, adding 4.44/6.55 s to the batch. Relative to Near, SD reduces remaining error by 10.5%/12.8% for 22.8%/24.9% more total time. For each retention budget, Greedy+SD lies on the quality-time frontier of the tested Original/Near/SD configurations across all four upstreams: no other configuration at equal or lower total time attains equal or lower mean error. Across MLSimp, RL4-derived and S3, SD reduces error by 58.7-84.7% versus Original, with 4.7-67.1% more total time (Table 3).

Total time includes upstream construction/inference, model loading where applicable, preparation, refinement and output assembly; raw-data loading and JIT setup precede measurement. The methods use the same hardware and a fixed eight-worker native refiner; S3 was measured in a separate batch. Sec. 4.2 and Appendix L provide all upstream costs, repetitions and the full frontier.

To test whether the quality gain persists at equal refinement time, we compare SD and Near on 128 MLSimp outputs using recorded completion times of accepted updates. This experiment uses just-in-time-compiled interval evaluation and the original nominal 1%/2% masks, timed independently of the full-pipeline study. At 50 ms, Near gives 172.33/63.99 m and SD gives 141.92/46.06 m: 17.6%/28.0% lower error at the same time. Near is better at 10 ms; SD is better at every tested time budget from 25 ms to 2 s. Appendix L gives curves at all eight time budgets.

W3. Longer trajectories and increasing k. Full refinement now covers natural GeoLife trajectories from 13 deduplicated source-user groups, n=1,000/2,000/4,000, k/n=2%/10%/25%, and fixed k=20: 11 configurations and 143 nested states; k includes endpoints. Identical Douglas-Peucker anchors, Linear costs at the original timestamps and a shared native implementation on one CPU core are used. Timing includes interval construction, search, updates and the terminal scan, with one warmup and five repetitions.

Compared with exhaustive refinement (EX), paired median EX/SD speedups at 10%/25% retention rise from 3.040/4.835x at n=1,000 to 13.157/20.599x at n=4,000. In the largest cell (n=4,000, k=1,000), marginal median EX/SD times are 1.4903/0.0725 s. All 143 terminal anchor sets/objectives match. Fixed-k speedups remain 1.161/1.116/1.061x: with fixed small k, EX's candidate count is already linear in n. Fig. 2 and Appendix N report all configurations, absolute costs and source-group bootstrap intervals.

AuthorsOpenReview ↗

Follow-up on our response

Dear Reviewer FHhY,

Thank you again for your helpful suggestions. We wanted to briefly follow up on the additional experiments in our response: comparisons with S3 and an RL4QDTS-derived selector, quality–runtime measurements for the full simplification-plus-refinement pipeline, and scalability tests with longer trajectories and increasing kk.

We would welcome your thoughts on these results and would be happy to discuss any remaining concerns or clarify any points that need further explanation.

The authors have addessed most of my concerns. I have raised the recommendation to weak acceptance.

Thank you for reviewing our additional experiments and clarifications. We really appreciate your time and helpful suggestions.

Reviewer_DoqgOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes Segment-Delta, an inference-time refinement method for trajectory simplification. It improves existing simplified trajectories by replacing selected anchor points while preserving the number of anchors. By exploiting the local structure of trajectory segments, the method reduces candidate-search complexity while identifying the same optimal replacement as exhaustive search.

Critical strengths
  1. The design is well-motivated and have theoretical guarantees.
  2. By exploiting the ordered structure of trajectory segments, the proposed method efficiently identifies the best replacement without evaluating all candidate pairs.
Critical weaknesses
  1. Although related trajectory refinement methods, such as Tabu Split and Merge and vertex relocation, are discussed in the Related Work section, they are not included in the experimental comparisons. It would be better to compare them under compatible settings. If such comparisons are not feasible, the authors should clarify why.
  2. The scalability evaluation could be more comprehensive. The measured speedups on length-1,000 trajectories are relatively modest (1.10–1.54×). Although larger speedups are reported in high-retention settings, those experiments involve only four trajectories and single-step evaluations. Furthermore, the contextual Transformer extension does not demonstrate a runtime advantage over batched complete evaluation.
  3. The abstract is overly dense, with extensive algorithmic details and numerical results that make the main contribution difficult to identify. A more concise presentation focusing on the central motivation, key idea, and main findings would improve readability.
Questions for authors

Please refer to weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer Doqg

Thank you for these suggestions.

W1. Existing refinement methods. We added comparisons of Segment-Delta (SD) with Tabu Move Merge Split (TMMS; Marteau and Menier, 2009) and iterative reduced-search DP (RSDP; Kolesnikov and Franti, 2003). Our paper-based adaptations retain the search mechanisms and use mean sample-index Linear error. All refine the same 128 length-1,000 GeoLife MLSimp outputs, preserving endpoints, eligible samples and actual k at nominal 1%/2% retention.

TMMS's original 2k-cycle schedule is fast. We extend its search to each trajectory's SD completion time, carrying over tabu memory and cache; only completed legal outputs count. We use the best fixed configuration completing all cases at both budgets. SD's mean error is 15.87%/15.38% lower than TMMS's, with lower error on 121/128 and 120/128 trajectories. Appendix M gives the configuration; the anonymous archive gives all eight alternatives and coverage.

A separate batch measures full-refinement time, including initialization, interval evaluation, search and output:

Refiner1% error / time2% error / time
TMMS, original 2k cycles167.26 m / 1.53 ms49.14 m / 2.24 ms
SD, to termination139.24 m / 22.62 ms40.09 m / 31.97 ms
RSDP POA4137.94 m / 1309.42 ms38.52 m / 1044.82 ms
RSDP POA6137.94 m / 1223.15 ms38.52 m / 1292.80 ms

Errors average across trajectories. For timing, we take the median of four runs per trajectory, then the median across trajectories. Both studies use the same earlier native SD implementation (Appendix M). Appendix M gives all five RSDP schedules.

RSDP retains its reference-corridor iterative search. Its constant-time formulas for squared geometric error do not transfer to our unsquared objective. We include interval-evaluation time and reuse computed interval costs across layers and iterations. TMMS/RSDP achieve lower terminal error on maximum-error objectives here; Appendix M reports all max-Linear/PED-line results. We did not measure runtime for these objectives.

We did not run Parvez's fixed-count vertex relocation: it admits off-contour pixels, whereas our outputs retain recorded samples and timestamps. Restricting its vertices removes that relaxation (Appendix M).

For mean Linear error, SD improves on continued TMMS at matched time, while its error is 1.30/1.57 m (0.94%/4.08%) above progressive RSDP at much lower cost.

W2. Scale and contextual runtime. Full-refinement scaling uses natural GeoLife trajectories from 13 deduplicated source-user groups: n=1,000/2,000/4,000, k/n=2%/10%/25%, and fixed k=20, including endpoints. The 143 nested states use identical Douglas-Peucker anchors, Linear costs at the original timestamps and shared native code on one CPU core. Five runs follow one warmup; all terminal anchors/objectives match. At 10%/25%, paired median speedups over exhaustive refinement (EX) rise from 3.040/4.835x at n=1,000 to 13.157/20.599x at n=4,000. The largest cell has median times of 1.4903 s (EX) and 0.0725 s (SD). Fixed-k speedups remain 1.161/1.116/1.061x; Fig. 2 and Appendix N give all configurations and group-bootstrap intervals.

At low retention, shared interval work limits SD's full-refinement speedup over EX. The scaling study's native implementation gives 1.002/1.048x EX/SD speedups on the original 128 MLSimp inputs. A separate diagnostic measures 2.90/4.09x search speedups. Search occupies only 6.8%/20.7% of profiled EX time; identical interval work consumes 79.7%/61.0%. Both studies are separate from the submitted Python 1.10/1.54x timings.

For the frozen Transformer, our new compiled contextual refinement retains 99.12-99.84% of batched EX's aggregate improvement on the full test sets: 1,782 GeoLife windows/19 users and 1,285 Porto windows/87 taxis, three selector seeds, n=56, k=14/28. Paired GPU timing on the existing 128 outcome-independent windows per dataset gives 1.65-2.19x full-refinement speedups and retains 98.70-99.91% of improvement there.

The submitted all-pair structural ranker scored every replacement and was slower (Appendix F). The new rule adds full-model single-edit effects to approximate disjoint edits and scores overlaps jointly. If a far proposal wins the joint near/far ranking, we verify it with the full model before selecting among true scores. Models and initial anchors remain fixed without retraining.

Batched EX and compiled refinement are timed through construction, scoring, verification, updates and termination, excluding loading/upstream simplification. Table 5 and Appendix O give all four cells, times and individual gaps. Verification ensures descent, not exhaustive equivalence; long-trajectory evidence concerns the exact branch.

W3. Abstract. We shortened the abstract to emphasize the problem, key idea and main findings; the technical details remain in the body and appendices.

Thank you for the detailed response. The additional experiments and comparisons have addressed my main concerns. I have updated my rating from 2 to 3.

Thank you for reviewing the additional experiments and comparisons. We are glad they addressed your main concerns, and we appreciate your suggestions for improving the paper.

Reviewer_eo8fOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Segment-Delta, an inference-time refinement algorithm for trajectory simplification. By exploiting the merge–split structure of anchor replacements, it reduces complete-neighborhood candidate evaluation from (O(kn)) to (O(n+k)) while preserving exhaustive-search equivalence for segment-local objectives. Experiments on GeoLife and Porto demonstrate improved reconstruction quality and reduced refinement time.

Critical strengths

S1: Provides exact algorithms and correctness guarantees for both additive and bottleneck reconstruction objectives.

S2: Significantly reduces candidate comparisons while preserving the same refinement results as exhaustive search.

S3: Includes classical and learned trajectory simplifiers, dynamic-programming comparisons, and correctness verification.

Critical weaknesses

W1: The core approach primarily exploits problem-specific merge–split decomposition and local-search acceleration, with limited conceptual innovation beyond existing structured optimization techniques.

W2: Despite substantial candidate reduction, actual speedups are only 1.10–1.54× on length-1,000 trajectories.

W3: The method does not introduce new learning mechanisms, and its Transformer extension is approximate and slower than batched exhaustive evaluation.

W4: Experiments focus on two trajectory datasets and reconstruction errors, without demonstrating downstream benefits or applicability to broader structured prediction tasks.

Questions for authors

See the above

4 comments
AuthorsOpenReview ↗

Response to Reviewer eo8f (1/2): W1 and W2

Response 1/2: W1 and W2.

Thank you for these comments.

W1. Conceptual contribution. We establish how trajectory order allows exact selection over the complete replacement neighborhood without enumerating all deletion-insertion pairs. Gap summaries recover the best disjoint combinations; only a linear number of overlapping pairs require joint evaluation.

Local search and reuse are established ideas: Resende-Werneck's best-swap acceleration uses sparse interaction corrections, with sparse-scan cost depending on their number. Here each insertion overlaps with at most two deletions, regardless of interval costs, guaranteeing at most 2(n-k) overlapping pairs at every legal anchor set. Summarizing the disjoint combinations and jointly scoring all overlaps recovers the best of all (k-2)(n-k) legal replacements with O(n+k) candidate work, given the requested interval costs.

Both additive and bottleneck objectives are covered. For the latter, we handle unchanged intervals that may determine the maximum and recover the canonical winner with the same linear bound, extending beyond additive reuse. Nonnegative interval costs are independent of other anchors; their construction remains charged. Exhaustive equivalence holds in exact arithmetic under the same tie rule (Secs. 1 and 5).

W2. Candidate savings versus full-refinement time. Our measurements identify two effects: exhaustive far scores already reuse cheap deltas, while SD also constructs gap summaries; shared interval evaluation dominates the full run at low retention. A matched native diagnostic on the original 128 length-1,000 inputs per rate, one CPU core and five repetitions including terminal scans gives:

Nominal retentionCandidate-count ratioSearch-time ratioFull-refinement time ratio
1%12.462.901.051
2%18.004.091.189

All ratios compare exhaustive refinement (EX) with Segment-Delta (SD); both time columns are ratios of means, with full-refinement times measured without instrumentation. This diagnostic is distinct from the submitted Python 1.10/1.54x timings. Search occupies only 6.8%/20.7% of profiled EX full-refinement time; identical interval evaluation occupies 79.7%/61.0%.

We therefore optimized interval evaluation and preparation between rounds, applying shared changes to both EX and SD. Matched full-refinement timing on the same 128 trajectories, with 16 repetitions across two balanced sessions, gives:

Nominal retentionFull-refinement EX/SD, paired medianSD mean refinement time
1%1.009x -> 1.015x5.129 -> 3.394 ms
2%1.052x -> 1.087x4.206 -> 2.754 ms

For search itself, reducing interval-access bookkeeping in both solvers gives the following paired medians on 45/48 correlated snapshots from 16 states per rate:

RetentionCandidate reduction, unchangedSearch saving before -> afterSearch speedup before -> after
1%68.72%53.48% -> 56.35%2.15x -> 2.29x
2%81.84%69.33% -> 72.27%3.26x -> 3.61x

In a separate full-refinement confirmation on the original 128 trajectories, paired speedups fall slightly, from 1.015/1.090x to 1.013/1.083x. Thus this further search improvement does not increase the full-refinement speedup over EX. The profiles and this test identify interval evaluation and per-round overhead as the remaining optimization priorities at low retention. Each comparison uses a baseline timed in the same batch. Appendix N distinguishes the diagnostic, snapshot and full-refinement studies.

Anchor budget changes this balance: with fixed small k, EX's candidate count is already linear in n; higher budgets expose more of the compilation benefit. An independent full-refinement study finds 3.040/4.835x speedups at n=1,000, k=100/250, and 20.599x at n=4,000, k=1,000. It uses 13 source-user groups, identical Douglas-Peucker anchors and Linear error at the original timestamps. All 11 configurations use shared native code, one CPU core and five repetitions. Fig. 2 and Appendix N report these results, including low k.

AuthorsOpenReview ↗

Response to Reviewer eo8f (2/2): W3 and W4

Response 2/2: W3 and W4.

W3. Learning relevance and contextual refinement. We optimize anchor decisions at inference time, complementing learned selectors and reconstructors. SD also lowers error beyond near-only refinement of MLSimp, RL4-derived and S3 NoGraph outputs in the shared-budget study (Table 3). Our new compiled contextual refinement retains 99.12-99.84% of the aggregate improvement from batched exhaustive refinement (EX) on the full test sets; a fixed timing subset gives 1.65-2.19x full-refinement speedups. Models and initial anchors stay fixed without retraining.

The submitted all-pair structural ranker scored every replacement; its slower timing remains in Appendix F. The new rule scores overlapping edits jointly. For disjoint edits, it adds their individual effects on the full Transformer, preserving global context in each score but ignoring interactions between the edits. If a far proposal ranks first among the near and far candidates, we verify its combined effect with the full model. We then select using all near scores and any verified far score. Temporal-locality research motivates this approximation (Li et al., 2019); candidate diagnostics and full runs test it here.

We fixed the rule using validation data before testing 1,782 GeoLife windows/19 users and 1,285 Porto windows/87 taxis, three seeds, n=56, k=14/28. Paired GPU timing uses the pre-existing 128 outcome-independent windows per dataset, one warmup and five repetitions, including construction/scoring, verification, updates and termination; loading/upstream simplification are excluded.

Dataset/kFull-test retained gainEX -> compiled median msPaired speedup
GeoLife/1499.33%30.80 -> 18.391.682x
GeoLife/2899.61%82.52 -> 36.772.193x
Porto/1499.84%47.99 -> 31.041.649x
Porto/2899.12%70.70 -> 33.352.087x

Retained gain is the ratio of summed error reductions from the same initial anchors, after averaging seeds within each window. For timing, we take the median of five runs for each seed and average across seeds within each window. We report the median of the resulting paired speedups, which need not equal the ratio of the two median times in the table. On the timing subset, the compiled rule retains 98.70-99.91% of EX's aggregate improvement. Appendix O gives entity-cluster bootstrap intervals and individual gaps. Verification ensures descent, not exhaustive equivalence.

W4. Downstream use and broader applicability. We added a downstream query evaluation and show how the compiler applies to a different structured objective. Reconstruction supports historical-location estimation. Cao et al. (2006) link location-at-time error to maximum time-uniform reconstruction distance.

We evaluate 200 spatiotemporal range-query events against a database of 2,000 GeoLife trajectories using released data/gau workloads (100 queries each). The comparisons use the same frozen MLSimp outputs and preserve per-trajectory point counts. Sample-index Linear uses a shared observation-time grid; original observations supply ground truth. Original denotes reconstruction from unrefined MLSimp outputs; Near is near-only refinement and SD is Segment-Delta.

Workload / nominal retentionOriginal F1Near F1SD F1
data / 1%0.95340.91890.9164
data / 2%0.94550.94590.9799
gau / 1%0.80520.89190.9311
gau / 2%0.85280.95300.9765

SD improves retrieval in three settings: macro F1 rises by 3.44-12.59 percentage points over Original and 2.35-3.92 over Near; data/1% drops 3.70 points against Original. Appendix P also reports micro F1 and false-positive/negative totals.

These query outcomes make alignment between the interval loss and the downstream decision important. Task-aware losses can target downstream information (e.g., Park et al., CVPR 2025). SD can optimize task-aware interval costs, including reconstruction costs with fixed nonnegative weights, when independent-interval sum/max structure is preserved.

Our empirical coverage remains GeoLife and Porto, including the query outcomes above. Beyond these evaluations, the compiler has a direct mathematical application to fixed-count time-series segmentation with independently fitted segments (Maidstone et al., 2017): boundary deletion/insertion likewise merges/splits segments. The additive compiler therefore finds the best single-boundary replacement under that task's own summed fitting cost (Sec. 4.5 and Appendix P).

The authors have addressed my concerns. I keep my positive score.

Thank you for your feedback. We are glad to hear that our response addressed your concerns, and we appreciate your time and helpful suggestions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.