Distributed Near-Maximum Independent Set Maintenance over Large-scale Dynamic Graphs

Wang, X; Wen, D; Zhang, W; Zhang, Y; Qin, L

Distributed Near-Maximum Independent Set Maintenance over Large-scale Dynamic Graphs

Wang, X Wen, D

Zhang, W Zhang, Y

Qin, L

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: 2023 IEEE 39th International Conference on Data Engineering (ICDE), 2023, 2023-April, pp. 2538-2550
Issue Date:: 2023-07-26

Embargoed

	Filename	Description	Size
	1659099-ManualAPI AM.pdf	Accepted version	524.72 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Embargoed
Open Access

This item is currently unavailable due to the publisher's embargo.

The embargo period expires on 26 Jul 2025

Full metadata record

Field	Value	Language
dc.contributor.author	Wang, X
dc.contributor.author	Wen, D https://orcid.org/0000-0002-0903-1503
dc.contributor.author	Zhang, W
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Qin, L
dc.date	2023-04-03
dc.date.accessioned	2024-03-04T03:44:53Z
dc.date.available	2024-03-04T03:44:53Z
dc.date.issued	2023-07-26
dc.identifier.citation	2023 IEEE 39th International Conference on Data Engineering (ICDE), 2023, 2023-April, pp. 2538-2550
dc.identifier.isbn	979-8-3503-2228-6
dc.identifier.issn	1063-6382
dc.identifier.uri	http://hdl.handle.net/10453/176058
dc.description.abstract	Computing the maximum independent set MIS in a graph is a fundamental NP hard problem which is widely adopted in many real world applications Extensive works have been done on computing an approximate MIS While the highly dynamic property of real world graphs calls for efficient MIS maintenance solutions existing works for dynamic MIS computation in the literature mainly focus on the single machine scenario The assumption that a single machine can access the whole graph makes them difficult to be straightforwardly applied for large scale graphs in distributed environment Motivated by this in this paper we study the problem of maintaining approximate MIS over large scale dynamic graphs in distributed environments We propose a new vertex centric algorithm OIMIS Compared with existing solutions OIMIS avoids the strong order dependency in distributed computation which makes it easy to handle dynamic graph updates OIMIS computes and maintains MIS with high effectiveness and efficiency In terms of high effectiveness OIMIS maintains consistent MIS results with the state of the art distributed algorithm to compute MIS in static graphs In terms of high efficiency each vertex in OIMIS only updates MIS status according to its neighbor attributes Novel optimization techniques are also designed to reduce communication and computation cost We conduct extensive experiments to prove the effectiveness and efficiency of our distributed algorithms
dc.language	en
dc.publisher	IEEE
dc.relation	http://purl.org/au-research/grants/arc/FT200100787
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation	http://purl.org/au-research/grants/arc/DP210101347
dc.relation	http://purl.org/au-research/grants/arc/DP230101445
dc.relation	http://purl.org/au-research/grants/arc/LP210301046
dc.relation	http://purl.org/au-research/grants/arc/DP240101322
dc.relation.ispartof	2023 IEEE 39th International Conference on Data Engineering (ICDE)
dc.relation.ispartof	2023 IEEE 39th International Conference on Data Engineering
dc.relation.isbasedon	10.1109/icde55515.2023.00195
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.title	Distributed Near-Maximum Independent Set Maintenance over Large-scale Dynamic Graphs
dc.type	Conference Proceeding
utslib.citation.volume	2023-April
utslib.location.activity	Anaheim, CA, USA
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 - AAII - Australian Artificial Intelligence Institute
utslib.copyright.status	embargoed	*
utslib.copyright.embargo	2025-07-26T00:00:00+1000Z
dc.date.updated	2024-03-04T03:44:51Z
pubs.finish-date	2023-04-07
pubs.place-of-publication	Piscataway, USA
pubs.publication-status	Published
pubs.start-date	2023-04-03
pubs.volume	2023-April
dc.location	Piscataway, USA

Abstract:

Computing the maximum independent set MIS in a graph is a fundamental NP hard problem which is widely adopted in many real world applications Extensive works have been done on computing an approximate MIS While the highly dynamic property of real world graphs calls for efficient MIS maintenance solutions existing works for dynamic MIS computation in the literature mainly focus on the single machine scenario The assumption that a single machine can access the whole graph makes them difficult to be straightforwardly applied for large scale graphs in distributed environment Motivated by this in this paper we study the problem of maintaining approximate MIS over large scale dynamic graphs in distributed environments We propose a new vertex centric algorithm OIMIS Compared with existing solutions OIMIS avoids the strong order dependency in distributed computation which makes it easy to handle dynamic graph updates OIMIS computes and maintains MIS with high effectiveness and efficiency In terms of high effectiveness OIMIS maintains consistent MIS results with the state of the art distributed algorithm to compute MIS in static graphs In terms of high efficiency each vertex in OIMIS only updates MIS status according to its neighbor attributes Novel optimization techniques are also designed to reduce communication and computation cost We conduct extensive experiments to prove the effectiveness and efficiency of our distributed algorithms

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

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