Finding Favourite Tuples on Data Streams with Provably Few Comparisons
Open Access
- 4 August 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 3229-3238
Abstract
One of the most fundamental tasks in data science is to assist a user with unknown preferences in finding high-utility tuples within a large database. To accurately elicit the unknown user preferences, a widely-adopted way is by asking the user to compare pairs of tuples. In this paper, we study the problem of identifying one or more high-utility tuples by adaptively receiving user input on a minimum number of pairwise comparisons. We devise a single-pass streaming algorithm, which processes each tuple in the stream at most once, while ensuring that the memory size and the number of requested comparisons are in the worst case logarithmic in n, where n is the number of all tuples. An important variant of the problem, which can help to reduce human error in comparisons, is to allow users to declare ties when confronted with pairs of tuples of nearly equal utility. We show that the theoretical guarantees of our method can be maintained for this important problem variant. In addition, we show how to enhance existing pruning techniques in the literature by leveraging powerful tools from mathematical programming. Finally, we systematically evaluate all proposed algorithms over both synthetic and real-life datasets, examine their scalability, and demonstrate their superior performance over existing methods.Keywords
All Related Versions
Funding Information
- Research Council of Finland (343045,325117)
- Wallenberg AI, Autonomous Systems and Software Program (WASP)
- EC H2020 RIA (871042)
- ERC Advanced Grant (834862)
This publication has 15 references indexed in Scilit:
- Parallelizing the dual revised simplex methodMathematical Programming Computation, 2017
- Active Classification with Comparison Queries2017
- Learning user preferences by adaptive pairwise comparisonProceedings of the VLDB Endowment, 2015
- Interactive regret minimization2012
- Regret-minimizing representative databasesProceedings of the VLDB Endowment, 2010
- Aggregating inconsistent informationJournal of the ACM, 2008
- The Skyline operator2002
- On saying “Enough already!” in SQL1997
- The quickhull algorithm for convex hullsACM Transactions on Mathematical Software, 1996
- Active Learning Using Arbitrary Binary Valued QueriesMachine Learning, 1993