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 c77a57e5041861867e3320516993d6e66d99bebb Author: Lei Rui <[email protected]> AuthorDate: Sun Jul 14 00:24:48 2024 +0800 add --- .../resources/conf/iotdb-engine.properties | 2 +- .../groupby/GroupByWithoutValueFilterDataSet.java | 6 + .../groupby/LocalGroupByExecutorTri_SC.java | 163 ++++++++++++++++++ .../groupby/LocalGroupByExecutorTri_Visval.java | 161 ++++++++++++++++++ .../db/query/simpiece/MySample_shrinkingcone.java | 78 +++++++++ .../{MySample.java => MySample_simpiece.java} | 6 +- .../iotdb/db/query/simpiece/MySample_visval.java | 92 ++++++++++ .../iotdb/db/query/simpiece/ShrinkingCone.java | 80 +++++++++ .../org/apache/iotdb/db/query/simpiece/Visval.java | 189 +++++++++++++++++++++ 9 files changed, 773 insertions(+), 4 deletions(-) diff --git a/server/src/assembly/resources/conf/iotdb-engine.properties b/server/src/assembly/resources/conf/iotdb-engine.properties index 60c5df8bf15..f26d8c0385a 100644 --- a/server/src/assembly/resources/conf/iotdb-engine.properties +++ b/server/src/assembly/resources/conf/iotdb-engine.properties @@ -19,7 +19,7 @@ #################### ### enable Tri #################### -# MinMax, MinMaxLTTB, M4, LTTB, ILTS, SimPiece +# MinMax, MinMaxLTTB, M4, LTTB, ILTS, SimPiece, SC, Visval enable_Tri=MinMax # SimPiece segment error threshold diff --git a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java index 7bc5433d854..322c1f51076 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java +++ b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java @@ -435,6 +435,12 @@ public class GroupByWithoutValueFilterDataSet extends GroupByEngineDataSet { } else if (CONFIG.getEnableTri().equals("SimPiece")) { return new LocalGroupByExecutorTri_SimPiece( path, allSensors, dataType, context, timeFilter, fileFilter, ascending); + } else if (CONFIG.getEnableTri().equals("SC")) { + return new LocalGroupByExecutorTri_SC( + path, allSensors, dataType, context, timeFilter, fileFilter, ascending); + } else if (CONFIG.getEnableTri().equals("Visval")) { + return new LocalGroupByExecutorTri_Visval( + path, allSensors, dataType, context, timeFilter, fileFilter, ascending); } else { logger.info("No matched enable_tri!"); return new LocalGroupByExecutor( diff --git a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_SC.java b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_SC.java new file mode 100644 index 00000000000..1cf596c7ff2 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_SC.java @@ -0,0 +1,163 @@ +/* + * 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.dataset.groupby; + +import org.apache.iotdb.db.conf.IoTDBConfig; +import org.apache.iotdb.db.conf.IoTDBDescriptor; +import org.apache.iotdb.db.engine.querycontext.QueryDataSource; +import org.apache.iotdb.db.exception.StorageEngineException; +import org.apache.iotdb.db.exception.query.QueryProcessException; +import org.apache.iotdb.db.metadata.PartialPath; +import org.apache.iotdb.db.query.aggregation.AggregateResult; +import org.apache.iotdb.db.query.aggregation.impl.MinValueAggrResult; +import org.apache.iotdb.db.query.context.QueryContext; +import org.apache.iotdb.db.query.control.QueryResourceManager; +import org.apache.iotdb.db.query.filter.TsFileFilter; +import org.apache.iotdb.db.query.reader.series.SeriesReader; +import org.apache.iotdb.db.query.simpiece.Point; +import org.apache.iotdb.db.query.simpiece.ShrinkingCone; +import org.apache.iotdb.db.query.simpiece.TimeSeries; +import org.apache.iotdb.db.query.simpiece.TimeSeriesReader; +import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType; +import org.apache.iotdb.tsfile.file.metadata.statistics.MinMaxInfo; +import org.apache.iotdb.tsfile.read.common.ChunkSuit4Tri; +import org.apache.iotdb.tsfile.read.filter.GroupByFilter; +import org.apache.iotdb.tsfile.read.filter.basic.Filter; +import org.apache.iotdb.tsfile.utils.Pair; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Comparator; +import java.util.List; +import java.util.Set; + +public class LocalGroupByExecutorTri_SC implements GroupByExecutor { + + private static final IoTDBConfig CONFIG = IoTDBDescriptor.getInstance().getConfig(); + + // Aggregate result buffer of this path + private final List<AggregateResult> results = new ArrayList<>(); + + TimeSeries timeSeries; + + double epsilon = CONFIG.getEpsilon(); + + public LocalGroupByExecutorTri_SC( + PartialPath path, + Set<String> allSensors, + TSDataType dataType, + QueryContext context, + Filter timeFilter, + TsFileFilter fileFilter, + boolean ascending) + throws StorageEngineException, QueryProcessException { + // long start = System.nanoTime(); + + // get all data sources + QueryDataSource queryDataSource = + QueryResourceManager.getInstance().getQueryDataSource(path, context, timeFilter); + + // update filter by TTL + // this.timeFilter = queryDataSource.updateFilterUsingTTL(timeFilter); + + SeriesReader seriesReader = + new SeriesReader( + path, + allSensors, + // fix bug: here use the aggregation type as the series data type, + // not using pageReader.getAllSatisfiedPageData is ok + dataType, + context, + queryDataSource, + timeFilter, + null, + fileFilter, + ascending); + + try { + // : this might be bad to load all chunk metadata at first + List<ChunkSuit4Tri> futureChunkList = new ArrayList<>(); + futureChunkList.addAll(seriesReader.getAllChunkMetadatas4Tri()); + // order futureChunkList by chunk startTime + futureChunkList.sort( + new Comparator<ChunkSuit4Tri>() { + public int compare(ChunkSuit4Tri o1, ChunkSuit4Tri o2) { + return ((Comparable) (o1.chunkMetadata.getStartTime())) + .compareTo(o2.chunkMetadata.getStartTime()); + } + }); + + GroupByFilter groupByFilter = (GroupByFilter) timeFilter; + long startTime = groupByFilter.getStartTime(); + long endTime = groupByFilter.getEndTime(); + + timeSeries = TimeSeriesReader.getTimeSeriesFromTsFiles(futureChunkList, startTime, endTime); + + } catch (IOException e) { + throw new QueryProcessException(e.getMessage()); + } + } + + @Override + public void addAggregateResult(AggregateResult aggrResult) { + results.add(aggrResult); + } + + @Override + public List<AggregateResult> calcResult( + long curStartTime, long curEndTime, long startTime, long endTime, long interval) + throws IOException { + // group by curStartTime and curEndTime are not used in Sim-Piece segmentation + + StringBuilder series = new StringBuilder(); + + // clear result cache + for (AggregateResult result : results) { + result.reset(); + } + + // shrinking cone + int length = timeSeries.length(); + List<Point> points = timeSeries.data; + + // Shrinking cone + List<Point> reducedPoints = ShrinkingCone.reducePoints(timeSeries.data, epsilon); + + for (Point p : reducedPoints) { + series.append(p.getValue()).append("[").append(p.getTimestamp()).append("]").append(","); + } + + MinValueAggrResult minValueAggrResult = (MinValueAggrResult) results.get(0); + minValueAggrResult.updateResult(new MinMaxInfo<>(series.toString(), 0)); + return results; + } + + @Override + public Pair<Long, Object> peekNextNotNullValue(long nextStartTime, long nextEndTime) + throws IOException { + throw new IOException("no implemented"); + } + + @Override + public List<AggregateResult> calcResult(long curStartTime, long curEndTime) + throws IOException, QueryProcessException { + throw new IOException("no implemented"); + } +} diff --git a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_Visval.java b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_Visval.java new file mode 100644 index 00000000000..0091e370620 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_Visval.java @@ -0,0 +1,161 @@ +/* + * 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.dataset.groupby; + +import org.apache.iotdb.db.conf.IoTDBConfig; +import org.apache.iotdb.db.conf.IoTDBDescriptor; +import org.apache.iotdb.db.engine.querycontext.QueryDataSource; +import org.apache.iotdb.db.exception.StorageEngineException; +import org.apache.iotdb.db.exception.query.QueryProcessException; +import org.apache.iotdb.db.metadata.PartialPath; +import org.apache.iotdb.db.query.aggregation.AggregateResult; +import org.apache.iotdb.db.query.aggregation.impl.MinValueAggrResult; +import org.apache.iotdb.db.query.context.QueryContext; +import org.apache.iotdb.db.query.control.QueryResourceManager; +import org.apache.iotdb.db.query.filter.TsFileFilter; +import org.apache.iotdb.db.query.reader.series.SeriesReader; +import org.apache.iotdb.db.query.simpiece.Point; +import org.apache.iotdb.db.query.simpiece.TimeSeries; +import org.apache.iotdb.db.query.simpiece.TimeSeriesReader; +import org.apache.iotdb.db.query.simpiece.Visval; +import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType; +import org.apache.iotdb.tsfile.file.metadata.statistics.MinMaxInfo; +import org.apache.iotdb.tsfile.read.common.ChunkSuit4Tri; +import org.apache.iotdb.tsfile.read.filter.GroupByFilter; +import org.apache.iotdb.tsfile.read.filter.basic.Filter; +import org.apache.iotdb.tsfile.utils.Pair; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Comparator; +import java.util.List; +import java.util.Set; + +public class LocalGroupByExecutorTri_Visval implements GroupByExecutor { + + private static final IoTDBConfig CONFIG = IoTDBDescriptor.getInstance().getConfig(); + + // Aggregate result buffer of this path + private final List<AggregateResult> results = new ArrayList<>(); + + TimeSeries timeSeries; + + int m; + + public LocalGroupByExecutorTri_Visval( + PartialPath path, + Set<String> allSensors, + TSDataType dataType, + QueryContext context, + Filter timeFilter, + TsFileFilter fileFilter, + boolean ascending) + throws StorageEngineException, QueryProcessException { + // long start = System.nanoTime(); + + // get all data sources + QueryDataSource queryDataSource = + QueryResourceManager.getInstance().getQueryDataSource(path, context, timeFilter); + + // update filter by TTL + // this.timeFilter = queryDataSource.updateFilterUsingTTL(timeFilter); + + SeriesReader seriesReader = + new SeriesReader( + path, + allSensors, + // fix bug: here use the aggregation type as the series data type, + // not using pageReader.getAllSatisfiedPageData is ok + dataType, + context, + queryDataSource, + timeFilter, + null, + fileFilter, + ascending); + + try { + // : this might be bad to load all chunk metadata at first + List<ChunkSuit4Tri> futureChunkList = new ArrayList<>(); + futureChunkList.addAll(seriesReader.getAllChunkMetadatas4Tri()); + // order futureChunkList by chunk startTime + futureChunkList.sort( + new Comparator<ChunkSuit4Tri>() { + public int compare(ChunkSuit4Tri o1, ChunkSuit4Tri o2) { + return ((Comparable) (o1.chunkMetadata.getStartTime())) + .compareTo(o2.chunkMetadata.getStartTime()); + } + }); + + GroupByFilter groupByFilter = (GroupByFilter) timeFilter; + long startTime = groupByFilter.getStartTime(); + long endTime = groupByFilter.getEndTime(); + long interval = groupByFilter.getInterval(); + this.m = (int) ((endTime - startTime) / interval); + + timeSeries = TimeSeriesReader.getTimeSeriesFromTsFiles(futureChunkList, startTime, endTime); + + } catch (IOException e) { + throw new QueryProcessException(e.getMessage()); + } + } + + @Override + public void addAggregateResult(AggregateResult aggrResult) { + results.add(aggrResult); + } + + @Override + public List<AggregateResult> calcResult( + long curStartTime, long curEndTime, long startTime, long endTime, long interval) + throws IOException { + // group by curStartTime and curEndTime are not used in Sim-Piece segmentation + + StringBuilder series = new StringBuilder(); + + // clear result cache + for (AggregateResult result : results) { + result.reset(); + } + + // Visval + List<Point> reducedPoints = Visval.reducePoints(timeSeries.data, m); + + for (Point p : reducedPoints) { + series.append(p.getValue()).append("[").append(p.getTimestamp()).append("]").append(","); + } + + MinValueAggrResult minValueAggrResult = (MinValueAggrResult) results.get(0); + minValueAggrResult.updateResult(new MinMaxInfo<>(series.toString(), 0)); + return results; + } + + @Override + public Pair<Long, Object> peekNextNotNullValue(long nextStartTime, long nextEndTime) + throws IOException { + throw new IOException("no implemented"); + } + + @Override + public List<AggregateResult> calcResult(long curStartTime, long curEndTime) + throws IOException, QueryProcessException { + throw new IOException("no implemented"); + } +} 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 new file mode 100644 index 00000000000..9abb7b748c6 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_shrinkingcone.java @@ -0,0 +1,78 @@ +/* + * 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_shrinkingcone { + + public static void main(String[] args) { + String fileDir = "D:\\desktop\\NISTPV\\"; + boolean series = true; // 从1开始编号列而不是时间戳列 + String[] datasetNameList = + new String[] { + // "NISTPV-Ground-2015-Qloss_Ah", + "NISTPV-Ground-2015-Pyra1_Wm2", + // "NISTPV-Ground-2015-RTD_C_3" + }; + + int[] noutList = new int[] {0}; + + 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 = ","; + TimeSeries ts = + TimeSeriesReader.getMyTimeSeries( + inputStream, delimiter, false, N, start, hasHeader, series); + + double epsilon = 10; + List<Point> reducedPoints = ShrinkingCone.reducePoints(ts.data, epsilon); + try (PrintWriter writer = + new PrintWriter( + new FileWriter(datasetName + "-" + N + "-" + reducedPoints.size() + "-sc.csv"))) { + for (Point p : reducedPoints) { + writer.println(p.getTimestamp() + "," + p.getValue()); + } + } + } catch (Exception e) { + e.printStackTrace(); + } + } + } + } +} diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece.java similarity index 97% rename from server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample.java rename to server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece.java index a54d60ac1d1..5d93d23bec7 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_simpiece.java @@ -28,7 +28,7 @@ import java.io.PrintWriter; import java.util.Comparator; import java.util.List; -public class MySample { +public class MySample_simpiece { public static void main(String[] args) { String fileDir = "D:\\desktop\\NISTPV\\"; @@ -36,8 +36,8 @@ public class MySample { String[] datasetNameList = new String[] { "NISTPV-Ground-2015-Qloss_Ah", - "NISTPV-Ground-2015-Pyra1_Wm2", - "NISTPV-Ground-2015-RTD_C_3" + // "NISTPV-Ground-2015-Pyra1_Wm2", + // "NISTPV-Ground-2015-RTD_C_3" }; int[] noutList = new int[] {100}; double[] r = new double[] {0.1, 0.5, 1.3}; 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 new file mode 100644 index 00000000000..7ca14859b37 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_visval.java @@ -0,0 +1,92 @@ +/* + * 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\\"; + boolean series = true; // 从1开始编号列而不是时间戳列 + String[] datasetNameList = + new String[] { + // "NISTPV-Ground-2015-Qloss_Ah", + "NISTPV-Ground-2015-Pyra1_Wm2", + // "NISTPV-Ground-2015-RTD_C_3" + }; + + int[] noutList = new int[] {0}; + + 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 = 100; + 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 = ","; + TimeSeries ts = + TimeSeriesReader.getMyTimeSeries( + inputStream, delimiter, false, N, start, hasHeader, series); + + List<Point> reducedPoints = Visval.reducePoints(ts.data, nout); + try (PrintWriter writer = + new PrintWriter(new FileWriter(datasetName + "-" + N + "-" + nout + "-visval.csv"))) { + for (Point p : reducedPoints) { + writer.println(p.getTimestamp() + "," + p.getValue()); + } + } + // 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()); + // } + + } catch (Exception e) { + e.printStackTrace(); + } + } + } + } +} diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/ShrinkingCone.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/ShrinkingCone.java new file mode 100644 index 00000000000..a5977068a69 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/ShrinkingCone.java @@ -0,0 +1,80 @@ +/* + * 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; + +public class ShrinkingCone { + + public static List<Point> reducePoints(List<Point> points, double epsilon) { + List<Point> result = new ArrayList<>(); + int length = points.size(); + + result.add(points.get(0)); // first point + + // Precompute upper and lower bounds + double[] p_upper = new double[length]; + double[] p_lower = new double[length]; + for (int j = 0; j < length; j++) { + double v = points.get(j).getValue(); + p_upper[j] = v + epsilon; + p_lower[j] = v - epsilon; + } + + // init the first segment + int sp = 0; + int i = 1; + double vsp = points.get(sp).getValue(); + double dx = points.get(i).getTimestamp() - points.get(sp).getTimestamp(); + double upSlope = (p_upper[i] - vsp) / dx; + double lowSlope = (p_lower[i] - vsp) / dx; + + while (i < length - 1) { + i++; + vsp = points.get(sp).getValue(); // the value of the start point + dx = points.get(i).getTimestamp() - points.get(sp).getTimestamp(); // time distance + double upV = upSlope * dx + vsp; // the upper bound for the current point + double lowV = lowSlope * dx + vsp; // the lower bound for the current point + + if (lowV <= points.get(i).getValue() && points.get(i).getValue() <= upV) { + // current point in the zone + // shrink the zone + upSlope = Math.min(upSlope, (p_upper[i] - vsp) / dx); + lowSlope = Math.max(lowSlope, (p_lower[i] - vsp) / dx); + } else { + // record segment point + result.add(points.get(i - 1)); + + // begin new segment + sp = i - 1; // joint style + vsp = points.get(sp).getValue(); // note sp has changed + dx = points.get(i).getTimestamp() - points.get(sp).getTimestamp(); // note sp has changed + upSlope = (p_upper[i] - vsp) / dx; + lowSlope = (p_lower[i] - vsp) / dx; + } + } + + // write last point + result.add(points.get(points.size() - 1)); + + return result; + } +} 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 new file mode 100644 index 00000000000..95002fd0d26 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval.java @@ -0,0 +1,189 @@ +/* + * 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 Visval { + + 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. + 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; + } + } + 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; + } + } + } 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); + } +}
