Skyline nearest neighbor search on multi-layer graphs

Liu, W; Wen, D; Wang, H; Zhang, F; Wang, X

Skyline nearest neighbor search on multi-layer graphs

Liu, W

Wen, D Wang, H Zhang, F Wang, X

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: Proceedings - 2019 IEEE 35th International Conference on Data Engineering Workshops, ICDEW 2019, 2019, pp. 259-265
Issue Date:: 2019-04-01

Closed Access

	Filename	Description	Size
	08750910.pdf	Published version	217.08 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	Liu, W https://orcid.org/0000-0002-8529-855X
dc.contributor.author	Wen, D
dc.contributor.author	Wang, H
dc.contributor.author	Zhang, F
dc.contributor.author	Wang, X
dc.date	2019-04-08
dc.date.accessioned	2020-06-13T06:39:36Z
dc.date.available	2020-06-13T06:39:36Z
dc.date.issued	2019-04-01
dc.identifier.citation	Proceedings - 2019 IEEE 35th International Conference on Data Engineering Workshops, ICDEW 2019, 2019, pp. 259-265
dc.identifier.isbn	9781728108902
dc.identifier.issn	1943-2895
dc.identifier.issn	2473-3490
dc.identifier.uri	http://hdl.handle.net/10453/141406
dc.description.abstract	© 2019 IEEE. Nearest neighbor search is a fundamental problem in graph theory. In real-world applications, the multi-layer graph model is extensively studied to reveal the multi-dimensional relations between the graph entities. In this paper, we formulate a new problem named skyline nearest neighbor search on multi-layer graphs. Given a query vertex u, we aim to compute a set of skyline vertices that are not dominated by other vertices in terms of the shortest distance on all graph layers. We propose an early-termination algorithm instead of naively adopting the traditional skyline procedure as a subroutine. We also investigate the rule to optimize search order in the algorithm and further improve the algorithmic efficiency. The experimental results demonstrate that the optimization strategies work well on different graphs and can speed up the algorithm significantly.
dc.language	en
dc.publisher	IEEE
dc.relation.ispartof	Proceedings - 2019 IEEE 35th International Conference on Data Engineering Workshops, ICDEW 2019
dc.relation.ispartof	International Conference on Data Engineering Workshops
dc.relation.isbasedon	10.1109/ICDEW.2019.000-3
dc.rights	© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.	en_US
dc.rights	info:eu-repo/semantics/restrictedAccess
dc.title	Skyline nearest neighbor search on multi-layer graphs
dc.type	Conference Proceeding
utslib.location.activity	Macao, Macao
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney
utslib.copyright.status	closed_access	*
pubs.consider-herdc	false
dc.date.updated	2020-06-13T06:39:32Z
pubs.finish-date	2019-04-12
pubs.place-of-publication	Piscataway, USA
pubs.publication-status	Published
pubs.start-date	2019-04-08
dc.location	Piscataway, USA

Abstract:

© 2019 IEEE. Nearest neighbor search is a fundamental problem in graph theory. In real-world applications, the multi-layer graph model is extensively studied to reveal the multi-dimensional relations between the graph entities. In this paper, we formulate a new problem named skyline nearest neighbor search on multi-layer graphs. Given a query vertex u, we aim to compute a set of skyline vertices that are not dominated by other vertices in terms of the shortest distance on all graph layers. We propose an early-termination algorithm instead of naively adopting the traditional skyline procedure as a subroutine. We also investigate the rule to optimize search order in the algorithm and further improve the algorithmic efficiency. The experimental results demonstrate that the optimization strategies work well on different graphs and can speed up the algorithm significantly.

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

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