Marrying Top-k with SkylineQueries: Operators with Relaxed Preference Input and Controllable Output Size

扫码查看

原文链接

NETL
NSTL
Assoc Computing Machinery

外文摘要：The two paradigms to identify records of preference in a multi-objective setting rely either on dominance(e.g., the skyline operator) or on a utility function defined over the records’ attributes (typically using a top-kquery). Despite their proliferation, each has its own palpable drawbacks. Motivated by these drawbacks, weidentify three hard requirements for practical decision support, namely, personalization, controllable outputsize, and flexibility in preference specification. With these requirements as a guide, we combine elementsfrom both paradigms and propose two new operators, ORD and ORU. We present a suite of algorithms fortheir efficient processing, dedicating more technical effort to ORU, whose nature is inherently more challenging.Specifically, besides a sophisticated algorithm for ORD, we describe two exact methods for ORU andone approximate. We perform a qualitative study to demonstrate how our operators work and evaluate theperformance of our algorithms against adaptations of previous work that mimic their output.

外文关键词：

Top-k queryskylinemulti-dimensional datasets

作者：

KYRIAKOS MOURATIDIS、KEMING LI、BO TANG

展开 >

作者单位：

School of Computing and Information Systems, Singapore ManagementUniversity, Singapore, Singapore

School of Information and Computer Sciences, University of California Irvine, Irvine, UnitedStates

Department of Computer Science and Engineering, Southern University of Science and Technology,Shenzhen, China and Research Institute of Trustworthy Autonomous Systems, Southern Universityof Science and Technology, Shenzhen, China

出版年：

2025

DOI：

10.1145/3705726

ACM Transactions on Database Systems

ISSN：0362-5915

年,卷(期)：2025.50(1)

参考文献量95