A Comparison of Top-k Threshold Estimation Techniques for Disjunctive Query Processing

Antonio Mallia, Michal Siedlaczek, Mengyang Sun, Torsten Suel

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    In the top-k threshold estimation problem, given a query q, the goal is to estimate the score of the result at rank k. A good estimate of this score can result in significant performance improvements for several query processing scenarios, including selective search, index tiering, and widely used disjunctive query processing algorithms such as MaxScore, WAND, and BMW. Several approaches have been proposed, including parametric approaches, methods using random sampling, and a recent approach based on machine learning. However, previous work fails to perform any experimental comparison between these approaches. In this paper, we address this issue by reimplementing four major approaches and comparing them in terms of estimation error, running time, likelihood of an overestimate, and end-to-end performance when applied to common classes of disjunctive top-k query processing algorithms.

    Original languageEnglish (US)
    Title of host publicationCIKM 2020 - Proceedings of the 29th ACM International Conference on Information and Knowledge Management
    PublisherAssociation for Computing Machinery
    Pages2141-2144
    Number of pages4
    ISBN (Electronic)9781450368599
    DOIs
    StatePublished - Oct 19 2020
    Event29th ACM International Conference on Information and Knowledge Management, CIKM 2020 - Virtual, Online, Ireland
    Duration: Oct 19 2020Oct 23 2020

    Publication series

    NameInternational Conference on Information and Knowledge Management, Proceedings

    Conference

    Conference29th ACM International Conference on Information and Knowledge Management, CIKM 2020
    CountryIreland
    CityVirtual, Online
    Period10/19/2010/23/20

    Keywords

    • query processing
    • threshold estimation
    • top-k document retrieval

    ASJC Scopus subject areas

    • Business, Management and Accounting(all)
    • Decision Sciences(all)

    Fingerprint Dive into the research topics of 'A Comparison of Top-k Threshold Estimation Techniques for Disjunctive Query Processing'. Together they form a unique fingerprint.

    Cite this