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

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

3、line查詢define2.1提出問題定義 2.1.1普通普通Skyline查詢查詢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查詢查詢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查詢查詢 相對于查詢Q來說，P在空間上能取代P即P占主導(dǎo)地位。即有p P, qi Q s.t. D(p, qi) D(p, qi) 也就是說如果每一個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查詢查詢 總的來說，空間輪廓查詢（SSQ）是查找給定集合P關(guān)于查詢集Q的空間輪廓點(diǎn)2.2 準(zhǔn)備工作理論前提： 兩個引理 三個定理圖：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的面積是最小的。 在每兩個點(diǎn)中間畫一條二等分線，找到交點(diǎn)，刪掉多余的線段進(jìn)行調(diào)整，就能得到voronoi圖Delaunay圖圖2 22.2.1 圖在voronoi圖中把相鄰區(qū)域中的兩個點(diǎn)連接起來就得到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. 提出問題及相應(yīng)的準(zhǔn)備工作2 23. 解決問題的方法4. 總結(jié)1. 研究背景主要內(nèi)容2 23.解決問題的方法Voronoi-based Spatial Skyline Algorithm（VS2）基于Voronoi圖的空間Skyline算法解決方法Branch-and-Bound

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