本发明提供了一种面向演化图高效历史查询的自适应快照调整方法，属于演化图存储技术领域，包括以下步骤:步骤S1：初始化快照调整周期；步骤S2：追踪并记录一个周期内所发生历史查询的相关信息；步骤S3：根据上述信息，评价一个周期内历史查询的性能；步骤S4：结合性能评价，确定进行哪些类型的快照调整；步骤S5：完成快照移动类型的调整；步骤S6：完成快照新建类型的调整；步骤S7：完成快照删除类型的调整；步骤S8：更新快照调整周期，回到S2。本发明对传统“快照+日志”的演化图存储方法进行了改进，利用本发明方法可根据用户历史查询的时空分布特征，实现快照的自适应调整，从而提高历史查询的效率。
1.一种面向演化图高效历史查询的自适应快照调整方法，其特征在于，包括以下步骤：步骤S1：初始化快照调整周期；
步骤S2：追踪并记录一个周期内所发生历史查询的相关信息；
步骤S3：根据上述信息，评价一个周期内历史查询的性能；
2.根据权利要求1所述的面向演化图高效历史查询的自适应快照调整方法，其特征在于，所述步骤S1中由用户给定快照调整周期T的一个初始值。
3.根据权利要求2所述的面向演化图高效历史查询的自适应快照调整方法，其特征在于，根据快照调整周期T，所述步骤S2追踪并记录一个周期内历史查询的相关信息，包括各个查询Qi所针对的历史时刻ti、完成该查询所使用的快照S(ti)、完成该查询所引发的图操作数ni。
4.根据权利要求3所述的面向演化图高效历史查询的自适应快照调整方法，其特征在于，所述步骤S3利用所述步骤S2中记录的信息：查询所针对的历史时刻ti、完成该查询所引发的图操作数ni，用一个周期内操作数的平均值和方差来评价历史查询的性能，具体步骤如下：步骤S31：根据查询所针对的历史时刻ti，计算上述周期内历史查询的总数numq；
步骤S32：将每个历史查询所发生的图操作数相加，记为numops；
步骤S33：计算各历史查询所发生图操作数平均值navg＝numops/numq；
5.根据权利要求4所述的面向演化图高效历史查询的自适应快照调整方法，其特征在2
于，所述步骤S4按照所述步骤S3中的性能评价指标平均值navg和方差S，确定是否进行快照移动、快照新建或快照删除；定义布尔值move、add、delete分别代表是否进行快照移动、快照新建或快照删除，调整策略如下：用户给定阈值A、B；
2)当navgB时，只进行快照新建，move＝flase、add＝true、delete＝flase；
3)当navg>A&&S >B时，先进行快照移动，再进行快照新建，move＝true、add＝true、delete＝flase；
6.根据权利要求5所述的面向演化图高效历史查询的自适应快照调整方法，其特征在于，所述步骤S5由所述步骤S2和步骤S4确定是否进行快照移动，判断S4中move的值，当move＝true时，进行快照移动，移动方法如下：用户给定一个阈值C；
步骤S51：计算周期内，每个快照上发生的历史查询的个数Si(Qi)；
步骤S52：计算每个快照上完成这些历史查询所引发的最小操作数，记为min(ni)；
步骤S53：计算周期内每个快照的Xmove值，Xmove＝Si(Qi)*min(ni)；
步骤S54：当Xmove>C时，需要把该快照向右移动min(ni)个长度；
步骤S55：重复步骤S51‑S54，对周期内每一个快照进行计算；
步骤S56：计算满足条件Xmove>C的快照个数nummove，nummove就是需要移动的快照个数。
7.根据权利要求6所述的面向演化图高效历史查询的自适应快照调整方法，其特征在于，所述步骤S6由所述步骤S2和步骤S4确定是否需要新建快照，判断S4中add值，当add＝true时，新建快照，方法如下：用户给定阈值D；
步骤S61：计算一个快照上完成历史查询所引发的最大操作数max(ni)；
步骤S62：计算该快照上完成历史查询所引发的最小操作数min(ni)；
步骤S63：计算最大操作数与最小操作数的差值Dadd＝max(ni)‑min(ni)；
步骤S65：计算发生在该快照和其后续相邻快照之间的图更新操作数numops，对介于1和numops之间的任意整数i，计算所引发图操作数大于等于i的历史查询的个数numi；
步骤S66：找出使得i*numi取值最大的i值，计为I；
步骤S67：以该快照为基础，执行I个图更新操作，并将获得的图状态作为新建快照；
步骤S68：重复步骤S61‑S67，直到每一个快照计算完毕；
8.根据权利要求7所述的面向演化图高效历史查询的自适应快照调整方法，其特征在于，所述步骤S7由所述步骤S2和步骤S4确定是否需要删除快照，判断S4中delete值，当delete＝true时，删除快照，方法如下：用户给定阈值E、F、G；
步骤S71：计算一个快照上发生的查询个数Si(Qi)；
步骤S72：计算该快照上完成历史查询所引发的最大操作数max(ni)；
步骤S73：由log日志得出该快照到前一个快照之间的操作数On；
步骤S74：用该快照的Si(Qi)，max(ni)，On与E，F，G进行比较，若Si(Qi)
步骤S75：重复步骤S71‑S74，直到每一个快照计算完毕；
9.根据权利要求8所述的面向演化图高效历史查询的自适应快照调整方法，其特征在于，所述步骤S8根据所述步骤S2、S5、S6、S7，计算更新快照调整周期T，计算过程如下：用户定义阈值H、I；
步骤S81：由S2中的S(ti)计算出该周期内快照总数ntotal；
步骤S82：计算发生变化的快照数Stotal＝nummove+numadd+numdel；
步骤S83：比较Stotal和ntotal①Stotal
②Stotal>ntotal*I，则T＝T*1/2；
③ntotal*H<＝Stotal<＝ntotal*I，则T＝T；
一种面向演化图高效历史查询的自适应快照调整方法
技术领域
[0001] 本发明属于演化图存储技术领域，具体涉及一种面向演化图高效历史查询的自适应快照调整方法。
背景技术
[0002] 近年来各类型网络迅速发展，诸如交通网络、社交网络等。这些网络产生了大量数据，可以通过图来表示。现实的网络在动态变化，例如在社交网络中，用户之间的关系随时间而不断变化。与之对应，相关的图数据亦呈现出动态演化的特点。
[0003] 这种演化图带来的一个重要挑战是如何高效地处理它们的历史，而不仅仅是它的最新状态。例如在社交网络中“2015年至今，某个人群之间的朋友关系是如何演变的”，类似问题可以通过查询图的历史状态解决。因此，需要为演化图设计一个可以支持历史状态查询的系统，该系统维护演化图的所有历史信息，并提供高效查询。
[0004] 快照和日志是记录演化图历史状态的两种方式。如果为演化图的每一次更新操作都新建一个快照，会占用较多的存储空间。若只为每一次更新操作记录日志，虽然会节省很多存储空间，但是访问某一历史时刻的图数据时，需要从零时刻进行恢复，浪费大量的时间。所以现在通常使用“快照+日志”的混合式方法，只在某些时刻建立快照，将相邻两个快照之间的更新操作用日志记录。当需要访问某一历史时刻的图数据时，可以用最近时刻的快照和日志文件中的部分更新操作生成。对“快照+日志”的混合式方法而言，快照和日志数据的排布方式非常关键，直接影响历史查询的性能。
[0005] 传统的快照和日志数据排布方法是在演化图开始产生的时刻，生成一个快照，这个时候是没有日志文件的。当演化图发生改变时，开始产生日志文件，日志文件存储的是对图数据的更新操作，这时不会产生快照。当日志文件体量达到预设值时，系统需要增加快照，以此不断交替。这种方法的缺点是：没有考虑用户不同的历史查询特征，这样会使得有些情况下历史查询的效率很低。目前尚缺乏一种能够根据用户历史查询的时空分布特征来自动调整快照和日志文件排布方式的技术。
[0006] 因此，本申请提供一种面向演化图高效历史查询的自适应快照调整方法。
发明内容
[0007] 为了克服上述现有技术存在的不足，本发明提供了一种面向演化图高效历史查询的自适应快照调整方法。
[0008] 为了实现上述目的，本发明提供如下技术方案：
[0009] 一种面向演化图高效历史查询的自适应快照调整方法，包括以下步骤：
[0010] 步骤S1：初始化快照调整周期；
[0011] 步骤S2：追踪并记录一个周期内所发生历史查询的相关信息；
[0012] 步骤S3：根据上述信息，评价一个周期内历史查询的性能；
[0013] 步骤S4：结合性能评价，确定进行哪些类型的快照调整；
[0014] 步骤S5：完成快照移动类型的调整；
[0015] 步骤S6：完成快照新建类型的调整；
[0016] 步骤S7：完成快照删除类型的调整；
[0017] 步骤S8：更新快照调整周期，回到S2。
[0018] 优选地，所述步骤S1中由用户给定快照调整周期T的一个初始值。
[0019] 优选地，根据快照调整周期T，所述步骤S2追踪并记录一个周期内历史查询的相关信息，包括各个查询Qi所针对的历史时刻ti、完成该查询所使用的快照S(ti)、完成该查询所引发的图操作数ni。
[0020] 优选地，所述步骤S3利用所述步骤S2中记录的信息：查询所针对的历史时刻ti、完成该查询所引发的图操作数ni，用一个周期内操作数的平均值和方差来评价历史查询的性能，具体步骤如下：
[0021] 步骤S31：根据查询所针对的历史时刻ti，计算上述周期内历史查询的总数numq；
[0022] 步骤S32：将每个历史查询所发生的图操作数相加，记为numops；
[0023] 步骤S33：计算各历史查询所发生图操作数平均值navg＝numops/numq；
[0024] 步骤S34：计算各历史查询所发生图操作数方差
[0025] 优选地，所述步骤S4按照所述步骤S3中的性能评价指标平均值navg和方差S2，确定是否进行快照移动、快照新建或快照删除；定义布尔值move、add、delete分别代表是否进行快照移动、快照新建或快照删除，调整策略如下：
[0026] 用户给定阈值A、B；
[0027] 1)当navg>A&&S2
[0028] 2)当navg
B时，只进行快照新建，move＝flase、add＝true、delete＝flase；[0029] 3)当navg>A&&S2>B时，先进行快照移动，再进行快照新建，move＝true、add＝true、delete＝flase；
[0030] 4)当navg
[0031] 优选地，所述步骤S5由所述步骤S2和步骤S4确定是否进行快照移动，判断S4中move的值，当move＝true时，进行快照移动，移动方法如下：
[0032] 用户给定一个阈值C；
[0033] 步骤S51：计算周期内，每个快照上发生的历史查询的个数Si(Qi)；
[0034] 步骤S52：计算每个快照上完成这些历史查询所引发的最小操作数，记为min(ni)；
[0035] 步骤S53：计算周期内每个快照的Xmove值，Xmove＝Si(Qi)*min(ni)；
[0036] 步骤S54：当Xmove>C时，需要把该快照向右移动min(ni)个长度；
[0037] 步骤S55：重复步骤S51‑S54，对周期内每一个快照进行计算；
[0038] 步骤S56：计算满足条件Xmove>C的快照个数nummove，nummove就是需要移动的快照个数。
[0039] 优选地，所述步骤S6由所述步骤S2和步骤S4确定是否需要新建快照，判断S4中add值，当add＝true时，新建快照，方法如下：
[0040] 用户给定阈值D；
[0041] 步骤S61：计算一个快照上完成历史查询所引发的最大操作数max(ni)；
[0042] 步骤S62：计算该快照上完成历史查询所引发的最小操作数min(ni)；
[0043] 步骤S63：计算最大操作数与最小操作数的差值Dadd＝max(ni)‑min(ni)；
[0044] 步骤S64：比较Dadd和D
[0045] 若Dadd
[0046] 步骤S65：计算发生在该快照和其后续相邻快照之间的图更新操作数numops，对介于1和numops之间的任意整数i，计算所引发图操作数大于等于i的历史查询的个数numi；
[0047] 步骤S66：找出使得i*numi取值最大的i值，计为I；
[0048] 步骤S67：以该快照为基础，执行I个图更新操作，将获得的图状态作为新建快照；
[0049] 步骤S68：重复步骤S61‑S67，直到每一个快照计算完毕；
[0050] 统计新建的快照个数numadd。
[0051] 优选地，所述步骤S7由所述步骤S2和步骤S4确定是否需要删除快照，判断S4中delete值，当delete＝true时，删除快照，方法如下：
[0052] 用户给定阈值E、F、G；
[0053] 步骤S71：计算一个快照上发生的查询个数Si(Qi)；
[0054] 步骤S72：计算该快照上完成历史查询所引发的最大操作数max(ni)；
[0055] 步骤S73：由log日志得出该快照到前一个快照之间的操作数On；
[0056] 步骤S74：用该快照的Si(Qi)，max(ni)，On与E，F，G进行比较，若Si(Qi)
[0057] 步骤S75：重复步骤S71‑S74，直到每一个快照计算完毕；
[0058] 统计被删除快照的个数numdel。
[0059] 优选地，所述步骤S8根据所述步骤S2、S5、S6、S7，计算更新快照调整周期T，计算过程如下：
[0060] 用户定义阈值H、I；
[0061] 步骤S81：由S2中的S(ti)计算出该周期内快照总数ntotal；
[0062] 步骤S82：计算发生变化的快照数Stotal＝nummove+numadd+numdel；
[0063] 步骤S83：比较Stotal和ntotal
[0064] ④Stotal
[0065] ⑤Stotal>ntotal*I，则T＝T*1/2；
[0066] ⑥ntotal*H<＝Stotal<＝ntotal*I，则T＝T；
[0067] 步骤S84：得到新的快照调整周期T，回到S2。
[0068] 本发明提供的面向演化图高效历史查询的自适应快照调整方法对传统“快照+日志”的演化图存储方法进行了改进。通过自适应的快照调整方法，使快照的分布与用户历史查询的时空分布相匹配，从而提高了演化图历史查询的性能。本发明弥补了传统固定快照分布方法的缺陷，具有更好的科学性和更高的实际应用价值。
附图说明
[0069] 图1为本发明实施例1的面向演化图高效历史查询的自适应快照调整方法的流程图；
[0070] 图2为传统固定快照方法与本发明实施例1的面向演化图高效历史查询的自适应快照调整方法对比实例图。
具体实施方式
[0071] 下面结合附图，对本发明的具体实施方式作进一步描述。以下实施例仅用于更加清楚地说明本发明的技术方案，而不能以此来限制本发明的保护范围。
[0072] 实施例1
[0073] 本发明提供了一种面向演化图高效历史查询的自适应快照调整方法，具体如图1所示，包括以下步骤：
[0074] 步骤S1：初始化快照调整周期；
[0075] 本实施例中，步骤S1中，为了适应不同用户的要求，由用户给定快照调整周期T的一个初始值；
[0076] 步骤S2：追踪并记录一个周期内所发生历史查询的相关信息；
[0077] 具体为，根据快照调整周期T，步骤S2追踪并记录一个周期内历史查询的相关信息，包括各个查询Qi所针对的历史时刻ti、完成该查询所使用的快照S(ti)、完成该查询所引发的图操作数ni；
[0078] 步骤S3：根据上述信息，评价一个周期内历史查询的性能；
[0079] 具体的，步骤S3利用步骤S2中记录的信息：查询所针对的历史时刻ti、完成该查询所引发的图操作数ni，用一个周期内操作数的平均值和方差来评价历史查询的性能；
[0080] 平均值小，代表该周期内的历史查询性能整体较高，平均值大，代表历史查询的整体性能较差，说明现有的快照数量较少，需要新建快照；方差小，代表一个周期内历史查询性能差异较小，不需要调整快照位置。方差大，代表历史查询性能差异较大，需要调整快照位置，提高历史查询的性能。
[0081] 具体步骤如下：
[0082] 步骤S31：根据查询所针对的历史时刻ti，计算上述周期内历史查询的总数numq；
[0083] 步骤S32：将每个历史查询所发生的图操作数相加，记为numops；
[0084] 步骤S33：计算各历史查询所发生图操作数平均值navg＝numops/numq；
[0085] 步骤S34：计算各历史查询所发生图操作数方差
[0086] 步骤S4：结合性能评价，确定进行哪些类型的快照调整；
[0087] 具体的，步骤S4按照步骤S3中的性能评价指标平均值navg和方差S2，确定是否进行快照移动、快照新建或快照删除；定义布尔值move、add、delete分别代表是否进行快照移动、快照新建或快照删除，调整策略如下：
[0088] 根据用户的实际情况，由用户给定衡量评价指标的标准，用户给定阈值A、B；
[0089] 1)当navg>A&&S2
[0090] 2)当navg
B时，只进行快照新建，move＝flase、add＝true、delete＝flase；[0091] 3)当navg>A&&S2>B时，先进行快照移动，再进行快照新建，move＝true、add＝true、delete＝flase；
[0092] 4)当navg
[0093] 步骤S5：完成快照移动类型的调整；
[0094] 具体的，步骤S5由步骤S2和步骤S4确定是否进行快照移动，判断S4中move的值，当move＝true时，进行快照移动；
[0095] 快照的移动是通过改变快照位置来提高查询效率的，但是快照的移动是要花费一定代价的，根据用户实际需求，当减少的开销满足用户需求C时，才进行快照移动。
[0096] 移动方法如下：
[0097] 用户给定一个阈值C；
[0098] 步骤S51：计算周期内，每个快照上发生的历史查询的个数Si(Qi)；
[0099] 步骤S52：计算每个快照上完成这些历史查询所引发的最小操作数，记为min(ni)；
[0100] 步骤S53：计算周期内每个快照的Xmove值，Xmove＝Si(Qi)*min(ni)；
[0101] 步骤S54：当Xmove>C时，需要把该快照向右移动min(ni)个长度；
[0102] 步骤S55：重复步骤S51‑S54，对周期内每一个快照进行计算；
[0103] 步骤S56：计算满足条件Xmove>C的快照个数nummove，nummove就是需要移动的快照个数；
[0104] 步骤S6：完成快照新建类型的调整；
[0105] 具体的，步骤S6由步骤S2和步骤S4确定是否需要新建快照，判断S4中add值，当add＝true时，新建快照；
[0106] 快照的新建是通过增加快照个数来提高查询性能的，但是增加快照需要更多的存储空间，不能无限制的添加，当快照增加后，历史查询性能可以达到用户的预设值时，才考虑新建快照。
[0107] 方法如下：
[0108] 用户给定阈值D；
[0109] 步骤S61：计算一个快照上完成历史查询所引发的最大操作数max(ni)；
[0110] 步骤S62：计算该快照上完成历史查询所引发的最小操作数min(ni)；
[0111] 步骤S63：计算最大操作数与最小操作数的差值Dadd＝max(ni)‑min(ni)；
[0112] 步骤S64：比较Dadd和D
[0113] 若Dadd
[0114] 步骤S65：计算发生在该快照和其后续相邻快照之间的图更新操作数numops，对介于1和numops之间的任意整数i，计算所引发图操作数大于等于i的历史查询的个数numi；
[0115] 步骤S66：找出使得i*numi取值最大的i值，计为I；
[0116] 步骤S67：以该快照为基础，执行I个图更新操作，将获得的图状态作为新建快照；
[0117] 步骤S68：重复步骤S61‑S67，直到每一个快照计算完毕；
[0118] 统计新建的快照个数numadd。
[0119] 步骤S7：完成快照删除类型的调整；
[0120] 具体的，步骤S7由步骤S2和步骤S4确定是否需要删除快照，判断S4中delete值，当delete＝true时，删除快照；
[0121] 快照的删除是通过减少快照数量来节省存储空间的，当删除快照后，历史查询的性能仍然处于用户的需求范围之内，可以删除此快照。
[0122] 删除快照方法如下：
[0123] 用户给定阈值E、F、G；
[0124] 步骤S71：计算一个快照上发生的查询个数Si(Qi)；
[0125] 步骤S72：计算该快照上完成历史查询所引发的最大操作数max(ni)；
[0126] 步骤S73：由log日志得出该快照到前一个快照之间的操作数On；
[0127] 步骤S74：用该快照的Si(Qi)，max(ni)，On与E，F，G进行比较，若Si(Qi)
[0128] 步骤S75：重复步骤S71‑S74，直到每一个快照计算完毕；
[0129] 统计被删除快照的个数numdel。
[0130] 步骤S8：更新快照调整周期，回到S2；
[0131] 具体的，步骤S8根据步骤S2、S5、S6、S7，计算更新快照调整周期T，计算过程如下：
[0132] 用户定义阈值H、I；
[0133] 步骤S81：由S2中的S(ti)计算出该周期内快照总数ntotal；
[0134] 步骤S82：计算发生变化的快照数Stotal＝nummove+numadd+numdel；
[0135] 步骤S83：比较Stotal和ntotal
[0136] ⑦Stotal
[0137] ⑧Stotal>ntotal*I，则T＝T*1/2；
[0138] ⑨ntotal*H<＝Stotal<＝ntotal*I，则T＝T；
[0139] 步骤S84：得到更新后的快照调整周期T，回到S2。
[0140] 图2为传统固定快照方法与本发明实施例1的面向演化图高效历史查询的自适应快照调整方法对比实例图。图2假定在传统固定快照方式下，每发生50次图更新操作存储一次快照，某时刻图的快照有四个，分别是sp1、sp2、sp3和sp4。某周期内发生了5次历史查询，且每次历史查询所针对的图状态分别对应于第26次更新操作处、第48次更新操作处、第110次更新操作处、第130次更新操作处和第151次更新操作处。完成5次历史查询所基于的快照分别是sp1、sp1、sp3、sp3和sp4，所产生的图操作数分别是26、48、10、30和1，因此，图操作总数是115。
[0141] 在本发明所提供的自适应快照下，会对快照进行调整，其中sp1发生移动，移至第26次更新操作处；sp2会被删除；sp3和sp4保持不动，且sp5被新建，位于第130次更新操作处。完成5次历史查询所基于的快照分别是sp1、sp1、sp3、sp5和sp4，所产生的图操作数分别是0、22、10、0和1，因此，图操作总数是33。与传统方法相比，在快照数量保持不变的情况下，本发明提供的调整方法极大降低了完成历史查询所需要的图操作数，从而提高了历史查询的效率。
[0142] 上所述实施例仅为本发明较佳的具体实施方式，本发明的保护范围不限于此，任何熟悉本领域的技术人员在本发明披露的技术范围内，可显而易见地得到的技术方案的简单变化或等效替换，均属于本发明的保护范围。
