空間Skyline查詢(xún)

1、空間Skyline查詢(xún) 匯報(bào)人匯報(bào)人：劉晴晴日日 期期：2016年年10月月6日日2. 提出問(wèn)題及相應(yīng)的準(zhǔn)備工作2 23. 解決問(wèn)題的方法4. 總結(jié)1. 研究背景主要內(nèi)容1. 研究背景 很多研究不同問(wèn)題的老師想利用他們吃飯的時(shí)間一起開(kāi)發(fā)一個(gè)項(xiàng)目，但他們?cè)诓煌牡胤焦ぷ?，這個(gè)開(kāi)會(huì)地點(diǎn)的選擇需要顧及每一位成員，考慮到時(shí)間問(wèn)題，希望餐廳距離每一位成員的距離能小于r，在選擇的時(shí)候發(fā)現(xiàn)很難有這樣一家餐廳。如果這幾位成員的位置是移動(dòng)的尋找這樣的一個(gè)餐廳就更具挑戰(zhàn)了。 假設(shè)把所有餐廳的信息裝入一個(gè)數(shù)據(jù)庫(kù)，老師們都在學(xué)校工作（地點(diǎn)固定），這個(gè)查找過(guò)程就是靜態(tài)Skyline項(xiàng)目，僅取決于數(shù)據(jù)庫(kù)本身，但是在用戶(hù)移

2、動(dòng)的情況下，餐廳位置的選擇就不僅取決于數(shù)據(jù)庫(kù)本身還取決于用戶(hù)的位置，這就是一個(gè)空間查詢(xún)，需要使用空間Skyline查詢(xún)。 2. 提出問(wèn)題及相應(yīng)的準(zhǔn)備工作2 23. 解決問(wèn)題的方法4. 總結(jié)1. 研究背景主要內(nèi)容那什么樣的查詢(xún)是空間Skyline查詢(xún)呢？ 給一些數(shù)據(jù)點(diǎn)P 和一些查詢(xún)點(diǎn)Q, 如上述問(wèn)題中的成員和餐廳，每個(gè)數(shù)據(jù)點(diǎn)到每個(gè)查詢(xún)點(diǎn)都有一段距離。 SSQ 檢索這些點(diǎn)P，找到?jīng)]有被別的點(diǎn)控制（取代）的點(diǎn)，即得到查詢(xún)區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)。這與普通Skyline最主要的區(qū)別是空間Skyline查詢(xún)依賴(lài)查詢(xún)點(diǎn)的位置Q。用戶(hù)的位置在變化相應(yīng)的查詢(xún)點(diǎn)也在變化。2.1提出問(wèn)題定義空間Skyline查詢(xún)普通Sky

3、line查詢(xún)define2.1提出問(wèn)題定義 2.1.1普通普通Skyline查詢(xún)查詢(xún)Given the two points p=(p1, . . . , pd) and p=(p1, . . . , pd) in Rd, p dominates p iff we have pi p，i for 1 i d and pj p，j for some 1 j d. To illustrate, in Figure 1b the point f=(3, 75) dominates the point d=(4, 125). Now,given a set of points P, the skyli

4、ne of P is the set of those points of P which are not dominated by any other point inP. The skyline of the points shown in Figure is the setS = a, c, e. 2.1.1普通普通Skyline查詢(xún)查詢(xún)The Skyline Query is to find the skyline set of the given database P considering attributes of the objects in P as dimensions o

5、f the space. Notice that every point of the skyline does not need to dominate a point of P. For instancein Figure, while the points c and e each dominate twoother points, the point a dominates no point.2.1.2 空間Skyline查詢(xún)查詢(xún) 相對(duì)于查詢(xún)Q來(lái)說(shuō)，P在空間上能取代P即P占主導(dǎo)地位。即有p P, qi Q s.t. D(p, qi) D(p, qi) 也就是說(shuō)如果每一個(gè)q的與P的距離都

6、小于或等于q到P的距離，P就可以在空間上主導(dǎo)PFigure 2 shows a set of nine 2-d points and two query points q1 and q2 The point p spatially dominates the point p as both q1 and q2 are closer to p than to p2.1.2 空間Skyline查詢(xún)查詢(xún) 總的來(lái)說(shuō)，空間輪廓查詢(xún)（SSQ）是查找給定集合P關(guān)于查詢(xún)集Q的空間輪廓點(diǎn)2.2 準(zhǔn)備工作理論前提： 兩個(gè)引理 三個(gè)定理圖：Voronoi圖 Delaunay圖 凸包準(zhǔn)備工作2.2.1 圖Vorono

7、i圖圖The region corresponding to the point p P contains all the points x Rd for which we have即圖中p的面積是最小的。 在每?jī)蓚€(gè)點(diǎn)中間畫(huà)一條二等分線(xiàn)，找到交點(diǎn)，刪掉多余的線(xiàn)段進(jìn)行調(diào)整，就能得到voronoi圖Delaunay圖圖2 22.2.1 圖在voronoi圖中把相鄰區(qū)域中的兩個(gè)點(diǎn)連接起來(lái)就得到delaunay圖 凸包凸包2.2.1 圖It is clear that the shape of the convex hull of a set P only depends on the convex

8、points in P. Consequently, the location of any non-convex point p P does not affect the shape of CH(P).可以理解為凸包是把所有頂點(diǎn)連在一起形成的面積最大的區(qū)域2.2 .2 理論2.2 .2 理論2.2 .2 理論2. 提出問(wèn)題及相應(yīng)的準(zhǔn)備工作2 23. 解決問(wèn)題的方法4. 總結(jié)1. 研究背景主要內(nèi)容2 23.解決問(wèn)題的方法Voronoi-based Spatial Skyline Algorithm（VS2）基于Voronoi圖的空間Skyline算法解決方法Branch-and-Bound

9、Spatial SkylineAlgorithm（B2S2）分值界定空間輪廓算法 3.1 B2S2 p代表數(shù)據(jù)點(diǎn)，q代表查詢(xún)點(diǎn)，N代表區(qū)域，e代表最小包圍盒，S(Q)表示關(guān)于查詢(xún)q的空間輪廓點(diǎn)，整個(gè)過(guò)程用R-樹(shù)表示如上圖 對(duì)于每一個(gè)點(diǎn)p我們定義 mindist(p,A)為p點(diǎn)到A區(qū)域中所有點(diǎn)的最小距離之和。右圖中，先用兩個(gè)最小面積的矩形框包住所有數(shù)據(jù)點(diǎn)p，然后遞歸的縮小范圍，得到離A最近的幾個(gè)區(qū)域，最后通過(guò)計(jì)算mindist(e,A), mindist(p,A),得到在查詢(xún)區(qū)域內(nèi)的三個(gè)數(shù)據(jù)點(diǎn)。即S(Q)=p1,p2,p3 3.1 B2S2B2S2 算法的偽代碼如下算法的偽代碼如下 3.2 VS2 畫(huà)一個(gè)矩形邊框圈住所有點(diǎn)，根據(jù)voronoi圖劃分總區(qū)域，然后根據(jù)定理1得出p1為關(guān)于查詢(xún)q的空間輪廓點(diǎn)，（這個(gè)點(diǎn)距離q點(diǎn)的距離和最小）然后由delaunay找出p1相鄰的點(diǎn)p3,p4,p5,p6,p8,并計(jì)算出mindist(p,A)進(jìn)行比較，以此類(lèi)推，得出S(Q) 3.2 VS2具體步驟如下： 3.2 VS2VS2 算法的偽代碼如下算法的偽代碼如下2. 提出問(wèn)題及相應(yīng)的準(zhǔn)備工作2 23. 解決問(wèn)題的方法4. 總結(jié)1. 研究背景主要內(nèi)容總結(jié) 通過(guò)舉例，我們了解了Skyline查詢(xún)和空間