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

    Abstract

    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
    Pages553-564
    Number of pages12
    DOIs
    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

    Other

    Other21st Annual European Symposium on Algorithms, ESA 2013
    CountryFrance
    CitySophia Antipolis
    Period9/2/139/4/13

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

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

    Cite this