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

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

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

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