Fast truss decomposition in memory

Yuxuan Xing; Nong Xiao; Yutong Lu; Ronghua Li; Songping Yu; Siqi Gao

doi:10.1007/978-3-319-72395-2_64

Fast truss decomposition in memory

Yuxuan Xing^*, Nong Xiao, Yutong Lu, Ronghua Li, Songping Yu, Siqi Gao

^*此作品的通讯作者

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

5 引用（Scopus）

摘要

The k-truss is a type of cohesive subgraphs proposed for the analysis of massive network. Existing in-memory algorithms for computing k-truss are inefficient for searching and parallel. We propose a novel traversal algorithm for truss decomposition: it effectively reduces computation complexity, we fully exploit the parallelism thanks to the optimization, and overlap IO and computation for a better performance. Our experiments on real datasets verify that it is 2x–5x faster than the exiting fastest in-memory algorithm.

源语言	英语
主期刊名	Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings
编辑	Guojun Wang, Zheng Yan, Kim-Kwang Raymond Choo, Mohammed Atiquzzaman
出版商	Springer Verlag
页	719-729
页数	11
ISBN（印刷版）	9783319723945
DOI	https://doi.org/10.1007/978-3-319-72395-2_64
出版状态	已出版 - 2017
已对外发布	是
活动	10th International Conference on Security, Privacy and Anonymity in Computation, Communication and Storage, SpaCCS 2017 - Guangzhou, 中国期限: 12 12月 2017 → 15 12月 2017

出版系列

姓名	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
卷	10658 LNCS
ISSN（印刷版）	0302-9743
ISSN（电子版）	1611-3349

会议

会议	10th International Conference on Security, Privacy and Anonymity in Computation, Communication and Storage, SpaCCS 2017
国家/地区	中国
市	Guangzhou
时期	12/12/17 → 15/12/17

访问文件

10.1007/978-3-319-72395-2_64

其它文件与链接

链接到 Scopus 的出版物

引用此

Xing, Y., Xiao, N., Lu, Y., Li, R., Yu, S., & Gao, S. (2017). Fast truss decomposition in memory. 在 G. Wang, Z. Yan, K.-K. R. Choo, & M. Atiquzzaman (编辑), Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings (页码 719-729). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 卷 10658 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-72395-2_64

Xing, Yuxuan ; Xiao, Nong ; Lu, Yutong 等. / Fast truss decomposition in memory. Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings. 编辑 / Guojun Wang ; Zheng Yan ; Kim-Kwang Raymond Choo ; Mohammed Atiquzzaman. Springer Verlag, 2017. 页码 719-729 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1fa94e1c8b854493bf3c981ad2ccc6a6,

title = "Fast truss decomposition in memory",

abstract = "The k-truss is a type of cohesive subgraphs proposed for the analysis of massive network. Existing in-memory algorithms for computing k-truss are inefficient for searching and parallel. We propose a novel traversal algorithm for truss decomposition: it effectively reduces computation complexity, we fully exploit the parallelism thanks to the optimization, and overlap IO and computation for a better performance. Our experiments on real datasets verify that it is 2x–5x faster than the exiting fastest in-memory algorithm.",

keywords = "Cohesive subgraphs, Triangle counting, Truss decomposition",

author = "Yuxuan Xing and Nong Xiao and Yutong Lu and Ronghua Li and Songping Yu and Siqi Gao",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 10th International Conference on Security, Privacy and Anonymity in Computation, Communication and Storage, SpaCCS 2017 ; Conference date: 12-12-2017 Through 15-12-2017",

year = "2017",

doi = "10.1007/978-3-319-72395-2_64",

language = "English",

isbn = "9783319723945",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "719--729",

editor = "Guojun Wang and Zheng Yan and Choo, {Kim-Kwang Raymond} and Mohammed Atiquzzaman",

booktitle = "Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings",

address = "Germany",

}

Xing, Y, Xiao, N, Lu, Y, Li, R, Yu, S & Gao, S 2017, Fast truss decomposition in memory. 在 G Wang, Z Yan, K-KR Choo & M Atiquzzaman (编辑), Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 卷 10658 LNCS, Springer Verlag, 页码 719-729, 10th International Conference on Security, Privacy and Anonymity in Computation, Communication and Storage, SpaCCS 2017, Guangzhou, 中国, 12/12/17. https://doi.org/10.1007/978-3-319-72395-2_64

Fast truss decomposition in memory. / Xing, Yuxuan; Xiao, Nong; Lu, Yutong 等.
Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings. 编辑 / Guojun Wang; Zheng Yan; Kim-Kwang Raymond Choo; Mohammed Atiquzzaman. Springer Verlag, 2017. 页码 719-729 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 卷 10658 LNCS).

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

TY - GEN

T1 - Fast truss decomposition in memory

AU - Xing, Yuxuan

AU - Xiao, Nong

AU - Lu, Yutong

AU - Li, Ronghua

AU - Yu, Songping

AU - Gao, Siqi

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - The k-truss is a type of cohesive subgraphs proposed for the analysis of massive network. Existing in-memory algorithms for computing k-truss are inefficient for searching and parallel. We propose a novel traversal algorithm for truss decomposition: it effectively reduces computation complexity, we fully exploit the parallelism thanks to the optimization, and overlap IO and computation for a better performance. Our experiments on real datasets verify that it is 2x–5x faster than the exiting fastest in-memory algorithm.

AB - The k-truss is a type of cohesive subgraphs proposed for the analysis of massive network. Existing in-memory algorithms for computing k-truss are inefficient for searching and parallel. We propose a novel traversal algorithm for truss decomposition: it effectively reduces computation complexity, we fully exploit the parallelism thanks to the optimization, and overlap IO and computation for a better performance. Our experiments on real datasets verify that it is 2x–5x faster than the exiting fastest in-memory algorithm.

KW - Cohesive subgraphs

KW - Triangle counting

KW - Truss decomposition

UR - http://www.scopus.com/inward/record.url?scp=85040130977&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-72395-2_64

DO - 10.1007/978-3-319-72395-2_64

M3 - Conference contribution

AN - SCOPUS:85040130977

SN - 9783319723945

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 719

EP - 729

BT - Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings

A2 - Wang, Guojun

A2 - Yan, Zheng

A2 - Choo, Kim-Kwang Raymond

A2 - Atiquzzaman, Mohammed

PB - Springer Verlag

T2 - 10th International Conference on Security, Privacy and Anonymity in Computation, Communication and Storage, SpaCCS 2017

Y2 - 12 December 2017 through 15 December 2017

ER -

Xing Y, Xiao N, Lu Y, Li R, Yu S, Gao S. Fast truss decomposition in memory. 在 Wang G, Yan Z, Choo KKR, Atiquzzaman M, 编辑, Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings. Springer Verlag. 2017. 页码 719-729. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-72395-2_64

Fast truss decomposition in memory

摘要

出版系列

会议

访问文件

其它文件与链接

指纹

引用此