Top-k querying of unknown values under order constraints

DOI10.4230/LIPICS.ICDT.2017.5zbMATH Open1402.68038arXiv1701.02634OpenAlexW2570568077MaRDI QIDQ3174893FDOQ3174893

Authors: Antoine Amarilli, Yael Amsterdamer, Tova Milo, Pierre Senellart 

Publication date: 18 July 2018

Abstract: Many practical scenarios make it necessary to evaluate top-k queries over data items with partially unknown values. This paper considers a setting where the values are taken from a numerical domain, and where some partial order constraints are given over known and unknown values: under these constraints, we assume that all possible worlds are equally likely. Our work is the first to propose a principled scheme to derive the value distributions and expected values of unknown items in this setting, with the goal of computing estimated top-k results by interpolating the unknown values from the known ones. We study the complexity of this general task, and show tight complexity bounds, proving that the problem is intractable, but can be tractably approximated. We then consider the case of tree-shaped partial orders, where we show a constructive PTIME solution. We also compare our problem setting to other top-k definitions on uncertain data.

Full work available at URL: https://arxiv.org/abs/1701.02634

Recommendations

• On the semantics of top-\(k\) ranking for objects with uncertain data
• Supporting various top-\(k\) queries over uncertain datasets
• Probabilistic top-\(k\) and ranking query algorithms in uncertain databases
• Probabilistic top-\(k\) range query processing for uncertain databases
• \(P\)-top-\(k\) queries in a probabilistic framework from information extraction models

zbMATH Keywords

interpolationuncertaintypartial ordercrowdsourcingunknown values

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Cited In (4)

• Possible and certain answers for queries over order-incomplete data
• $$Top$$ - $$K$$ Query Retrieval of Combinations with Sum-of-Subsets Ranking
• Computing possible and certain answers over order-incomplete data
• On the semantics of top-\(k\) ranking for objects with uncertain data

This page was built for publication: Top-\(k\) querying of unknown values under order constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174893)