Publication Type

Journal Article

Version

acceptedVersion

Publication Date

7-2026

Abstract

Traditional rank-aware processing assumes a dataset that contains available options to cover a specific need (e.g., restaurants, hotels, etc) and users who browse that dataset via top-k queries with linear scoring functions, i.e., by ranking the options according to the weighted sum of their attributes, for a set of given weights. In practice, however, user preferences (weights) may only be estimated with bounded accuracy, or may be inherently imprecise due to the inability of a human user to specify exact weight values with absolute accuracy. Motivated by this, we define the constrained-preference top-k (CT) query. Given an approximate description of the weight values, CT reports all options that may belong to the top-k set. Our CT algorithm assumes that the dataset is indexed with a general-purpose index (e.g., an R-tree) and delivers efficient processing, be it when data and index are in memory, or on the disk. Furthermore, we delve deeper into the special and highly practical case of CT for top-record sets (i.e., k = 1), termed CT1 , and devise a specialized method for it. Our CT1 algorithm offers node-access optimality, i.e., a guarantee to access the minimum number of index nodes. This translates to optimal I/O cost (in the disk-based scenario) and to significant computation savings (which is relevant in both the disk-based and the memory-based scenarios).

Keywords

Top-k query, Skyline, Multi-dimensional datasets

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

VLDB Journal

Volume

35

Issue

27

First Page

1

Last Page

23

ISSN

1066-8888

Identifier

10.1007/s00778-026-00972-w

Publisher

Springer

Additional URL

https://doi.org/10.1007/s00778-026-00972-w

Download

Share

COinS