Finding top-m leading records in temporal data

• Main Author: WANG, Yiyi
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2022
• Subjects: durable query; top-k query; multi-dimensional time series; temporal data; Databases and Information Systems; Data Storage Systems
• Online Access: https://ink.library.smu.edu.sg/etd_coll/422; https://ink.library.smu.edu.sg/context/etd_coll/article/1420/viewcontent/GPIS_AY2019_MbR_Wang_Yiyi.pdf
• Institution: Singapore Management University

A traditional top-k query retrieves the records that stand out at a certain point in time. On the other hand, a durable top-k query considers how long the records retain their supremacy, i.e., it reports those records that are consistently among the top-k in a given time interval. In this thesis, we introduce a new query to the family of durable top-k formulations. It finds the top-m leading records, i.e., those that rank among the top-k for the longest duration within the query interval. Practically, this query assesses the records based on how long they stay ahead of competition. We perform a case study with real NBA data to demonstrate the value of the query. In addition, we present a meaningful problem variant for the special scenario where the data are sparse. We propose a first-cut algorithm for solving the problem, which we later enhance with an early termination condition. We compare the two versions of the algorithm and demonstrate their practicality using synthetic and real datasets.