Encodings for range selection and top-k queries

Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, Satti Srinivasa Rao

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


    We study the problem of encoding the positions the top-k elements of an array A[1..n] for a given parameter 1 ≤ k ≤ n. Specifically, for any i and j, we wish create a data structure that reports the positions of the largest k elements in A[i..j] in decreasing order, without accessing A at query time. This is a natural extension of the well-known encoding range-maxima query problem, where only the position of the maximum in A[i..j] is sought, and finds applications in document retrieval and ranking. We give (sometimes tight) upper and lower bounds for this problem and some variants thereof.

    Original languageEnglish (US)
    Title of host publicationAlgorithms, ESA 2013 - 21st Annual European Symposium, Proceedings
    Number of pages12
    StatePublished - 2013
    Event21st Annual European Symposium on Algorithms, ESA 2013 - Sophia Antipolis, France
    Duration: Sep 2 2013Sep 4 2013

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume8125 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other21st Annual European Symposium on Algorithms, ESA 2013
    CitySophia Antipolis

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Encodings for range selection and top-k queries'. Together they form a unique fingerprint.

    Cite this