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 aaa8825052f686955294ba4d5380b2cd39064433 Author: Lei Rui <[email protected]> AuthorDate: Thu Jan 23 18:04:13 2025 +0800 add m --- .../java/org/apache/iotdb/db/query/eBUG/Test1.java | 4 +- .../java/org/apache/iotdb/db/query/eBUG/Test2.java | 41 +++++++++++++++++++ .../java/org/apache/iotdb/db/query/eBUG/eBUG.java | 46 ++++++++++++++++++++-- 3 files changed, 86 insertions(+), 5 deletions(-) diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java index 426cfdc538d..f53f5719217 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java @@ -13,7 +13,7 @@ public class Test1 { public static void main(String[] args) { Polyline polyline = new Polyline(); List<Polyline> polylineList = new ArrayList<>(); - Random rand = new Random(2); + Random rand = new Random(3); int n = 10000; int p = 10; @@ -44,7 +44,7 @@ public class Test1 { } System.out.println("---------------------------------"); - int eParam = 0; + int eParam = 1; long startTime = System.currentTimeMillis(); List<Point> results = buildEffectiveArea(polyline, eParam, false); // 输出结果 diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test2.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test2.java new file mode 100644 index 00000000000..589603525e5 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test2.java @@ -0,0 +1,41 @@ +package org.apache.iotdb.db.query.eBUG; + +import io.jsonwebtoken.lang.Assert; + +import java.util.List; +import java.util.Random; + +import static org.apache.iotdb.db.query.eBUG.eBUG.buildEffectiveArea; + +public class Test2 { + // 用于测试在线采样 + public static void main(String[] args) { + int n = 100000; + int eParam = 1; + +// int m = 100; // >2代表在线采样，<=2代表预计算 + for (int m = 9900; m <= n; m++) { + + Polyline polyline = new Polyline(); + Random rand = new Random(2); + for (int i = 0; i < n; i++) { + double v = rand.nextInt(1000000); + polyline.addVertex(new Point(i, v)); + } + + long startTime = System.currentTimeMillis(); + List<Point> results = buildEffectiveArea(polyline, eParam, false, m); + long endTime = System.currentTimeMillis(); + System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms"); + + System.out.println(results.size()); + Assert.isTrue(results.size() == m); + } +// if (results.size() <= 100) { +// System.out.println("+++++++++++++++++++"); +// for (Point point : results) { +// System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")"); +// } +// } + } +} diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java index e283789239a..b9147e4c574 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java @@ -56,10 +56,21 @@ public class eBUG { } public static List<Point> buildEffectiveArea(Polyline lineToSimplify, int e, boolean debug) { + // precomputation mode + return buildEffectiveArea(lineToSimplify, e, debug, 0); + } + + public static List<Point> buildEffectiveArea(Polyline lineToSimplify, int e, boolean debug, int m) { if (e < 0) { throw new IllegalArgumentException("Parameter e must be non-negative."); } + if (m > 2) { + System.out.println("online sampling mode, returning " + m + " sampled points"); + } else { + System.out.println("offline precomputation mode, returning each point with dominated significance"); + } + List<Point> results = lineToSimplify.getVertices(); // 浅复制 // 存储的是点的引用，这样可以修改原来序列里点的淘汰状态 @@ -100,7 +111,13 @@ public class eBUG { Collections.addAll(triangleHeap, triangles); // complexity TODO O(n) or O(nlogn)? double previousEA = -1; - while (!triangleHeap.isEmpty()) { +// while (!triangleHeap.isEmpty()) { // TODO 注意triangleHeap里装的是non-terminal point对应的三角形 + // TODO 在线采样m个点，也就是说最后留下m-2个non-terminal point + // 注意：triangleHeap里装的包括了标记删除的点！所以triangleHeap.size()不是真正的留下的未被淘汰点数！ + // 因此需要用fakeCnt来统计heap里的非真实点数，这样triangleHeap.size()-fakeCnt就是真正的留下的未被淘汰点数 + int remainNonTerminalPoint = Math.max(0, m - 2); + int fakeCnt = 0; + while (triangleHeap.size() - fakeCnt > remainNonTerminalPoint) { // 注意peek只需要直接访问该位置的元素，不涉及任何重排或堆化操作 // 而poll是删除堆顶元素，需要重新堆化以维护堆的性质，复杂度是O(logk),k是当前堆的大小 Triangle tri = triangleHeap.poll(); // O(logn) @@ -108,6 +125,7 @@ public class eBUG { // 如果该三角形已经被删除，跳过. Avoid using heap.remove(x) as it is O(n) complexity // 而且除了heap里，已经没有其他节点会和它关联了，所有的connections关系已经迁移到新的角色替代节点上 if (tri.isDeleted) { + fakeCnt--; // 取出了一个被标记删除点 if (debug) { System.out.println(">>>bottom-up, remaining " + triangleHeap.size() + " triangles (including those marked for removal)"); } @@ -185,6 +203,7 @@ public class eBUG { // 在 Java 的 PriorityQueue 中，修改元素的属性不会自动更新堆的顺序 // 所以必须通过add来显式重新插入修改后的元素 triangleHeap.add(tri.prev); // O(logn) 注意加入的是一个新的对象isDeleted=false + fakeCnt++; // 表示heap里多了一个被标记删除的假点 } if (tri.next != null) { @@ -232,12 +251,33 @@ public class eBUG { // 在 Java 的 PriorityQueue 中，修改元素的属性不会自动更新堆的顺序 // 所以必须通过add 来显式重新插入修改后的元素 triangleHeap.add(tri.next); // 注意加入的是一个新的对象isDeleted=false + fakeCnt++; // 表示heap里多了一个被标记删除的假点 } if (debug) { System.out.println(">>>bottom-up, remaining " + triangleHeap.size() + " triangles (including those marked for removal)"); } } - return results; // 注意这就是lineToSimplify.getVertices() + + if (m > 2) { // online sampling mode + // 把滞后的淘汰点施加上去，然后返回在线采样结果（也就是返回剩余未被淘汰的点） + for (Point p : laggedEliminatedPoints) { + p.markEliminated(); + if (debug) { + System.out.println("apply lagged elimination of " + p); + } + } + List<Point> onlineSampled = new ArrayList<>(); + Point start = lineToSimplify.get(0); + Point end = lineToSimplify.get(lineToSimplify.size() - 1); + while (start != end) { // Point类里增加prev&next指针，这样T'_max{0,k-e}里点的连接关系就有了，这样从Pa开始沿着指针，遍历点数一定不超过e+3 + onlineSampled.add(start); + start = start.next; // when e=0, only traversing three points pa pi pb + } + onlineSampled.add(end); + return onlineSampled; + } else { // offline precomputation mode, for precomputing the dominated significance of each point + return results; // 注意这就是lineToSimplify.getVertices() + } } public static void main(String[] args) { @@ -262,7 +302,7 @@ public class eBUG { } long startTime = System.currentTimeMillis(); - List<Point> results = buildEffectiveArea(polyline, eParam, false); + List<Point> results = buildEffectiveArea(polyline, eParam, false, 0); long endTime = System.currentTimeMillis(); System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms");
