Efficient processing of k-regret minimization queries with theoretical guarantees

Zheng, J; Dong, Q; Wang, X; Zhang, Y; Ma, W; Ma, Y

Efficient processing of k-regret minimization queries with theoretical guarantees

Zheng, J Dong, Q Wang, X Zhang, Y

Ma, W Ma, Y

Permalink

Publisher:: Elsevier
Publication Type:: Journal Article
Citation:: Information Sciences, 2022, 586, pp. 99-118
Issue Date:: 2022-03-01

Closed Access

	Filename	Description	Size
	1-s2.0-S0020025521012020-main.pdf	Published version	1.28 MB	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	Zheng, J
dc.contributor.author	Dong, Q
dc.contributor.author	Wang, X
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Ma, W
dc.contributor.author	Ma, Y
dc.date.accessioned	2023-06-30T21:41:02Z
dc.date.available	2023-06-30T21:41:02Z
dc.date.issued	2022-03-01
dc.identifier.citation	Information Sciences, 2022, 586, pp. 99-118
dc.identifier.issn	0020-0255
dc.identifier.uri	http://hdl.handle.net/10453/171057
dc.description.abstract	Assisting end users to identify desired results from a large dataset is an important problem for multi-criteria decision making. To address this problem, top-k and skyline queries have been widely adopted, but they both have inherent drawbacks, i.e., the user either has to provide a specific utility function or faces many results. The k-regret minimization query is proposed, which integrates the merits of top-k and skyline queries. Due to the NP-hardness of the problem, the k-regret minimization query is time consuming and the greedy framework is widely adopted. However, formal theoretical analysis of the greedy approaches for the quality of the returned results is still lacking. In this paper, we first fill this gap by conducting a nontrivial theoretical analysis of the approximation ratio of the returned results. To speed up query processing, a sampling-based method, STOCPRESGREED, is developed to reduce the evaluation cost. In addition, a theoretical analysis of the required sample size is conducted to bound the quality of the returned results. Finally, comprehensive experiments are conducted on both real and synthetic datasets to demonstrate the efficiency and effectiveness of the proposed methods.
dc.language	en
dc.publisher	Elsevier
dc.relation.ispartof	Information Sciences
dc.relation.isbasedon	10.1016/j.ins.2021.11.080
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	01 Mathematical Sciences, 08 Information and Computing Sciences, 09 Engineering
dc.subject.classification	Artificial Intelligence & Image Processing
dc.title	Efficient processing of k-regret minimization queries with theoretical guarantees
dc.type	Journal Article
utslib.citation.volume	586
utslib.for	01 Mathematical Sciences
utslib.for	08 Information and Computing Sciences
utslib.for	09 Engineering
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	closed_access	*
dc.date.updated	2023-06-30T21:41:01Z
pubs.publication-status	Published
pubs.volume	586

Abstract:

Assisting end users to identify desired results from a large dataset is an important problem for multi-criteria decision making. To address this problem, top-k and skyline queries have been widely adopted, but they both have inherent drawbacks, i.e., the user either has to provide a specific utility function or faces many results. The k-regret minimization query is proposed, which integrates the merits of top-k and skyline queries. Due to the NP-hardness of the problem, the k-regret minimization query is time consuming and the greedy framework is widely adopted. However, formal theoretical analysis of the greedy approaches for the quality of the returned results is still lacking. In this paper, we first fill this gap by conducting a nontrivial theoretical analysis of the approximation ratio of the returned results. To speed up query processing, a sampling-based method, STOCPRESGREED, is developed to reduce the evaluation cost. In addition, a theoretical analysis of the required sample size is conducted to bound the quality of the returned results. Finally, comprehensive experiments are conducted on both real and synthetic datasets to demonstrate the efficiency and effectiveness of the proposed methods.

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

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