本文選題：LBS + 倒排網(wǎng)格索引�。� 參考：《大連海事大學(xué)》2013年碩士論文

【摘要】：基于位置服務(wù)(Location Based Services, LBS)應(yīng)用隨著地理信息系統(tǒng)(Geographic Information System,GIS)和移動(dòng)定位、3G技術(shù)的發(fā)展而迅猛增長(zhǎng),手持設(shè)備端要處理的空間數(shù)據(jù)也越來越大。本文在移動(dòng)云計(jì)算環(huán)境下開發(fā)LBS應(yīng)用大規(guī)模拼車系統(tǒng)。開發(fā)移動(dòng)云計(jì)算中的應(yīng)用,高效地處理日益增長(zhǎng)的海量數(shù)據(jù)是至關(guān)重要的需求以及挑戰(zhàn)。傳統(tǒng)的空間數(shù)據(jù)索引具有局限性,只有高擴(kuò)展性、分布式的空間索引才能更高效地完成大規(guī)模空間數(shù)據(jù)查詢分析的任務(wù)。目前有利用MapReduce模型對(duì)空間查詢索引進(jìn)行并行化實(shí)現(xiàn)的方法,如基于R-tree以及Voronoi圖的索引并行化。這些方法存在著不足：R-tree不適合于進(jìn)行并行化：基于Voronoi]圖的索引,可以用于并行化,然而進(jìn)行查詢時(shí)需要對(duì)局部索引進(jìn)行重建計(jì)算。 相比于以上兩種方法,網(wǎng)格索引更易于擴(kuò)展和并行化。而倒排索引利用有限的索引條目就可以為無限的數(shù)據(jù)點(diǎn)建立索引。結(jié)合網(wǎng)格索引和倒排索引的優(yōu)點(diǎn),本文提出倒排網(wǎng)格索引,利用MapReduce編程模型,將倒排網(wǎng)格索引建立過程并行化。倒排網(wǎng)格索引更簡(jiǎn)單、無共享而且松耦合,因此適合用于MapReduce并行化建立�；诘古啪W(wǎng)格索引,本文提出KNN算法的并行化,KNN查詢算法利用多線程方式進(jìn)行并行化,可以加速k近鄰的查找效率。并行化倒排網(wǎng)格索引和KNN查詢技術(shù),在處理大規(guī)模位置數(shù)據(jù)方面具有高效性。最后,本文在倒排網(wǎng)格索引結(jié)構(gòu)和并行KNN算法基礎(chǔ)上,開發(fā)了大規(guī)模拼車系統(tǒng),一方面驗(yàn)證了倒排網(wǎng)格索引和并行KNN算法處理大規(guī)�？臻g數(shù)據(jù)的性能,一方面滿足了人們出行便捷打車的需求。本文所提出的云計(jì)算空間索引以及查詢技術(shù)適用于開發(fā)基于位置服務(wù)的應(yīng)用,同時(shí)為L(zhǎng)BS應(yīng)用開發(fā)提供了新思路。
[Abstract]:With the development of Geographic Information system (GIS) and mobile positioning technology (3G), the application of location based Services (LBS) is growing rapidly. This paper develops a large scale carpool system for LBS applications in mobile cloud computing environment. The development of mobile cloud computing applications and efficient processing of the growing mass of data is a critical requirement and challenge. The traditional spatial data index has its limitations. Only with high scalability and distributed spatial index can the task of query and analysis of large-scale spatial data be completed more efficiently. At present, there are methods to implement spatial query index parallelization using MapReduce model, such as index parallelization based on R-tree and Voronoi diagram. These methods are not suitable for parallelization: indexes based on Voronoi diagrams can be used for parallelization, but local indexes need to be reconstructed when querying. Compared with the above two methods, the grid index is easier to extend and parallelize. The inverted index uses a limited number of index entries to index an infinite number of data points. Combined with the advantages of grid index and inverted index, the inverted grid index is proposed in this paper. Using MapReduce programming model, the establishment process of inverted grid index is parallelized. The inverted grid index is simpler, non-shared and loosely coupled, so it is suitable for MapReduce parallelization. Based on inverted grid index, a parallel KNN query algorithm is proposed in this paper, which can speed up the search efficiency of k-nearest neighbor. Parallel inverted grid indexing and KNN query techniques are efficient in dealing with large scale location data. Finally, on the basis of inverted grid index structure and parallel KNN algorithm, a large-scale carpool system is developed. On the one hand, the performance of inverted grid index and parallel KNN algorithm in dealing with large-scale spatial data is verified. On the one hand, it meets the demand of convenient taxi. The spatial index and query techniques proposed in this paper are suitable for the development of location-based applications and provide a new idea for LBS application development.
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：P208;TP3

【參考文獻(xiàn)】

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

1 趙華;王海闊;;移動(dòng)云計(jì)算綜述[J];電腦知識(shí)與技術(shù);2012年01期

2 李建江;崔健;王聃;嚴(yán)林;黃義雙;;MapReduce并行編程模型研究綜述[J];電子學(xué)報(bào);2011年11期

3 黃敬良;郝忠孝;;移動(dòng)對(duì)象的K個(gè)連續(xù)最近鄰查詢算法[J];哈爾濱理工大學(xué)學(xué)報(bào);2007年06期

4 宋曉宇;孫業(yè)挺;孫煥良;;支持動(dòng)態(tài)負(fù)載的移動(dòng)對(duì)象最近鄰查詢算法[J];計(jì)算機(jī)工程與應(yīng)用;2007年27期

5 朱承璋;張舸;楊紅;;淺析移動(dòng)云計(jì)算技術(shù)研究現(xiàn)狀[J];科技信息;2011年34期

6 閆成印;;2011年移動(dòng)互聯(lián)網(wǎng)回顧與未來展望[J];互聯(lián)網(wǎng)天地;2012年02期

7 王淼;;基于Voronoi圖的最近鄰查詢的索引結(jié)構(gòu)的研究[J];齊齊哈爾大學(xué)學(xué)報(bào);2006年06期

8 羅軍舟;金嘉暉;宋愛波;東方;;云計(jì)算:體系架構(gòu)與關(guān)鍵技術(shù)[J];通信學(xué)報(bào);2011年07期

9 鄭榕增;林世平;;基于Lucene的中文倒排索引技術(shù)的研究[J];計(jì)算機(jī)技術(shù)與發(fā)展;2010年03期

10 陳如明;;大數(shù)據(jù)時(shí)代的挑戰(zhàn)、價(jià)值與應(yīng)對(duì)策略[J];移動(dòng)通信;2012年17期

，

本文編號(hào)：2075729