306 X. Han et al.
Table 1 Summary of symbols
Symbol Meaning
T The table for top-k query
M The dimensionality of T
N The tuple number in T
F The ranking function in top-k query
m Attribute number involved in F
SL
i
The sorted list for attribute A
i
tscore
thres
Pruning score threshold computed by APTS
gdep Scan depth when k terminating tuples are
obtained in round-robin retrieval
b
mn
i
Used minimum positional index of EGBFT
i
b
mx
i
Used maximum positional index of EGBFT
i
Fig. 1 The data set of the running example
3.2 LARA algorithm
In this paper, we take LARA [17] as example to discuss sorted-list-based methods due to its
superior performance. Given ranking function F, LARA retrieves tuples from SL
1
,...,SL
m
in a round-robin fashion. Suppose that the tuples retrieved in m sorted lists currently are
( pi
1
, a
1
), ...,(pi
m
, a
m
), the threshold of LARA is τ = F(a
1
,...,a
m
). The execution of
LARA consists of two phases: growing phase and shrinking phase. In growing phase, LARA
maintains each candidate t seen during retrieval in set C and updates its score lower-bound
F
lb
t
. Here, F
lb
t
=
m
i=1
(w
i
× t.A
il
) where t.A
il
= t.A
i
if t.A
i
has been obtained in SL
i
,
otherwise t.A
il
= MIN
i
(the minimum value of A
i
). A priority queue P
Q
is used to maintain k
candidates with the largest score lower-bounds seen so far. Let P
Q
.min be the minimum score
lower-bound in P
Q
. When P
Q
.min ≥ τ, growing phase is over. In shrinking phase, LARA
continues its round-robin retrieval, maintains the score lower-bounds and upper-bounds of
the candidates in set C and updates P
Q
. For each candidate t, its score upper-bound is
F
ub
t
=
m
i=1
(w
i
×t. A
iu
),heret.A
iu
= t. A
i
if t. A
i
has been seen in SL
i
already, otherwise
t.A
iu
= a
i
(the maximum possible value of t.A
i
). When P
Q
.min ≥ F
ub
t
(∀t ∈ (C − P
Q
)),
LARA terminates and P
Q
keeps the top-k results.
We use a running example (table RTable) illustrated in Fig. 1 to describe the execu-
tion of algorithms in this paper. The sorted lists generated in the running example are
depicted in Fig. 2. We suppose that top-2 results are required here. When LARA exe-
cutes, it performs a round-robin retrieval on SL
1
, SL
2
, SL
3
and maintains the candidates
in C. When SL
1
(8), SL
2
(8), SL
3
(8) are retrieved, growing phase ends and the current
candidates in C are shown in Fig. 2. Every element in C is a three tuple, including posi-
123
剩余27页未读，继续阅读
weixin_38719890
- 粉丝: 4
- 资源: 992
我的内容管理
展开
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述：模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成：理论与算法
- 基于语义元的相似度计算方法研究：改进与有效性验证
- 网格梯度多密度聚类算法：去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型：有效提升系统状态预测
- 煤矿安全评价：信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN：统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
