grid-file详细讲解整理版(内含代码).ppt

1、2016.01.02,Grid file,目,录,1,2,3,4,5,原始程式簡介,Grid file 類別介紹,API 介紹,使用說明,程序碼來源,01,PART ONE,原始程式簡介,#include grid/Grid.hpp #include data/Query.hpp #include data/Point.hpp #include util/Timer.hpp #include util/Util.hpp #include struc/List.hpp #include sort/Sort.hpp #include const.hpp,網格文件 數據查詢 坐標點 時間類 操作方法

2、 鏈表結構 排序 常量,test,int main(int argc, char* argv) if (argc != 10) printf(USAGE: index nXcell nYcell query_perc query_sz skewed num_point num_query navq_sz nav_stepXnn); getchar(); return -1; ,輸入10個參數，存入數組 否則異常,主函數,生成查詢,分配內存,建立索引,添加查詢到索引 服務器跟蹤運動物體的位置,移動點,02,PART TWO,Grid file 類別介紹,我們的“網格”的代碼是一個非常快速和有效執

3、行的處理連續範圍查詢大量的運動物體的頂部的一個經典問題。即使代碼已經執行前一段時間，我們不知道的任何其他的解決方案，速度更快。 在問題的設置，所述假設是，一個或多個伺服器跟蹤運動物體的位置。對象的數量可以非常高，例如，數以百萬計。在使用者對空間域的頂部發出大量的連續（監測）查詢。不像一次性查詢，連續查詢過的一定時間內執行，更新他們的結果作為情況的變化和對象移動。用於基於位置的發球，連續範圍的查詢（CRQ）是最重要的一個查詢類型。主要的挑戰是建立一個有效的和可擴展的 CRQ解決方案。 傳統的方法來處理CRQs是建立在對象上的索引（數據），並利用它進行查詢處理。在移動物體的環境，方法需要頻繁更新索

4、引，並由此經常導致性能很差。為了解決上述問題的效率和可伸縮性的挑戰，我們已經提出了一種新的計算技術，稱為查詢索引（QI）。查詢索引依靠扭轉查詢和數據的作用。即，空間索引（QIndex）是建立在連續查詢，並沒有索引是建立在對象（數據）。查詢結果通過發出點的查詢（即，對象的位置）到QIndex和尋找對象和查詢之間的匹配計算的。 我們已經意識到，對於移動的物體，CRQ問題可以（也應該）通過記憶體來解決。這是因為通過僅保留在主記憶體中和其餘的在磁片上的必要的資訊，所述數據適合於平均工作站的記憶體中。我們已經表明非常不同類型的索引在內存執行更好。具體地講，我們開發了網格索引技術用於處理查詢在運動對象的資

5、料庫，從而改進幅度超過競爭策略命令。如今，當然，很多研究工作使用記憶體基於網格的solutins為準則。 我們的解決方案的一個有趣的方面是，與許多其他的技術，它並沒有對許多常見的限制，如限制對象的速度和軌跡，使得更廣泛的應用了。,Choosing grid size,性能介紹,具體點查詢： 我們直接找到適當的桶，因而唯一的磁片I/O就是讀入該桶所需的操作。如果我們進行插入或刪除，則還需要一個磁片寫操作。若插入需要創建溢出塊，則需另一個寫操作。 部分匹配查詢 我們需要查找桶矩陣某一行或某列的所有桶。如果在一行或列上有許多桶，那麼磁片I/O的數可能很大，然而只有很小的一部分桶真正需要被訪問。 範圍

6、查詢 範圍查詢定義網格的一個矩形區域，且在覆蓋該區域的桶中找到的所有點都是該查詢的答案，除了搜索範圍邊界上的桶中的某些點外。不過，如果搜索區域包括大量的桶，那麼大多數桶必定是內部的，且這些桶的所有點都是查詢的結果。對於範圍查詢來說，由於我們需要檢查許多的桶，因此磁片I/O數可能會很大。 最近鄰查詢 給定一個點P，我們首先查找該點所屬的桶。如果我們至少找到了一個點，則我們對最近鄰點就有了一個候選點Q。但我們必須考慮P到該桶的邊界的距離是否小於P到Q的距離。如果存在這樣的邊界，那在每個這樣的邊界的相鄰桶也必須被搜索。,03,PART THREE,API 介紹,Generate points Poi

7、nt *pointArr = new Pointnum_point + 1; / last point has x = -1 Generate queries Query *queryArr; Allocating memory for map pPListNode q2pmap = new ListNodeMAX_MAP_SZ; Grid Grid *index = new Grid(numXCells, numYCells); Adding queries to index index-addQueryArr(queryArr, num_query); Do processing inde

8、x-getQ2P(pointArr, num_point, queryArr, num_query, q2pmap);,佈局,Model of object movement,Each object moves on a straight line path with a constant speed, and updates the server with its direction of movement and speed when they change. A similar assumption is that objects are moving with constant spe

9、ed on a known road. A mutual feature of these assumptions is that for each moving object the server can determine its location based upon a formula. In our experiments new locations of objects are generated at the beginning of each cycle. While some index structures for moving objects rely upon rest

10、ricted models of movement (e.g. 26), Query Indexing allows objects to move arbitrarily. Therefore, the objects can move anywhere in the domain, but the overall object distribution chosen for the experiment is maintained (uniform, skewed, etc.).,Query indexing,The problem of continuous query evaluati

11、on is: Given a set of queries and a set of moving objects, continuously determine the set of objects that are contained within each query. Notice that this approach can be easily extended to compute object to query mapping, handle region queries, answer simple density queries (e.g. monitor how many

12、people are in a building), compute similarity join for multidimensional data.,DynArray（1）,創建 template DynArray:DynArray(int max_sz) this-max_sz = max_sz; this-cur_sz = 0; arr = new DATAmax_sz; ,DynArray（2）,刪除 template DynArray:DynArray() delete arr; 清空 template bool DynArray:isEmpty() return cur_sz

13、= 0; ,插入 template void DynArray:insert(DATA q) /- check if need to generate new array - if (cur_sz = max_sz) /- allocate new array - DATA *new_arr = new DATAmax_sz * 2; /- copy old stuff to new array - memcpy(new_arr, arr, sizeof(DATA) * max_sz); /- delete old array - delete arr; /- adjust list - ar

14、r = new_arr; max_sz *= 2; arrcur_sz = q; cur_sz +; ,DynArray（3）,DynArray（4）,移動 template void DynArray:remove(DATA q) int find_i = -1; for (int i = 0; i cur_sz; i+) if (arri = q) find_i = i; break; if (find_i = -1) printf(nDynArray:remove() attempt to delete non-existing entry); getchar(); return; ar

15、rfind_i = arrcur_sz - 1; cur_sz -; ,List（1）,創建 template List:List() phead = NULL; /- template List:List() while( get() != NULL); template bool List:isEmpty() return phead = NULL; ,List（2）,插入 template void List:insert(DATA data) phead = new ListNode(data, phead); ,List（3）,訪問 template DATA List:get()

16、if (phead = NULL) return NULL; DATA data = phead-data; ListNode *tmp = phead; phead = phead-next; delete tmp; return data; ,清空 template void List:remove(DATA data) /- handle empty list - if ( isEmpty() ) printf(nList:remove() - attempt to delete from empty list); getchar(); return; /- handle case wh

17、en data is first elem - if (phead-data = data) ListNode *tmp = phead; phead = tmp-next; delete tmp; return; ,List（4）,/- data is not the first elem - ListNode *prev_node = phead; for (ListNode *cur_node = phead-next; cur_node != NULL; cur_node = cur_node-next) if (cur_node-data = data) /- remove cur_

18、node - prev_node-next = cur_node-next; delete cur_node; return; prev_node = cur_node; printf(nList:remove() - specified queue is not found in list); getchar(); return; ,04,PART FOUR,使用說明,Running the code for 500,000 moving objects and 25,000 continuos range queries of size 0.01x0.01 each using 100 x

19、100 grid.建立 100*100 網格，指定查詢大小範圍是 0.01*0.01 ，跟蹤500 000個運動物體并在連續範圍內進行25 000次查詢。,input：./index 100 100 0 0.01 0 500 25 0.001 0.0001 解釋：./index nXcell nYcell query_perc query_sz skewed num_point num_query navq_sz nav_stepX,output:,num_point=500K num_query=25K x_sz =0.010000 y_sz =0.010000 query_perc=0.000000 numXCells =100 numYCells =100 skewed =0 Generating points . uniform point 0.043000 secs/ 生成點數花費的時間 Generating queries . query U, query sides S 0.002000 secs/ 生成查詢數花費的時間