rnn.rar

  • K0_140201
    了解作者
  • 6.3MB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-04-28 06:54
    上传日期
逆向最近邻查询算法在实际应用中有很多领域
rnn.rar
  • rnn
  • two-step prunning.pdf
    1.2MB
  • Partition-Based Similarity Joins Using Diagonal.pdf
    211KB
  • Accelerating High-dimensional Nearest Neighbor Queries.pdf
    323.2KB
  • Reverse k-Nearest Neighbor Search.pdf
    478.3KB
  • 基于SR_树的空间对象反最近邻查询技术研究.pdf
    224.7KB
  • Reverse kNN Search in Arbitrary Dimensionality.pdf
    243.7KB
  • Reverse Nearest Neighbors in Large Graphs.pdf
    66.8KB
  • Optimizing spatial MinMax aggregations.pdf
    460.7KB
  • 超平面树_度量空间中相似性搜索的索引结构.pdf
    308.8KB
  • Search Reverse Nearest Neighbor Query On Air.pdf
    581.2KB
  • 二维空间中基于约束关系的RNN查询算法.pdf
    1.1MB
  • An index structure for efficient reverse nearest neighbor queries.pdf
    703.3KB
  • 基于Voronoi图的反向最近邻查询方法研究.pdf
    340.3KB
  • 空间对象的反最近邻查询.pdf
    427.2KB
  • 20081022140328750Progressive Computation of the MinDist.pdf
    533.6KB
内容介绍
<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/63223af7f0cde613575602d1/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/63223af7f0cde613575602d1/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0"><span class="fc0 sc0">Two-Step </span><span class="_ _0"> </span><span class="ls1"><span class="fc0 sc0">Pruning </span><span class="_ _0"> </span><span class="ls2"><span class="fc0 sc0">: </span><span class="_ _1"></span><span class="fc0 sc0">A </span><span class="_ _2"> </span><span class="ls3"><span class="fc0 sc0">Distributed </span><span class="_ _3"> </span><span class="ls4"><span class="fc0 sc0">Query </span></span></span></span></span></div><div class="t m0 x2 h2 y2 ff1 fs0 fc0 sc0 ls5 ws0"><span class="fc0 sc0">Optimization </span><span class="_ _4"></span><span class="ls6"><span class="fc0 sc0">Algorithm </span></span></div><div class="t m1 x3 h3 y3 ff2 fs1 fc0 sc0 ls7 ws0"><span class="fc0 sc0">Hyeokman </span><span class="_ _5"></span><span class="ls8"><span class="fc0 sc0">Kim </span><span class="_ _6"></span><span class="ls9"><span class="fc0 sc0">1,2, </span><span class="_ _7"></span><span class="lsa"><span class="fc0 sc0">Sukho </span><span class="_ _7"></span><span class="ls2"><span class="fc0 sc0">Lee </span><span class="_ _8"></span><span class="lsb"><span class="fc0 sc0">1, </span><span class="_ _9"></span><span class="lsc"><span class="fc0 sc0">Hyoung-Joo </span><span class="_ _5"></span><span class="lsd"><span class="fc0 sc0">Kim </span><span class="_ _a"></span><span class="ls2"><span class="fc0 sc0">1 </span></span></span></span></span></span></span></span></span></div><div class="t m1 x4 h3 y4 ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">1 </span><span class="_ _4"> </span><span class="fc0 sc0">Dept. </span><span class="_ _1"></span><span class="lse"><span class="fc0 sc0">of </span><span class="_ _5"></span><span class="ls2"><span class="fc0 sc0">Computer </span><span class="_ _9"></span><span class="fc0 sc0">Engineering, </span><span class="_ _b"></span><span class="lsf"><span class="fc0 sc0">Seoul </span><span class="_ _c"></span><span class="ls2"><span class="fc0 sc0">National </span><span class="_ _9"></span><span class="fc0 sc0">University </span></span></span></span></span></div><div class="t m1 x5 h3 y5 ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">Shinrim-Dong, </span><span class="fc0 sc0">Kwanak-Gu, </span><span class="_ _b"></span><span class="fc0 sc0">Seoul, </span><span class="_ _7"></span><span class="ls10"><span class="fc0 sc0">151-742, </span></span><span class="fc0 sc0">Korea </span></div><div class="t m1 x6 h3 y6 ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">2 </span><span class="_ _9"></span><span class="fc0 sc0">Korea </span><span class="fc0 sc0">Telecom </span><span class="fc0 sc0">Research </span><span class="fc0 sc0">Laboratories </span></div><div class="t m1 x7 h3 y7 ff2 fs1 fc0 sc0 ls11 ws0"><span class="fc0 sc0">17, </span><span class="_ _9"></span><span class="ls2"><span class="fc0 sc0">Woomyon-Dong, </span><span class="_ _8"></span><span class="fc0 sc0">Suhcho-Gu, </span><span class="_ _7"></span><span class="fc0 sc0">Seoul, </span><span class="_ _7"></span><span class="ls10"><span class="fc0 sc0">137-792, </span></span><span class="fc0 sc0">Korea </span></span></div><div class="t m1 x8 h3 y8 ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">E-mail: </span><span class="_ _b"></span><span class="fc0 sc0">{hmkim, </span><span class="_ _d"></span><span class="ls12"><span class="fc0 sc0">shlee}@snucom.snu.ac.kr, </span><span class="_ _c"></span><span class="ls2"><span class="fc0 sc0">hjk@inm4u.snu.ac.kr </span></span></span></div><div class="t m1 x9 h3 y9 ff2 fs1 fc0 sc0 ls13 ws0"><span class="fc0 sc0">Abstract. </span><span class="_ _3"> </span><span class="ls14"><span class="fc0 sc0">The </span><span class="_ _4"> </span><span class="lse"><span class="fc0 sc0">problem </span><span class="ls15"><span class="fc0 sc0">of </span><span class="_ _7"></span><span class="ls2"><span class="fc0 sc0">finding </span><span class="_ _9"></span><span class="fc0 sc0">an </span><span class="_"> </span><span class="fc0 sc0">optimal </span><span class="_"> </span><span class="ls16"><span class="fc0 sc0">global </span><span class="_ _5"></span><span class="ls2"><span class="fc0 sc0">plan </span><span class="_"> </span><span class="fc0 sc0">for </span><span class="_ _9"></span><span class="fc0 sc0">a </span><span class="_ _e"> </span><span class="fc0 sc0">tree </span></span></span></span></span></span></span></div><div class="t m1 x9 h3 ya ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">query </span><span class="_ _1"></span><span class="fc0 sc0">in </span><span class="_ _4"> </span><span class="fc0 sc0">a </span><span class="_ _1"></span><span class="fc0 sc0">distributed </span><span class="_ _0"> </span><span class="fc0 sc0">database </span><span class="_"> </span><span class="ls17"><span class="fc0 sc0">is </span><span class="_ _9"></span></span><span class="fc0 sc0">studied </span><span class="_ _e"> </span><span class="fc0 sc0">under </span><span class="_ _e"> </span><span class="lse"><span class="fc0 sc0">the </span><span class="_ _b"></span></span><span class="fc0 sc0">objective </span><span class="_ _9"></span><span class="ls15"><span class="fc0 sc0">of </span><span class="ls18"><span class="fc0 sc0">total </span></span></span></div><div class="t m1 x9 h3 yb ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">processing </span><span class="_ _b"></span><span class="fc0 sc0">time </span><span class="_ _9"> </span><span class="fc0 sc0">minimization. </span><span class="_ _4"> </span><span class="fc0 sc0">A </span><span class="_ _1"></span><span class="fc0 sc0">two-step </span><span class="_ _9"></span><span class="fc0 sc0">pruning </span><span class="_ _3"> </span><span class="fc0 sc0">algorithm </span><span class="_ _4"> </span><span class="fc0 sc0">based </span><span class="_ _9"></span><span class="ls17"><span class="fc0 sc0">on </span></span></div><div class="t m1 x9 h3 yc ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">dynamic </span><span class="_ _b"></span><span class="fc0 sc0">programming </span><span class="_ _1"></span><span class="ls17"><span class="fc0 sc0">is </span><span class="_ _b"></span></span><span class="fc0 sc0">presented. </span><span class="_ _9"></span><span class="fc0 sc0">This </span><span class="_ _1"></span><span class="fc0 sc0">algorithm </span><span class="_ _4"> </span><span class="fc0 sc0">performs </span><span class="_ _b"></span><span class="fc0 sc0">a </span><span class="_ _1"></span><span class="fc0 sc0">pruning </span></div><div class="t m1 x9 h3 yd ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">step </span><span class="_ _1"></span><span class="fc0 sc0">twice </span><span class="_ _5"></span><span class="fc0 sc0">for </span><span class="_ _5"></span><span class="lse"><span class="fc0 sc0">each </span><span class="_ _c"></span><span class="ls2"><span class="fc0 sc0">subquery </span><span class="_ _b"></span><span class="fc0 sc0">by </span><span class="fc0 sc0">designing </span><span class="_ _5"></span><span class="fc0 sc0">two </span><span class="_ _5"></span><span class="fc0 sc0">separate </span><span class="_ _4"> </span><span class="fc0 sc0">equivalence </span><span class="_ _8"></span><span class="fc0 sc0">crite- </span></span></span></div><div class="t m1 x9 h3 ye ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">ria </span><span class="_ _b"></span><span class="fc0 sc0">applicable </span><span class="lse"><span class="fc0 sc0">to </span><span class="_ _d"></span><span class="fc0 sc0">each </span><span class="_ _8"></span><span class="ls2"><span class="fc0 sc0">subquery. </span><span class="fc0 sc0">This </span><span class="_ _7"></span><span class="fc0 sc0">lessens </span><span class="_ _5"></span><span class="lse"><span class="fc0 sc0">the </span><span class="_ _d"></span><span class="ls2"><span class="fc0 sc0">search </span><span class="_ _7"></span><span class="ls19"><span class="fc0 sc0">work </span><span class="_ _8"></span><span class="ls2"><span class="fc0 sc0">done </span><span class="fc0 sc0">by </span><span class="lse"><span class="fc0 sc0">the </span></span></span></span></span></span></span></span></div><div class="t m1 x9 h3 yf ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">optimizer </span><span class="_ _9"></span><span class="fc0 sc0">considerably. </span><span class="ls1a"><span class="fc0 sc0">Without </span><span class="_ _b"></span></span><span class="fc0 sc0">losing </span><span class="_ _7"></span><span class="fc0 sc0">optimality, </span><span class="_ _4"> </span><span class="lse"><span class="fc0 sc0">the </span><span class="_ _1"></span><span class="ls1a"><span class="fc0 sc0">search </span><span class="_ _5"></span><span class="lse"><span class="fc0 sc0">space </span><span class="_ _5"></span><span class="ls2"><span class="fc0 sc0">for </span></span></span></span></span></div><div class="t m1 x9 h3 y10 ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">finding </span><span class="lse"><span class="fc0 sc0">the </span><span class="_ _5"></span><span class="ls2"><span class="fc0 sc0">optimum </span><span class="_ _1"></span><span class="ls17"><span class="fc0 sc0">is </span><span class="_ _7"></span></span><span class="fc0 sc0">reduced </span><span class="_ _7"></span><span class="fc0 sc0">by </span><span class="_ _7"></span><span class="fc0 sc0">aggregating </span><span class="_ _b"></span><span class="fc0 sc0">partial </span><span class="_ _4"> </span><span class="fc0 sc0">plans </span><span class="_ _7"></span><span class="ls1b"><span class="fc0 sc0">that </span><span class="_ _b"></span></span><span class="fc0 sc0">always </span></span></span></div><div class="t m1 x9 h3 y11 ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">incur </span><span class="_ _b"></span><span class="ls14"><span class="fc0 sc0">the </span><span class="_ _7"></span></span><span class="fc0 sc0">same </span><span class="fc0 sc0">processing </span><span class="_ _5"></span><span class="fc0 sc0">time </span><span class="_ _7"></span><span class="fc0 sc0">into </span><span class="_ _9"></span><span class="fc0 sc0">a </span><span class="fc0 sc0">single </span><span class="_ _5"></span><span class="fc0 sc0">plan </span><span class="_ _1"></span><span class="fc0 sc0">and </span><span class="_ _b"></span><span class="fc0 sc0">eliminating </span><span class="_ _7"></span><span class="fc0 sc0">partial </span></div><div class="t m1 xa h3 y12 ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">plans </span><span class="_ _b"></span><span class="ls1c"><span class="fc0 sc0">that </span><span class="_ _b"></span></span><span class="fc0 sc0">can </span><span class="_ _1"></span><span class="lse"><span class="fc0 sc0">never </span><span class="_ _f"></span><span class="ls2"><span class="fc0 sc0">be </span><span class="_ _1"></span><span class="lse"><span class="fc0 sc0">the </span></span><span class="fc0 sc0">optimum. </span></span></span></div><div class="t m1 xb h3 y13 ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">1 </span><span class="_ _10"> </span><span class="ls1d"><span class="fc0 sc0">Introduction </span></span></div><div class="t m1 xb h3 y14 ff2 fs1 fc0 sc0 lsd ws0"><span class="fc0 sc0">The </span><span class="_ _9"></span><span class="ls1e"><span class="fc0 sc0">importance </span><span class="_ _7"></span><span class="ls1f"><span class="fc0 sc0">of </span><span class="ls20"><span class="fc0 sc0">query </span><span class="_ _1"></span></span></span><span class="fc0 sc0">optimization </span><span class="lse"><span class="fc0 sc0">in </span><span class="_ _4"> </span><span class="ls20"><span class="fc0 sc0">centralized </span><span class="_ _1"></span></span></span></span><span class="fc0 sc0">and </span><span class="_ _9"></span><span class="lsc"><span class="fc0 sc0">distributed </span><span class="_ _9"></span></span><span class="fc0 sc0">database </span></div><div class="t m1 xb h3 y15 ff2 fs1 fc0 sc0 ls21 ws0"><span class="fc0 sc0">systems </span><span class="ls2"><span class="fc0 sc0">is </span><span class="_ _b"></span><span class="ls22"><span class="fc0 sc0">widely </span></span><span class="fc0 sc0">recognized. </span><span class="_ _0"> </span><span class="lse"><span class="fc0 sc0">One </span><span class="_ _b"></span><span class="lsd"><span class="fc0 sc0">of </span><span class="_ _5"></span><span class="fc0 sc0">the </span><span class="_ _1"></span><span class="ls23"><span class="fc0 sc0">key </span><span class="ls24"><span class="fc0 sc0">components </span><span class="lse"><span class="fc0 sc0">in </span><span class="_ _1"></span><span class="lsa"><span class="fc0 sc0">query </span><span class="ls1e"><span class="fc0 sc0">optimization </span></span></span></span></span></span></span></span></span></div><div class="t m1 xb h3 y16 ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">is </span><span class="_"> </span><span class="lsd"><span class="fc0 sc0">the </span><span class="_ _9"> </span><span class="lse"><span class="fc0 sc0">search </span><span class="_ _e"> </span><span class="ls25"><span class="fc0 sc0">strategy. </span><span class="_ _4"> </span></span></span><span class="fc0 sc0">The </span><span class="_ _e"> </span><span class="ls7"><span class="fc0 sc0">ability </span><span class="_ _b"></span></span><span class="fc0 sc0">to </span><span class="_ _4"> </span><span class="ls26"><span class="fc0 sc0">efficiently </span><span class="_ _7"></span><span class="ls22"><span class="fc0 sc0">find </span><span class="_ _4"> </span><span class="ls27"><span class="fc0 sc0">an </span><span class="_ _4"> </span><span class="ls28"><span class="fc0 sc0">optimal </span><span class="_ _1"></span><span class="lse"><span class="fc0 sc0">or </span><span class="_ _11"> </span><span class="ls29"><span class="fc0 sc0">best </span><span class="_"> </span><span class="ls1c"><span class="fc0 sc0">plan </span></span></span></span></span></span></span></span></span></div><div class="t m1 xb h3 y17 ff2 fs1 fc0 sc0 lsd ws0"><span class="fc0 sc0">among </span><span class="ls14"><span class="fc0 sc0">all </span><span class="_ _7"></span><span class="ls1a"><span class="fc0 sc0">possible </span><span class="_ _1"></span><span class="ls21"><span class="fc0 sc0">alternatives </span><span class="ls2"><span class="fc0 sc0">is </span><span class="_ _1"></span><span class="ls16"><span class="fc0 sc0">indeed </span><span class="_ _7"></span><span class="fc0 sc0">essential </span><span class="_ _b"></span></span></span></span></span></span><span class="fc0 sc0">to </span><span class="_ _1"></span><span class="ls2a"><span class="fc0 sc0">performance. </span></span></div><div class="t m1 xc h3 y18 ff2 fs1 fc0 sc0 ls28 ws0"><span class="fc0 sc0">Dynamic </span><span class="_ _f"></span><span class="ls2b"><span class="fc0 sc0">programming </span><span class="_ _f"></span><span class="lsf"><span class="fc0 sc0">which </span><span class="ls2"><span class="fc0 sc0">is </span><span class="ls7"><span class="fc0 sc0">probably </span><span class="lsd"><span class="fc0 sc0">the </span><span class="ls22"><span class="fc0 sc0">best </span><span class="_ _1"></span><span class="ls20"><span class="fc0 sc0">known </span><span class="_ _5"></span><span class="ls2c"><span class="fc0 sc0">standard </span><span class="ls25"><span class="fc0 sc0">optimiza- </span></span></span></span></span></span></span></span></span></span></div><div class="t m1 xb h3 y19 ff2 fs1 fc0 sc0 ls1b ws0"><span class="fc0 sc0">tion </span><span class="_ _9"></span><span class="lsa"><span class="fc0 sc0">technique </span><span class="_ _4"> </span><span class="ls23"><span class="fc0 sc0">has </span><span class="_ _4"> </span><span class="lse"><span class="fc0 sc0">been </span><span class="_ _e"> </span><span class="ls2d"><span class="fc0 sc0">employed </span><span class="_ _b"></span><span class="ls15"><span class="fc0 sc0">as </span><span class="_ _e"> </span><span class="ls2"><span class="fc0 sc0">a </span><span class="_"> </span></span></span></span><span class="fc0 sc0">search </span><span class="_ _4"> </span><span class="ls1f"><span class="fc0 sc0">strategy </span><span class="_ _9"> </span><span class="ls20"><span class="fc0 sc0">in </span><span class="_ _4"> </span><span class="fc0 sc0">query </span><span class="_ _9"></span><span class="ls1e"><span class="fc0 sc0">optimization </span></span></span></span></span></span></span></div><div class="t m1 xb h3 y1a ff2 fs1 fc0 sc0 ls2e ws0"><span class="fc0 sc0">[3, </span><span class="_ _1"></span><span class="ls17"><span class="fc0 sc0">9, </span><span class="_ _9"> </span><span class="lsb"><span class="fc0 sc0">10, </span><span class="_"> </span><span class="fc0 sc0">12, </span><span class="_ _9"> </span><span class="ls2"><span class="fc0 sc0">15]. </span><span class="_ _d"></span><span class="ls1f"><span class="fc0 sc0">If </span><span class="_ _f"></span><span class="ls8"><span class="fc0 sc0">dynamic </span><span class="_ _f"></span><span class="ls2b"><span class="fc0 sc0">programming </span><span class="_ _5"></span><span class="ls2"><span class="fc0 sc0">is </span><span class="_ _7"></span><span class="lse"><span class="fc0 sc0">used </span><span class="_ _b"></span><span class="lsd"><span class="fc0 sc0">to </span><span class="_ _7"></span></span></span><span class="fc0 sc0">solve </span><span class="_ _b"></span><span class="ls27"><span class="fc0 sc0">an </span><span class="_ _7"></span><span class="ls1e"><span class="fc0 sc0">optimization </span><span class="_ _12"></span><span class="lse"><span class="fc0 sc0">prob- </span></span></span></span></span></span></span></span></span></span></span></div><div class="t m1 xb h3 y1b ff2 fs1 fc0 sc0 ls29 ws0"><span class="fc0 sc0">lem, </span><span class="_ _d"></span><span class="ls8"><span class="fc0 sc0">the </span><span class="ls2f"><span class="fc0 sc0">problem </span><span class="ls30"><span class="fc0 sc0">must </span><span class="ls21"><span class="fc0 sc0">satisfy </span><span class="_ _5"></span><span class="fc0 sc0">the </span></span></span></span></span></div><div class="t m2 xd h4 y1b ff3 fs2 fc0 sc0 ls2 ws0"><span class="fc0 sc0">principle </span><span class="_ _13"> </span><span class="ls27"><span class="fc0 sc0">of </span></span><span class="fc0 sc0">optimality: </span></div><div class="t m1 xe h3 y1b ff2 fs1 fc0 sc0 lse ws0"><span class="fc0 sc0">in </span><span class="lsd"><span class="fc0 sc0">optimal </span><span class="ls2"><span class="fc0 sc0">sequence </span><span class="_ _4"> </span><span class="ls1f"><span class="fc0 sc0">of </span></span></span></span></div><div class="t m1 xb h3 y1c ff2 fs1 fc0 sc0 ls2 ws0"><span class="fc0 sc0">decisions, </span><span class="_"> </span><span class="lse"><span class="fc0 sc0">each </span><span class="_ _1"></span><span class="fc0 sc0">subsequence </span><span class="_ _1"></span><span class="lsd"><span class="fc0 sc0">must </span><span class="_ _1"></span><span class="ls15"><span class="fc0 sc0">be </span><span class="_ _1"></span><span class="ls8"><span class="fc0 sc0">optimal </span><span class="_ _b"></span></span></span></span></span><span class="fc0 sc0">[6]. </span><span class="ls27"><span class="fc0 sc0">Thus, </span><span class="_ _9"></span><span class="lsd"><span class="fc0 sc0">the </span><span class="_ _1"></span><span class="ls19"><span class="fc0 sc0">cost </span><span class="_ _1"></span><span class="ls1b"><span class="fc0 sc0">function </span><span class="ls18"><span class="fc0 sc0">based </span></span></span></span></span></span></div><div class="t m1 xb h3 y1d ff2 fs1 fc0 sc0 ls20 ws0"><span class="fc0 sc0">on </span><span class="ls8"><span class="fc0 sc0">dynamic </span><span class="_ _c"></span><span class="ls1e"><span class="fc0 sc0">programming </span><span class="_ _f"></span><span class="ls2"><span class="fc0 sc0">is </span><span class="fc0 sc0">expressed </span><span class="_ _3"> </span><span class="ls20"><span class="fc0 sc0">as </span></span><span class="fc0 sc0">a </span><span class="_ _b"></span><span class="ls31"><span class="fc0 sc0">recursive </span><span class="ls27"><span class="fc0 sc0">form. </span><span class="_ _d"></span><span class="ls1b"><span class="fc0 sc0">When </span><span class="ls2a"><span class="fc0 sc0">building </span><span class="_ _12"></span><span class="ls2"><span class="fc0 sc0">execu- </span></span></span></span></span></span></span></span></span></div><div class="t m1 xb h3 y1e ff2 fs1 fc0 sc0 ls1b ws0"><span class="fc0 sc0">tion </span><span class="_ _b"></span><span class="lsa"><span class="fc0 sc0">plans </span><span class="_ _9"> </span><span class="ls28"><span class="fc0 sc0">through </span><span class="_ _9"></span><span class="fc0 sc0">dynamic </span><span class="ls24"><span class="fc0 sc0">programming, </span><span class="_ _7"></span><span class="lsd"><span class="fc0 sc0">the </span><span class="_ _9"></span><span class="lsc"><span class="fc0 sc0">optimizer </span><span class="ls1e"><span class="fc0 sc0">systematically </span><span class="_ _5"></span><span class="ls16"><span class="fc0 sc0">builds </span></span></span></span></span></span></span></span></div><div class="t m1 xb h3 y1f ff2 fs1 fc0 sc0 ls14 ws0"><span class="fc0 sc0">all </span><span class="_ _9"></span><span class="ls1a"><span class="fc0 sc0">possible </span><span class="_ _4"> </span><span class="ls28"><span class="fc0 sc0">partial </span><span class="_ _9"></span><span class="lsa"><span class="fc0 sc0">plans </span><span class="_ _4"> </span><span class="ls21"><span class="fc0 sc0">and </span><span class="_ _e"> </span><span class="ls20"><span class="fc0 sc0">compares </span><span class="_ _9"></span><span class="ls32"><span class="fc0 sc0">them </span><span class="_ _9"></span><span class="ls8"><span class="fc0 sc0">through </span><span class="_ _9"></span><span class="ls24"><span class="fc0 sc0">their </span><span class="_ _4"> </span><span class="ls19"><span class="fc0 sc0">cost </span><span class="_ _4"> </span><span class="ls25"><span class="fc0 sc0">estimates. </span><span class="_ _4"> </span><span class="lsd"><span class="fc0 sc0">It </span></span></span></span></span></span></span></span></span></span></span></span></div><div class="t m1 xb h3 y20 ff2 fs1 fc0 sc0 lsd ws0"><span class="fc0 sc0">then </span><span class="ls22"><span class="fc0 sc0">prunes </span><span class="_ _1"></span><span class="ls16"><span class="fc0 sc0">costly </span><span class="_ _5"></span><span class="ls28"><span class="fc0 sc0">partial </span><span class="lsa"><span class="fc0 sc0">plans </span><span class="_ _7"></span><span class="ls33"><span class="fc0 sc0">that </span><span class="_ _7"></span><span class="ls23"><span class="fc0 sc0">are </span><span class="_ _b"></span><span class="ls2d"><span class="fc0 sc0">equivalent </span><span class="_ _d"></span><span class="lsd"><span class="fc0 sc0">to </span><span class="_ _7"></span><span class="ls2"><span class="fc0 sc0">a </span><span class="_ _1"></span><span class="ls34"><span class="fc0 sc0">cheaper </span><span class="_ _b"></span><span class="ls19"><span class="fc0 sc0">one. </span><span class="ls1b"><span class="fc0 sc0">This </span><span class="_ _7"></span><span class="lsa"><span class="fc0 sc0">prun- </span></span></span></span></span></span></span></span></span></span></span></span></span></span></div><div class="t m1 xb h3 y21 ff2 fs1 fc0 sc0 lsa ws0"><span class="fc0 sc0">ing </span><span class="lse"><span class="fc0 sc0">reduces </span><span class="_ _1"></span><span class="lsd"><span class="fc0 sc0">the </span><span class="_ _7"></span><span class="ls1e"><span class="fc0 sc0">optimization </span><span class="_ _5"></span><span class="ls19"><span class="fc0 sc0">cost </span><span class="_ _1"></span><span class="ls34"><span class="fc0 sc0">because </span><span class="_ _b"></span><span class="ls28"><span class="fc0 sc0">partial </span><span class="_ _b"></span><span class="lsa"><span class="fc0 sc0">plans </span><span class="_ _b"></span><span class="ls33"><span class="fc0 sc0">that </span><span class="_ _1"></span><span class="ls23"><span class="fc0 sc0">are </span><span class="_ _b"></span><span class="lsd"><span class="fc0 sc0">not </span><span class="_ _b"></span></span></span></span></span></span><span class="fc0 sc0">likely </span><span class="_ _5"></span><span class="lsd"><span class="fc0 sc0">to </span><span class="_ _7"></span><span class="lse"><span class="fc0 sc0">be </span></span></span></span></span></span></span></span></div><div class="t m1 xb h3 y22 ff2 fs1 fc0 sc0 ls8 ws0"><span class="fc0 sc0">optimal </span><span class="_ _5"></span><span class="lse"><span class="fc0 sc0">are </span><span class="_ _b"></span><span class="ls25"><span class="fc0 sc0">pruned </span><span class="_ _b"></span><span class="ls15"><span class="fc0 sc0">as </span><span class="_ _7"></span></span></span><span class="fc0 sc0">soon </span><span class="ls15"><span class="fc0 sc0">as </span><span class="_ _b"></span><span class="ls2"><span class="fc0 sc0">possible. </span><span class="_"> </span><span class="lsd"><span class="fc0 sc0">The </span><span class="_ _b"></span><span class="fc0 sc0">advantage </span><span class="_ _12"></span><span class="fc0 sc0">of </span><span class="_ _12"></span><span class="ls28"><span class="fc0 sc0">dynamic </span><span class="_ _f"></span><span class="ls2b"><span class="fc0 sc0">programming </span></span></span></span></span></span></span></div><div class="t m1 xb h3 y23 ff2 fs1 fc0 sc0 ls24 ws0"><span class="fc0 sc0">stems </span><span class="_ _5"></span><span class="ls1b"><span class="fc0 sc0">from </span><span class="_ _5"></span><span class="ls21"><span class="fc0 sc0">the </span><span class="ls1b"><span class="fc0 sc0">fact </span><span class="ls35"><span class="fc0 sc0">that </span><span class="_ _d"></span><span class="lsd"><span class="fc0 sc0">the </span><span class="_ _7"></span><span class="ls2"><span class="fc0 sc0">chosen </span><span class="_ _1"></span><span class="ls28"><span class="fc0 sc0">partial </span><span class="_ _5"></span><span class="ls1b"><span class="fc0 sc0">plan </span><span class="fc0 sc0">with </span><span class="lsa"><span class="fc0 sc0">its </span><span class="_ _b"></span><span class="ls2"><span class="fc0 sc0">cost </span><span class="_ _1"></span><span class="fc0 sc0">is </span><span class="ls1a"><span class="fc0 sc0">saved, </span><span class="lsd"><span class="fc0 sc0">and </span><span class="ls34"><span class="fc0 sc0">reused </span></span></span></span></span></span></span></span></span></span></span></span></span></span></div><div class="t m1 xb h3 y24 ff2 fs1 fc0 sc0 ls28 ws0"><span class="fc0 sc0">rather </span><span class="ls32"><span class="fc0 sc0">than </span><span class="ls24"><span class="fc0 sc0">recomputed </span><span class="_ _d"></span><span class="lse"><span class="fc0 sc0">when </span><span class="ls1b"><span class="fc0 sc0">this </span><span class="_ _d"></span><span class="ls1c"><span class="fc0 sc0">plan </span><span class="ls2"><span class="fc0 sc0">is </span><span class="ls27"><span class="fc0 sc0">employed </span><span class="_ _f"></span><span class="ls15"><span class="fc0 sc0">as </span><span class="_ _7"></span><span class="ls2"><span class="fc0 sc0">a </span><span class="_ _7"></span><span class="ls21"><span class="fc0 sc0">subplan </span><span class="_ _7"></span><span class="lsd"><span class="fc0 sc0">of </span><span class="_ _f"></span><span class="fc0 sc0">another </span><span class="_ _5"></span><span class="ls27"><span class="fc0 sc0">plan. </span></span></span></span></span></span></span></span></span></span></span></span></span></div><div class="t m1 xb h3 y25 ff2 fs1 fc0 sc0 ls1b ws0"><span class="fc0 sc0">This </span><span class="_ _1"></span><span class="ls24"><span class="fc0 sc0">means </span><span class="_ _b"></span><span class="ls33"><span class="fc0 sc0">that </span><span class="_ _9"></span><span class="lsd"><span class="fc0 sc0">the </span><span class="_ _1"></span><span class="lse"><span class="fc0 sc0">saved </span><span class="_ _1"></span></span><span class="fc0 sc0">partial </span><span class="_ _1"></span><span class="ls27"><span class="fc0 sc0">plans </span><span class="_ _9"></span><span class="lse"><span class="fc0 sc0">are </span><span class="_ _9"></span><span class="ls1c"><span class="fc0 sc0">shared </span><span class="_ _9"></span><span class="ls20"><span class="fc0 sc0">by </span><span class="_ _1"></span><span class="ls32"><span class="fc0 sc0">many </span></span></span></span></span></span></span></span><span class="fc0 sc0">other </span><span class="_ _1"></span><span class="ls36"><span class="fc0 sc0">subsequent </span></span></span></div><div class="t m1 xb h3 y26 ff2 fs1 fc0 sc0 lsa ws0"><span class="fc0 sc0">plans </span><span class="_ _7"></span><span class="ls24"><span class="fc0 sc0">built </span><span class="_ _b"></span><span class="ls1b"><span class="fc0 sc0">from </span><span class="ls2b"><span class="fc0 sc0">them. </span></span></span></span></div><div class="t m1 xc h3 y27 ff2 fs1 fc0 sc0 ls8 ws0"><span class="fc0 sc0">The </span><span class="_ _7"></span><span class="ls7"><span class="fc0 sc0">pruning </span><span class="_ _7"></span><span class="ls2"><span class="fc0 sc0">is </span><span class="_ _1"></span><span class="ls1c"><span class="fc0 sc0">performed </span><span class="_ _7"></span><span class="ls18"><span class="fc0 sc0">based </span><span class="_ _1"></span><span class="lse"><span class="fc0 sc0">on </span></span></span></span></span></span></div><div class="t m2 xf h4 y27 ff3 fs2 fc0 sc0 ls2 ws0"><span class="fc0 sc0">equivalence </span><span class="_ _4"></span><span class="fc0 sc0">criteria, </span></div><div class="t m1 x10 h3 y27 ff2 fs1 fc0 sc0 ls33 ws0"><span class="fc0 sc0">that </span><span class="_ _b"></span><span class="ls2"><span class="fc0 sc0">is, </span><span class="_ _9"></span><span class="ls21"><span class="fc0 sc0">the </span><span class="_ _b"></span><span class="ls8"><span class="fc0 sc0">optimal </span></span></span></span></div><div class="t m1 xb h3 y28 ff2 fs1 fc0 sc0 lsd ws0"><span class="fc0 sc0">partial </span><span class="ls1c"><span class="fc0 sc0">plan </span><span class="_ _d"></span><span class="ls2"><span class="fc0 sc0">is </span><span class="fc0 sc0">chosen </span><span class="_ _9"> </span><span class="ls2b"><span class="fc0 sc0">among </span><span class="_ _12"></span><span class="ls14"><span class="fc0 sc0">all </span><span class="_ _d"></span><span class="ls2"><span class="fc0 sc0">possible </span><span class="_ _4"> </span><span class="lsd"><span class="fc0 sc0">partial </span><span class="lsa"><span class="fc0 sc0">plans </span><span class="ls35"><span class="fc0 sc0">that </span><span class="lse"><span class="fc0 sc0">are </span><span class="ls36"><span class="fc0 sc0">equivalent </span><span class="_ _5"></span><span class="ls20"><span class="fc0 sc0">in </span><span class="_ _d"></span><span class="ls22"><span class="fc0 sc0">some </span></span></span></span></span></span></span></span></span></span></span></span></span></div></div><div class="pi" data-data='{"ctm":[2.048982,0.000000,0.000000,2.048982,0.000000,-1.475267]}'></div></div> </body> </html>
评论