Paper Notes: Hashedcubes: Simple, Low Memory, Real-Time Visual Exploration of Big Data

Intro Hashedcubes 是 Cicero A. L. Pahins 等作者发表在 TVCG 2017 年上的工作,旨在提出一个可以对大数据进行实时可视探索的数据结构。该数据结构可以满足低内存占用、低查询延迟、简单易实现等要求。经实验,在部分情况下,Hashedcubes 可以在空间占用上比最新的方式减少两个数量级的占用。本文描述了 Hashedcubes 的数据结构与构建方式,以及其在注入聚类散点图、直方图、热力图等可视化图表中的应用方式。也用真实世界中的若干数据集进行了评测,从内存占用、构建时间、查询延迟等维度来进行评价。 动机 高维大规模数据的实时可视化系统开发中时常需要解决数据查询的高延迟问题。对数据简单的线性扫描往往会使得延迟不可接受,而近年来提出的种种复杂数据结构虽然能带来高效的查询效率,却由于复杂的实现和 GPU 的支持而难以和现有的系统有机整合。于是本文提出思考:是否存在一个相对简单的数据结构,既能够提供和复杂数据结构想当的性能表现,又能够保持较低的内存占用与实现的简洁性? 主要工作 于是本文主要做的工作包括: 提出了 Hashedcubes,一个用于对高维大规模数据的实时可视化探索的简洁数据结构 一个对 Hashedcubes 的实验性的、验证性的系统实现,用于评测内存占用与查询、构建时间 一系列关于使用 Hashedcubes 的 trade-off 讨论 与本文相关的工作包括大规模数据的可视化分析、时空数据分析与相关系统实现的若干挑战等。 Hashedcubes 的构建 直观认知 文章讲述了设计 Hashedcubes 背后的动机与逻辑。可视化图表中常见的图表绘制问题背后的数据来源往往是「计数」(如某一天、某一区域发生的事件次数作为视觉编码中的一个符号)。此外,数组的长度不受其内元素顺序的影响。因此,对于数组 $A$ 中一个连续区域的元素集 $S$,我们可以使用一对索引 $(b,e)$ 来表示,称为 pivot。通过将 $S$ 划分为互不重合的区域,我们可以通过若干 pivot 来表示整个数组。这样的一种表示方式允许用户在查询时快速跳跃数据,也充分保留了划分的自由性。而每一个划分又可以作为一个新的数组,允许后续在此划分上做进一步划分。 直观上,这种层级的划分机制便是 Hashedcubes 的基础。例如,对于一个具有星期数 $d$,小时数 $h$,网络端口 $p$ 三个维度的网络日志数据集,我们可以依次对每个维度进行划分并得到一系列的 pivot 数组,即三个,分别对应于 $d$ 维度、$(d,h)$ 维度、$(d,h,p)$ 维度。有了这些 pivot 数组之后,计数统计也就可以快速完成,而无需依次扫描数组了。在次基础之上,再给每个 pivot 记录他们所下属的更细维度的范围(如 $d$ 维度的 pivot 同时也会记录这个 pivot 所下属的 $(d,h)$ 维度的范围),便可以在不同层级的 pivot 数组间建立联系 —— 这些机制是对 Hashcudes 的直观认知。...

June 13, 2022 · Bill Chen

Paper Notes: P4: Portable Parallel Processing Pipelines for Interactive Information Visualization

Intro P4, 即 Portable Parallel Processing Pipelines,是由 Jianping Kelven Li、Kwan-Liu Ma 发表在 TVCG 2020 的工作。其提出了一个结合了声明式设计标准和 GPU 计算的、用于构建高性能可视化系统的信息可视化框架,利用 GPU 计算来加速数据处理过程和交互可视化应用中的可视化渲染流程。其提供的 API 可以用于数据转换、视觉编码、交互的快速开发。P4 通过在保持对设计标准的高度灵活性和可自定义性的前提下,简化了经 GPU 加速的可视化系统的开发流程。同时,相对于其他工具链,P4 在创建可交互的可视化方面提供了极大的效率提升。 动机 具备交互的可视化系统,尤其是在处理大规模数据时,需要在数据处理和可视化渲染两个任务上具备高效性。而主流的计算设备大多可以通过 GPU 为这两个任务提供性能提升。因此本文尝试探索 GPU 计算在这两个任务上的潜力,以为开发人员提供一个新的、高性能的可视化开发工具。 P4 主要针对 4 个目标进行设计: Performance:旨在合理分配利用 GPU 资源来储存、处理数据,以获得无缝的高性能 Productivity:旨在提供一个良好架构的、声明式的 API Programmability:旨在提供高度的可定制性和灵活性,让用户可以自定义数据操作与视觉编码的复杂逻辑 Portablity:P4 作为利用 WebGL 的 Web 开发框架,可在不同的现代浏览器中按预期工作 相关工作 可视化工具链 许多可视化工具与库均提供声明式的语法来设计可视化应用,包括 ggplot2、Protovis、D3、Vega、Vega-Lite 等。声明式的语法可以将可视化、互动的具体设计从其背后的执行细节解耦出来,让开发者更聚焦在和应用相关的设计决策上。但现有工具极少利用到 GPU,难以保证大数据的实时互动性。 在与 GPU 相关的技术与可视化工具的结合发面,包括 OpenGL、WebGL 等图形 API,General Purpose GPU 的若干 API OpenCL、CUDA等,以及可视化社区一些使用 shader 来绘制可视化结果的尝试。不过目前的工作大多聚焦在使用 GPU 来渲染可视化结果,而没有利用到其并行的特性来处理数据。...

April 24, 2022 · Bill Chen

使用 Cargo.site 构建你的作品集

如何利用 Cargo.site 做一份拿得出手的作品集。

August 7, 2021 · Bill Chen

站在盒子外面思考

关于如何做决策的一些探索。

April 9, 2021 · Bill Chen

Ready for 20?

写在 20 岁生日的前一天。

October 3, 2020 · Bill Chen