处理大型结构化数据集

4
我想请您提供一种方法,而不是一个具体的解决方案。我将首先描述我所面临的挑战情况,然后再提出问题。希望这样做更有意义。
我正在处理从自然语言中提取出来的数据。稍后,这些数据必须与某种“知识库”进行分析(它被引用是因为它不是真正的知识库,稍后我会详细介绍)。这个知识库非常大,目前只是理论上的,但很快就会超过可以存储在内存中的容量。我的两个问题是:
1. 将数据移动到数据库服务器上将意味着速度降低了...好吧,我不知道降低了多少倍,但它可能会轻松地降低几个数量级。也就是说,在运行时本地对象中查找数据的任务比在查询数据库中要快得多。 2. 所有庞大的数据并不是同时需要的。 实际上,只使用了很小一部分,因此,可能一些缓存可以解决这个问题。 我实际上希望已经有人面对过这个问题,缓存是正确的答案。
这个“知识库”目前只是一个复杂的数据结构,可以通过使用一些查询语言类似于查询数据库来查询它。也就是说,它不是一个简单的按键操作查找值,它需要多个子查询来识别匹配给定条件的对象。
只是为了给您更具体的例子,我正在尝试开发一个解析器(我称其为“预测性解析器”,如果这个术语已经被使用并且有其他含义,请原谅: )。主要思想是,不像langutils,我试图以一种方式来分配POS标记到单词,并通过应用一组规则来迭代地校正原始假设,而是在给定某个前缀的情况下,引擎将基于其“学习的知识”生成一个延续。也就是说,假设知识库学习到前缀“I could”几乎肯定后跟动词短语,因此解析器将假定动词短语并进行解析,除非出现错误。困难的部分是找到适当的前缀。糟糕的是,“I will”和“Thou shalt”等前缀会获得相同的优先级,也就是说,它们将按照随机、字母表顺序等相同的顺序检查是否匹配。然而,想法是在知识获取过程中,知识库将学习以这种方式存储和查找信息,以便首先查找最有可能的前缀,并且最不可能的前缀甚至不会最初加载。这个概念与CPU高速缓存的工作方式有些相似。因此,如果我写得太长了:我正在寻找一种数据结构,它的功能类似于CPU高速缓存,当前缓存的内容驻留在内存中,而未缓存的内容则存储在数据库或文件等中。

抱歉我的标签可能不太清晰,无法准确描述我的问题。如果您知道问题所属的领域,请随意调整标签。

PS. 抱歉我的标签可能不太清晰,无法准确描述我的问题。如果您知道问题所属的领域,请随意调整标签。


1
这是一个难度较大的设计问题。如果性能不重要而数据的可维护性重要,我会建议使用数据库。如果主要流程是标签化,则每个令牌需要与数据库进行一次往返查询(仅查询成本,更新更难)。对于实时马尔可夫模型,数据必须在核心内存中。 - wildplasser
一个两级结构 - 前缀和规则的使用 - 其中前缀是1:M到规则的,并且两者都被索引可能会有所帮助。前缀索引是正常的,但规则使用索引是动态和加权的,并且按前缀内的权重排序。学习过程将填充a)规则使用表b)规则使用索引c)索引中的加权和d)前缀表和前缀索引。这个结构可以被缓存 - 适用于一小组前缀的两个索引和规则集。我不知道是否存在这样的加权索引结构。 - Chris Walton
听起来Datomic非常适合你的需求。它有一个非常类似于你所描述的缓存模型,并且它有一个基于datalog的查询系统。 - C. K. Young
如果您有构建网络集群的手段,并且可以将知识块划分为不同节点上的分布式形式,那么您仍然可以使用全内存实现。请查看此Erlang实现示例:http://act-r.psy.cmu.edu/papers/926/Douglass(2).pdf - Clayton Stanley
1个回答

1

如果我们只考虑这一部分:

想法是在知识获取过程中,知识库将学习以这种方式存储和查找信息,即首先查找最有可能的前缀,而最不可能的前缀甚至不会被加载。

那么,如果我理解正确的话,您正在处理处理n-gram的任务。由于您在前缀上没有设置任何明确的限制,因此可以假定通常合理的限制适用于4-5个单词的n-gram。有很多这样的n-gram:从真实世界的语料库中,您可以轻松获得几十亿字节的数据。但是,即使您仅限于3-gram,除非进行某些聪明的预处理来分离“好”的n-gram(与适当的平滑配合使用,这可能是可行的解决方案),否则仍将获得至少几个千兆字节。

n-gram的坏消息除了它们的大小之外,还分布在Zipf's law,这基本上意味着缓存不会非常有用。

所以,我会把数据放入本地机器上的某个快速数据库中(也许是dbm的某个变体)。如果你可以将所有数据都放入内存中,那么使用Memcached或Redis可能会更快。


当然,对于“the”的缓存会起作用,但一般的问题是你会得到最多的中频n-gram请求。因此,如果你缓存最常见的20% n-gram,你将得到20%,甚至30%的请求。而一个好的缓存使用案例是它能够用最常用的20%项目的20%来服务80%的请求。(尽管我对这个主题的理解可能不精确和不完整 - 尽管我有一些实践经验,这在某种程度上证实了它)。 - Vsevolod Dyomkin

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接