Finding Favourite Tuples on Data Streams with Provably Few Comparisons
Authors:
- Guangyi ZhangGZGuangyi Zhang
- Nikolaj TattiNTNikolaj Tatti
- Aristides GionisAGAristides Gionis
Preprint
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
This publication has 6 references indexed in Scilit:
- OSQP: an operator splitting solver for quadratic programsMathematical Programming Computation, 2020
- Parallelizing the dual revised simplex methodMathematical Programming Computation, 2017
- Theory of Disagreement-Based Active LearningFoundations and Trends in Machine Learning, 2014
- Learning to Rank for Information RetrievalFoundations and Trends® in Information Retrieval, 2009
- The quickhull algorithm for convex hullsACM Transactions on Mathematical Software, 1996
- The Average number of pivot steps required by the Simplex-Method is polynomialMathematical Methods of Operations Research, 1982