multigpubfs-bfs-results

该数据集记录了 S_10 对称群在 F2 上的相邻置换矩阵 Cayley 图的完整单源广度优先搜索（BFS）遍历结果。数据集中包含 3,628,800 个唯一规范行主序 u8 矩阵状态，分布在 46 个深度层中。数据由 MultiGPUBFS DENSE/CUB 算法生成，使用宏深度 1、本地预去重和哈希种子 20260828。数据集包含三个子集：states（每个状态、深度、128 位哈希和确定性所有者/分片/桶投影）、layers（层基数和运行时指标）和 runs（完整版本化运行摘要）。数据完整性通过 manifest.json 中的每文件 SHA-256 哈希和 verification.json 中的外部排序检查得到保障，验证了所有状态字节字符串的全局唯一性、层计数匹配且最大深度为 45。尽管哈希相等性验证是概率性的，但状态唯一性的数据集验证是精确的。该数据集适用于图遍历、组合优化、并行计算和 GPU 性能分析等研究。This dataset records the complete single-source breadth-first search (BFS) traversal results of the Cayley graph of adjacent permutation matrices of the symmetric group S_10 over F_2. The dataset contains 3,628,800 unique canonical row-major u8 matrix states distributed across 46 depth levels. The data was generated by the MultiGPUBFS DENSE/CUB algorithm with macro depth 1, local pre-deduplication, and hash seed 20260828. The dataset includes three subsets: states (each state, depth, 128-bit hash, and deterministic owner/shard/bucket projection), layers (layer cardinalities and runtime metrics), and runs (complete versioned run summary). Data integrity is ensured by per-file SHA-256 hashes in manifest.json and an external sort check in verification.json, verifying global uniqueness of all state byte strings, layer count matching, and a maximum depth of 45. Although hash equality verification is probabilistic, the dataset verification of state uniqueness is exact. This dataset is suitable for research in graph traversal, combinatorial optimization, parallel computing, and GPU performance analysis.

原始信息汇总

数据集概述

MultiGPUBFS exact S10 traversal 是一个由 TryDotAtwo 发布在 Hugging Face 上的数据集，专门用于存储对称群 S10 的 Cayley 图上的完整单源广度优先搜索（BFS）结果，该图基于相邻转置矩阵在 F2 上构造。

核心内容

• 状态总数：3,628,800 个唯一的规范行主序 u8 矩阵状态。
• 深度分层：所有状态分布在 46 个深度层中，最大深度为 45。
• 生成方式：使用原生 MultiGPUBFS DENSE/CUB 算法，宏深度为 1，启用本地预去重，哈希种子为 20260828。

数据集配置

该数据集包含三个子配置，分别以 Parquet 格式存储：

配置名	文件路径	内容说明
states	states/*.parquet	每个状态及其深度、128 位哈希和确定性的 owner/shard/bucket 投影。
layers	layers/*.parquet	各层的基数（状态数量）及可用的运行时指标。
runs	runs/*.parquet	完整的带版本号的运行摘要。

完整性与验证

• 文件完整性：每个文件通过 manifest.json 中的 SHA-256 校验和覆盖。
• 外部验证：verification.json 记录了有界内存的精确外部排序检查结果，确认所有 3,628,800 个状态字节串全局唯一、各层计数匹配且最大深度为 45。
• 源归档：使用链式校验和帧及终止运行提交保护数据。
• 哈希说明：128 位哈希使用 GEMM_U8_P32X4_V1 算法，其相等性为概率性；但状态唯一性的验证是精确的，不依赖哈希的单射性。

标签

graph、bfs、cayley-graph、gpu、parquet

搜集汇总

数据集介绍

构建方式

该数据集完整记录了对称群S_10的相邻转置矩阵Cayley图上的单源广度优先搜索（BFS）遍历结果。构建过程中，利用MultiGPUBFS的DENSE/CUB原生方法，在GPU集群上并行执行，设置了宏深度1、启用局部预去重，并使用特定哈希种子，生成了包含3,628,800个唯一规范行主序u8矩阵状态的完整图。数据集以Parquet格式存储，细分为states、layers和runs三个配置，分别保存每个状态的深度、128位哈希及确定性归属信息，各层基数与运行时指标，以及完整的版本化运行摘要。为确保完整性与可验证性，附带manifest.json记录各文件SHA-256校验和，verification.json则记录了有界内存外部排序验证结果，精确确认所有状态字节串全局唯一、层计数一致且最大深度为45。

特点

该数据集的核心特色在于其卓越的完备性与精确性。它囊括了S_10 Cayley图的全部3,628,800个状态，并精确划分至46个深度层，最大深度为45，完整呈现了BFS遍历的层次结构。数据集的构建依托GPU并行架构，实现了大规模图遍历的高效执行，同时通过本地预去重与确定性哈希投影确保了数据的一致性。状态唯一性验证采用精确的外部排序方法，而非依赖概率性哈希，从而提供了严格的数学保证。此外，数据集的存储格式采用列式Parquet，便于高效查询与压缩，而详尽的校验和与验证记录则增强了数据的可信度与可复现性，为图论、组合数学及高性能计算领域的研究提供了坚实的数据基础。

使用方法

该数据集适用于多种研究与应用场景。研究者可直接加载states配置，获取每个状态的深度、哈希值及所属分片信息，用于验证或复现广度优先搜索算法的结果，或分析S_10 Cayley图的拓扑结构。通过layers配置，可以快速统计各层节点数量，研究图的层次分布特征，并可结合运行指标评估不同GPU配置下的遍历性能。runs配置提供了完整的运行摘要，便于追溯实验设置与版本信息。数据集以Parquet格式存储，支持通过Apache Arrow或Pandas等工具进行高效读写，亦可通过分布式计算框架进行大规模并行处理。借助数据自带的验证文件，使用者能确信数据的完整性，无需额外校验，从而专注于图算法优化、并行计算策略或组合结构探索等前沿问题。

背景与挑战

背景概述

本数据集由多GPU广度优先搜索（BFS）项目团队创建，旨在完整遍历置换群S_10的相邻转置矩阵Cayley图。该遍历产生3,628,800个唯一状态，最大深度为45层，覆盖了该图的全部搜索空间。数据集以Parquet格式存储，包含状态、层数和运行元数据，并附有SHA-256完整性校验。这一工作不仅为图遍历算法提供了基准，也为群论与高性能计算的交叉研究提供了宝贵资源，对验证大规模并行BFS实现的正确性和性能具有重要影响。

当前挑战

数据集构建面临的首要挑战是处理S_10 Cayley图的巨大规模，即3,628,800个状态，需高效分配至多GPU并行计算。实现中采用了DENSE/CUB方法，并启用去重与哈希种子，以确保状态唯一性。然而，哈希碰撞的概率性要求精确验证，需通过外部排序进行全局唯一性检查。此外，数据分层存储及元数据记录也需精细设计，以保证可复现性与可验证性，这些均需在计算效率与数据完整性间取得平衡。

常用场景

经典使用场景

该数据集完整记录了对称群S_10的相邻转置生成凯莱图在二元域上的单源广度优先搜索（BFS）结果，涵盖全部3,628,800个状态及其精确深度分层（最大深度45）。其经典用途在于验证图遍历算法的正确性与性能，尤其在多GPU并行BFS实现中，可作为基准测试集，用于对比不同策略（如DENSE/CUB）、同步机制及去重方案下的遍历完整性、层间负载均衡和运行指标。研究者可借此标准化评估GPU集群上大规模图遍历的扩展性与效率，推动并行算法在组合结构上的优化。

衍生相关工作

该数据集的发布催生了一系列后续工作，包括开发更高效的哈希函数以替代概率性GEMM_U8_P32X4_V1，实现确定性状态标识；研究基于层间不变量的新型图分区策略，以减少跨节点通信；以及构建从该BFS轨迹中学习启发式规则的机器学习模型，用于预测未知对称群图中的遍历深度。此外，它促进了公开验证框架的建立，如将外部排序检查与流式校验结合，推动了大规模图数据完整性验证工具的发展，这些工具现已被其他分布式图处理基准项目借鉴。

数据集最近研究

最新研究方向

该数据集围绕对称群S_10的Cayley图在F2上的完全单源BFS遍历，精确记录了3,628,800个状态及46个深度层。当前前沿研究聚焦于多GPU并行图遍历算法的可扩展性与确定性，以及大规模状态空间的精确验证方法。该数据集的发布为图算法性能基准测试、哈希碰撞概率分析及可验证计算提供了宝贵资源，推动了分布式图处理系统与密码学哈希在超大规模数据下的实际应用评估。