考慮最近和最遠鄰居為基礎之天際線查詢

Skyline query processing considering nearest and farthest neighbors

林以文

指導教授 ： 陳良弼

國立清華大學/電機資訊學院/資訊工程學系/碩士(2012年)

https://doi.org/10.6843/NTHU.2012.00675

摘要

最近鄰居問題一直是在平面資料庫中熱門研究的題目之一，而它延伸的問題也同樣被重視。然而最遠鄰居也有一些相關的研究，但是卻沒有研究將最遠鄰居和最近鄰居做結合。在我們情境當中，我們假設有一個家庭想要在一些要賣的房子當中挑選對於自己適合的房子。對於一個家庭而言，他們不會希望房子接近一些不好的地方，像是工廠、夜店或公墓。除此之外，他們也同時希望能夠離一些地方越近越好，像是圖書館，公園甚至是上班上學的地方。而我們用最遠的好的設施和最近的不好的設施衡量這些房子適不適合。用最遠和最近鄰居來衡量，背後的意義是知道最近的不好的設施之距離後，我們可以確定其餘不好的設施都一定落在這個距離以外。反過來說，知道了最遠的好的設施的距離，其餘的好的設施都一定在這個距離以內。然而，一定會有一些房子在最遠的好的設施維度中表現突出，或是遠離不好的設施而表現突出，如何決定哪一個房子是適合的，也是問題之一。為了解決這個問題，我們用天際線查詢來回傳達案給使用者，讓使用者能夠在這些答案當中選自己想要的房子。我們是第一個解決在平面資料庫尋找最近鄰居和最遠鄰居的問題，我們提出了一個新的資料結構能夠有效率地找出最近和最遠鄰居。我們也提出了一些方法針對這個資料結構去快速的搜尋，並且提出一個演算法。而最後在我們的實驗當中，我們把我們的演算法和目前最常用來找最遠和最近鄰居的方法做比較，也驗證了我們的方法十分有效率。

關鍵字

天際線 ； 最近鄰居 ； 最遠鄰居 ； 平面資料庫

參考文獻

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD 1984:47-57

Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD 1995:71-79

King Lum Cheung, Ada Wai-Chee Fu: Enhanced Nearest Neighbour Search on the R-tree. SIGMOD Record (SIGMOD) 27(3):16-21 (1998)

Gísli R. Hjaltason, Hanan Samet: Distance Browsing in Spatial Databases. ACM Trans. Database Syst. (TODS) 24(2):265-318 (1999)

Thomas Seidl, Hans-Peter Kriegel: Optimal Multi-Step k-Nearest Neighbor Search. SIGMOD 1998:154-165