Scalable Top-K structural diversity search

Chang, L; Zhang, C; Lin, X; Qin, L

Scalable Top-K structural diversity search

Chang, L Zhang, C Lin, X Qin, L

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings - International Conference on Data Engineering, 2017, pp. 95 - 98
Issue Date:: 2017-05-16

Closed Access

	Filename	Description	Size
	07929944.pdf	Published version	887.44 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Chang, L	en_US
dc.contributor.author	Zhang, C	en_US
dc.contributor.author	Lin, X	en_US
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062	en_US
dc.date.issued	2017-05-16	en_US
dc.identifier.citation	Proceedings - International Conference on Data Engineering, 2017, pp. 95 - 98	en_US
dc.identifier.isbn	9781509065431	en_US
dc.identifier.issn	1084-4627	en_US
dc.identifier.uri	http://hdl.handle.net/10453/125886
dc.description.abstract	© 2017 IEEE. This paper studies the problem of top-k structural diversity search, which is to compute k users with the highest structural diversities that is measured by the number of connected components in the neighborhood of a user. As the existing algorithms are not scalable for processing large graphs due to their limits, in this paper we propose a scalable algorithm Div-TriE to improve the efficiency. Div-TriE has two optimal features compared with the existing algorithms. Firstly, we show that as a key building block, we only need to enumerate each triangle at most once in Div-TriE, in contrast to the up-To three times in the existing techniques. Secondly, we develop efficient techniques so that the computation against each enumerated triangle is (amortized) constant, in contrast to the non-constant costs in the corresponding costs of the existing techniques. Extensive experimental results on real graphs show that Div-TriE outperforms the existing techniques by one order of magnitude.	en_US
dc.relation.ispartof	Proceedings - International Conference on Data Engineering	en_US
dc.relation.isbasedon	10.1109/ICDE.2017.48	en_US
dc.title	Scalable Top-K structural diversity search	en_US
dc.type	Conference Proceeding
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

© 2017 IEEE. This paper studies the problem of top-k structural diversity search, which is to compute k users with the highest structural diversities that is measured by the number of connected components in the neighborhood of a user. As the existing algorithms are not scalable for processing large graphs due to their limits, in this paper we propose a scalable algorithm Div-TriE to improve the efficiency. Div-TriE has two optimal features compared with the existing algorithms. Firstly, we show that as a key building block, we only need to enumerate each triangle at most once in Div-TriE, in contrast to the up-To three times in the existing techniques. Secondly, we develop efficient techniques so that the computation against each enumerated triangle is (amortized) constant, in contrast to the non-constant costs in the corresponding costs of the existing techniques. Extensive experimental results on real graphs show that Div-TriE outperforms the existing techniques by one order of magnitude.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/125886