CAJ | 학술논문

直径作为图的一个重要属性,旨在提出一种在数据流环境下计算不同大小的滑动窗口直径的算法机制.基本思想是:在一维上采取较容易实现的精确算法,主要体现在只保存现在组成了直径和未来可能成为直径的元素;高维时通过投影到低维的方法计算出滑动窗口直径的近似值,并且可以通过投影的个数控制近似解的精度.最后通过对实验数据的分析和解释得到了若干有益的结论,为进一步的研究工作奠定了基础.
직경작위도적일개중요속성,지재제출일충재수거류배경하계산불동대소적활동창구직경적산법궤제.기본사상시:재일유상채취교용역실현적정학산법,주요체현재지보존현재조성료직경화미래가능성위직경적원소;고유시통과투영도저유적방법계산출활동창구직경적근사치,병차가이통과투영적개수공제근사해적정도.최후통과대실험수거적분석화해석득도료약간유익적결론,위진일보적연구공작전정료기출.
Diameter is a very important aggregate of graph.In the paper,a novel mechanism is proposed to compute over sliding windows with various sizes in the data stream environment.A simple exact algorithm is presented for computing the diameter in the streaming model.It maintains the diameter in one dimension and is easy to extend to multi-dimension.Experimental results show that the algorithm yields very good performance on both space and time cost.