0

我面临一个问题，我觉得图论或图数据库中有解决方案。我在这些领域的知识非常有限。我希望有人能认出我的问题，也许可以指出用于解决它的技术的名称。

简化示例：

我正在处理时间序列的状态。一个简单的例子，只有两种状态：

TS    State
t0    T
t1    F
t2    F
t3    F
t4    T
t5    T
t6    T
t7    F
t...  ...

我可以将其转换为具有两个节点（T 和 F）的图，其中状态中的“停留时间”是一个属性（在括号中）：

T(1) -> F(3) -> T(3) -> F(1)

我的问题的一个例子是编写一个“查询”来提取与此模式匹配的任何子序列F(>=2) -> T(<10)。在上面的示例中，我的查询将提取子序列： F(3) -> T(3)

但如果它存在于数据集中，查询也可以提取如下序列：

F(2) -> T(8)
F(20) -> T(3)

我提出的示例已简化：有两个以上的状态，并且更高级的查询将允许循环，其中这些循环可以限制在循环中花费的总时间或可以完成的循环数量：例如

`T(>2) -> [loops of F(1)->T(1)] -> T(<10)`

我的循环可能会被限制为不超过 10 次迭代，或者不超过 10 个时间单位。锦上添花的是找到这样的序列

T(n)->F(<n)

翻译为：以 T 开始的序列（并在 T 中停留n 个时间单位），然后是 F 状态，它在 F 中停留的时间小于n（即，F 比前面的 T 短）

我尝试了什么：

我最初想将其转换为字符串，并使用 RegEx 来提取匹配项。正则表达式可以满足我的所有需求，但无法理解像“大于”这样的算术。我想我可以保留我的原始时间序列状态（TFFFTTTF）并对此进行正则表达式......但它看起来很丑陋。

自然语言处理、图论、图数据库等领域会出现类似问题。我不知道如何在我的图表中编码“状态持续时间”属性。我不知道是否有某种“行业标准”查询语言用于图形数据库中的子序列搜索。

问题：

- 有没有解决这些子序列提取问题的框架，如果有，是怎么调用的？有“最佳实践”吗？我应该如何构建我的数据？是否有查询语言来查询序列数据库中的子序列？

4

1 回答 1

1

我可能会把问题反过来。您已经指出这是时间序列数据。鉴于此，我可能会在每次状态更改时创建一个新的状态节点。然后，我将对前一个节点中的“停留”时间进行编码，并将新节点链接到前一个状态节点，在图形数据库中创建一个链表。使用这种结构，您的模式查询变得简单。

Objectivity/DB 是一个基于模式的对象/图形数据库，具有一整套图形导航查询能力。它有自己的查询语言，称为声明性客观性或 DO。

我们从模式定义开始：

UPDATE SCHEMA { 
    CREATE CLASS State{
        label       : String,
        dwellTime   : INTEGER { Storage: B32 },               
        prev        : Reference { referenced: State, Inverse: next },
        next        : Reference { referenced: State, Inverse: prev}
    }           
};

然后我们可以执行如下的 DO 查询：

MATCH p = (:State {label == 'T' AND dwellTime > 5})
           -->(:State {label == 'F' AND dwellTime > 5})
           -->(:State {label == 'T' AND dwellTime < 2})
           -->(:State {label == 'T' AND dwellTime > 100})
           -->(:State {label == 'F' AND dwellTime > 100})
           RETURN p;

这种查询将找到所有满足指定停留时间的“TFTTF”模式。

于 2021-02-27T13:37:09.583 回答