A unified framework for efficiently processing ranking related queries

Muhammad Aamir Cheema, Zhitao Shen, Xuemin Lin, Wenjie Zhang

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    25 Citations (Scopus)


    The computation of k-lower envelope is a classical problem and has been very well studied for main memory non-indexed data. In this paper, we study the problem from the database perspective and present the first algorithm which utilizes the presence of the index and achieves access optimality, i.e., it accesses a node of the index only if the correctness of the results cannot be guaranteed without accessing this node. We also demonstrate the applications of k-lower envelope in ranking systems. Let an object be called valuable if it is one of the top-k objects according to at least one linear scoring function. In this paper, we answer the following important questions that may be asked by different users: 1) I am not sure what scoring function I should use, therefore, return me the set of valuable objects so that I can select an object I like the most; 2) How can I modify the attributes (e.g., price) of my product such that it becomes a valuable object; 3) What are the preference functions for which a given object is among the top-k objects. These three questions are formalized and called k-snippet, k-depth contour and reverse top-k query, respectively. We propose a unified framework to solve these queries by utilizing k-lower envelope as a common foundation. Our main algorithm is access optimal for k-snippet and k-lower envelope computation. We also demonstrate its access optimality for the k-depth contour problem when k is smaller than the minimum number of objects in any leaf node of the index structure. Our algorithms outperform state-of-the-art algorithms by more than an order of magnitude in terms of both CPU and I/O cost.

    Original languageEnglish
    Title of host publicationAdvances in Database Technology - EDBT 2014: 17th International Conference on Extending Database Technology, Proceedings
    EditorsSihem Amer-Yahia, Vassilis Christophides, Anastasios Kementsietsidis, Minos Garofalakis, Stratos Idreos, Vincent Leroy
    Place of PublicationKonstanz Germany
    Number of pages12
    ISBN (Electronic)9783893180653
    ISBN (Print)9783893180653
    Publication statusPublished - 2014
    EventExtending Database Technology 2014 - Athens, Greece
    Duration: 24 Mar 201428 Mar 2014
    Conference number: 17th
    https://openproceedings.org/html/pages/2014_edbt.html (Proceedings)


    ConferenceExtending Database Technology 2014
    Abbreviated titleEDBT 2014
    OtherEDBT/ICDT 2014 Joint Conference
    March 24-28, 2014 - Athens, Greece

    EDBT: 17th International Conference on Extending Database Technology
    ICDT: 17th International Conference on Database Theory,
    Internet address

    Cite this