计算机工程与应用Issue(2)：117-124,8.DOI:10.3778/j.issn.1002-8331.1308-0190
基于压缩全文索引的演变图查询
Querying on evolving graphs based on compressed full-text index
摘要
Abstract
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.关键词
演变图/查询/演变子图/后缀数组/压缩全文索引Key words
evolving graph/query/evolving subgraph/suffix array/compressed full-text index分类
信息技术与安全科学引用本文复制引用
肖洋,朱青,吴粤皖..基于压缩全文索引的演变图查询[J].计算机工程与应用,2015,(2):117-124,8.基金项目
国家自然科学基金（No.61070053）。 （）
