路網中互近鄰查詢和最大化雙色反近鄰查詢方法研究.pdf

1、空間數(shù)據庫是近年的熱點研究領域，而反近鄰查詢作為空間查詢的重要操作被廣泛研究。隨著研究深入，在反近鄰查詢的基礎上擴展了各種查詢處理方法來滿足人們新的查詢需求，如互近鄰查詢和最大化雙色反近鄰查詢。由于目前對它們的研究只是限定在歐式空間中，不能很好的為路網環(huán)境下的應用提供服務，因此，本文主要提出并研究了路網環(huán)境下的互近鄰查詢和最大化雙色反近鄰查詢問題。
　　首先，針對互近鄰查詢方法只能適用于歐式空間的不足，提出了適用于路網環(huán)境下的互近

2、鄰查詢問題。為解決該問題，根據互近鄰的定義提出了基礎算法。即先求出查詢點q的k近鄰作為候選，再驗證這些候選是否為真正的結果。在此基礎上，提出了優(yōu)化算法。根據落在對象點與查詢點最短路徑邊上的標記點個數(shù)直接排除掉一些錯誤的候選對象，以提高查詢效率。
　　其次，針對最大化雙色反近鄰查詢問題不能用于路網環(huán)境下的不足，提出了適用于路網環(huán)境下的最大化雙色反近鄰查詢問題。為解決該問題，利用 Dijkstra算法求出所有單顧客點集的有效點集和所有