CAJ | 학술논문

演变图中含有大量的时间和空间信息，其中某些空间信息随着时间的推移表现出相似的演变规律。给出了一种演变图查询模型，可以挖掘出在相同时间范围内具有相同变化规律的演变子图。但是演变图的规模往往是巨大的，当需要对其进行多次查询时，每次遍历整个演变图将带来非常高的查询代价，而现有的基于枚举的哈希索引算法又使得预处理过程拥有相当大的时间和空间开销，为了减少对大规模演变图的预处理代价，将压缩的全文索引技术应用于演变图，它基于涡轮转换和后缀数组。在构建后缀数组时，给出了两种不同的线性算法，确保了预处理过程的稳定性。通过在Facebook、Enron邮件系统以及模拟数据集上的实验，评估了该算法的可行性、效率以及可扩展性。
연변도중함유대량적시간화공간신식，기중모사공간신식수착시간적추이표현출상사적연변규률。급출료일충연변도사순모형，가이알굴출재상동시간범위내구유상동변화규률적연변자도。단시연변도적규모왕왕시거대적，당수요대기진행다차사순시，매차편력정개연변도장대래비상고적사순대개，이현유적기우매거적합희색인산법우사득예처리과정옹유상당대적시간화공간개소，위료감소대대규모연변도적예처리대개，장압축적전문색인기술응용우연변도，타기우와륜전환화후철수조。재구건후철수조시，급출료량충불동적선성산법，학보료예처리과정적은정성。통과재Facebook、Enron유건계통이급모의수거집상적실험，평고료해산법적가행성、효솔이급가확전성。
Evolving graph contains large amount of temporal and spatial information, some of which always perform in similar evolving rules. This paper gives a query model, mining for the evolving subgraphs whose edges changing in the same way at the same time range. However, the size of evolving graphs in real world is huge. Querying on it repeatedly will cost a lot. Even though the existing index method based on Hash has solved query problem, it is also faced in chal-lenge of preprocessing. In order to reduce the price of preprocessing in mass evolving graph, it proposes a compressed full-text indexing technique. It is based on Burrows-Wheeler transform and suffix array. In constructing a suffix array, it also gives two different linear algorithms, ensuring the stability of preprocessing. It evaluates the feasibility, efficiency and scalability of the algorithm on Facebook, Enron email system and simulated datasets.