KD-Box：基于线段的 KD 树用于大规模时间序列数据的交互式探索
摘要
时间序列数据-通常以线条形式呈现，在金融、气象、健康和城市信息学等众多领域中发挥重要作用。然而，针对大规模时间序列数据的交互式探索尚未得到充分支持，而这需要一种无杂乱的可视化表现与低延迟交互。本文提出了一种新颖的基于线段的 KD 树方法，以实现对众多时间序列的交互式分析。该方法不仅能在选定感兴趣区域对时间序列进行快速查询，还提供了一种线条散点（line splatting）方法，用于高效计算密度场并选择代表性线条。此外，我们开发了 KD-Box，一款交互式系统，提供丰富的交互功能，例如时间框（timebox）、属性过滤以及协调多视图。我们通过定量比较展示了 KD-Box 在支持高效线条查询和密度场计算方面的有效性，并证明其在多个真实数据集上进行交互式可视化分析时的实用性。
作者
Yue Zhao 山东大学，青岛，中国
Yunhai Wang 山东大学，青岛，中国
Jian Zhang CNIC, CAS., 美国
Chi-Wing Fu 香港中文大学，中国
Mingliang Xu 郑州大学，中国
Dominik Moritz 卡内基梅隆大学，美国
出版信息
期刊: IEEE Transactions on Visualization and Computer Graphics 年: 2022 卷: 28 期: 1 页: 890-900 DOI: 10.1109/TVCG.2021.3114865 文章编号: 9552923 ISSN: Print ISSN: 1077-2626, Electronic ISSN: 1941-0506, CD: 2160-9306
指标
论文引用: 32 总下载量: 1313
资金
- NSFC (资助: 61772315 and 61861136012)
关键词
IEEE 关键词: Data visualization, Time series analysis, Visualization, Rendering (computer graphics), Market research, Clutter, Three-dimensional displays
索引词: Time Series, Time Series Data, Large-scale Data, Exploratory Data, Interactive Exploration, Large-scale Time Series Data, Time Series Analysis, Interactive System, Selection Of Lines, Density Field, Line Density, Rich Interactions, Fast Query, Trends Data, Line Segment, Sequence Search, Leaf Node, Line Graph, Number Of Time Points, Range Of Nodes, Range Query, Line Search, Number Of Time Series, Query Results, Representative Time Series, Visual Clutter, Set Of Curves, Query Point, Normal Kernel
作者关键词: Many time series, density-based visualization, interactive visualization for large-scale data
未定义
第一章 介绍
越来越多的时序数据在金融、医疗和城市信息学等广泛领域被收集、存储和分析。为了洞察这些时序数据，分析师通常需要探索、比较并关联多种实体的数据，其数量可从数十个到数百万个，例如多支股票、机器的功耗等。因此，能够处理大规模时序数据的交互式分析系统需求非常大。
典型的方法 1 将时间序列数据可视化为折线图中的单独线条。这些方法通常提供动态查询工具，供用户交互式过滤满足特定模式的一部分线条，以实现交互式探索。随着时间序列数量增加，折线图往往会出现过度绘图和查询缓慢，阻碍分析师交互式探索数据。为减少视觉杂乱，研究者提出了基于密度的方法 2、[^3]，将多条时间序列一起可视化为密度场，而不是单独的线条。然而，基于密度的可视化并不支持时间序列数据的交互式探索，主要原因是三方面限制。首先，在CPU上计算和渲染密度可视化过于繁重，无法提供交互式反馈。其次，从密度可视化中查询一部分线条几乎不可能，因为可视化仅是光栅图像，省略了单独的线条。第三，虽然密度可视化能让分析师感知数据整体密度模式，但个别线条的详细信息丢失，尤其是代表性的连续趋势。因此，密度可视化阻碍了涉及单个时间序列的分析任务，例如 给定时间区间内哪些股票是代表性的？ 通过聚类时间序列线条可能识别代表性线条，但涉及的计算成本过高 3，不适合交互式探索。这些限制促使我们研究 如何在结合折线图和密度场优势的同时，实现多条时间序列的交互式分析.
支持大型时序数据的交互式探索是一项非平凡的任务。挑战在于现有基于密度的可视化无法满足的三个基本需求：
快速 渲染——密度场的计算与渲染必须足够快，以便为用户提供及时的反馈；
快速 查询——可视化必须允许低延迟交互，以查询时序探索中的线段子集；且
代表性 线条——可视化还必须通过展示兴趣区域中的代表性线条来呈现主要趋势。
随着线条（时序）数量的增加，这些挑战变得更加严重。我们需要能够同时展示全局趋势与局部代表性时序，并支持快速渲染与查询的新方法。
本文提出了一种新颖的 K‑维（KD）树方法，以实现对大量时序数据的交互式分析。我们方法的核心是一种基于线段的 KD‑树 [^5]，我们将其改编用于时序可视化。KD‑树首先将每条时序分段为少量线段，然后为所有线段构建 KD‑树。为了支持交互式探索中的各种查询操作，例如矩形刷选和角度查询 4，我们在时序-数值-斜率空间构建了一个 3D KD‑树。该 KD‑树可在 30 秒以内为包含 100K 条时序、1350 万个数据点的数据集构建完成。使用我们的增量查询，线段搜索平均可在 15 毫秒以内完成，搜索精度在我们测试的各个数据集上均超过 98.5%。
通过高效的半径最近线（RNL）搜索，我们的 KD 树能够利用线聚合 5、[^7] 高效计算密度场. 对于给定显示中的每个像素，我们执行 RNL 搜索，以查找距离为 r 内的所有线段，并迅速获取这些线段的组合密度. 我们的方法比最先进的实现 6 快一个数量级地快速渲染大量线条的密度. 一旦得到密度场，我们提供一种启发式方法，在选定感兴趣区域内定位代表性时间序列. 我们的方法在考虑线条的密度和形状的同时，找到多样化的时间序列. 将这些代表性时间序列线条叠加在密度场或所有选定线条上，既能帮助用户交互式探索局部模式，又能展示整个数据集的全局趋势.
我们开发了 KD-Box [^9]，这是一套具有灵活与 Timebox 7 交互以及协调视图的交互式系统，用于对大规模时间序列数据进行可视化探索. 为评估我们的方法，我们将其与现有的密度场计算和动态查询方法进行了对比. 实验结果表明，即使在 100K 条时间序列的情况下，我们的方法也能在高分辨率（1200×600px）的可视化上实现实时交互. 我们还演示了 KD-Box 如何让分析师快速测试他们的大型真实世界时间序列数据上的不同假设. 我们的主要贡献列于下文：
一种基于线段的 3D KD 树，构建于时间-数值-斜率空间，能够实现增量查询更新，从而支持对大量时间序列的交互式探索;
通过基于 KD 树的线聚集和用于选择代表线的启发式方法实现快速密度场计算；以及
一个具有丰富交互的交互式探索系统，通过定量比较和在大型真实世界数据集上的应用，展示我们方法的有效性。
第2节 相关工作
2.1 多时间序列的可视化
许多领域的分析师需要通过交互式探索来可视化时间序列数据。为了减少过度绘图，研究人员提出了无杂乱的可视化和交互式查询方法。
无杂乱可视化
许多可视化方法已被引入用于可视化时间序列数据，例如基于日历的 [^10]、基于圆形的 [^11]、基于符号的 8，以及基于瓦片的 [^13]。其中，折线图是呈现时间序列数据最常见的方式。Javed 等人 9 总结了基于折线图技术的权衡。所有这些方法，然而，当底层数据量很大时，都会出现过度绘图的问题。Lopez-Hernandez 等人 10 开发了一种 2.5D 基于层的技术用于多时间序列，但它主要设计用于垂直方向范围非常小的时间序列。
与其逐条可视化单独的线，Muigg 等人 [^16] 通过统计每个像素所穿过的时间序列数量，计算出一个频率 binmap [^17]（一个离散密度场）。每个数据项再额外包含三个关注度（DOI）变量，他们的四层 focus+context 方法将时间序列的四个密度场组合在一起。随后，Lampe 和 Hauser 引入了连续线核 11 并进一步提出 Curve Density Estimates (CDE) 12，以可视化多条线的密度，旨在解决视觉混乱问题。这种密度场使用户能够看到数据的整体趋势。然而，CDE 的计算速度过慢，无法支持交互式探索。受到 CDE 的启发，Moritz 与 Fisher 提出了 DenseLines [^3]，它将数据聚合成分箱，并生成时间序列数据的离散密度表示。他们进一步建议通过弧长归一化密度，以去除密度场中的伪影。尽管 DenseLines 的计算速度快于 CDE，但仍不足以在实时交互探索 100k lines（参见 5.1 节）时生成平滑的密度图。在本研究中，我们的方法通过预先计算的基于线段的 KD-tree 确保了平滑的交互体验。
交互式查询
与一次性可视化所有时间序列不同，减少视觉杂乱的另一种方法是让用户交互式查询部分线条以供显示。 例如，Time-boxes 13 和 QuerySketch [^19] 提供交互式小部件，允许用户根据形状查询特定的时间序列。 Zhao 等人 [^20] 提出了 ChronoLenses，该方法使用透镜隐喻来支持对时间序列数据中局部区域的探索。 然而，这些方法在大规模时间序列数据上扩展性不佳，因为这些系统支持的查询太慢，无法进行交互式探索。
研究人员还开发了加速大规模数据查询过程的技术。大多数这些技术采用高级数据管理技术，例如数据立方体 14, 15, 近似 16, [^24], 以及预取 17, [^26]。其中一些已被优化以支持大规模时间序列数据。ATLAS 18 结合预测缓存和细节层级管理，以确保在探索大规模时间序列数据时实现流畅交互。Time Lattice [^28] 为时间序列数据定制了带有隐式时间层次结构的数据立方体结构，从而实现以交互速率进行多分辨率时间序列查询。然而，这些方法使用折线图可视化时间序列，无法适用于基于密度的可视化。四级焦点+上下文框架 [^16] 支持在密度场中查询，但将结果显示为另一 DOI 变量的密度场，失去了所选（原始）线条的细节。相比之下，我们的 KD-Box 允许用户使用 Timebox 19 引入的灵活交互，交互式查询大规模时间序列数据，并同时支持基于密度的可视化和代表线选择。
代表线选择
聚类是科学可视化中用于从时间序列数据中挑选代表性线条的常用方法。Moberts 等人 [^29] 比较了不同的聚类方法和 DTI 聚类的距离度量，并且 Yu 等人 [^30] 将层次聚类应用于流线并创建了流线束的层级结构。然而，由于聚类的计算成本高昂，这些技术大多不是交互式的。对于时间序列数据，也可以通过直接聚类时间序列 20 来选择代表性序列，但这样做计算成本高昂。为克服此问题，我们提出了一种基于密度场的启发式方法，以高效识别代表性时间序列。
2.2 基于密度的可视化
基于密度的可视化常用于清理大量数据点的图表。一种朴素的展示密度的方法是将个别标记设为半透明，并使用 alpha 混合，使密集区域更加突出 21。更为复杂的方法会聚合彼此接近的数据点，并可视化计算得到的密度场。热图通过使用可调节的比例尺（例如使用对数比例）来展示密度颜色，从而突出显示大范围（例如使用对数比例）或强调无数据与有数据之间的差异 22。
典型的密度可视化示例是基于密度的散点图。Mayorga 和 Gleicher 引入了 Splatterplots [^33]，它可以自动将密集的数据点分组到密度轮廓中并采样其余点。Splatterplots 通过感知上准确的颜色混合将数据点和密度轮廓结合在一起。其他方法通过降低密度的透明度 [^34] 或平滑处理 [^35] 来混合数据点和密度轮廓。密度可视化也已被用于其他图表类型，例如轨迹图 [^36]、平行坐标 23、24 以及图形可视化 25、[^40]。
大多数现有技术通过 splatting 估计密度，即将每个基本样本（节点或边）与各种核卷积，并累积所有样本的贡献。例如，Graph splatting [^40] 对每个节点使用高斯核卷积，以在不产生视觉杂乱的情况下渲染大型图形。Telea 和 Ersoy [^41] 以及 Heinrich 等人 26 分别使用边 splatting 来生成基于图像的边捆绑和连续平行坐标。作为一种基于对象顺序的方法，splatting 技术的复杂度取决于可视化原语的数量，因此在 CPU 上处理大量时间序列时可能较慢。相比之下，我们的密度场计算是一种基于图像顺序的方法。其复杂度取决于屏幕空间，或像素数量。因此，随着对象数量的增加，我们的方法获得了更多优势。
对于从时间序列数据中采样的数据点，Lampe 和 Hauser 提出的曲线密度估计（Curve Density Estimates，CDE）27，展示了沿时间轴的分布特征，利用移动的列式归一化实现。通过显示密度场，CDE 能实现无杂乱的可视化，但实现困难且计算缓慢。Moritz 和 Fisher [^3] 引入了 DenseLines，这是 CDE 的一种特殊情况，将数据分组为箱子并生成离散密度，GPU 上比 CDE 快数个数量级。然而，两种方法都忽略了个别线条的信息，导致用户无法在时间序列数据中探究细节。我们的方法在三个方面改进了现有基于密度场的时间序列数据可视化。首先，我们在时间-数值-斜率空间中设计了基于 3D 线段的 KD 树，以实现对密度场中时间序列线条的交互式查询。其次，我们通过基于 KD 树的 RNL 搜索提出了快速计算时间序列密度场的方法。最后，我们将密度和代表线条同时呈现，为分析师提供个别线条的细节，帮助他们探索感兴趣的局部区域。
第 3 节 背景：Timebox 与 Curve Density Estimate
在本节中，我们介绍最近线查询和 Timebox 查询，回顾 Curve Density Estimate（CDE）的背景，并讨论如何将线查询技术应用于 CDE。
最近线查询
给定一组曲线，Lu 等人 [^5] 提出了两种基于邻域的线查询技术：半径最近线（RNL）查询和 k 最近线（KNL）查询。给定查询点 \mathbf{q}，RNL 查找所有与 \mathbf{q} 的距离不超过 r 的曲线，而 KNL 查找最接近 \mathbf{q} 的 k 条曲线。图 1a 用查询点 \mathbf{q}_{1} 和 \mathbf{q}_{2} 分别说明了 RNL 和 KNL 查询。注意，曲线上距离 \mathbf{q} 最近的点可能不是该曲线上的采样点。
时间盒和角度查询
给定一个带有时间序列集合的线图，用户可以选择穿过由时间框刷选28或基于属性的过滤所指定兴趣区域的时间序列。将框查询表示为一个四元组 (t_{\min},t_{\max},v_{\min},v_{\max})，该四元组指定了时间和值维度的范围，我们定位曲线 c_{i}（第 i 个时间序列），条件是 c_{i} 中在时间范围 [t_{\min},t_{\max}] 内的所有点都应位于给定的值范围 [v_{\min},v_{\max}] 内。图 1b 展示了一个示例，其中曲线 c_{1} 和 c_{2} 被排除在查询结果之外，因为在给定时间范围内，它们的部分采样点高于 v_{\max} 或低于 v_{\min}。对于具有多个时间框的查询，检索到的序列需要满足所有时间框的条件。
角度查询的工作方式与时间框查询相同，但范围是在时间-角度域中指定，而非时间-数值域。对于曲线中的每个线段，计算其斜率角度需要昂贵的 arctan 函数，因此我们将角度范围约束转换为斜率范围约束。图 1c 展示了一个示例：角度范围约束由左侧显示的 (t_{\min},t_{\max}, \Theta_{\min}, \Theta_{\max}) 指定，而转换后的斜率范围约束则以分段线段的形式显示在右侧的时间-斜率空间中。从右侧图中可以看到，只有曲线 c_{2}（黄色）和 c_{3}（绿色）被检索为查询结果。
时间盒可以被视为二维矩形范围查询，因此已经提出了一些高效的搜索方法 [^44]，例如正交范围树和网格结构。然而，Hochheiser 和 Shneiderman 29 对多种方法的性能进行了定量比较，发现顺序搜索仍然优于其他方法。通过细致分析，他们将顺序搜索的成功归因于早期终止，即当检测到某个数据点超出范围时搜索即可停止，而其他方法则需要检查时间盒中的每个点。由于该盒子是可移动且可调整大小的，他们进一步开发了一种优化的顺序搜索算法 30，用于提供快速和增量查询。
曲线密度估计 (CDE)
给定一组从未知概率密度采样的1D点\{p_{1},\cdots,p_{n}\}，在位置{x}处通过核密度估计（KDE）估计的密度为
\begin{equation*} f(x)=\frac{1}{n}\sum_{i=1}^{n}K_{r}(x,p_{i}) \tag{1} \end{equation*}
其中 K_{r} 是核函数，r 是带宽。常见的核函数是正态核 N_{r}(x)=\frac{1}{\sqrt{2 \pi}} e^{-\frac{1}{2}(x / r)^{2}}。对于两个离散点，正态核会产生一个具有两个峰值的分布（图 2a）。然而，当两个相邻点来自连续时间序列时，这个分布无法忠实地揭示相邻点之间的连续变化。
为了解决这个问题，CDE 在每条线段上引入了二维线核，即曲线 c_{i} 上的连续点 \mathbf{p}_{i} 和 \mathbf{p}_{i+1}。给定二维空间中的任意点 \mathbf{x}，令 \boldsymbol{\mu} 为将 \mathbf{x} 投影到线段上的垂足，即 \boldsymbol{\mu}=\mathbf{x}-\vert \pmb{v}\cdot(\mathbf{x}-\mathbf{p}_{i})\vert \pmb{v}，其中 \pmb{v} 是垂直于该线段并朝向 \mathbf{x} 的单位向量。 在点 \mathbf{x} 处的二维线核是沿线段 (L_{r}^{1D}) 的一维线核与沿垂直于该线段的 \pmb{v} 方向的正态核 (N_{r}) 的乘积：
\begin{equation*} L_{r}\left(\mathbf{x}, \mathbf{p}_{i}, \mathbf{p}_{i+1}\right)=L_{r}^{1 D}(\mu, p_{i}, p_{i+1}) \cdot N_{r}(\vert\mathbf{x}-\boldsymbol{\mu}\vert) \tag{2} \end{equation*}
其中\mu, p_{i}和p_{i+1}分别是沿通过\mathbf{p}_{i}和\mathbf{p}_{i+1}的直线定义的2D点\boldsymbol{\mu}, \mathbf{p}_{i}和\mathbf{p}_{i+1}的1D等价物。1D线核L_{r}^{1D}是两个正态核的累积分布函数（CDF）相减得到的：
\begin{equation*} L_{r}^{1 D}\left(\mu, p_{i}, p_{i+1}\right)=\frac{\text{CDF}_{r}\left(\mu, p_{i}\right)-\text{CDF}_{r}\left(\mu, p_{i+1}\right)}{\left\vert p_{i+1}-p_{i}\right\vert} \tag{3} \end{equation*}
其中 \text{CDF}_{r}(\mu,p_{i}) 是正态核的积分：
\begin{equation*} \text{CDF}_{r}\left(\mu, p_{i}\right)=\int_{p_{i}}^{\mu} N_{r}\left(\left\vert t-p_{i}\right\vert\right) d t. \tag{4} \end{equation*}
Fig. 1. 四种不同线查询方法的示例：(a) 半径最近线（rnl）查询定位线 c_{1}, c_{5} 与 c_{6}，查询点为 \mathbf{q}_{1}，半径为 r；k-最近线（KNL）查询定位线 c_{3}, c_{4} 与 c_{5}，查询点为 \mathbf{q}_{2} 与 k=3；(b) timebox 查询定位线 c_{3} 与 c_{4} 位于盒内；(c) 角度查询：用户在时间-角度域（左）刷选，计算在时间-斜率域（右）完成，其中连续线变为分段线段。
因此，估计密度在相邻点之间均匀分布（见图 2b）。每个点 \mathbf{x} 的密度是所有单个线段密度之和。
KDE 通常仅使用半径范围 r 内的点来估计密度，而忽略其他点。同样，计算线密度时也只需要考虑距离 \mathbf{x} 半径为 r 内的线段。虽然 KD 树已广泛用于 r-最近邻（RNN）搜索 [^45]，但只有曲线复杂度启发式（CCH）[^5] KD 树专门用于从一组 3D 曲线中搜索最近线。本文将此类树扩展，以进一步支持多条时间序列的 timebox 和 angular 查询。
第 4 节 方法
在本节中，我们首先介绍了一个改进的CCH KD树 [^5]，即基于线段的KD树，用于探索时序数据。与原始的CCH KD树类似，我们也用少量直线段来拟合每条线（曲线），但我们在时间-值-斜率（TVS）空间构建基于线段的KD树。基于该树，我们可以执行类似于传统基于点的KD树中最近点查询的 KNL 和 RNL 查询 [^5]。此外，我们在 TVS 空间中扩展了基于线段的 KD 树，采用三种技术来探索大规模时序数据：（i）高效的密度计算，（ii）增量时间盒查询，以及（iii）代表性线段选择。接下来，我们详细阐述树的构造过程，然后展示探索技术。
图 2. 给定由两点 \mathbf{p}_{i} 与 \mathbf{p}_{i+1} 定义的一条线，其密度分别通过 (a) 正态核和 (b) 线核计算。
图 3. 我们的树构造概览：(a) 一组输入曲线，带有点样本（白色）和分割点（橙色）；(b) 为输入曲线构建的 TVS 空间中的 KD 树，使用新增的分割点（黄色），分割平面边界的厚度（蓝色）表示层级，边界更厚的分割平面位于 KD 树的更高（上层）层级；以及 (c) 每个网格单元体积中的曲线段被拟合为直线段。
4.1 预处理
给定 n 条时序线，我们的基于线段的 KD 树分三步构造，如图 3 所示： (i) 将每条线分解为段； (ii) 构建基于线段的 KD 树； (iii) 用直线段拟合每个段。
曲线分解
将给定时序数据中的每条线视为有序点列表 \{\pmb{p}_{1}, \cdots,\pmb{p}_{m}\}，我们首先应用经典的 Ramer-Douglas-Peucker 算法 [^46]，并使用阈值 \varepsilon 来将每条线近似为少量直线段。我们接着寻找点 \pmb{p}_{i}，它相对于连接端点 \pmb{p}_{1} 和 \pmb{p}_{m} 的直线段 l 的距离偏差最大。If 该距离偏差小于阈值 \varepsilon，则可以删除 \pmb{p}_{1} 与 \pmb{p}_{m} 之间的所有点，因为整条线可以用 l 近似。否则，我们保留 \pmb{p}_{i}，并递归地在 \{\pmb{p}_{1},\cdots,\pmb{p}_{j}\} 与 \{\pmb{p}_{i}, \cdots,\pmb{p}_{m}\} 上重复该过程，其中 \pmb{p}_{i} 被称为 split point; 请参见图 3a 中的橙色点。更大的 \varepsilon 倾向于移除更多点，曲线形状会发生更大变化，反之亦然。默认情况下，\varepsilon 在我们的实验中设为一个像素单位。
树结构构建
我们在 TVS 空间中通过递归地将所有线段的 3D 轴对齐包围体划分来构建基于线段的 KD‑树。以整个 TVS 体积作为树的根，划分分为三步：(i) 使用空间中位数 [^47] 在体积中为每个维度寻找候选分割平面；(ii) 采用查询成本最小的分割平面（由 Lu 等人定义 [^5]）将当前节点划分为两个子节点；(iii) 对与分割平面相交的线段进行划分，并将每条线段延长到与分割平面相交的对应点。此类相交点（见图 3b 中的黄色点）也被视为更好曲线拟合的分割点。递归在所有候选分割平面的成本低于零时停止。由于分割平面选择考虑了查询成本，得到的树被优化为最近线查询。
曲线拟合
树构建完成后，每条时间序列线由多个直线段表示，每个直线段存储在相应的单元格中。该线段可通过在网格单元中连接时间序列线的两个端点得到，或通过对 2D 点样本进行主成分分析投影到一条线段。我们采用前一种方法，因为它更快且在大多数情况下引入的误差更小。最后，每个叶节点包含每条线段六个值（即时间-值空间中的两个端点、一个斜率值和一个线索引），而每个内部节点记录分割维度和该节点在分割维度上的包围体积范围（最小值和最大值）。图 3c 显示了 TVS 空间中所有拟合的线段。
4.2 高效密度计算
一旦构建了 KD 树，我们就可以对每个像素执行最近线 (NL) 查询来构建密度场。对于时间-值空间中的每个像素 \mathbf{x}，我们通过执行 RNL 查询来收集半径为 r 内的线段（见图 1a），并随后对每条线段的贡献进行求和，贡献按公式 2 计算。得益于高效的 RNL 查询，我们的方法甚至比经典的 splatting‑based 方法 31、[^3] 更快（见第 5 节）。
图 4. 说明树遍历查询和基于边界的过滤。(a) 用 (b) 中所示的树将时间序列 c_{1} 到 c_{5} 覆盖的空间分解；B_{1} 到 B_{7} 表示与树叶节点相关的边界体积（网格单元）。蓝框表示具有一对“幽灵”范围（红色）位于上方和下方的时间盒查询。(b) 通过遍历树可以高效地找到所有叶节点和与时间盒相交的线 \langle c_{1}, c_{2}、c_{3})。接下来，基于边界的过滤利用这两个幽灵范围来过滤线：我们丢弃 c_{1}，因为它与下方的幽灵范围相交，意味着它在 [t_{\min},t_{\max}] 中的一些点必须在时间盒之外。
4.3 快速增量范围查询
为支持 timebox 查询和 angular 查询，我们将关联的范围查询 R 定义为 TVS 空间中的六元组 (t_{\min},t_{\max}, v_{\min}, v_{\max}, s_{\min},s_{\max})。由于 timebox 查询不限制角度，我们将 s_{\min} 设为负无穷，s_{\max} 设为正无穷，以在 timebox 查询中跳过斜率维度。同样，我们将 v_{\min} 设为负无穷，v_{\max} 设为正无穷，以满足 angular 查询。
树遍历查询
给定一个六元组范围查询 R，树遍历查询旨在找到所有与 R 所指定的 TVS 体积相交的时间序列（线段）。该遍历从根节点开始，可高效完成。在每个内部节点，我们只需比较该节点的包围体积范围与 R 在分割维度上的对应范围。假设分割维度为“value”，我们只需比较节点包围体积的“value”范围与 R 的“value”范围：有三种情况：
Case 1: 如果节点的范围完全在 R 的范围内，我们直接去所有叶子节点并收集所有存储的曲线索引；
Case 2: 如果节点的范围部分在 R 的范围内，我们遍历其每个子节点并进一步检查每个子节点；并
Case 3: 如果节点的范围完全不在 R 的范围内，我们停止对该节点的遍历。
在 Case 2 中，如果子节点是叶子节点，我们还需要检查其包含的每条线段是否在 R 内。图 4a 显示了一个例子，叶子节点 B_{1} 的包围体积与 R 相交，但 B_{1} 中并非所有曲线都真正与 R 相交，例如 c_{4}。图 4b 说明了整个树遍历过程。遍历完成后，我们得到一组与给定范围查询 R 相交的线段（记作 \bar{\Omega}）。
*Fig. 5. 展示了三种不同情况下修改范围查询查询窗口时的增量查询更新，从 R_{o} 到 R_{n} \ (\mathrm{a})：案例 1：当扩大查询窗口时，我们插入范围 R_{n}-R_{o} 内的行。(b) 案例 2：当缩小查询窗口时，我们删除范围 R_{o}-R_{n} 内的行，但保留穿过绿色幽灵范围的行。(c) 案例 3：当移动查询窗口时，我们需要在案例 1 的基础上插入范围 R_{n}-R_{i} 内的行，然后在案例 2 的基础上删除范围 R_{o}-R_{i} 内的行，其中 R_{i}=R_{o}\cap R_{n}。对于这三种情况，我们最终需要删除穿过红色幽灵范围的行。
基于边界的过滤
通过树遍历查询，我们可以为给定的范围查询 R 获得 \bar{\Omega}。然而，要满足 timebox/angular 查询，我们需要找到位于 R 的查询体积内、覆盖 R 的整个时间范围 [t_{\min},t_{\max}] 的线段。因此，我们需要通过丢弃不合格的线段来过滤 \bar{\Omega}，例如在图 4a 所示的蓝色 timebox 中的 c_{1}。
我们的核心思路是利用高效的树遍历查询来快速过滤 \bar{\Omega}; 换句话说，我们在 R 的查询体积旁边定义一对与时间轴平行的幽灵范围，并丢弃与这些幽灵范围相交的 \bar{\Omega} 中的任何线。对于时间框查询（参见图 4a 的示例），我们定义幽灵范围 (t_{\min}, t_{\max}, v_{\max}, v_{\max}+\varepsilon,-\infty, \infty) 和 (t_{\min}, t_{\max}, v_{\min}-\varepsilon, v_{\min},-\infty, \infty)，并设定一个小阈值 \varepsilon; 请参见图 4a 中的两个小红框。随后，我们使用树遍历查询定位与幽灵范围相交的线。如果发现 \bar{\Omega} 中的某条线穿过这些幽灵范围，则意味着该线的一部分位于时间范围 [t_{\min}, t_{\max}] 的时间框之外。因此，应将该线从时间框的查询结果中排除。通过这样做，我们可以获得最终查询结果 \Omega，其中包含 \bar{\Omega} 中所需的线。虽然时间复杂度为 O(\log N+k)(N（所有线段数量）和 k（\bar{\Omega} 中线段数量），该过程仍然非常快，尤其是在后面配置增量查询更新后。此外，我们还可以同时查询两个幽灵范围中的线以提升性能。图 4b 显示了一个例子，其中 c_{1} 在此基于边界的过滤后被丢弃，因为 C_{1} 穿过了底部幽灵范围（红色）。
在角度查询（angular query）的情况下，上述幽灵范围无法工作，因为斜率维度中的时间序列线是离散的而非连续的。因此，与其在范围查询 R 的包围体上附加小的幽灵范围，我们定义两个幽灵范围为 (t_{\min},t_{\max},\ -\infty,\infty,s_{\max},\infty) 和 (t_{\min},t_{\max},-\infty,\infty,-\infty,s_{\min_{-}})，使其延伸到无穷大，并帮助检查在给定时间范围 R 内，\bar{\Omega} 中的任何线是否超出 R。
增量查询更新
当用户在标记范围查询（timebox/angular query）的可视化界面中调整或移动查询小部件时，我们可以执行增量查询以快速更新 \Omega。假设之前的范围是 R_{o}，新的范围是 R_{n}，它们的空间关系可以是以下三种情况之一（参见图5a-c中的相应示意图）：
情况1：R_{o}\subset R_{n}（放大查询小部件时）；
情况2：R_{n}\subset R_{o}（缩小查询小部件时）；和
情况3：R_{o} 与 R_{n} 在移动查询小部件时相交于范围 R_{i}。
假设线段在空间 [^5] 中均匀分布，搜索整个范围 R_{n} 内的线比搜索小子范围更慢。因此，我们设计了一系列增量查询机制来处理 R_{o} 与 R_{n} 之间的三种情况。
对于案例1，我们首先找到所有穿过范围 R_{n}-R_{o}（参见图5a）的线，并将它们添加到 \Omega。由于 R_{n}-R_{o} 是 L 型的，我们先将其区域分成两个常规框（如图5a中显示的虚线橙线）再寻找与这些框相交的线。我们还设置了一对幽灵范围（参见图5a中的红色框）以确保这些线在整个时间范围内严格位于 R_{n} 内。
对于案例2，我们找到穿过 R_{o}-R_{n}（同样被划分为两个框）的线，并将检索到的线从 \Omega 中移除。然而，这种移除可能排除一些有效线。以图5b为例，它将移除线 c_{1}, c_{2}, c_{4}, c_{5}, c_{6}，以及在这些线中 c_{7};；而 c_{1} 和 c_{2} 满足 R_{n}。为了解决此问题，我们在 R_{n} 的左或右边界相邻 R_{o}-R_{n} 的位置构造幽灵范围 R_{c}；参见图5b中的绿色框；然后，我们可以像案例1一样，添加回穿过 R_{c} 但不在红色幽灵范围内的线。通过这种方式，我们可以保留 c_{1} 和 c_{2}。
案例3结合了案例1和案例2。增量查询更新分两步完成。首先，我们在范围 R_{n}-R_{i} 内找到线，并将其插入 \Omega，遵循案例1（参见图5c的左侧），其中 R_{i}=R_{o}\cap R_{n}。然后，我们遵循案例2，移除范围 R_{o}-R_{i} 内的线，但保留那些穿过幽灵范围 R_{c} 的线。再次注意，在所有三个案例中，我们使用红色幽灵范围来确保所有结果线在整个时间范围内严格位于 R_{n} 内。
时间复杂度为 \log(N)+k，其中包括查询 N 条线段的成本以及执行 k 集合操作以插入或删除查询结果中的线条；\Omega k 是查询中涉及的线条数量。
4.4 代表线选择
分析师经常需要查看代表性的时间序列（作为单独的线条），以探索感兴趣区间的局部模式，而基于密度的可视化本质上会丢失单个线条的信息。解决此问题的一个直接方案是根据相似度指标 32 对时间序列线进行聚类；但这种计算对于交互式查询响应时间来说过于昂贵。
我们的目标是找到遵循数据主要趋势的代表线。受到基于密度的边捆绑 33 的启发，我们认为一条线如果尽可能多地穿过高密度区域，则可以很好地代表许多时间序列。另一方面，每条代表线应该是唯一的，即能够揭示所有线条的多样趋势。在此，我们使用曲率差异来刻画线条之间的变化 [^48]。此外，代表线不应过短。因此，我们提出一种启发式方法，通过考虑它们的密度得分和曲率来选择 k 条代表线。
对于从给定范围查询 R 检索到的每条线，我们通过汇总其占据的所有像素的密度来计算其密度得分：
\begin{equation*} \rho_{i}=\frac{1}{\mathrm{~L}_{i}} \sum_{k} \rho\left(\mathbf{x}_{i, k}\right) \tag{5} \end{equation*}
其中 \mathbf{x}_{i,k} 是位于第 i 行的第 kth 像素，而 \mathrm{L}_{i} 是时间轴上线段的长度。与此同时，我们计算两条线 c_{i} 与 c_{j} 之间的形状差异：
\begin{equation*} \beta_{i, j}=\frac{1}{\mathrm{~L}_{i, j}} \sum_{k}\left\vert\kappa\left(\mathbf{x}_{i, k}\right)-\kappa\left(\mathbf{x}_{j, k}\right)\right\vert \tag{6} \end{equation*}
其中 \kappa(\mathbf{x}_{i,k}) 是位于第 i 行的第 kth 像素 \mathbf{p}_{k} 处的曲率，而 \mathrm{L}_{i,j} 是时间轴上第 i 行与第 j 行的公共长度范围。为了实现快速后续查询，我们在生成 KD-树后预先计算每条线中每个像素点的曲率 \kappa:(\mathbf{x}_{i,k})，并为每个线段计算 \rho_{i}。通过两个用户提供的参数，即长度阈值 \tau 和形状差异阈值 \lambda，我们在给定范围 R 内以两步方式寻找代表性线段。先计算完 \rho_{i} 和 \beta_{i,j} 后，针对 R 中的所有线段，按其密度得分降序排序，并以得分最高的线段初始化队列。随后，我们在满足两个条件的前提下选择下一条线段： (i) 下一条线段与已在队列中的线段之间的曲率差异 \beta_{i,j} 必须大于 \lambda； (ii) 下一条线段的长度必须大于 \tau。我们重复此过程，直到找到所需数量的代表性线段，默认数量为三条。
Fig. 6. 在包含众多时间序列的合成数据集上查询代表线。(a) 过度叠加的线图由来自三个组的线条组成，其代表线被突出显示； (b) 密度可视化通过三个代表线与密度场中的总体趋势对齐，减少视觉杂乱； (c) 我们使用时间框小部件（蓝色）查询一组线条，然后找到三个代表线。在 (b & c) 中，线索引（一到三）指示线条的降密度顺序。
Fig. 7. 我们的交互式探索系统 KD-box 的界面： (a) 数据面板，用于加载数据并指定数据字段； (b) 主视图，用于展示得到的密度场； (c) 细节视图，用于展示查询结果的统计信息； (d) 控制面板，供用户在交互和渲染中调整参数。
在我们的实验中，我们发现将 \tau 和 \lambda 设置为 (t_{\max}-t_{\min})/2 和 0.1，分别能在大多数数据集上表现良好，并且这两个参数都可以由用户交互式调整。图 6 显示了在通过将三条指定趋势线（参见图 6a 中高亮线）垂直移动一个从高斯分布中抽取的随机值并扰动每个数据点 \mathbf{x}_{i,k} 加入少量高斯噪声的情况下合成的数据集的一个示例。我们方法识别出的代表线如图 6b 所示，与图 6a 中的真值相同。图 6c 展示了时段查询的代表线，我们将选中的线叠加在密度场上。
4.5 交互式探索系统
我们已在 KD-Box（一个基于 JavaScript 的原型 Web 应用程序）中实现了上述方法，KD-Box 允许在不使用任何服务器端组件的情况下交互式探索时间序列数据。图 7 展示了 KD-Box 的用户界面，共分为四个部分。当从 Data Panel（图 7a）加载数据集时，使用两种配合的视图显示数据概览：Main View（图 7b）和 Detail View（图 7c），分别显示密度场以及对应代表曲线和查询小部件的细节（若用户已指定）。此外，用户可以在 Detail View 中悬停任何信息，对应的曲线或小部件会在 Main View 中高亮，反之亦然。进一步地，用户可以在 Control Panel（图 7d）中自定义渲染层、指定参数并调整色图，同时使用提供的查询工具交互式探索数据。以下将描述渲染层和查询工具。
渲染层
在 Main View 中有五个渲染层：密度场、所有时间序列的折线图、查询线条的折线图、查询线条的密度场以及代表线条。对于每一次查询操作，默认层为密度场，而用户可以组合并以可调透明度顺序排列任意层。对于所选密度场，用户可以在控制面板中选择不同的色图。用户指定查询后，系统会在密度场上叠加代表线条，并默认在 Detail View 中显示相应细节。
查询工具
我们支持通过使用四种已知交互来查询部分线条，即 timebox、angular query、mouse hover 和 attribute filtering。对于前两种工具，请参见 Sect. 3 的详细说明；attribute filtering 允许用户通过指定多个属性值来过滤时间序列，而 mouse hover 允许用户与单个线条交互。为实现此功能，我们重用高效的 RNL 查询，半径为 3 × 3 像素，中心位于用户光标位置，同时允许用户使用鼠标滚轮放大半径。
第5节 比较评估
我们在两方面评估我们的技术：line query 和 density rendering，使用一台 Intel Core i5-8400 CPU @ 2.8GHz、32GB 内存、运行 Google Chrome 89 的电脑。
Datasets. 我们遵循现有做法 34, 35 生成具有不同分布的合成数据集。基于非季节性时间序列模型 36，我们合成了一个具有两个成分的时间序列：
\begin{equation*} v_{t}=\mathbf{T}_{t}+\beta \mathbf{W}_{t}, \tag{7} \end{equation*}
其中 v_{t} 为第 tth 步的值，\mathbf{T}_{t} 为趋势成分，\mathbf{W}_{t} 为白噪声。趋势成分 \mathbf{T}_{t} 是通过从七种趋势分布（高斯、指数、泊松、线性、对数、正弦和余弦函数）列表中随机选择一种来计算的，白噪声 \mathbf{W}_{t} 与 \beta 的参数则随机生成。为研究我们的方法在不同时间序列数据下的性能变化，我们通过改变两个参数生成数据集：时间序列的数量和每个时间序列中的时间点数。具体做法是将一个参数固定为 100，另一个从 1 K 到 10 K 以 1 K 为步长变化，再从 10 K 到 100 K 以 10 K 为步长变化。总共生成了 38 个数据集。
5.1 行查询
我们通过执行 (i) RNL、(ii) timebox 查询和 (iii) angular 查询，对四种选定方法进行了比较评估，使用 M 个随机生成的查询点分别用于 RNL、timeboxes 和每个数据集的 angular 范围。这里，我们将 M 设为 1,000，并测试了不同的 r 值用于 RNL 搜索，即相对于归一化屏幕空间范围 [0, 1] 的 \{0.01, 0.02, \cdots,0.1\}。
图 8. Boxplots 展示了 RNL 搜索 (\mathrm{r}=0.02)、timebox 查询和 angular 查询在所有数据集上使用四种查询方法的线召回 (a)、线精度 (b)、查询时间 (c,d,e) 与树构建时间 (f) 的结果。
方法
我们将我们的方法与三种方法进行比较：KD-Tree、R-Tree 和顺序搜索。在它们中，顺序搜索在时间盒搜索 37 上表现优于范围树和哈希表，因此我们选择实现它。为了将基于点的 KD-Tree 38 和 R - Tree 39 适配为最近线（NL）搜索，我们在叶节点中预先存储了每个点的线索引，并基于最先进的 JavaScript 实现 40, [^54] 进行了实现。
测量
我们从树构建时间、查询处理时间和查询准确率三方面定量评估线查询的质量和性能。关于查询准确率，我们遵循 Lu 等人 [^5]，使用两种数值指标 line recall 与 line precision。设检索到的线集合为 \hat{\Omega}，而真实值为 \Omega，line recall 衡量在真实值 \Omega 中检索到的线所占比例：
\begin{equation*} line \ recall(L R)=\frac{\vert\hat{\Omega} \cap \Omega\vert}{\vert\Omega\vert}, \end{equation*}
其范围从 0 到 1。数值越大表示发现的真实线越多。同样，line precision 衡量在 \hat{\Omega} 中正确检索到的线所占比例：
\begin{equation*} {line} \ {precision}(L P)=\frac{\vert\hat{\Omega} \cap \Omega\vert}{\vert\hat{\Omega}\vert}, \end{equation*}
其范围也从 0 到 1。数值越大表示在 \hat{\Omega} 中检索到的线越接近真实最近线。
图9. 我们的方法与顺序搜索在执行 RNL、时间盒查询和角度查询时不同参数下的查询时间比较：(a) 时间序列数量；(b) 每条线的时间样本点数量。
图10. 我们的方法与 denseplot 在渲染密度场时不同参数下的渲染时间 (a) 与 MSE (b) 的比较。
结果
为了定量评估这四种方法。我们计算了在每个数据集上，由这四种查询方法发出的 M 次查询操作所得到的平均 LR, LP 和 query time。图 8a-e 中展示的箱线图总结了这四种方法的三项指标。
结果显示，我们的方法在行召回率和行精度方面分别取得了 99.1 % 和 99.9 %的平均准确率，而 KD‑tree 的平均行召回率仅为 80.9 %，R‑tree 的平均行精度仅为 90.3 %。 KD‑tree 准确率低的主要原因是其构建基于采样点，未考虑连续线信息。 R‑tree 也存在类似问题，其存储的包围盒未能准确覆盖线段范围，导致查询结果中包含更多不合格线段。 相反，顺序搜索始终返回真实结果，但在 RNL 查询上比我们的方法慢 3 倍，在 timebox 查询上慢 5 倍，在角度查询上慢 15 倍。 虽然我们的方法在三种查询策略下比 KD‑tree 和 R‑tree 更慢，但它足够快，能够支持有效探索 41，在该处三种查询策略的平均查询时间均低于 16 ms。 此外，构建树的时间也比 KD‑tree 和 R‑tree 更短，如图 8(f)所示。 综合上述结果，我们得出结论：我们的方法在离线预处理和在线查询中以更低的计算成本实现更高的准确率。
如图 9 所示，无论使用哪种查询策略，我们的方法与顺序搜索的查询时间都随行数和时间点数量的增加而上升。与顺序搜索相比，当行数或时间点数量为 100K 时，我们的方法在 RNL 查询、时间盒查询和角度查询方面分别快约 10 倍、10 倍和 20 倍。所有查询均在 300 ms 内完成，足以支持对大规模时序数据的高效探索。
此外，对三种查询策略的查询时间进行比较后发现，角度查询最快，时间盒查询其次，RNL 查询最后。这样是合理的，因为我们的 RNL 查询涉及计算查询点到线段的距离，时间盒查询需要检查线段与查询框的相交情况，而角度查询则不需要这些操作。
图 11. (a) 所有阅读者在网页交互式文章中的阅读行为密度可视化及代表性线条。 (b) 在整体时间范围内将时间盒放置在较低滚动位置较早的位置时，我们可以揭示非常早滚动并快速完成阅读的阅读者，从而快速生成这些阅读者阅读行为的密度图。 注意两张密度图 (a & b) 都采用相同的颜色尺度。
5.2 密度渲染
为了评估我们密度场的渲染性能和质量，我们选择 DensePlot 42（DenseLine 的最先进 CPU 实现 [^3]）作为渲染基准。由于树构建是支持交互所必需的，我们仅测量渲染时间和我们结果与 DensePlot 之间的均方误差（MSE）。所有密度图的显示尺寸为 1200×600 像素。
结果
图10a 概括了两种方法的渲染时间。我们可以看到，当时间序列数量少于5K时，我们的方法仅比DensePlot稍慢一点，但随后速度更快。 此外，它的渲染时间增加非常缓慢，最大渲染时间约为500毫秒。原因是我们的方法是一种图像顺序方法，其复杂度与时间序列数量或时间点无关。尽管如此，我们的密度场仍高度准确，MSE错误低于0.15%（见图10(b)）。因此，我们得出结论，我们的方法能够更快地生成几乎准确且高质量的密度场。
第6节 Kd-Box 演示
本节中，我们展示了三种基于真实数据的演示，以展示 KD-Box 中的交互。我们通过假设的用户情境来探讨这些演示，说明人们如何使用我们的工具。我们研究了来自在线阅读模式（第6.1节）、硬盘统计（第6.2节）和温度数据（第6.3节）的海量时间序列数据。
虽然 KD-Box 仅支持先前系统（如 TimeSearcher 43）中的一部分交互，但它能够处理更大的数据集。因此，我们将演示案例聚焦于 KD-Box 可扩展性所支持的数据方面。
6.1 发现 Beat Basics 的阅读模式
本演示案例探讨了 Beat Basics[^56] 的阅读行为，该交互式文章解释了 3/4 拍与 6/8 拍之间的区别。Conlen 等人 44 通过对记录的活动进行可视化来表征本文中的交互模式，并公开了他们收集的数据以进行分析。该数据集包含 4430 条时间序列，每条序列都代表一次会话中用户的阅读行为，并记录从打开到关闭文章的滚动位置。Conlen 等人使用了覆盖低透明度线条的密度可视化。在这种朴素的表示中，每条线条具有相同的透明度。因此，如果设置得太低，低密度区域会消失；如果设置得太高，密度会过快达到顶部。此外，这种表示法会导致像我们在 3 节中讨论的那样的陡峭线条视觉伪影。
*Fig. 12. (a) 92K 硬盘六年温度的密度场可视化与代表性线条。(b) 由灰色框选的长期硬盘的叠加密度与代表性线条。整体密度场及所选区域分别使用黄-绿-蓝和黄-橙-红色标度编码。
我们将数据集加载到 KD-Box 并生成图 11 所示的密度可视化。水平轴表示阅读时间，垂直轴表示文章中的滚动位置。阅读时间范围为 0 到 3.3 分钟，滚动位置范围为 0%（文章顶部）到 100%（文章底部）。密度可视化（图 11a）显示左上角高密度模式，这很合理，因为我们期望读者从顶部开始阅读。
有趣的是，一些高密度区域在阅读初期出现于较低的滚动位置。使用刷子查询（图 11b）进一步调查显示，一些读者只是立即向下滚动，而另一些则从文章中间开始阅读。刷子查询只选择了几百行，因此我们可以渲染所有被选中的行（并使用图 7d 所示的控制面板隐藏完整密度）。正如图 11b 所示，具有此类行为的读者过多（约 1 000 名），因此我们可以切换到密度表示。代表性行可以揭示其他常见的阅读模式，例如先向下滚动后再返回向上的用户（亦被 Conlen 等人识别45。）
6.2 硬盘的传感器数据
传感器是最常见的时间序列数据来源之一，提供关于环境和电子系统随时间变化的测量。作为电子系统中传感器的一个例子，在第二个演示案例中，我们探讨了超过92 000个硬盘的统计数据。Backblaze（一家云存储提供商）每季度发布关于其数据中心硬盘的详细统计信息[^57]。
图 13. (a) 在美国的气象数据集的密度可视化，由 ACIS 网络服务获取。 (b) 当所有行一起可视化时的数据集原始行。 (c) 通过时间盒和角度查询选取的1月持续高温地区的密度可视化；见左侧叠加的灰色框。整体密度场与所选区域分别使用黄绿蓝和黄橙红色尺度编码。
图 12a 显示了在完整数据集中超过 160K 条时间序列中随机抽取 92K 条时间序列的硬盘温度（SMART 194）的时间序列。请注意，我们的方法可以处理更大规模的数据，但目前受限于浏览器（见第 7 节）。然而，图 12a中的可视化已经显示了 2.4M 条单独记录的聚合，从中我们可以看到没有硬盘温度超过 55°C，且大多数保持在 20°C 与 30°C 之间。相同数据的非密度版本将会是一幅高度拥挤的可视化。
通过在 2014 年记录开始时绘制一个笔刷，我们可以看到第一代硬盘根本不再运行。我们可能想查看过去四年仍在使用的硬盘。设置相隔四年的一对时间盒可以过滤数据并定位 14K 条时间序列（图 12b）。这些选定线条的密度显示，大多数长寿命硬盘的温度范围比其余的更窄。同时，绝大多数硬盘保持在较低温度。这个洞察可以为更好的硬盘维护提供指标。
6.3 大规模温度数据中的模式
在本例中，我们探索了来自应用气候信息系统（ACIS）网络服务 [^58] 的环境传感器数据集，该数据集记录了 2019 年美国 6187 家公共气象站的每日温度。
图 13a 中不使用过滤器的密度可视化显示了一个明显的季节性模式，即夏季平均气温更高。 这一模式并不令人意外，因为美国位于北半球。 尽管仅绘制折线（图 13b）也能看到这一趋势，但密度可视化显示大多数气象站的变异性比外壳所暗示的更大。 代表性折线也展示了数据中更广泛的这一趋势。
我们可能对一年中前几个月持续高温的地方的温度趋势感兴趣。 为此，我们可以创建一个角度查询，以查找年初月份陡度（斜率）较小的时间序列，并在高温处进行刷子查询。 密度可视化（图 13c）显示这些地方的温度普遍较高，并且全年相当持续温暖，这也得到了叠加在所选密度场上的代表线的确认。 在夏季，这些地方的温度与美国大多数温度相似。 细节视图（图 7c）显示该选择中的代表线对应南部或靠近海洋的地方（即佛罗里达、加利福尼亚海岸和夏威夷）。 接近海洋可以获得巨大的热容量，从而导致温度更为稳定。
同样，我们可能希望查看在其他月份具有一致（不受范围限制）温度地点的温度曲线。我们可以沿时间轴移动角度滤波器来更新查询。由于 KD-Box 在 40 ms 内提供快速查询响应，我们可以观察所选地点的温度发展，并注意到低温地点通常具有更高的温度变异性。交互速度快是因为我们可以增量更新查询结果（第 4.3 节）。
第 7 章 讨论与未来工作
Hochheiser 等人 46 证明了 timebox 查询是探索性时间序列数据分析的有价值工具。其系统 Time-Searcher 47、48 为小型时间序列数据集提供交互式响应时间。然而，针对大规模时间序列数据存在两个可扩展性问题。首先，过度绘制和视觉杂乱会使数据概览变得意义不大。约束可以帮助在显示中过滤时间序列，但仅此不足以解决问题，因为许多有趣的查询可能不易被选择。在本文中，我们通过一种高效的密度可视化来解决这些问题，该可视化显示了所有时间序列以及符合查询约束的时间序列。第二，Hochheiser 等人 49 指出，75% 的查询时间花费在查询评估上，而非渲染。我们将基于线段的 KD 树集成到 KD-Box 中，能够在更大数据上实现快速查询，同时保持高度响应性。
我们当前KD-Box实现相关的主要限制有三项。 首先，由于浏览器施加的内存限制，我们最多只能高效探索10万条时间序列。 为了解决此问题，我们计划将基于线段的KD树扩展为逐步工作的方式 [^59]，其中数据以块的形式流入内存。 其次，我们的代表性线选择基于启发式方法，可能无法捕捉复杂数据的所有有趣趋势。 我们计划将一种快速基于密度的聚类方法——均值漂移聚类 50、51——扩展为曲线基密度场，以识别代表性线。 最后，我们的KD-Box仅关注时间盒和角度查询的核心功能；而未来版本的系统应该支持TimeSearcher 52中的全部功能，包括领头者和滞后者、查询反转和可变时间盒。
未来有两项工作可能性。 第一项是将我们的系统扩展为支持在金融、移动和物联网等各个领域对流式时间序列数据进行交互式分析。 第二项，基于密度的表示已被用于可视化各种类型的数据 53，如轨迹、图形和高维数据，而它们中的大多数都面临与时间序列数据类似的挑战。 未来，我们将扩展基于线段的KD树，以探索这些不同的数据以完成其他分析任务。
注脚
idyll-lang.org/gallery/beat-basics