动态数据获取：在时间推移中优化查询答案的策略
需积分: 1 116 浏览量
更新于2024-09-09
收藏 568KB PDF 举报
"随机数据获取：随着时间推移回答查询"
在数据驱动的世界中，数据与行动之间存在着紧密的联系。一方面，数据分析的结果引导决策和行动；另一方面，数据的获取是整个数据处理流程的第一步，通常会伴随着一定的成本，这可能是金钱代价，也可能是计算资源消耗，如传感器电池电力、网络传输费用或I/O开销。为了降低成本，可以使用过时的数据来回答查询，但这可能导致结果的不准确性。本研究关注的是在时间序列中，如何针对不断到来的查询，决定何时获取新数据以及何时使用现有数据进行回答的问题。通过强化学习和定制化的局部敏感哈希方法，提出了解决这一问题的两种策略。
强化学习是一种机器学习方法，通过与环境的交互来优化决策策略。在这个场景中，它可以用来动态地决定何时更新数据，以最大化长期的性能（例如，准确性和成本的平衡）。而局部敏感哈希（LSH）是一种用于近似相似性的数据结构，它能够有效地处理大数据中的相似性搜索。通过定制化LSH，可以更高效地处理数据版本的选择，减少不必要的数据获取。
文章的实验部分使用了两个真实世界的数据集进行系统性的实证研究，结果显示所提出的策略既有效又高效。这意味着这些方法在实际应用中能够在降低数据获取成本的同时，保持相对较高的查询准确性。
总结来看，该研究主要涉及以下知识点：
1. **数据与行动的耦合**：数据分析对决策的影响以及数据获取作为数据处理流程的先决条件。
2. **数据获取成本**：包括货币成本和计算资源成本，如传感器能源、网络带宽和存储I/O。
3. **使用过时数据的权衡**：节省成本但可能导致结果的不准确性。
4. **序列决策问题**：在时间序列中的查询处理，决定何时获取新数据以优化性能。
5. **强化学习应用**：用以优化何时获取数据的策略，以平衡成本和准确性。
6. **定制化局部敏感哈希**：用于提高选择使用哪个数据版本的效率。
7. **实证研究**：通过实际数据集验证了方法的有效性和效率。
这些研究结果对于大数据环境下的决策制定和资源管理具有重要的理论和实践价值，特别是在需要实时响应查询且成本控制严格的场景中。
To answer a query q that requires a set R of blocks, P
decides in an online manner whether to use the current ver-
sions of data blocks in D, or to acquire the most recent
versions of blocks in R from S (and update D) by paying a
cost c
d
(R), which is called the data cost. If P decides not to
pay the data cost, and the version in D is outdated, there is
a query result penalty cost c
q
(R, q) for its inaccuracy. Let a
policy be an oracle that tells what next action for P to take,
given P’s current action and the distribution of states P is
believed to be in.
Definition 1. (Sequential Data Acquisition Problem)
An infinite sequence of queries are revealed to a query pro-
cessor P in an online manner. Upon receiving each query q,
P decides, also in an online fashion, whether or not to ac-
quire the data blocks R required by q from the data source
S. The sequential data acquisition problem for P is to find
an optimal policy π
∗
so as to minimize the long term costs,
which include both data costs and query result penalty costs,
for answering the sequence of queries.
The notion of “long term costs” will be made more precise
in Section 2.2 below (i.e., expected discounted sum of costs).
Analogous to DBMS blocks/pages, in this work, we assume
simple equal-size partitioning of blocks. For instance, in Ex-
ample 1, the sequence of data from each road can be treated
as a block; data tuples from each sensor in a sensor network
are a block. More sophisticated block partitioning is beyond
the scope of this paper. In addition, in these applications,
typically there are one or a few highly dynamic attributes
(which are to be kept track of), while other attributes (e.g.,
locations) are relatively stable/static. An example is the
multidimensional array model which is the most common
data model in scientific databases, where the dimension at-
tributes are usually static and in the clear. Most, if not all,
queries have predicates over ranges of the dimensions. The
block partitions should be based on stable/static attributes.
R can be easily determined if there is a predicate over
block-partitioning attributes. In the (arguably rare) event
that either (E1) there are predicates on static attributes,
but none of these attributes is aligned with block partitions,
or (E2) there are no predicates on static attributes, then we
use a simple two-step process. In the first step, we execute
the query using the existing data (without acquisition), and
get a version of qualified/required set of blocks R. In the
second step, we use R to determine the action of whether to
acquire the data in R (and re-run the query) or to just stop
there (returning the result from the first step). Note that in
the event of E2 above, R may be approximate (a precise R
would include all blocks of the table, as there is no predicate
on stable attributes).
2.2 Preliminaries
POMDP. Markov Decision Processes (MDPs) provide a
mathematical framework for modeling decision making in
situations where outcomes are partly random and partly
under the control of a decision maker [22]. MDPs are an
extension of Markov chains; the difference is the addition of
actions (allowing choice) and rewards (giving motivation).
Figure 2 shows an example of a simple MDP with three
states s
0
, s
1
, s
2
and two actions a
0
, a
1
. A yellow squiggle
arrow shows the reward associated with the corresponding
transition black edge. Formally, an MDP is defined as a
tuple (S, A, T, R), where S is a set of states, A is a set of
actions, T is the transition function T (s, a, s
0
) = P r[s
t+1
=
Figure 2: A simple MDP with 3 states and 2 actions.
s
0
| s
t
= s, a
t
= a] (where s
t
and a
t
denote the state and
action at time t, resp.), and R(s, a) is the reward for execut-
ing action a in state s. The core problem of MDPs is to find
a policy for the decision maker: a function π that specifies
the action π(s) that the decision maker will choose when in
state s. The goal is to choose a policy π that will maximize
some cumulative function of the random rewards, typically
the expected discounted sum over a potentially infinite hori-
zon:
P
∞
t=0
γ
t
R(s
t
, π(s
t
)), where γ is called a discount factor
and satisfies 0 ≤ γ < 1. The larger the discount factor
(closer to 1), the more effect future rewards have on current
decision making. This is equivalent to minimizing expected
discounted sum of costs as in Definition 1.
In MDP, we assume that the decision maker knows the
environment state exactly; in other words, the environment
state must be fully observable. However, this assumption of-
ten does not hold in reality. A Partially Observable Markov
Decision Process (POMDP) is for this problem. In addition
to S, A, T , R, a POMDP has two extra elements: a set
of observations Ω and an observation function O(a, s
0
, o) =
P r[o
t+1
= o | a
t
= a, s
t+1
= s
0
]. There are a number of tools
for solving a POMDP model. We need to first define and
learn the S, A, T , R, Ω, and O elements, and provide them
to a POMDP solver, which in turn computes the optimal
policy. At runtime, when each query comes in, we interact
with a program and feed our observation to it. Accordingly,
the program consults the computed policy and notifies us
the next action. This step at runtime is instantaneous as
the policy is pre-computed only once. We refer the reader
to [22, 16] for the details of POMDP.
Locality-sensitive hashing. Locality-sensitive hashing
(LSH) is a method of performing probabilistic dimension re-
duction of high-dimensional data [19]. The idea is to hash
the input items so that similar items are mapped to the
same buckets with high probability. A key element is defin-
ing “similarity”. One metric we use is set similarity. In par-
ticular, the Jaccard similarity coefficient between two sets
A and B is defined as J(A, B) =
|A∩B|
|A∪B|
, which is a value
in [0,1] and measures the similarity of two sets (e.g., when
A = B, J(A, B) = 1). The Jaccard distance is 1 − J(A, B).
MinHash is a LSH mechanism based on this metric [10]. Our
goal is to hash a set of elements E. A simple version of Min-
Hash is to start with k independent conventional (random)
hash functions h
1
, ..., h
k
. Then the MinHash value for the
whole set E is the concatenation of k minimum hash values:
min
e∈E
h
1
(e), ..., min
e∈E
h
k
(e).
Q-learning. As surveyed by Kaelbling et al. [15], there
are mainly three types of model-free approaches in the liter-
ature: (1) Adaptive Heuristic Critic (AHC), (2) Q-learning,
and (3) Model-free learning with average reward. AHC ar-
chitectures are more difficult to work with than Q-learning
on a practical level [15]. It can be hard to get the relative
279
剩余11页未读，继续阅读
143 浏览量
266 浏览量
点击了解资源详情
152 浏览量
2021-02-20 上传
235 浏览量
2021-02-22 上传
126 浏览量
113 浏览量
170 浏览量
myishh
- 粉丝: 0
- 资源: 6
我的内容管理
展开
最新资源
- 保险行业培训资料：胡萝卜、鸡蛋、咖啡豆
- pts后处理
- lms2021.1
- neo4j-community-3.5.13-windows.zip
- Computational_Physics:3月优先注意事项
- Gymzzy-Demo：演示Gymzzy角站点托管
- 电子功用-带滤波功能的轮椅电机
- MyPasswords:个人密码管理器-开源
- partners:Qiskit合作伙伴计划的主要存储库
- 保险行业培训资料：目标市场增员
- 随机生成70多万的网名数据
- codecon2015samples:AsyncAwait的TypeScript a Babel在CodeCon 2015之前的示例
- 电子功用-圆柱形锂离子电池化成分容设备
- sphinx-html-multi-versions:允许在 Sphinx 生成的文档中切换产品版本的简单模板和包含脚本
- 搏斗
- neo4j-community-3.5.13-unix.tar.gz
