科研之友
微信
新浪微博
Facebook
分享链接
摘要
图相似性搜索是在给定的度量标准下查找与查询图相似的图集合，目前大多采用“过滤-验证”的计算框架。针对现有方法中过滤下界不紧密和索引空间占用较大等问题，提出了一种基于查询图分区的多层级过滤、低索引空间占用的图相似性搜索算法Z-Index。该算法首先通过全局粗粒度过滤得到预候选集；然后提出基于扩展概率的查询图分区算法，并采用层级过滤机制进一步精简候选集，增强下界紧密性；最后引入序列相似性差值计算序列中数据分布的稀疏度，提出分区压缩和差值压缩两种编码压缩算法，并据此构建“零”索引结构，降低索引空间开销。实验结果表明，Z-Index算法所得下界更加紧密，产生的候选集大小可减少50%左右，算法执行时间大大缩短，且该算法在索引空间占用极小的情况下仍具有可扩展性。
- 单位
