A framework for top-k queries with constrained preferences
The VLDB Journal · 2026-07 · 35 (4)
DOI: 10.1007/s00778-026-00972-w ↗Kurz gefasst
Fachartikel in der Zeitschrift The VLDB Journal, online erschienen am 19.05.2026. Verfasst von Kyriakos Mouratidis und 2 weiteren Autor:innen. Die Arbeit nennt 52 Literaturangaben. Gefördert von: Ministry of Education - Singapore.
Abstract (Originalsprache)
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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {top-}k$$\end{document} 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-preferencetop-k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {top-}k$$\end{document} (CT\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$CT$$\end{document}) query. Given an approximate description of the weight values, CT\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$CT$$\end{document} reports all options that may belong to the top-k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {top-}k$$\end{document} set. Our CT\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$CT$$\end{document} 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$CT$$\end{document} for top-record sets (i.e., k=1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=1$$\end{document}), termed CT1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$CT^1$$\end{document}, and devise a specialized method for it. Our CT1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$CT^1$$\end{document} 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).
Förderung
- Ministry of Education - Singapore
Zitieren
APA
Mouratidis, K., Chaloulakos, N., & Tang, B. (2026). A framework for top-k queries with constrained preferences. The VLDB Journal, 35(4). https://doi.org/10.1007/s00778-026-00972-w
Vancouver
Mouratidis K, Chaloulakos N, Tang B. A framework for top-k queries with constrained preferences. The VLDB Journal. 2026;35(4). doi:10.1007/s00778-026-00972-w
BibTeX
@article{Mouratidis2026,
author = {Mouratidis, Kyriakos and Chaloulakos, Nikolaos and Tang, Bo},
title = {A framework for top-k queries with constrained preferences},
journal = {The VLDB Journal},
year = {2026},
volume = {35},
number = {4},
doi = {10.1007/s00778-026-00972-w}
}
EUVIMED