Dominant Graph: 提升Top-K查询效率的索引结构
需积分: 9 127 浏览量
更新于2024-09-07
收藏 1.82MB PDF 举报
"Dominant Graph: An Efficient Indexing Structure to Answer Top-K Queries"
本文主要探讨了在数据记录集D上，给定一个查询评分函数F时，如何高效地处理Top-K查询的问题。Top-K查询旨在返回记录集中具有最高F函数值的k个记录。作者 Lei Zou 和 Lei Chen 分别来自华中科技大学和香港科技大学，他们提出了一种基于图的高效索引结构——主导图（Dominant Graph, DG），以提升查询效率。
首先，研究者发现了Top-K查询与记录间主导关系之间的内在联系。主导关系是指一个记录在某些属性上的F函数值高于另一个记录。利用这种关系，他们设计了一个离线构建的分层索引结构DG，该结构能够表达记录之间的主导关系。在DG中，Top-K查询被转化为一个图遍历问题，即Traveler算法。
理论证明，基本算法的搜索空间大小（即，从记录集中检索以回答Top-K查询的记录数量）直接受到记录集中 skyline 点（无向下方点）基数的影响（见定理3.2）。Skyline是多维数据中的非支配点集合，对于Top-K查询至关重要，因为它能确保找到最优秀的结果集。
DG的主要优势在于它能够减少在线查询时的计算复杂性。通过预先构建的图结构，查询可以更快地定位到满足条件的顶级记录，而不必检查整个数据集。此外，DG还可能支持动态更新和查询优化，适应数据变化和多样化的查询需求。
文章中，作者可能会详细阐述DG的构建过程、查询算法的具体实现以及性能分析。这包括DG如何存储和组织记录，旅行者算法如何遍历图以找到Top-K结果，以及与现有方法相比的性能改进。实验部分通常会展示在不同数据集和查询配置下的评估结果，验证DG的有效性和效率。
"Dominant Graph.pdf" 提供了一种新颖且高效的解决方案，用于处理大数据集中的Top-K查询，特别是在多维数据场景下，其对skyline概念的应用和主导图的构建，有望显著提升查询性能。这对于数据分析、数据库管理系统和数据挖掘等领域具有重要的实际应用价值。
Dominant
Graph:
An
Efficient
Indexing
Structure
to
Answer
Top-K
Queries
Lei
Zou
1
,
Lei
Chen
2
1Huazhong
University
of
Science
and
Technology
1037
Luoyu
Road,
Wuhan,
P.
R.
China
1zoulei@mail
.hust
.edu.
cn
2Hong
Kong
University
of
Science
and
Technology
Clear
Water
Bay,
Kowloon,
Hong
Kong
2leichen@cse
.ust
.hk
Abstract-
Given
a
record
set
D
and
a
query
score
function
F,
a
top-k
query
returns
k
records
from
D,
whose
values
of
function
F
on
their
attributes
are
the
highest.
In
this
paper,
we
investigate
the
intrinsic
connection
between
top-k
queries
and
dominant
relationship
between
records,
and
based
on
which,
we
propose
an
efficient
layer-based
indexing
structure,
Dominant
Graph
(DG),
to
improve
the
query
efficiency.
Specifically,
DG
is
built
offline
to
express
the
dominant
relationship
between
records
and
top-k
query
is
implemented
as
a
graph
traversal
problem,
i.e.
Traveler
algorithm.
We
prove
theoretically
that
the
size
of
search
space
(that
is
the
number
of
retrieved
records
from
the
record
set
to
answer
top-k
query)
in
our
basic
algorithm
is
directly
related
to
the
cardinality
of
skyline
points
in
the
record
set
(see
Theorem
3.2).
Based
on
the
cost
analysis,
we
propose
the
optimization
technique,
pseudo
record,
to
improve
the
search
efficiency.
In
order
to
handle
the
top-k
query
in
the
high
dimension
record
set,
we
also
propose
N-Way
Traveler
algorithm.
Finally,
extensive
experiments
demonstrate
that
our
proposed
methods
have
significant
improvement
over
its
counterparts,
including
both
classical
and
state
art
of
top-k
algorithms.
For
example,
the
search
space
in
our
algorithm
is
less
than
5
of
that
5
in
AppRI
[1],
one
of
state
art
of
top-k
algorithms.
Furthermore,
our
method
can
support
any
aggregate
monotone
query
function.
I.
INTRODUCTION
Given
a
record
set
D
and
a
query
function
F,
a
top-k
preference
query
(top-k
query
for
short)
returns
k
records
from
D,
whose
values
of
function
F
on
their
attributes
are
the
highest.
Top-k
queries
are
very
popular
in
many
applications.
For
example,
a
job
seeker
may
want
to
find
the best
jobs
fit
to
her
preferences,
such
as
near
to
her
home,
high
salary,
and
short
working
time.
For
different
applicants,
they
may
have
their
own
ranking
by
assigning
different
weights.
Some
may
put
a
high
weight
on
"salary",
while
others
care
more
about
"reputation"
of
the
company.
No
matter
what
their
preferences
are,
all
these
queries
belong
to
top-k
preference
queries.
A.
Motivation
Due
to
the
popularity
of
top-k
queries,
there
are
many
solutions
that
have
been
proposed
in
the
database
literature.
Basically,
they
can
be
divided
into
three
categories:
Sorted
list-based,
Layer-based
and
View-based.
1.
Sorted
lists-based.
The
methods
in
this
category
sort
the
records
in
each
dimension
and
aggregate
the
rank
by
parallel
scanning
each
list
until
the
top-k
results
are
returned,
such
as
TA
and
CA[2],
[3],
[4].
2.
Layer-based.
The
algorithms
in
this
category organize
all
records
into
consecutive
layers,
such
as
Onion
[5]
and
AppRI
[1].
The
organization
strategy
is
based
on
the
common
property
among
the
records,
such
as
the
same
convex
hull
layer
in
Onion
[5].
Any
top-k
query
can
be
answered
by
up
to
k
layers
of
records.
3.
View-based.
Materialized
views
are
used
to
answer
top-k
query,
such
as
PREFER
[6]
and
LPTA
[7].
The
algorithms
in
the
first
category
need
to
merge
different
sorted
lists,
and
their
query
performance
is
not
as
good
as
the
rest
two
categories.
However,
the
layer-based
and
view-based
approaches
have
some
common
limitations:
1)
all
existing
algorithms
in
these
two
categories
only
support
linear
query
function,
such
as
[5],
[1],
[6],
[7];
2)
they
have
high
maintenance
cost.
Observed
from
the
limitations,
we
propose
a
novel
layer-based
method
in
this
paper.
Parallel
to
top-k
queries,
there
is
another
type
of
query,
skylines,
which
also
attracts
much
attention
recently
[8], [9],
[10], [11].
Given
a
record
set
D
of
dimension
m,
a
skyline
query
over
D
returns
a
set
of
records
which
are
not
dominated
by
any
other
record.
Here
we
say
one
record
X
dominates
another
record
Y
if
among
all
the
m
attributes
of
X,
there
exists
at
least
one
attribute
value
is
smaller
than
the
corresponding
attribute
in
Y
and
the
rest
the
attributes
of
X
are
either
smaller
or
equal
to
the
matched
attributes
in
Y.
The
difference
between
skylines
and
top-k
queries
is
that
the
results
of
top-k
queries
change
with
the
different
preference
functions,
while
the
results
of
skyline
queries
are
fixed
for
a
given
record
set.
Many
solutions
have
been
proposed
for
computing
skylines
efficiently,
such
as
block
nested
loops
[8],
divide-and-conquer
[8],
bitmap
[10],
index
[10],
nearest
neighbor
[11]
and
branch
and
bound
[9].
In
fact,
both
top-k
and
skyline
query
are
not
independent
of
each
other,
they
are
connected
by
the
dominant
relationships.
Thus,
we
would
like
to
make
use
of
dominant
relationship
to
answer
top-k
query.
The
intuition
is
that
for
the
aggregate
monotonic
function,
F,
of
a
top-k
query,
when
record
X
dominates
record
Y,
the
query
score
of
X
must
be
less
than
that
of
Y.
It
also
means
that
X
can
be
pruned
safely
when
978-1-4244-1837-4/08/$25.00
(©
2008
IEEE
536
ICDE
2008
下载后可阅读完整内容，剩余9页未读，立即下载
2020-04-04 上传
2019-07-19 上传
2009-03-24 上传
2023-07-23 上传
2023-12-06 上传
2023-09-06 上传
2024-02-07 上传
2023-05-15 上传
2023-05-30 上传
weixin_45227065
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- Android圆角进度条控件的设计与应用
- mui框架实现带侧边栏的响应式布局
- Android仿知乎横线直线进度条实现教程
- SSM选课系统实现：Spring+SpringMVC+MyBatis源码剖析
- 使用JavaScript开发的流星待办事项应用
- Google Code Jam 2015竞赛回顾与Java编程实践
- Angular 2与NW.js集成：通过Webpack和Gulp构建环境详解
- OneDayTripPlanner：数字化城市旅游活动规划助手
- TinySTM 轻量级原子操作库的详细介绍与安装指南
- 模拟PHP序列化:JavaScript实现序列化与反序列化技术
- ***进销存系统全面功能介绍与开发指南
- 掌握Clojure命名空间的正确重新加载技巧
- 免费获取VMD模态分解Matlab源代码与案例数据
- BuglyEasyToUnity最新更新优化：简化Unity开发者接入流程
- Android学生俱乐部项目任务2解析与实践
- 掌握Elixir语言构建高效分布式网络爬虫
