Projects per year
Abstract
Selecting a small set of representatives from a large database is important in many applications such as multi-criteria decision making, web search, and recommendation. The k-regret minimizing set (k-RMS) problem was recently proposed for representative tuple discovery. Specifically, for a large database P of tuples with multiple numerical attributes, the k-RMS problem returns a size-r subset Q of P such that, for any possible ranking function, the score of the top-ranked tuple in Q is not much worse than the score of the k th-ranked tuple in P. Although the k-RMS problem has been extensively studied in the literature, existing methods are designed for the static setting and cannot maintain the result efficiently when the database is updated. To address this issue, we propose the first fully-dynamic algorithm for the k-RMS problem that can efficiently provide the up-to-date result w.r.t. any tuple insertion and deletion in the database with a provable guarantee. Experimental results on several real-world and synthetic datasets demonstrate that our algorithm runs up to four orders of magnitude faster than existing k-RMS algorithms while providing results of nearly equal quality.
Original language | English |
---|---|
Title of host publication | 2021 IEEE 37th International Conference on Data Engineering (ICDE) |
Number of pages | 12 |
Publisher | IEEE |
Publication date | 2021 |
Pages | 1631-1642 |
ISBN (Print) | 978-1-7281-9185-0 |
ISBN (Electronic) | 978-1-7281-9184-3 |
DOIs | |
Publication status | Published - 2021 |
MoE publication type | A4 Article in conference proceedings |
Event | IEEE International Conference on Data Engineering - Chania, Greece Duration: 19 Apr 2021 → 23 Apr 2021 Conference number: 37 https://icde2021.gr/ |
Publication series
Name | IEEE International Conference on Data Engineering |
---|---|
Publisher | IEEE COMPUTER SOC |
ISSN (Print) | 1084-4627 |
Fields of Science
- 113 Computer and information sciences
- regret minimizing set
- dynamic algorithm
- set cover
- top-k query
- skyline
- COVER
Projects
- 1 Active
-
MLDB: Model Management Systems: Machine learning meets Database Systems
Gionis, A., Mahadevan, A., Maniatis, A., Merchant, A., Pai, S. G. & Mathioudakis, M.
Suomen Akatemia Projektilaskutus
01/09/2019 → 31/12/2023
Project: Academy of Finland: Academy Project