道路網(wǎng)中分布式關(guān)鍵詞查詢算法研究.pdf

1、道路網(wǎng)是現(xiàn)實(shí)生活中地圖的抽象，其結(jié)構(gòu)為一個(gè)帶邊權(quán)重的圖。其中，圖頂點(diǎn)代表在道路網(wǎng)中的一個(gè)路段交界位置或是一個(gè)重要地理位置（如景區(qū)，重要醫(yī)院，著名大學(xué)等），而兩點(diǎn)之間的連邊代表一個(gè)路段。連邊的權(quán)值代表該路段的長(zhǎng)度（或者需要行駛的時(shí)間）。有了這樣的道路網(wǎng)數(shù)據(jù)庫(kù)，可以提供基于位置的服務(wù)(Location-based Service)。代表性的應(yīng)用像Google Local和YahooMaps已經(jīng)得到越來(lái)越廣泛的應(yīng)用。一種更為廣義的道路網(wǎng)圖結(jié)構(gòu)

2、則是每個(gè)圖頂點(diǎn)都附有相應(yīng)的描述信息，如“復(fù)旦大學(xué)正校門”可以描述復(fù)旦大學(xué)正校門地理位置對(duì)應(yīng)的頂點(diǎn)。有了帶文本的道路網(wǎng)數(shù)據(jù)庫(kù)，我們可以進(jìn)行基于關(guān)鍵詞的位置信息查詢，如“找到距離復(fù)旦大學(xué)正校門500米以內(nèi)的郵局”。這類基于關(guān)鍵詞的道路網(wǎng)查詢豐富了基于位置的服務(wù)。我們將這類空間關(guān)鍵詞查詢嚴(yán)格定義為關(guān)鍵詞組合查詢。
　　本文首先研究了道路網(wǎng)中關(guān)鍵詞組合查詢?nèi)绾卫梅植际江h(huán)境加速查詢。我們提出分布式索引技術(shù)來(lái)加快查詢計(jì)算，并從理論上證明了索

3、引空間的最優(yōu)意義。其次，我們指出，提出的分布式索引技術(shù)適用于一個(gè)更廣義的查詢類，我們稱其為Q類，并證明提出的方法對(duì)于整個(gè)Q類查詢的可行性。Q類查詢能夠處理諸如“找到距離超市和醫(yī)院都比較近的位置”，“找到距離當(dāng)前位置500米以內(nèi)的所有中餐館”等查詢。我們考慮了兩種實(shí)驗(yàn)設(shè)置:Hadoop MapReduce集群以及一個(gè)基于協(xié)調(diào)器的集群，并分別提出了分布式算法。在基于協(xié)調(diào)器的分布式環(huán)境中，我們通過(guò)實(shí)驗(yàn)比較了NPD索引算法相比于集中式算法的效率