- 學位論文
可供快速查詢的空間物件統計資料索引裝置
A Spatial Object Index Device with Statistical Data for Quick Query
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
近年來由於地理資訊系統和影像資料查詢的蓬勃發展，現在社會對於空間資料的處理愈來愈重視，如何快速取得多樣化資料，是相當值得探討的研究議題。以各種不同範圍的多樣化統計資料為例，這些統計資料是需要花很多時間來計算大量數據，若是能事先計算好相關統計資料，當需要這些統計資料時，就可以立即取得，省去重複計算時間。快速查詢預先準備好的統計資料可以有幾種索引方式呈現，例如表格、鏈結串列、樹狀結構等，分別適用在各種維度的資料。空間資料因具備二維以上，使用樹狀索引比較適合。本研究結合資料預先彙總與樹狀索引的概念，將小範圍的基本資料，逐層往上彙總成中甚至大範圍的統計資料，再將不同範圍的統計資料存放在R-tree的不同節點entry內，以供快速取得。 R-tree節點的每個entry描述資料空間裡的某個特定範圍物件，為了使空間資料應用更多樣化，本研究在R-tree節點的entry上附加十五個具有代表性的統計項目，並預先計算好各項彙總資料值，同時將其命名為ASD-R-tree (Appending Statistical Data R-tree)。所提出的統計項目依特性可分成三種，分別是與空間物件個數、空間物件面積、和空間物件重疊區域有關。第一種與空間物件個數有關的統計項目，有物件個數、個數平均值、個數標準差、個數最少值、個數最多值等五項；第二種與空間物件面積有關的統計項目，有物件面積、面積平均值、面積標準差、總和面積最少值、總和面積最多值、單個面積最小值、單個面積最大值等七項；第三種與空間物件重疊區域有關的統計項目，有涵蓋所有重疊區域的最小矩形、面積最大的重疊區域、同時被最多物件重疊的區域等三項。ASD-R-tree上層節點entry內的每個統計項目值是彙總下層所有節點entry內的相關統計項目值而得。當使用者欲查詢某個大範圍區域內的某些統計資料時，可以直接存取ASD-R-tree上層代表該範圍的entry所包含的那些統計資料，而不需要到下層的各個小範圍區域，實際彙總所有相關節點的個別統計資料，省去許多節點entry的資料搜尋、計算、和彙總時間。
並列摘要
As geographic information system and image retrieval become popular, the management of spatial data is more and more important in recent years. It is worth to discuss that the research theme about how to get various data quickly. As an example of various statistical data at different regions, it spends much time on computing many numerics to get statistical data. If statistical data is pre-calculated already, the user can get it immediately to omit the computing time. There are some index methods to present pre-calculated, statistical data such as table, link list, and tree structure for various dimensional data, respectively. The tree structure is better for index of spatial data because spatial data has two or more dimensions. With the idea of combining pre-calcuated sum data and tree structure index, this research first calculates the basic values of small regions to statistical values of moderate and large regions; then saves the statistical data to different entries of R-tree nodes for quickly obtaining. Each entry in R-tree node describes a specific spatial object in data space. For the variety of spatial data applications, this research appends fifteen representative, pre-calculated statictiscal data items to every entry in an R-tree node. And, it is called ASD-R-tree (Appending Statistical Data R-tree). The proposed statistical data items can be divided into three types, (1) the quantity of spatial object, (2) the area of spatial object, and (3) overalp region of spatial object. The first type items includes the object number, the mean of object number, the standard deviation of object number, the least value of object number, and the most value of object number. The second type items includes the object area, the mean of object area, the standard deviation of object area, the least value of object area, the most value of object area, the minimum of an object area, and the maximum of an object area. The third type items contains the minimum rectangle of covering overlap regions, the overlapped region with the maximum area, and the region overlapped by the most objects. Each statistical value in an entry of an upper-level ASD-R-tree node is calculated from all related statistical values in the entries of the lower-level ASD-R-tree nodes. When a user queries some statistical data of a large region, we can directly access and quickly return to the user the desired statical data in the specific entry, which corresponds to the large region, of an upper-level ASD-R-tree node. We do not need to compute and to collect the statistical data in the entries, which correspond to some small regions, of several lower-level ASD-R-tree nodes. This mechanism saves much time of search, calculation, and collection of statistical data in some entries.
參考文獻
[3] 陳佳揚，「範圍查詢近似總和之動態資料方體」，碩士論文，元智大學，1992。
[6] R. Agrawal, A. Gupta, and S. Sarawagi, “Modeling Multidimensional Databases,” in Proc. of the 13th Int. Conf. on Data Engineering, pp. 232-243, 1997.
[7] N. Beckmann, H. P. Kriegel, R. Schneider, and B. Seeger, “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,” in Proc. of ACM SIGMOD Int. Conf. Management of Data, pp. 322-331, 1990.
[8] J. L. Bentley, “Multidimensional Binary Search Trees Used for Associative Searching,” Communications of the ACM, Vol. 18, pp.509-517, 1975.
[9] S. Berchtold, D. A. Keim, and H. P. Kriegel, “The X-tree: An Index Structure for High-Dimensional Data,” in Proc. of the 22th Int. Conf. on VLDB, pp. 28-39, 1996.