本文選題：空間數(shù)據(jù)庫　切入點(diǎn)：空間數(shù)據(jù)多層網(wǎng)格索引　出處：《浙江大學(xué)》2017年博士論文　論文類型：學(xué)位論文

【摘要】：近年來,隨著互聯(lián)網(wǎng)、移動(dòng)通信以及感知定位技術(shù)的快速發(fā)展與應(yīng)用,各種移動(dòng)終端、圖像視頻采集設(shè)備以及社交平臺(tái)產(chǎn)生了大量的地理位置等低維空間數(shù)據(jù),和圖像、文本等高維空間數(shù)據(jù)。這些數(shù)據(jù)具有海量、異構(gòu)等特征,因而需要借助高效、準(zhǔn)確的處理模型及算法,來挖掘其內(nèi)在的信息與價(jià)值,從而支持相關(guān)行業(yè)進(jìn)行更好的決策。因此,如何高效、準(zhǔn)確地分析處理空間數(shù)據(jù)并挖掘其內(nèi)在價(jià)值和信息,已成為當(dāng)今計(jì)算機(jī)領(lǐng)域的重大前沿學(xué)術(shù)問題。在該領(lǐng)域問題中,空間數(shù)據(jù)最優(yōu)點(diǎn)查詢是近幾年快速興起的一類子問題。現(xiàn)有的空間數(shù)據(jù)查詢算法在處理復(fù)雜決策分析問題時(shí)會(huì)出現(xiàn)低效和低準(zhǔn)確度等不足,同時(shí)索引和查詢算法還面臨諸多難點(diǎn)和技術(shù)瓶頸。一方面,互聯(lián)網(wǎng)、移動(dòng)設(shè)備等每時(shí)每刻都在產(chǎn)生海量空間數(shù)據(jù)。這些海量數(shù)據(jù)是面向不同決策支持場(chǎng)景的,需要同時(shí)考慮數(shù)據(jù)點(diǎn)的變化特征、維度特征與度量空間特征等諸多因素。然而,目前國內(nèi)外索引技術(shù)大多針對(duì)靜態(tài)數(shù)據(jù)點(diǎn),很少有考慮時(shí)間維度的索引,同時(shí)現(xiàn)有算法很難做到查詢效率和查詢準(zhǔn)確性的兼顧。另一方面,針對(duì)不同的決策支持場(chǎng)景,最優(yōu)點(diǎn)查詢問題本身是復(fù)雜多變的。現(xiàn)有的(空間)最優(yōu)點(diǎn)查詢方法大多針對(duì)某一種特定的目標(biāo)方程進(jìn)行算法優(yōu)化,因此擴(kuò)展性差,執(zhí)行效率低,尤其是在處理高維或者路網(wǎng)數(shù)據(jù)集,以及在處理組合最優(yōu)點(diǎn)查詢問題時(shí),現(xiàn)有算法的準(zhǔn)確性和效率都隨著數(shù)據(jù)集復(fù)雜度的增加而急劇下降。基于上述兩點(diǎn)對(duì)國內(nèi)外研究現(xiàn)狀和趨勢(shì)的分析,本文研究并提出了面向不同應(yīng)用背景的高效的最優(yōu)點(diǎn)查詢算法以支持不同的分析與決策場(chǎng)景。主要包括:1.研究提出了歐氏空間下單一最優(yōu)點(diǎn)查詢算法,針對(duì)現(xiàn)有雙色反向最近鄰數(shù)目最大化問題在大數(shù)據(jù)場(chǎng)景下的算法效率低和可擴(kuò)展性差的不足,結(jié)合計(jì)算幾何等領(lǐng)域的經(jīng)典算法,提出了空間掃描策略、空間劃分和上限估計(jì)策略以及基于“弧重疊”的影響值計(jì)算方法。實(shí)驗(yàn)結(jié)果證明,提出的算法相比于已有算法,有更高的效率,更低的內(nèi)存占用率。2.研究提出了三維空間下單一最優(yōu)點(diǎn)查詢算法,首次解決了三維空間下雙色體反向最近鄰最大化問題。針對(duì)問題本身的空間特性和對(duì)索引效率的需求,提出了基于“細(xì)粒度”空間劃分和上限估計(jì)的三維空間最優(yōu)點(diǎn)查詢算法,算法具有高效準(zhǔn)確的特點(diǎn)。并且,證明了提出的算法擴(kuò)展到更高維空間的可行性,對(duì)于空間數(shù)據(jù)最優(yōu)點(diǎn)查詢問題在高維空間下的研究有重要的意義。3.研究提出了考慮服務(wù)設(shè)施點(diǎn)容量限制的空間最優(yōu)點(diǎn)查詢算法,首次解決了服務(wù)點(diǎn)容量受限場(chǎng)景下的空間數(shù)據(jù)最優(yōu)點(diǎn)查詢問題。通過研究空間數(shù)據(jù)庫以及運(yùn)籌學(xué)領(lǐng)域的帶有容量限制的服務(wù)設(shè)施點(diǎn)選址查詢問題,并分析現(xiàn)有算法的應(yīng)用場(chǎng)景局限性,最后提出了基礎(chǔ)搜索算法、基于漸進(jìn)式算法的搜索算法以及基于空間剪枝的搜索算法。實(shí)驗(yàn)證明提出的算法能準(zhǔn)確查詢空間最優(yōu)點(diǎn),并給出準(zhǔn)確的服務(wù)設(shè)施點(diǎn)和數(shù)據(jù)點(diǎn)之間的分配方案。4.研究提出了歐氏和路網(wǎng)空間中基于聚類算法的組合最優(yōu)點(diǎn)查詢算法。通過研究數(shù)據(jù)挖掘中的各種聚類方法,以及算法導(dǎo)論領(lǐng)域解決組合優(yōu)化問題的各種經(jīng)典近似算法,首次提出了基于聚類算法的組合最優(yōu)點(diǎn)查詢方案。提出的算法可以準(zhǔn)確返回一組最少的最優(yōu)位置點(diǎn)來覆蓋所有數(shù)據(jù)點(diǎn)。相比于傳統(tǒng)的組合最優(yōu)點(diǎn)查詢算法,具有更高的效率及更高的準(zhǔn)確度。同時(shí),首次將算法擴(kuò)展到了路網(wǎng)數(shù)據(jù)空間,提出了高效的路網(wǎng)空間距離計(jì)算策略。本文研究內(nèi)容主要圍繞空間數(shù)據(jù)最優(yōu)點(diǎn)查詢問題,研究了二維三維歐氏空間中的單個(gè)最優(yōu)點(diǎn)查詢問題,并擴(kuò)展到帶有容量限制的場(chǎng)景,以及歐氏及路網(wǎng)空間中的組合最優(yōu)點(diǎn)查詢問題。提出的算法能夠更高效、更正確地處理市場(chǎng)決策支持等問題。未來的研究方向包括動(dòng)態(tài)場(chǎng)景下及高維空間和度量空間下的最優(yōu)點(diǎn)查詢問題:主要問題是將組合最優(yōu)點(diǎn)問題擴(kuò)展到高維空間(圖片,文本)以及度量空間;以及研究利用分布式處理框架來處理空間數(shù)據(jù)最優(yōu)點(diǎn)查詢問題,使提出的查詢算法在大規(guī)模數(shù)據(jù)集上有更好的性能。
[Abstract]:In recent years, with the rapid development and application of Internet, mobile communication and location aware technology, various mobile terminals, video image acquisition equipment and social networking platform to produce a large number of geographical position and low dimensional data, and images, text and other data in high dimensional space. These data are massive, heterogeneous characteristics, which need the help efficient, accurate processing model and algorithm, to explore the inner information and value, so as to support related industries to make a better decision. Therefore, how to efficiently and accurately analyze the processing of spatial data mining and its intrinsic value and information, has become a major academic problem in computer field. In the field of space. The advantages of data query is a subclass in recent years the rapid rise of the problem. The algorithm in the analysis of problems of complex decision process will appear inefficient and low quasi existing spatial data query The accuracy and other issues, at the same time indexing and query algorithm still faces many difficulties and technical bottlenecks. On the one hand, the Internet, mobile devices at all times produce huge amounts of spatial data. These data support for different decision-making scenarios, taking into account the needs of the changing characteristics of data points, many factors dimensions and metric space characteristics however, at home and abroad are mostly based on the static data indexing technology, seldom consider the time dimension index, while the existing algorithm is difficult to achieve both efficiency and accuracy of query query. On the other hand, according to the different decision support scenarios, the advantages of query problem itself is complicated. Most existing (space) most of the advantages of the query for a particular kind of goal equation algorithm optimization method, it has poor scalability, low efficiency, especially in dealing with high dimensional data set or network, And the problems in dealing with the combination of the advantages of the query, the accuracy and efficiency of the existing algorithms with the increase of the complexity of the data set decreases. Analysis of the above two research status at home and abroad and based on the trend, this paper studies and presents the advantages of different application background for efficient query algorithm to support different scene analysis and the decision mainly includes: 1. research and put forward the Euclidean space of a single optimal query algorithm, aiming at the existing reverse nearest neighbor number maximization problem in large data scenarios of the algorithm of low efficiency and poor scalability, combined with the classical algorithms of computational geometry and other fields, put forward the strategy of spatial scanning, and space division the upper limit estimation strategy and based on the "arc overlap effect value calculation method. The experiment results prove that the proposed algorithm compared to the existing algorithm, more efficient, more low The memory occupancy rate.2. study presents the three-dimensional space of a single point query algorithm, for the first time to solve the three-dimensional space under the double color reverse nearest neighbor maximization problem. According to the characteristics of the problem itself and on the index of efficiency, based on "fine-grained" space partition and upper bound estimate of the three-dimensional space has the advantage of query algorithm the algorithm has the advantages of high efficiency, accurate. And the result shows that the proposed algorithm is extended to the feasibility of higher dimensional space, the research for spatial data query has the problem in high dimensional space under the study of the importance of.3. considering the facility capacity constraints of the space the advantages of query algorithm, for the first time to solve the spatial data point of service capacity constrained scenarios of the most advantages of query problem. Through the study of spatial database and operational research with limited capacity in the field of facility location check Question, and application scenario analysis of existing algorithm limitations, finally proposed based search algorithm, search algorithm based on the incremental algorithm and search algorithm based on spatial pruning. Experiments show that the proposed algorithm can accurately query space the advantages, and provide accurate service allocation scheme in.4. between data points and the service facilities the combination of clustering algorithm based on the advantages of query algorithm and Euclidean space. The network through a variety of clustering methods in data mining research field, and introduction to algorithms solve various classical combinatorial optimization problems of the approximate algorithm is proposed for the first time, combined clustering algorithm has the advantage of query scheme based on the proposed algorithm can accurately return a group. The optimal position to cover all the data points. The advantages compared to the traditional combined query algorithm, has higher efficiency and higher accuracy. At the same time, the algorithm is extended to the network data space, proposed network space distance efficient calculation method. This paper mainly focuses on the advantages of spatial data query, on a single two-dimensional Euclidean space and the advantages of query, and extended to the capacitated scene, and Euclidean and road space combination the most advantage of the query problem. The proposed algorithm can more efficient and more accurate handling market decision support and other issues. Future research directions include query optimal dynamic scenes and high dimensional space and metric space: the main problem is the combination of the most advantages extended to higher dimensional space (picture and text) metric space; and based on a distributed processing framework to deal with the advantages of spatial data query, the query algorithm is better in large-scale data sets on the Performance.

【學(xué)位授予單位】：浙江大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP311.13

【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

1 Jos C.Pereira;Fernando G.Lobo;;An Optimized Divide-and-Conquer Algorithm for the Closest-Pair Problem in the Planar Case[J];Journal of Computer Science & Technology;2012年04期

2 趙元;張新長;康停軍;;并行蟻群算法及其在區(qū)位選址中的應(yīng)用[J];測(cè)繪學(xué)報(bào);2010年03期

，

本文編號(hào)：1638317