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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\text {top-}k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>top-</mtext> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\text {top-}k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>top-</mtext> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation> (<InlineEquation ID="IEq3"> <EquationSource Format="TEX">$CT$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="italic">CT</mi> </mrow> </math></EquationSource> </InlineEquation>) query. Given an approximate description of the weight values, <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$CT$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="italic">CT</mi> </mrow> </math></EquationSource> </InlineEquation> reports all options that may belong to the <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\text {top-}k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>top-</mtext> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation> set. Our <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$CT$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="italic">CT</mi> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$CT$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="italic">CT</mi> </mrow> </math></EquationSource> </InlineEquation> for top-record sets (i.e., <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$k=1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>), termed <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$CT^1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>C</mi> <msup> <mi>T</mi> <mn>1</mn> </msup> </mrow> </math></EquationSource> </InlineEquation>, and devise a specialized method for it. Our <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$CT^1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>C</mi> <msup> <mi>T</mi> <mn>1</mn> </msup> </mrow> </math></EquationSource> </InlineEquation> 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).

A framework for top-k queries with constrained preferences

期刊论文
发表日期：

2026年5月19日

查看全文

Kyriakos Mouratidis,
Nikolaos Chaloulakos,
Bo Tang

摘要

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 $\text {top-}k$ $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 $\text {top-}k$ $top- k$ ( $CT$ $CT$ ) query. Given an approximate description of the weight values, $CT$ $CT$ reports all options that may belong to the $\text {top-}k$ $top- k$ set. Our $CT$ $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$ $CT$ for top-record sets (i.e., $k=1$ $k = 1$ ), termed $CT^1$ $C T^{1}$ , and devise a specialized method for it. Our $CT^1$ $C T^{1}$ 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).