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

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

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