Durable Queries over Historical Time Series
Durable Queries over Historical Time Series
复制标题
DOI：
10.1109/tkde.2013.10
复制
发表时间：
2013-01
影响因子：
8.9
通讯作者：
Hao Wang;Yilun Cai;Y. Yang;Shiming Zhang;N. Mamoulis
中科院分区：
文献类型：
--
作者：
Hao Wang;Yilun Cai;Y. Yang;Shiming Zhang;N. Mamoulis
本文研究了在历史时间序列数据库中发现具有持久质量的对象的问题。例如，社会学家可能对某些历史事件期间的前10个网络搜索词感兴趣;持久top-k（DTop-k）和最近邻（DkNN）查询可以被看作是标准快照top-k查询的自然扩展。k和NN查询到时间戳序列的值或位置。虽然他们的快照同行已被广泛研究，据我们所知，很少有以前的工作，解决这一类新的持久性查询。用于DTop-k处理的现有方法要么应用平凡的解决方案，要么依赖于特定于域的属性。出于这一动机，我们提出了高效和可扩展的算法的DTop-k和DkNN查询，基于新的索引和查询评估技术。我们的实验表明，所提出的算法优于以前的基线解决方案的一个很大的保证金。
This paper studies the problem of finding objects with durable quality over time in historical time series databases. For example, a sociologist may be interested in the top 10 web search terms during the period of some historical events; the police may seek for vehicles that move close to a suspect 70 percent of the time during a certain time period and so on. Durable top-k (DTop-k) and nearest neighbor (DkNN) queries can be viewed as natural extensions of the standard snapshot top-k and NN queries to timestamped sequences of values or locations. Although their snapshot counterparts have been studied extensively, to our knowledge, there is little prior work that addresses this new class of durable queries. Existing methods for DTop-k processing either apply trivial solutions, or rely on domain-specific properties. Motivated by this, we propose efficient and scalable algorithms for the DTop-k and DkNN queries, based on novel indexing and query evaluation techniques. Our experiments show that the proposed algorithms outperform previous and baseline solutions by a wide margin.