This is an automated email from the ASF dual-hosted git repository. leirui pushed a commit to branch research/LTS-visualization in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit ba493800bf842c9ccfd2c959124b48c59e78d114 Author: Lei Rui <[email protected]> AuthorDate: Sun Jul 21 23:45:32 2024 +0800 update readme --- README.md | 7 +- .../groupby/LocalGroupByExecutorTri_SimPiece.java | 6 - .../org/apache/iotdb/db/query/simpiece/FSW.java | 3 - .../iotdb/db/query/simpiece/MySample_fsw.java | 24 +-- .../iotdb/db/query/simpiece/MySample_fsw_full.java | 12 +- .../query/simpiece/MySample_fsw_full_serial.java | 198 -------------------- .../db/query/simpiece/MySample_shrinkingcone.java | 25 +-- .../simpiece/MySample_shrinkingcone_full.java | 16 +- .../MySample_shrinkingcone_full_serial.java | 195 -------------------- .../iotdb/db/query/simpiece/MySample_simpiece.java | 29 +-- .../db/query/simpiece/MySample_simpiece_full.java | 8 +- .../simpiece/MySample_simpiece_full_serial.java | 199 -------------------- .../iotdb/db/query/simpiece/MySample_visval.java | 94 ---------- .../org/apache/iotdb/db/query/simpiece/Visval.java | 41 ----- .../iotdb/db/query/simpiece/VisvalPoint.java | 23 ++- .../apache/iotdb/db/query/simpiece/Visvalold.java | 203 --------------------- 16 files changed, 59 insertions(+), 1024 deletions(-) diff --git a/README.md b/README.md index 4f288392135..f4b5b8681fc 100644 --- a/README.md +++ b/README.md @@ -23,8 +23,13 @@ - The code for ILTS and other baselines compared in experiments are available in this repository. - ILTS is implemented in [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_ILTS.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_ILTS.java) with convex hull precomputation in [tsfile/src/main/java/org/apache/iotdb/tsfile/file/metadata/statistics/Statistics.java](tsfile/src/main/java/org/apache/iotdb/tsfile/file/metadata/statistics/Statistics.java). - LTTB is implemented in [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_LTTB.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_LTTB.java). + - MinMaxLTTB is implemented in [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_MinMaxPreselection.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_MinMaxPreselection.java) and [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java). + - Visval is implemented in [server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval.java](server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval.java). - MinMax is implemented in [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_MinMax.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_MinMax.java). - M4 is implemented in [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_M4.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_M4.java). - - MinMaxLTTB is implemented in [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_MinMaxPreselection.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_MinMaxPreselection.java) and [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java). + - Uniform is implemented in [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_Uniform.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_Uniform.java). + - FSW is implemented in [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_FSW.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_FSW.java) and [server/src/main/java/org/apache/iotdb/db/query/simpiece/FSW.java](server/src/main/java/org/apache/iotdb/db/query/simpiece/FSW.java). + - SC is implemented in [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_SC.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_SC.java) and [server/src/main/java/org/apache/iotdb/db/query/simpiece/ShrinkingCone.java](server/src/main/java/org/apache/iotdb/db/query/simpiece/ShrinkingCone.java). + - Sim-Piece is implemented in [server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_SimPiece.java](server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_SimPiece.java) and [server/src/main/java/org/apache/iotdb/db/query/simpiece/SimPiece.java](server/src/main/java/org/apache/iotdb/db/query/simpiece/SimPiece.java). - Some integration tests for correctness are in [server/src/test/java/org/apache/iotdb/db/integration/tri/MyTest_ILTS.java](server/src/test/java/org/apache/iotdb/db/integration/tri/MyTest_ILTS.java). - For the README of [Apache IoTDB](https://iotdb.apache.org/) itself, please see [README_IOTDB.md](README_IOTDB.md). To build this repository, run `mvn clean package -DskipTests -pl -distribution`. diff --git a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_SimPiece.java b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_SimPiece.java index 0a9b4fbefa5..3412d022d09 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_SimPiece.java +++ b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_SimPiece.java @@ -133,9 +133,6 @@ public class LocalGroupByExecutorTri_SimPiece implements GroupByExecutor { result.reset(); } - // - // series.append(CONFIG.getP1v()).append("[").append(CONFIG.getP1t()).append("]").append(","); - SimPiece simPiece = new SimPiece(timeSeries.data, epsilon); List<SimPieceSegment> segments = simPiece.segments; segments.sort(Comparator.comparingLong(SimPieceSegment::getInitTimestamp)); @@ -176,9 +173,6 @@ public class LocalGroupByExecutorTri_SimPiece implements GroupByExecutor { .append("]") .append(","); - // - // series.append(CONFIG.getPnv()).append("[").append(CONFIG.getPnt()).append("]").append(","); - MinValueAggrResult minValueAggrResult = (MinValueAggrResult) results.get(0); minValueAggrResult.updateResult(new MinMaxInfo<>(series.toString(), 0)); diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/FSW.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/FSW.java index 4b2e0163e1a..057e7c29607 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/FSW.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/FSW.java @@ -57,14 +57,12 @@ public class FSW { ((p_upper[i] - points.get(segmentPoint.get(seg_no)[1]).getValue()) / (points.get(i).getTimestamp() - points.get(segmentPoint.get(seg_no)[1]).getTimestamp()))); - // (i - segmentPoint.get(seg_no)[1]))); lowSlope = Math.max( lowSlope, ((p_lower[i] - points.get(segmentPoint.get(seg_no)[1]).getValue()) / (points.get(i).getTimestamp() - points.get(segmentPoint.get(seg_no)[1]).getTimestamp()))); - // (i - segmentPoint.get(seg_no)[1]))); if (upSlope < lowSlope) { seg_no += 1; segmentPoint.add(new int[] {seg_no, csp_id}); @@ -76,7 +74,6 @@ public class FSW { (points.get(i).getValue() - points.get(segmentPoint.get(seg_no)[1]).getValue()) / (points.get(i).getTimestamp() - points.get(segmentPoint.get(seg_no)[1]).getTimestamp()); - // (i - segmentPoint.get(seg_no)[1]); if (s >= lowSlope && s <= upSlope) { csp_id = i; } diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_fsw.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_fsw.java index da43f5b824e..358b1e2d891 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_fsw.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_fsw.java @@ -31,25 +31,17 @@ public class MySample_fsw { public static void main(String[] args) { String fileDir = "D:\\desktop\\NISTPV\\"; - String[] datasetNameList = - new String[]{ - "NISTPV-Ground-2015-Qloss_Ah", - "NISTPV-Ground-2015-Pyra1_Wm2", - "NISTPV-Ground-2015-RTD_C_3", - "NISTPV-Ground-2015-WindSpeed_ms" - }; - int[] noutList = new int[]{100}; - double[] r = new double[]{0.1, 0.5, 1.3, 0}; - int[] NList = new int[]{2500000, 2500000, 2500000, 500000}; - double[] epsilonList = new double[]{9.999999E-4, 284.4034399986267, 6.428162097930908,10.814893245697021}; - for (int y = 3; y < datasetNameList.length; y++) { + String[] datasetNameList = new String[] {"Qloss", "Pyra1", "RTD", "WindSpeed"}; + int[] noutList = new int[] {100}; + double[] r = new double[] {0.1, 0.5, 1.3, 0}; + int[] NList = new int[] {2500000, 2500000, 2500000, 500000}; + double[] epsilonList = + new double[] {9.999999E-4, 284.4034399986267, 6.428162097930908, 10.814893245697021}; + for (int y = 0; y < datasetNameList.length; y++) { String datasetName = datasetNameList[y]; int start = (int) (10000000 / 2 - NList[y] * r[y]); // 从0开始计数 int end = (int) (10000000 / 2 + NList[y] * (1 - r[y])); int N = end - start; - // int start = 0; - // int end = 10000; - // int N = end - start; for (int nout : noutList) { boolean hasHeader = false; @@ -58,7 +50,7 @@ public class MySample_fsw { TimeSeries ts = TimeSeriesReader.getMyTimeSeries( inputStream, delimiter, false, N, start, hasHeader, false); -// double epsilon = getFSWParam(nout, ts, 1e-6); + // double epsilon = getFSWParam(nout, ts, 1e-6); double epsilon = epsilonList[y]; List<Point> reducedPoints = FSW.reducePoints(ts.data, epsilon); System.out.println( diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_fsw_full.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_fsw_full.java index e4e581488dd..706e140a1fd 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_fsw_full.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_fsw_full.java @@ -31,13 +31,7 @@ public class MySample_fsw_full { public static void main(String[] args) { String fileDir = "D:\\desktop\\NISTPV\\"; - String[] datasetNameList = - new String[] { - "NISTPV-Ground-2015-WindSpeed_ms", - "NISTPV-Ground-2015-Qloss_Ah", - "NISTPV-Ground-2015-Pyra1_Wm2", - "NISTPV-Ground-2015-RTD_C_3" - }; + String[] datasetNameList = new String[] {"WindSpeed", "Qloss", "Pyra1", "RTD"}; int[] noutList = new int[] {320, 360, 400, 440, 480, 520, 560, 600, 640}; double[][] epsilonArray = { @@ -142,8 +136,8 @@ public class MySample_fsw_full { } } - for (int i = 0; i < epsilonArray.length; i++) { // 遍历行 - for (int j = 0; j < epsilonArray[i].length; j++) { // 遍历列 + for (int i = 0; i < epsilonArray.length; i++) { + for (int j = 0; j < epsilonArray[i].length; j++) { System.out.print(epsilonArray[i][j] + ","); } System.out.println(); diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_fsw_full_serial.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_fsw_full_serial.java deleted file mode 100644 index b51c8dddcb2..00000000000 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_fsw_full_serial.java +++ /dev/null @@ -1,198 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - -// Sim-Piece code forked from https://github.com/xkitsios/Sim-Piece.git - -package org.apache.iotdb.db.query.simpiece; - -import java.io.FileInputStream; -import java.io.FileWriter; -import java.io.IOException; -import java.io.PrintWriter; -import java.util.List; - -public class MySample_fsw_full_serial { - - public static void main(String[] args) { - String fileDir = "D:\\desktop\\NISTPV\\"; - String[] datasetNameList = - new String[] { - "NISTPV-Ground-2015-WindSpeed_ms", - "NISTPV-Ground-2015-Qloss_Ah", - "NISTPV-Ground-2015-Pyra1_Wm2", - "NISTPV-Ground-2015-RTD_C_3" - }; - int[] noutList = new int[] {320, 360, 400, 440, 480, 520, 560, 600, 640}; - - double[][] epsilonArray = { - { - 9.618271350860596, - 9.101282596588135, - 8.991526126861572, - 8.62817907333374, - 8.374999523162842, - 8.202636241912842, - 7.999906063079834, - 7.947059154510498, - 7.858933925628662 - }, - { - 9.999275207519531E-4, - 9.989738464355469E-4, - 9.980201721191406E-4, - 9.970664978027344E-4, - 9.961128234863281E-4, - 9.951591491699219E-4, - 9.942054748535156E-4, - 9.932518005371094E-4, - 9.922981262207031E-4 - }, - { - 440.0235962867737, - 432.0247492790222, - 423.55674982070923, - 414.65001153945923, - 405.77113008499146, - 401.21820974349976, - 396.7935194969177, - 393.2065939903259, - 392.30953645706177 - }, - { - 9.295397281646729, - 8.096678256988525, - 7.536666393280029, - 6.961357593536377, - 6.473535060882568, - 6.064479351043701, - 5.743286609649658, - 5.5219340324401855, - 5.185042858123779 - } - }; - - // double[][] epsilonArray = new double[datasetNameList.length][]; - // for (int i = 0; i < datasetNameList.length; i++) { - // epsilonArray[i] = new double[noutList.length]; - // } - - for (int y = 0; y < datasetNameList.length; y++) { - String datasetName = datasetNameList[y]; - int start = 0; - int end = 1000_0000; - int N = end - start; - boolean hasHeader = false; - try (FileInputStream inputStream = new FileInputStream(fileDir + datasetName + ".csv")) { - String delimiter = ","; - TimeSeries ts = - TimeSeriesReader.getMyTimeSeries( - inputStream, delimiter, false, N, start, hasHeader, true); - for (int x = 0; x < noutList.length; x++) { - int nout = noutList[x]; - // double epsilon = getFSWParam(nout, ts, 1e-6); - // epsilonArray[y][x] = epsilon; - - double epsilon = epsilonArray[y][x]; - - List<Point> reducedPoints = FSW.reducePoints(ts.data, epsilon); - System.out.println( - datasetName - + ": n=" - + N - + ",m=" - + nout - + ",epsilon=" - + epsilon - + ",actual m=" - + reducedPoints.size()); - try (PrintWriter writer = - new PrintWriter( - new FileWriter( - datasetName - + "-" - + N - + "-" - + nout - + "-" - + reducedPoints.size() - + "-fsw.csv"))) { - for (Point p : reducedPoints) { - writer.println(p.getTimestamp() + "," + p.getValue()); - } - } - } - } catch (Exception e) { - e.printStackTrace(); - } - } - - for (int i = 0; i < epsilonArray.length; i++) { // 遍历行 - for (int j = 0; j < epsilonArray[i].length; j++) { // 遍历列 - System.out.print(epsilonArray[i][j] + ","); - } - System.out.println(); - } - } - - public static double getFSWParam(int nout, TimeSeries ts, double accuracy) throws IOException { - double epsilon = 1; - boolean directLess = false; - boolean directMore = false; - while (true) { - List<Point> reducedPoints = FSW.reducePoints(ts.data, epsilon); - if (reducedPoints.size() > nout) { - if (directMore) { - break; - } - if (!directLess) { - directLess = true; - } - epsilon *= 2; - } else { - if (directLess) { - break; - } - if (!directMore) { - directMore = true; - } - epsilon /= 2; - } - } - double left = 0; - double right = 0; - if (directLess) { - left = epsilon / 2; - right = epsilon; - } - if (directMore) { - left = epsilon; - right = epsilon * 2; - } - while (Math.abs(right - left) > accuracy) { - double mid = (left + right) / 2; - List<Point> reducedPoints = FSW.reducePoints(ts.data, mid); - if (reducedPoints.size() > nout) { - left = mid; - } else { - right = mid; - } - } - return (left + right) / 2; - } -} diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone.java index 1b167064f62..f2e88ca98f3 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone.java @@ -31,26 +31,17 @@ public class MySample_shrinkingcone { public static void main(String[] args) { String fileDir = "D:\\desktop\\NISTPV\\"; - String[] datasetNameList = - new String[]{ - "NISTPV-Ground-2015-Qloss_Ah", - "NISTPV-Ground-2015-Pyra1_Wm2", - "NISTPV-Ground-2015-RTD_C_3", - "NISTPV-Ground-2015-WindSpeed_ms" - }; - int[] noutList = new int[]{100}; - double[] r = new double[]{0.1, 0.5, 1.3, 0}; - int[] NList = new int[]{2500000, 2500000, 2500000, 500000}; - double[] epsilonList = new double[]{0.001, 408.55843019485474, 7.996772289276123, - 14.692305088043213}; - for (int y = 3; y < datasetNameList.length; y++) { + String[] datasetNameList = new String[] {"Qloss", "Pyra1", "RTD", "WindSpeed"}; + int[] noutList = new int[] {100}; + double[] r = new double[] {0.1, 0.5, 1.3, 0}; + int[] NList = new int[] {2500000, 2500000, 2500000, 500000}; + double[] epsilonList = + new double[] {0.001, 408.55843019485474, 7.996772289276123, 14.692305088043213}; + for (int y = 0; y < datasetNameList.length; y++) { String datasetName = datasetNameList[y]; int start = (int) (10000000 / 2 - NList[y] * r[y]); // 从0开始计数 int end = (int) (10000000 / 2 + NList[y] * (1 - r[y])); int N = end - start; - // int start = 0; - // int end = 10000; - // int N = end - start; for (int nout : noutList) { boolean hasHeader = false; @@ -59,7 +50,7 @@ public class MySample_shrinkingcone { TimeSeries ts = TimeSeriesReader.getMyTimeSeries( inputStream, delimiter, false, N, start, hasHeader, false); -// double epsilon = getSCParam(nout, ts, 1e-6); + // double epsilon = getSCParam(nout, ts, 1e-6); double epsilon = epsilonList[y]; List<Point> reducedPoints = ShrinkingCone.reducePoints(ts.data, epsilon); System.out.println( diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone_full.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone_full.java index 6cb8dd16a92..3ab602021f9 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone_full.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone_full.java @@ -31,19 +31,9 @@ public class MySample_shrinkingcone_full { public static void main(String[] args) { String fileDir = "D:\\desktop\\NISTPV\\"; - String[] datasetNameList = - new String[] { - "NISTPV-Ground-2015-WindSpeed_ms", - "NISTPV-Ground-2015-Qloss_Ah", - "NISTPV-Ground-2015-Pyra1_Wm2", - "NISTPV-Ground-2015-RTD_C_3" - }; + String[] datasetNameList = new String[] {"WindSpeed", "Qloss", "Pyra1", "RTD"}; int[] noutList = new int[] {320, 360, 400, 440, 480, 520, 560, 600, 640}; - // double[] epsilonList = new double[]{0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, - // 0.001, - // 0.0009999999999999999}; - double[][] epsilonArray = { { 14.388325214385986, @@ -92,7 +82,7 @@ public class MySample_shrinkingcone_full { int end = 1000_0000; int N = end - start; boolean hasHeader = false; - try (FileInputStream inputStream = new FileInputStream(fileDir + datasetName + ".csv")) { + try (FileInputStream inputStream = new FileInputStream(fileDir + datasetName + ".csv")) { String delimiter = ","; TimeSeries ts = TimeSeriesReader.getMyTimeSeries( @@ -105,8 +95,6 @@ public class MySample_shrinkingcone_full { double epsilon = epsilonArray[y][x]; - // double epsilon = epsilonList[x]; // 单独给Qloss手调 - List<Point> reducedPoints = ShrinkingCone.reducePoints(ts.data, epsilon); System.out.println( datasetName diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone_full_serial.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone_full_serial.java deleted file mode 100644 index c2705919029..00000000000 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone_full_serial.java +++ /dev/null @@ -1,195 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - -// Sim-Piece code forked from https://github.com/xkitsios/Sim-Piece.git - -package org.apache.iotdb.db.query.simpiece; - -import java.io.FileInputStream; -import java.io.FileWriter; -import java.io.IOException; -import java.io.PrintWriter; -import java.util.List; - -public class MySample_shrinkingcone_full_serial { - - public static void main(String[] args) { - String fileDir = "D:\\desktop\\NISTPV\\"; - String[] datasetNameList = - new String[] { - "NISTPV-Ground-2015-WindSpeed_ms", - "NISTPV-Ground-2015-Qloss_Ah", - "NISTPV-Ground-2015-Pyra1_Wm2", - "NISTPV-Ground-2015-RTD_C_3" - }; - int[] noutList = new int[] {320, 360, 400, 440, 480, 520, 560, 600, 640}; - - // double[] epsilonList = new double[]{0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, - // 0.001, - // 0.0009999999999999999}; - - double[][] epsilonArray = { - { - 14.388325214385986, - 13.768231868743896, - 13.343345165252686, - 13.091249942779541, - 12.69767427444458, - 12.391706943511963, - 12.167190074920654, - 11.972727298736572, - 11.756273746490479 - }, - {0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.0009999999999999999}, - { - 680.2196469306946, - 665.2842917442322, - 650.2610821723938, - 636.7945942878723, - 620.9016032218933, - 604.7394433021545, - 592.9867577552795, - 578.6471419334412, - 570.5106825828552 - }, - { - 11.259880542755127, - 10.37297010421753, - 9.402754306793213, - 8.867334842681885, - 8.384315967559814, - 7.915340900421143, - 7.39516019821167, - 6.892223834991455, - 6.5178914070129395 - } - }; - - // double[][] epsilonArray = new double[datasetNameList.length][]; - // for (int i = 0; i < datasetNameList.length; i++) { - // epsilonArray[i] = new double[noutList.length]; - // } - - for (int y = 0; y < datasetNameList.length; y++) { - String datasetName = datasetNameList[y]; - int start = 0; - int end = 1000_0000; - int N = end - start; - boolean hasHeader = false; - try (FileInputStream inputStream = new FileInputStream(fileDir + datasetName + ".csv")) { - String delimiter = ","; - TimeSeries ts = - TimeSeriesReader.getMyTimeSeries( - inputStream, delimiter, false, N, start, hasHeader, true); - for (int x = 0; x < noutList.length; x++) { - int nout = noutList[x]; - - // double epsilon = getSCParam(nout, ts, 1e-6); - // epsilonArray[y][x] = epsilon; - - double epsilon = epsilonArray[y][x]; - - // double epsilon = epsilonList[x]; // 单独给Qloss手调 - - List<Point> reducedPoints = ShrinkingCone.reducePoints(ts.data, epsilon); - System.out.println( - datasetName - + ": n=" - + N - + ",m=" - + nout - + ",epsilon=" - + epsilon - + ",actual m=" - + reducedPoints.size()); - try (PrintWriter writer = - new PrintWriter( - new FileWriter( - datasetName - + "-" - + N - + "-" - + nout - + "-" - + reducedPoints.size() - + "-sc.csv"))) { - for (Point p : reducedPoints) { - writer.println(p.getTimestamp() + "," + p.getValue()); - } - } - } - } catch (Exception e) { - e.printStackTrace(); - } - } - - for (int i = 0; i < epsilonArray.length; i++) { // 遍历行 - for (int j = 0; j < epsilonArray[i].length; j++) { // 遍历列 - System.out.print(epsilonArray[i][j] + ","); - } - System.out.println(); - } - } - - public static double getSCParam(int nout, TimeSeries ts, double accuracy) throws IOException { - double epsilon = 1; - boolean directLess = false; - boolean directMore = false; - while (true) { - List<Point> reducedPoints = ShrinkingCone.reducePoints(ts.data, epsilon); - if (reducedPoints.size() > nout) { - if (directMore) { - break; - } - if (!directLess) { - directLess = true; - } - epsilon *= 2; - } else { - if (directLess) { - break; - } - if (!directMore) { - directMore = true; - } - epsilon /= 2; - } - } - double left = 0; - double right = 0; - if (directLess) { - left = epsilon / 2; - right = epsilon; - } - if (directMore) { - left = epsilon; - right = epsilon * 2; - } - while (Math.abs(right - left) > accuracy) { - double mid = (left + right) / 2; - List<Point> reducedPoints = ShrinkingCone.reducePoints(ts.data, mid); - if (reducedPoints.size() > nout) { - left = mid; - } else { - right = mid; - } - } - return (left + right) / 2; - } -} diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece.java index 8792c3a327e..c0f64f24a46 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece.java @@ -32,26 +32,17 @@ public class MySample_simpiece { public static void main(String[] args) { String fileDir = "D:\\desktop\\NISTPV\\"; - String[] datasetNameList = - new String[]{ - "NISTPV-Ground-2015-Qloss_Ah", - "NISTPV-Ground-2015-Pyra1_Wm2", - "NISTPV-Ground-2015-RTD_C_3", - "NISTPV-Ground-2015-WindSpeed_ms" - }; - int[] noutList = new int[]{100}; - double[] r = new double[]{0.1, 0.5, 1.3, 0}; - double[] epsilonList = new double[]{0.0009999, 316.5642651891633, 9.186667042922977, - 11.162719900131227}; - int[] NList = new int[]{2500000, 2500000, 2500000, 500000}; - for (int y = 3; y < datasetNameList.length; y++) { + String[] datasetNameList = new String[] {"Qloss", "Pyra1", "RTD", "WindSpeed"}; + int[] noutList = new int[] {100}; + double[] r = new double[] {0.1, 0.5, 1.3, 0}; + double[] epsilonList = + new double[] {0.0009999, 316.5642651891633, 9.186667042922977, 11.162719900131227}; + int[] NList = new int[] {2500000, 2500000, 2500000, 500000}; + for (int y = 0; y < datasetNameList.length; y++) { String datasetName = datasetNameList[y]; int start = (int) (10000000 / 2 - NList[y] * r[y]); // 从0开始计数 int end = (int) (10000000 / 2 + NList[y] * (1 - r[y])); int N = end - start; - // int start = 0; - // int end = 10000; - // int N = end - start; for (int nout : noutList) { // apply Sim-Piece on the input file, outputting nout points saved in csvFile @@ -61,7 +52,7 @@ public class MySample_simpiece { TimeSeries ts = TimeSeriesReader.getMyTimeSeries( inputStream, delimiter, false, N, start, hasHeader, false); -// double epsilon = getSimPieceParam(nout, ts, 1e-6); + // double epsilon = getSimPieceParam(nout, ts, 1e-6); double epsilon = epsilonList[y]; SimPiece simPiece = new SimPiece(ts.data, epsilon); System.out.println( @@ -86,7 +77,7 @@ public class MySample_simpiece { // end point of this segment double v = (segments.get(i + 1).getInitTimestamp() - segments.get(i).getInitTimestamp()) - * segments.get(i).getA() + * segments.get(i).getA() + segments.get(i).getB(); writer.println(segments.get(i + 1).getInitTimestamp() + "," + v); } @@ -97,7 +88,7 @@ public class MySample_simpiece { + segments.get(segments.size() - 1).getB()); double v = (simPiece.lastTimeStamp - segments.get(segments.size() - 1).getInitTimestamp()) - * segments.get(segments.size() - 1).getA() + * segments.get(segments.size() - 1).getA() + segments.get(segments.size() - 1).getB(); writer.println(simPiece.lastTimeStamp + "," + v); } diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece_full.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece_full.java index e7a2cd19c43..16876b2886b 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece_full.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece_full.java @@ -32,13 +32,7 @@ public class MySample_simpiece_full { public static void main(String[] args) { String fileDir = "D:\\desktop\\NISTPV\\"; - String[] datasetNameList = - new String[] { - "NISTPV-Ground-2015-WindSpeed_ms", - "NISTPV-Ground-2015-Qloss_Ah", - "NISTPV-Ground-2015-Pyra1_Wm2", - "NISTPV-Ground-2015-RTD_C_3" - }; + String[] datasetNameList = new String[] {"WindSpeed", "Qloss", "Pyra1", "RTD"}; int[] noutList = new int[] {320, 360, 400, 440, 480, 520, 560, 600, 640}; double[][] epsilonArray = { diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece_full_serial.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece_full_serial.java deleted file mode 100644 index 4dd8c88eaf7..00000000000 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece_full_serial.java +++ /dev/null @@ -1,199 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - -// Sim-Piece code forked from https://github.com/xkitsios/Sim-Piece.git - -package org.apache.iotdb.db.query.simpiece; - -import java.io.FileInputStream; -import java.io.FileWriter; -import java.io.IOException; -import java.io.PrintWriter; -import java.util.Comparator; -import java.util.List; - -public class MySample_simpiece_full_serial { - - public static void main(String[] args) { - String fileDir = "D:\\desktop\\NISTPV\\"; - String[] datasetNameList = - new String[] { - "NISTPV-Ground-2015-WindSpeed_ms", - "NISTPV-Ground-2015-Qloss_Ah", - "NISTPV-Ground-2015-Pyra1_Wm2", - "NISTPV-Ground-2015-RTD_C_3" - }; - int[] noutList = new int[] {320, 360, 400, 440, 480, 520, 560, 600, 640}; - - double[][] epsilonArray = { - { - 10.470000203704831, - 9.973635465240477, - 9.571347576141356, - 9.339938166046142, - 9.208912633514405, - 9.135163892364506, - 8.744444478607178, - 8.61042620162964, - 8.422101323699948 - }, - { - 9.987499999999999E-4, - 9.974999999999997E-4, - 9.784999999999998E-4, - 9.4425E-4, - 9.255E-4, - 8.8375E-4, - 8.4775E-4, - 7.865E-4, - 7.3825E-4 - }, - { - 502.0505219552564, - 493.3274919509581, - 485.91779255051347, - 479.26180967157245, - 463.5216509033579, - 446.88677012006065, - 441.2913785749938, - 435.45897277584766, - 426.0481592410648 - }, - { - 13.678959740142822, - 12.275238493499756, - 11.224719192962645, - 10.475999729766848, - 9.741776887359617, - 9.125823136444094, - 8.625197060394289, - 8.105121862335203, - 7.743280215911865 - } - }; - - // double[][] epsilonArray = new double[datasetNameList.length][]; - // for (int i = 0; i < datasetNameList.length; i++) { - // epsilonArray[i] = new double[noutList.length]; - // } - - for (int y = 0; y < datasetNameList.length; y++) { - String datasetName = datasetNameList[y]; - int start = 0; - int end = 1000_0000; - int N = end - start; - // apply Sim-Piece on the input file, outputting nout points saved in csvFile - boolean hasHeader = false; - try (FileInputStream inputStream = new FileInputStream(fileDir + datasetName + ".csv")) { - String delimiter = ","; - TimeSeries ts = - TimeSeriesReader.getMyTimeSeries( - inputStream, delimiter, false, N, start, hasHeader, true); - for (int x = 0; x < noutList.length; x++) { - int nout = noutList[x]; - - // double epsilon = getSimPieceParam(nout, ts, 1e-6); - // epsilonArray[y][x] = epsilon; - - double epsilon = epsilonArray[y][x]; - - SimPiece simPiece = new SimPiece(ts.data, epsilon); - System.out.println( - datasetName - + ": n=" - + N - + ",m=" - + nout - + ",epsilon=" - + epsilon - + ",actual m=" - + simPiece.segments.size() * 2); - List<SimPieceSegment> segments = simPiece.segments; - segments.sort(Comparator.comparingLong(SimPieceSegment::getInitTimestamp)); - try (PrintWriter writer = - new PrintWriter( - new FileWriter( - datasetName - + "-" - + N - + "-" - + nout - + "-" - + segments.size() * 2 - + "-simpiece.csv"))) { - for (int i = 0; i < segments.size() - 1; i++) { - // start point of this segment - writer.println(segments.get(i).getInitTimestamp() + "," + segments.get(i).getB()); - // end point of this segment - double v = - (segments.get(i + 1).getInitTimestamp() - segments.get(i).getInitTimestamp()) - * segments.get(i).getA() - + segments.get(i).getB(); - writer.println(segments.get(i + 1).getInitTimestamp() + "," + v); - } - // the two end points of the last segment - writer.println( - segments.get(segments.size() - 1).getInitTimestamp() - + "," - + segments.get(segments.size() - 1).getB()); - double v = - (simPiece.lastTimeStamp - segments.get(segments.size() - 1).getInitTimestamp()) - * segments.get(segments.size() - 1).getA() - + segments.get(segments.size() - 1).getB(); - writer.println(simPiece.lastTimeStamp + "," + v); - } - } - } catch (Exception e) { - e.printStackTrace(); - } - } - - for (int i = 0; i < epsilonArray.length; i++) { // 遍历行 - for (int j = 0; j < epsilonArray[i].length; j++) { // 遍历列 - System.out.print(epsilonArray[i][j] + ","); - } - System.out.println(); - } - } - - public static double getSimPieceParam(int nout, TimeSeries ts, double accuracy) - throws IOException { - double epsilon = ts.range * 0.001; - while (true) { - SimPiece simPiece = new SimPiece(ts.data, epsilon); - if (simPiece.segments.size() * 2 > nout) { // note *2 for disjoint - epsilon *= 2; - } else { - break; - } - } - double left = epsilon / 2; - double right = epsilon; - while (Math.abs(right - left) > accuracy) { - double mid = (left + right) / 2; - SimPiece simPiece = new SimPiece(ts.data, mid); - if (simPiece.segments.size() * 2 > nout) { // note *2 for disjoint - left = mid; - } else { - right = mid; - } - } - return (left + right) / 2; - } -} diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_visval.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_visval.java deleted file mode 100644 index 1ed02baba7c..00000000000 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_visval.java +++ /dev/null @@ -1,94 +0,0 @@ -// * Licensed to the Apache Software Foundation (ASF) under one -// * or more contributor license agreements. See the NOTICE file -// * distributed with this work for additional information -// * regarding copyright ownership. The ASF licenses this file -// * to you under the Apache License, Version 2.0 (the -// * "License"); you may not use this file except in compliance -// * with the License. You may obtain a copy of the License at -// * -// * http://www.apache.org/licenses/LICENSE-2.0 -// * -// * Unless required by applicable law or agreed to in writing, -// * software distributed under the License is distributed on an -// * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY -// * KIND, either express or implied. See the License for the -// * specific language governing permissions and limitations -// * under the License. -// */ -// Sim-Piece code forked from https://github.com/xkitsios/Sim-Piece.git - -package org.apache.iotdb.db.query.simpiece; - -import java.io.FileInputStream; -import java.io.FileWriter; -import java.io.PrintWriter; -import java.util.List; - -public class MySample_visval { - - public static void main(String[] args) { - String fileDir = "D:\\desktop\\NISTPV\\"; - String[] datasetNameList = - new String[] { - "NISTPV-Ground-2015-Qloss_Ah", - // "NISTPV-Ground-2015-Pyra1_Wm2", - // "NISTPV-Ground-2015-RTD_C_3" - }; - - int[] noutList = new int[] {2400000}; - - double[] r = new double[] {0.1, 0.5, 1.3}; - for (int y = 0; y < datasetNameList.length; y++) { - String datasetName = datasetNameList[y]; - int start = (int) (10000000 / 2 - 2500000 * r[y]); // 从0开始计数 - int end = (int) (10000000 / 2 + 2500000 * (1 - r[y])); - int N = end - start; // -1 for all - // - // int start = 0; - // int end = 100000; - // int N = end - start; - - for (int nout : noutList) { - // apply Sim-Piece on the input file, outputting nout points saved in csvFile - boolean hasHeader = false; - try (FileInputStream inputStream = new FileInputStream(fileDir + datasetName + ".csv")) { - String delimiter = ","; - List<VisvalPoint> points = - TimeSeriesReader.getMyTimeSeriesVisval( - inputStream, delimiter, false, N, start, hasHeader, false); - System.out.println(points.size()); - System.out.println(nout); - - List<VisvalPoint> reducedPoints = Visval.reducePoints(points, nout); - try (PrintWriter writer = - new PrintWriter( - new FileWriter( - datasetName + "-" + N + "-" + reducedPoints.size() + "-visval.csv"))) { - for (VisvalPoint p : reducedPoints) { - writer.println(p.x + "," + p.y); - } - } - System.out.println(reducedPoints.size()); - } catch (Exception e) { - e.printStackTrace(); - } - } - } - } - - // List<Point> points = new ArrayList<>(); - // points.add(new Point(1, 10)); - // points.add(new Point(2, 20)); - // points.add(new Point(3, 15)); - // points.add(new Point(4, 10)); - // points.add(new Point(5, 30)); - // points.add(new Point(6, 25)); - // points.add(new Point(7, 20)); - // int m = 4; - // List<Point> reducedPoints = Visval.reducePoints(points, m); - // System.out.println("Reduced points:"); - // for (Point point : reducedPoints) { - // System.out.println("Timestamp: " + point.getTimestamp() + ", Value: " + - // point.getValue()); - // } -} diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval.java index d4b54d3adc1..62b3019edac 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval.java @@ -30,7 +30,6 @@ public class Visval { } ConcurrentSkipListMap<Double, VisvalPoint> minHeap = new ConcurrentSkipListMap<>(); - // 初始化双向链表和优先队列 for (int i = 1; i < points.size() - 1; i++) { VisvalPoint p = points.get(i); p.prev = points.get(i - 1); @@ -40,18 +39,15 @@ public class Visval { } while (points.size() > targetCount) { - // 移除面积最小的点 VisvalPoint p = minHeap.pollFirstEntry().getValue(); if (p == null) { return points; } - // 移除点 p VisvalPoint prev = p.prev; VisvalPoint next = p.next; prev.next = next; next.prev = prev; - // 更新相邻点的三角形面积 if (prev.prev != null) { minHeap.remove(prev.area); prev.area = calculateArea(prev.prev, prev, next); @@ -69,43 +65,6 @@ public class Visval { } private static double calculateArea(VisvalPoint a, VisvalPoint b, VisvalPoint c) { - // 计算三角形面积的函数 return Math.abs(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2.0; } - - // public static void main(String[] args) { - // List<VisvalPoint> points = new ArrayList<>(); - // List<Point> pointsold = new ArrayList<>(); - // // 添加点到列表 points 100万数据 - // Random rand = new Random(); - // - // int targetCount = 10; - // for (int i = 0; i < 10000; i++) { - // int v = rand.nextInt(1000); - // points.add(new VisvalPoint(i, v)); - // pointsold.add(new Point(i, v)); - // } - // - //// int targetCount = 9000000; - //// for (int i = 0; i < 10000000; i++) { - //// points.add(new VisvalPoint(i, rand.nextInt(1000))); - //// } - // - // // 计算运行时间 - // long startTime = System.currentTimeMillis(); - // - // List<VisvalPoint> reducedPoints = Visval.reducePoints(points, targetCount); - // for (VisvalPoint point : reducedPoints) { - // System.out.println("Timestamp: " + point.x + ", Value: " + point.y); - // } - // List<Point> reducedPointsold = Visvalold.reducePoints(pointsold, targetCount); - // for (Point point : reducedPointsold) { - // System.out.println("Timestamp: " + point.getTimestamp() + ", Value: " + - // point.getValue()); - // } - // // 输出结果 - // System.out.println(reducedPoints.size()); - // long endTime = System.currentTimeMillis(); - // System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms"); - // } } diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/VisvalPoint.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/VisvalPoint.java index ef29bc30c09..358c68d2cac 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/VisvalPoint.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/VisvalPoint.java @@ -1,10 +1,29 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + package org.apache.iotdb.db.query.simpiece; public class VisvalPoint { public double x, y; - public VisvalPoint prev, next; // 双向链表中的前驱和后继 - public double area; // 与相邻点形成的三角形面积 + public VisvalPoint prev, next; + public double area; VisvalPoint(double x, double y) { this.x = x; diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visvalold.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visvalold.java deleted file mode 100644 index 2592d042c3c..00000000000 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visvalold.java +++ /dev/null @@ -1,203 +0,0 @@ -// * Licensed to the Apache Software Foundation (ASF) under one -// * or more contributor license agreements. See the NOTICE file -// * distributed with this work for additional information -// * regarding copyright ownership. The ASF licenses this file -// * to you under the Apache License, Version 2.0 (the -// * "License"); you may not use this file except in compliance -// * with the License. You may obtain a copy of the License at -// * -// * http://www.apache.org/licenses/LICENSE-2.0 -// * -// * Unless required by applicable law or agreed to in writing, -// * software distributed under the License is distributed on an -// * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY -// * KIND, either express or implied. See the License for the -// * specific language governing permissions and limitations -// * under the License. -// */ - -package org.apache.iotdb.db.query.simpiece; - -import java.util.ArrayList; -import java.util.List; -import java.util.stream.IntStream; - -// Visvalingam-Whyatt method of poly-line vertex reduction -// -// Visvalingam, M and Whyatt J D (1993) -// "Line Generalisation by Repeated Elimination of Points", Cartographic J., 30 (1), 46 - 51 -// -// Described here: -// -// http://web.archive.org/web/20100428020453/http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html -// -// ========================================= -// -// The MIT License (MIT) -// -// Copyright (c) 2014 Elliot Hallmark -// -// Permission is hereby granted, free of charge, to any person obtaining a copy -// of this software and associated documentation files (the "Software"), to deal -// in the Software without restriction, including without limitation the rights -// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -// copies of the Software, and to permit persons to whom the Software is -// furnished to do so, subject to the following conditions: -// -// The above copyright notice and this permission notice shall be included in all -// copies or substantial portions of the Software. -// -// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE -// SOFTWARE. -// -// ================================ -public class Visvalold { - - private static class Triangle implements Comparable<Triangle> { - - int index; - double area; - - Triangle(int index, double area) { - this.index = index; - this.area = area; - } - - @Override - public int compareTo(Triangle other) { - return Double.compare(this.area, other.area); - } - } - - public static List<Point> reducePoints(List<Point> points, int m) { - if (points.size() <= m) { - return points; - } - - // areas and remainIdx: records the dominating areas and indexes of remaining points during - // bottom-up elimination - // through remainIdx we can know the adjacency of remaining points easily. - // TreeMap<Double, Integer> areasMap = new TreeMap<>();// for speedup - List<Double> areas = triangleAreaList(points); - List<Integer> remainIdx = new ArrayList<>(); - IntStream.range(0, points.size()).forEach(remainIdx::add); - - int minIndex = 0; - for (int i = 1; i < areas.size(); i++) { - if (areas.get(i) < areas.get(minIndex)) { - minIndex = i; - } - } - // AtomicInteger minIndexTmp = new AtomicInteger(0); - // IntStream.range(0, areas.size()).parallel().forEach(i -> { - // if (areas.get(i) < areas.get(minIndexTmp.get())) { - // minIndexTmp.set(i); - // } - // }); - // int minIndex = minIndexTmp.get(); - double this_area = areas.get(minIndex); - areas.remove(minIndex); - remainIdx.remove(minIndex); - - while (remainIdx.size() > m) { - boolean skip = - false; // false mean next round needs to argmin globally, otherwise use recentMinIdx - int recentMinIdx = -1; - - // update right new triangle area - double right_area = Double.POSITIVE_INFINITY; - if (minIndex <= remainIdx.size() - 2) { - // note that now i already pop out min_vert - right_area = - calculateTriangleArea( - points.get(remainIdx.get(minIndex - 1)), - points.get(remainIdx.get(minIndex)), - points.get(remainIdx.get(minIndex + 1))); - if (right_area <= this_area) { - // so next round does not need argmin globally - skip = true; - recentMinIdx = minIndex; // note that now i already pop out min_vert - } - areas.set(minIndex, right_area); - } - - // update left new triangle area - if (minIndex >= 2) { - // note that now i already pop out min_vert - double left_area = - calculateTriangleArea( - points.get(remainIdx.get(minIndex - 2)), - points.get(remainIdx.get(minIndex - 1)), - points.get(remainIdx.get(minIndex))); - if (left_area <= this_area) { - if (skip) { // means right point area is smaller than this_area, then compare left and - // right - if (left_area <= right_area) { - recentMinIdx = minIndex - 1; - } - // otherwise keep skip right point - } else { // means right point area is larger than this_area, while left is smaller than - skip = true; // so next round does not need argmin globally - recentMinIdx = minIndex - 1; - } - } - areas.set(minIndex - 1, left_area); - } - - if (!skip) { // left and right new triangle both larger than this_area, needs to argmin - // globally - minIndex = 0; - for (int i = 1; i < areas.size(); i++) { - if (areas.get(i) < areas.get(minIndex)) { - minIndex = i; - } - } - // AtomicInteger minIndexTmp2 = new AtomicInteger(0); - // IntStream.range(0, areas.size()).parallel().forEach(i -> { - // if (areas.get(i) < areas.get(minIndexTmp2.get())) { - // minIndexTmp2.set(i); - // } - // }); - // minIndex = minIndexTmp2.get(); - } else { - minIndex = recentMinIdx; - } - this_area = areas.get(minIndex); - areas.remove(minIndex); - remainIdx.remove(minIndex); - } - - List<Point> result = new ArrayList<>(); - for (int i : remainIdx) { - result.add(points.get(i)); - } - return result; - } - - private static List<Double> triangleAreaList(List<Point> points) { - List<Double> result = new ArrayList<>(); - result.add(Double.POSITIVE_INFINITY); // first - for (int i = 1; i < points.size() - 1; i++) { - double area = calculateTriangleArea(points.get(i - 1), points.get(i), points.get(i + 1)); - result.add(area); - } - result.add(Double.POSITIVE_INFINITY); // last - return result; - } - - private static double calculateTriangleArea(Point a, Point b, Point c) { - double x1 = a.getTimestamp(); - double y1 = a.getValue(); - double x2 = b.getTimestamp(); - double y2 = b.getValue(); - double x3 = c.getTimestamp(); - double y3 = c.getValue(); - - return Math.abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0); - } -}
