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

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Citations (Scopus)

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.

Original language	English
Title of host publication	Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings
Editors	Guojun Wang, Zheng Yan, Kim-Kwang Raymond Choo, Mohammed Atiquzzaman
Publisher	Springer Verlag
Pages	719-729
Number of pages	11
ISBN (Print)	9783319723945
DOIs	https://doi.org/10.1007/978-3-319-72395-2_64
Publication status	Published - 2017
Externally published	Yes
Event	10th International Conference on Security, Privacy and Anonymity in Computation, Communication and Storage, SpaCCS 2017 - Guangzhou, China Duration: 12 Dec 2017 → 15 Dec 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10658 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Conference on Security, Privacy and Anonymity in Computation, Communication and Storage, SpaCCS 2017
Country/Territory	China
City	Guangzhou
Period	12/12/17 → 15/12/17

Keywords

Cohesive subgraphs
Triangle counting
Truss decomposition

Access to Document

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

Cite this

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

Xing, Yuxuan ; Xiao, Nong ; Lu, Yutong et al. / Fast truss decomposition in memory. Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings. editor / Guojun Wang ; Zheng Yan ; Kim-Kwang Raymond Choo ; Mohammed Atiquzzaman. Springer Verlag, 2017. pp. 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. in G Wang, Z Yan, K-KR Choo & M Atiquzzaman (eds), 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), vol. 10658 LNCS, Springer Verlag, pp. 719-729, 10th International Conference on Security, Privacy and Anonymity in Computation, Communication and Storage, SpaCCS 2017, Guangzhou, China, 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 et al.
Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings. ed. / Guojun Wang; Zheng Yan; Kim-Kwang Raymond Choo; Mohammed Atiquzzaman. Springer Verlag, 2017. p. 719-729 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10658 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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. In Wang G, Yan Z, Choo KKR, Atiquzzaman M, editors, Security, Privacy, and Anonymity in Computation, Communication, and Storage - SpaCCS 2017 International Workshops, Proceedings. Springer Verlag. 2017. p. 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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this