0

对于按主题划分 RDF 三元组，我使用主题的 String.hashCode() 并将三元组放在相应的分区中。目标是能够处理内存中的分区文件（可能无法处理大文件）。

现在为了限制分区数量，我执行以下操作。假设我们想要有 10 个分区，在一个大的 RDF 文件中：

    String subject; 
    partitionFileName = subject.hashCode / (Integer.MAX_VALUE/10)

因此，所有具有相同主题的三元组都将在一个分区中，总体上我们将有 10 个分区。

现在的问题是，当三元组具有不同的分布时，可能会导致不希望出现的非常大或非常小的分区。

有人有什么建议吗？

先感谢您。

4

2 回答 2

3

算法：

  • 为每个主题创建一个分区（这可以在 RDF 处理期间即时完成）
  • 对于每一个三元组，根据主题将其分配给一个分区，并记住主题-分区映射
  • 当分区数 > 10 时，合并两个最小的分区并更新地图

优点：

  • 确保具有相同主题的所有三元组都在同一个分区中
  • 只要您的数据不是非常不平衡，就保持平衡
  • 如果您不想使用哈希码，则不必使用

缺点：

  • 额外的处理时间，虽然不是繁重的数量；这是 O(n * m) 其中 n 是三元组的数量，m 是不同主题的数量
  • 如果您的数据非常不均匀，则使用不同的分区大小，但这是不可避免的，因为您希望所有三元组在同一个分区中具有相同的主题
  • 您必须维护映射以执行查找，但这最终是微不足道的，并且是一个恒定的时间操作

如果您不关心在单个分区中保留相同主题的三元组，那么只需创建十个桶并循环填充它们。O(n) 并且尽可能平衡。

于 2016-02-18T21:15:54.880 回答
0

您可以简单地使用模来拆分分区：

subject.hashCode() % 10

将或多或少均匀地分布在十个分区上。

于 2016-02-18T18:51:28.473 回答