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

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

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