You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by le...@apache.org on 2025/02/23 17:44:44 UTC
(iotdb) 43/44: add
This is an automated email from the ASF dual-hosted git repository.
leirui pushed a commit to branch research/area-visualization
in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit 35b3b2c7a37b3ad034513f990eca770b75cf3b80
Author: Lei Rui <10...@qq.com>
AuthorDate: Sun Feb 23 18:14:05 2025 +0800
add
---
.../java/org/apache/iotdb/db/query/eBUG/DNSL1.java | 159 +++++++++++----------
1 file changed, 81 insertions(+), 78 deletions(-)
diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/DNSL1.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/DNSL1.java
index be4ffe2d6f1..28f26a3f619 100644
--- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/DNSL1.java
+++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/DNSL1.java
@@ -9,91 +9,94 @@ import java.util.Random;
import static org.apache.iotdb.db.query.eBUG.DP.dynamic_programming;
public class DNSL1 {
- // 默认使用linear interpolation连接分段首尾点来近似
- // 默认使用L1 error
- // 使用divide and conquer算法
- public static List<Point> reducePoints(List<Point> points, int m, boolean debug) {
- int n = points.size();
- int k = m - 1; // 分段数
- int intervalPts = (int) Math.pow((double) n / k, (double) 2 / 3); // divide batch点数
+ // 默认使用linear interpolation连接分段首尾点来近似
+ // 默认使用L1 error
+ // 使用divide and conquer算法
+ public static List<Point> reducePoints(List<Point> points, int m, boolean debug) {
+ int n = points.size();
+ int k = m - 1; // 分段数
+ int intervalNum = (int) Math.pow((double) n / k, (double) 2 / 3); // divide batch点数
+ int intervalPts = n / intervalNum;
- if (debug) {
- System.out.println("interval point length=" + intervalPts);
- }
+ if (debug) {
+ System.out.println("interval point length=" + intervalPts);
+ }
- // divide into intervalPts equal-length intervals
- List<Point> allSampledPoints = new ArrayList<>();
- for (int start = 0; start < n; start += intervalPts) {
- int end = Math.min(start + intervalPts, n);
- List<Point> batch = points.subList(start, end); // 左闭右开
- if (debug) {
- System.out.println("Processing batch: [" + start + "," + end + ")");
- }
- List<Point> sampledForBatch = dynamic_programming(batch, k, DP.ERRORtype.L1, false);
- allSampledPoints.addAll(sampledForBatch); // 把上一步的结果加到大的容器里
- }
+ // divide into intervalPts equal-length intervals
+ List<Point> allSampledPoints = new ArrayList<>();
+ for (int start = 0; start < n; start += intervalPts) {
+ int end = Math.min(start + intervalPts, n);
+ List<Point> batch = points.subList(start, end); // 左闭右开
+ if (debug) {
+ System.out.println("Processing batch: [" + start + "," + end + ")");
+ }
+ List<Point> sampledForBatch = dynamic_programming(batch, k, DP.ERRORtype.L1, false);
+ allSampledPoints.addAll(sampledForBatch); // 把上一步的结果加到大的容器里
+ }
- // 在大的容器上最后执行DP.dynamic_programming得到最后的m个采样点
- if (debug) {
- System.out.println("number of points from batch sampling: " + allSampledPoints.size());
- }
- List<Point> finalSampledPoints =
- dynamic_programming(allSampledPoints, k, DP.ERRORtype.L1, false);
- if (debug) {
- System.out.println("result point number: " + finalSampledPoints.size());
- }
- return finalSampledPoints;
- }
+ // 在大的容器上最后执行DP.dynamic_programming得到最后的m个采样点
+ if (debug) {
+ System.out.println("number of points from batch sampling: " + allSampledPoints.size());
+ }
- public static void main(String[] args) {
- Random rand = new Random(10);
- String input = "raw.csv";
- boolean hasHeader = true;
- int timeIdx = 0;
- int valueIdx = 1;
- int N = 1000;
- // List<Point> points = Tool.readFromFile(input, hasHeader, timeIdx, valueIdx, N);
- Polyline polyline = new Polyline();
- for (int i = 0; i < N; i += 1) {
- double v = rand.nextInt(1000);
- polyline.addVertex(new Point(i, v));
+ // TODO 但是注意这里用的是linear interpolation近似，而不是DNS原文的constant
+ List<Point> finalSampledPoints =
+ dynamic_programming(allSampledPoints, k, DP.ERRORtype.L1, false);
+ if (debug) {
+ System.out.println("result point number: " + finalSampledPoints.size());
+ }
+ return finalSampledPoints;
}
- List<Point> points = polyline.getVertices();
- try (FileWriter writer = new FileWriter("raw.csv")) {
- // 写入CSV头部
- writer.append("x,y,z\n");
- // 写入每个点的数据
- for (Point point : points) {
- writer.append(point.x + "," + point.y + "," + point.z + "\n");
- }
- System.out.println(points.size() + " Data has been written");
- } catch (IOException e) {
- System.out.println("Error writing to CSV file: " + e.getMessage());
- }
+ public static void main(String[] args) {
+ Random rand = new Random(10);
+ String input = "raw.csv";
+ boolean hasHeader = true;
+ int timeIdx = 0;
+ int valueIdx = 1;
+ int N = 100_0000;
+// List<Point> points = Tool.readFromFile(input, hasHeader, timeIdx, valueIdx, N);
+ Polyline polyline = new Polyline();
+ for (int i = 0; i < N; i += 1) {
+ double v = rand.nextInt(1000);
+ polyline.addVertex(new Point(i, v));
+ }
+ List<Point> points = polyline.getVertices();
+ try (FileWriter writer = new FileWriter("raw.csv")) {
+ // 写入CSV头部
+ writer.append("x,y,z\n");
+
+ // 写入每个点的数据
+ for (Point point : points) {
+ writer.append(point.x + "," + point.y + "," + point.z + "\n");
+ }
+ System.out.println(points.size() + " Data has been written");
+ } catch (IOException e) {
+ System.out.println("Error writing to CSV file: " + e.getMessage());
+ }
- // int m = (int) Math.pow(points.size(), 0.5);
- int m = 10;
+ // int m = (int) Math.pow(points.size(), 0.5);
+ int m = 1_000;
- // long startTime = System.currentTimeMillis();
- // List<Point> sampled = dynamic_programming(points, m - 1, DP.ERROR.area, false);
- // long endTime = System.currentTimeMillis();
- // System.out.println("Time taken: " + (endTime - startTime) + "ms");
- // for (Point p : sampled) {
- // System.out.println(p);
- // }
- // System.out.println(sampled.size());
+ // long startTime = System.currentTimeMillis();
+ // List<Point> sampled = dynamic_programming(points, m - 1, DP.ERROR.area, false);
+ // long endTime = System.currentTimeMillis();
+ // System.out.println("Time taken: " + (endTime - startTime) + "ms");
+ // for (Point p : sampled) {
+ // System.out.println(p);
+ // }
+ // System.out.println(sampled.size());
- long startTime2 = System.currentTimeMillis();
- // System.out.println(points.size() * m / (Math.pow(points.size() * 1.0 / (m - 1), 2 /
- // 3.0)));
- // System.out.println(10000000 * (2 / (Math.pow(10000000 * 1.0 / (2 - 1), 2 / 3.0))));
- List<Point> sampled2 = reducePoints(points, m, true);
- long endTime2 = System.currentTimeMillis();
- System.out.println("Time taken: " + (endTime2 - startTime2) + "ms");
- // for (Point p : sampled2) {
- // System.out.println(p);
- // }
- // System.out.println(sampled2.size());
- }
+ long startTime2 = System.currentTimeMillis();
+ // System.out.println(points.size() * m / (Math.pow(points.size() * 1.0 / (m - 1), 2 /
+ // 3.0)));
+ // System.out.println(10000000 * (2 / (Math.pow(10000000 * 1.0 / (2 - 1), 2 / 3.0))));
+ List<Point> sampled2 = reducePoints(points, m, true);
+ long endTime2 = System.currentTimeMillis();
+ System.out.println("Time taken: " + (endTime2 - startTime2) + "ms");
+ // for (Point p : sampled2) {
+ // System.out.println(p);
+ // }
+ // System.out.println(sampled2.size());
+ }
}