满足极小帕累托前沿的XY数据集更新操作：是否有标准命名及高效算法？

Yes, this operation is directly related to maintaining a Pareto frontier (also called a Pareto optimal set) for a 2-dimensional dataset. Specifically, your condition—keeping only points where no other point has both strictly smaller X and Y values—defines the non-dominated points in the set, and your process of adding a new point then pruning dominated ones is a standard part of dynamic Pareto frontier maintenance for incremental additions.

Efficient CPU Algorithms #

Since you're working with 2D data, you can optimize this process by keeping the frontier in a sorted structure:

• Sort the frontier by X (ascending): The valid frontier will always be a monotonic decreasing sequence of Y values. That's because if you have two points (x1, y1) and (x2, y2) where x1 < x2, y1 must be > y2—otherwise, (x2, y2) would be dominated by (x1, y1) (since x1 < x2 and y1 ≤ y2 violates your condition).
• Insert and prune:
  1. Use binary search (e.g., Python's bisect module) to find where the new point fits in the sorted list.
  2. Check if the new point is dominated by any existing point: given the sorted structure, you only need to check adjacent points to see if any have X < new.X and Y < new.Y.
  3. If the new point is valid (not dominated), add it to the list, then remove all existing points that are now dominated by it (i.e., points with X > new.X and Y > new.Y—these now have the new point with both smaller coordinates, so they no longer meet your condition).

This approach runs in O(log n + k) time per insertion, where n is the current size of the frontier and k is the number of points you end up removing.

GPU-Accelerated Methods #

If you're dealing with very large datasets and need to process batches of points quickly, GPU acceleration can help:

• Batch dominance checks: Use parallel operations (via CUDA kernels or tensor frameworks like PyTorch/TensorFlow) to compare new points against the existing frontier in bulk.
• Parallel pruning: After identifying non-dominated new points, merge them with the frontier and use parallel sorting/reduction to filter out any dominated points efficiently.
• Batch insertion: Instead of adding one point at a time, process entire batches to leverage the GPU's parallel processing power.

Libraries to Simplify Implementation #

• Python:
  • pymoo: A robust optimization library with built-in tools for computing and maintaining Pareto frontiers. You can use non_dominated_sort to filter the combined set of old and new points, or use its dynamic frontier utilities for incremental updates.
  • Custom bisect implementation: For lightweight use cases, the standard bisect module lets you maintain a sorted list, with simple custom logic to check dominance and prune points.
• C++:
  • Use std::set with a custom comparator to keep points sorted, then implement insertion/pruning logic manually.
  • Boost libraries offer helper functions for efficient range filtering that can simplify pruning dominated points.
• GPU:
  • CUDA: Write custom kernels for parallel dominance checks and sorted merging.
  • PyTorch/TensorFlow: Use tensor operations to batch-process comparisons and filtering, leveraging GPU acceleration out of the box.

内容的提问来源于stack exchange，提问作者Caustix