Concept and Computation of Ranking-based Dominance. (September 2019)

• Record Type: Journal Article
• Authors: Panev, Kiril; Michel, Sebastian
• Is Part Of: Information systems. Volume 84(2019)
• Page Start: 174
• Page End: 188
• Publication Date: 2019-09
• Subjects: Dominance -- Rankings -- Data exploration; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2019.05.004
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: We presentCOMPETE, a novel approach that models and computes dominance over user-provided input entities, given a database of top-k rankings. The resulting entities are found superior or inferior with tunable degree of dominance over the input set—a very intuitive, yet insightful way to explore pros and cons of entities of interest. Several notions of dominance are defined which differ in computational complexity and strictness of the dominance concept—yet, interdependent through containment relations.COMPETE is able to pick the most promising approach to satisfy a user request at minimal runtime latency, using a probabilistic model that is estimating the result sizes. The individual flavors of dominance are cast into a stack of algorithms over inverted indices and auxiliary structures. The extensive experimental evaluation over real-world and synthetically generated data and workloads demonstrates the diversity of the problem in terms of number of valid results and need for result ordering and, in particular, emphasizes the immense effect of the pruning strategies with performance gains up to an order of magnitude over baseline approaches. Highlights: Intuitive way to explore and understand pros and cons of favorite entities. User-friendly query formulation and comprehensible result interpretation. Different flavors of dominance, from strict to relaxed, at different computing cost. Automated selection of feasible algorithm using probabilistic result size estimation.