Durable Top-K Instant-Stamped Temporal Records with User-Specified Scoring Functions
Durable Top-K Instant-Stamped Temporal Records with User-Specified Scoring Functions
复制标题
DOI：
10.1109/icde51399.2021.00068
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Junyang Gao;Stavros Sintos;P. Agarwal;Jun Yang
中科院分区：
文献类型：
--
作者：
Junyang Gao;Stavros Sintos;P. Agarwal;Jun Yang
从即时标记的时态数据中找到有趣或特殊记录的一种方法是考虑它们的“持久性”，或者，直观地说，它们与其他更早或更晚到达的记录相比有多好，以及它们保持霸主地位的时间有多长。例如，人们自然而然地对经久不衰的说法着迷，比如：2006年1月22日，科比在对阵多伦多猛龙的比赛中丢了81分，自那以后，这一得分记录一直没有被打破。一般来说，给定一系列即时标记的记录，假设我们可以通过用户指定的评分函数f对它们进行排序，该函数可以考虑一条记录的多个属性来计算用于排序的单个分数。本文研究了持久top-k查询，即在给定长度的“持久性窗口”内，例如从记录的时间戳开始/结束的10年窗口内，在这些记录中找到得分在top-k内的记录。参数k、耐久性窗口的长度、以及计分函数(捕捉用户偏好)的参数都可以在查询时给出。我们解释了为什么在某些实际情况下，这种问题形式比以前考虑的其他类似类型的查询产生更有意义的答案。我们提出了新的算法来解决这个问题，并对问题本身和算法的复杂性进行了全面的理论分析。我们的算法远远超过各种基线(在真实和合成数据集上高达两个数量级)。
A way of finding interesting or exceptional records from instant-stamped temporal data is to consider their "durability, " or, intuitively speaking, how well they compare with other records that arrived earlier or later, and how long they retain their supremacy. For example, people are naturally fascinated by claims with long durability, such as: "On January 22, 2006, Kobe Bryant dropped 81 points against Toronto Raptors. Since then, this scoring record has yet to be broken." In general, given a sequence of instant-stamped records, suppose that we can rank them by a user-specified scoring function f, which may consider multiple attributes of a record to compute a single score for ranking. This paper studies durable top-k queries, which find records whose scores were within top-k among those records within a "durability window" of given length, e.g., a 10-year window starting/ending at the timestamp of the record. The parameter k, the length of the durability window, and parameters of the scoring function (which capture user preference) can all be given at the query time. We illustrate why this problem formulation yields more meaningful answers in some practical situations than other similar types of queries considered previously. We propose new algorithms for solving this problem, and provide a comprehensive theoretical analysis on the complexities of the problem itself and of our algorithms. Our algorithms vastly outperform various baselines (by up to two orders of magnitude on real and synthetic datasets).