File(s) under permanent embargo
Towards both local and global query result diversification
conference contribution
posted on 2019-01-01, 00:00 authored by M Zhong, H Cheng, Y Wang, Y Zhu, T Qian, Jianxin LiJianxin LiQuery result diversification is critical for improving users’ query satisfaction by making the top ranked results cover more different query semantics. The state-of-the-art works address the problem via bi-criteria (namely, relevance and dissimilarity) optimization. However, such works only consider how dissimilar the returned results are to each other, which is referred to “local diversity”. In contrast, some works consider how similar the not returned results are to the returned results, which is referred to “global diversity”, and however need a user defined threshold to predicate whether a result set is diverse. In this paper, we extend the traditional bi-criteria optimization problem to a tri-criteria problem that considers both local diversity and global diversity. For that, we formally define the metrics of global diversity and global-and-local diversity. Then, we prove the NP-hardness of the proposed problems, and propose two heuristic algorithms, greedy search and vertex substitution, and sophisticated optimization techniques to solve the problems efficiently. To evaluate our approach, we perform comprehensive experiments on three real datasets. The results demonstrate that our approach can indeed find more reasonably diversified results. Moreover, our greedy search algorithm can significantly reduce the time cost by leveraging the critical object, and then our vertex substitution algorithm can incrementally improve the objective value of results returned by greedy search with extra time cost.
History
Event
Database Systems for Advanced Applications. Conference (24th : 2019 : Chiang Mai, Thailand)Volume
11447Series
Database Systems for Advanced Applications ConferencePagination
464 - 481Publisher
SpringerLocation
Chiang Mai, ThailandPlace of publication
Cham, SwtizerlandPublisher DOI
Start date
2019-04-22End date
2019-04-25ISSN
0302-9743eISSN
1611-3349ISBN-13
9783030185787Language
engPublication classification
E1 Full written paper - refereedCopyright notice
2019, Springer Nature Switzerland AGEditor/Contributor(s)
G Li, J Yang, J Gama, J Natwichai, Y TongTitle of proceedings
DASFAA 2019 : Proceedings of the 24th International Conference on Database Systems for Advanced Applications 2019Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC