Before revision:  Our approach offers strong time and space complexity guarantees in the standard RAM model of computation, getting surprisingly close to those of equi-joins. With n denoting the number of tuples in the database, we guarantee  that for every value of k, the k top-ranked answers are returned in \mathcal{O (n polylog n + k  k) time and \mathcal{O n + k) space .
After revision:  Our approach offers strong time and space complexity properties: with n denoting the number of tuples in the database, we guarantee that for every value of k, the k top-ranked answers are returned in \mathcal{O (n polylog n + k k) time and \mathcal{O n + k) space .