Dominant Graph: 提升Top-K查询效率的索引结构
需积分: 9 7 浏览量
更新于2024-09-06
收藏 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页未读，立即下载
181 浏览量
155 浏览量
2019-08-22 上传
2023-09-13 上传
1372 浏览量
2021-10-04 上传
142 浏览量
147 浏览量
471 浏览量
weixin_45227065
- 粉丝: 0
我的内容管理
展开
最新资源
- SBO、用友与金蝶软件功能及特点深度比较
- Portal Star Kit：企业门户建设与源码解析
- Gson解析Json冲突文件修复与代码功能参考
- 综合布线系统案例分析与应用
- 简易窗口分割方法实例教程
- 掌握PdfTools：高效处理PDF文件的必备工具
- 掌握Spring 4.2核心JAR包及其功能
- MATLAB仿真源文件：直流双闭环控制系统详解
- 掌握Solr开发：入门到实践案例详解
- 掌握C#开发：打造高级文本编辑器与编码识别技术
- 提升界面美感的QQ抽屉控件详解
- Android中实现定时图片滑动显示的技巧
- 高效字库文件处理工具：仅截取所需文字
- Android端解析XML和JSON以及Webservice、UPnP的实践教程
- 串口DLL编程初学者与商业级应用指南
- Python版本的t-rex随机工具使用教程
