# 臺灣博碩士論文加值系統

(3.236.84.188) 您好！臺灣時間：2021/08/05 01:19

:::

### 詳目顯示

:

• 被引用:0
• 點閱:99
• 評分:
• 下載:1
• 書目收藏:0
 傳統的最近鄰居查詢(NN)主要是尋找距離單一查詢點最近的資料點。近年來，也有許多關於處理多個查詢點的NN查詢或FN查詢的研究被提出。舉例來說，集合最近鄰居查詢(ANN)可以讓多個在不同地點的使用者尋找一間餐廳讓他們所有人到該餐廳的距離最短以節省交通費。使用者也能用集合最遠鄰居查詢(AFN)來從多個飯店預建地中尋找一塊距離所有潛在競爭對手的飯店最遠的地方來蓋新飯店以增加獲利。這些研究都只專注在尋找靠近某個集合或是遠離某個集合的資料點。然而，在現實生活中，使用者的查詢不會只想要靠近某個集合或是只希望遠離某個集合。例如，某購屋人在買房屋時會希望房屋靠近一些使用者喜歡的地點(例如：賣場、健身房...)，同時也遠離一些使用者不喜歡的地點(例如：平交道、機場...)。為了區別這兩種性質不同的查詢點，我們將使用者希望靠近的查詢點集合命名為正向查詢點集合，並將使用者希望遠離的查詢點集合命名為負向查詢點集合。我們提出一種新的查詢，結合了ANN查詢和AFN查詢，並稱作集合正向最近以及負向最遠鄰居查詢(ANPFNN)。給定一個使用者認為較佳的正向查詢點集合P = {p1, p2, ..., px}，跟一個使用者認為較不佳的負向查詢點集合N = {n1, n2, ..., ny}，以及一個資料點集合Q = {q1, q2, ..., qi}。ANPFNN查詢會從Q中找出距離集合P很近且距離集合N很遠的資料點。我們提出一種演算法能有效處理ANPFNN查詢。最後，我們藉由實驗來驗證演算法的效能。
 Traditional NN query focuses on efficiently finding the nearest neighbor of one single query point. Recently, researches are proposed for processing the nearest or farthest neighbor search of an aggregate query points. For instance, researchers use the aggregate nearest neighbor (ANN) search for users at different locations (query points) that want to find one restaurant (data point), which leads to the minimum sum of distances where they have to travel in order to meet. Users can also use aggregate farthest neighbor (AFN) search to find one of the building locations of a new hotel (query points) so as to maximize the aggregate distances to all the other existing hotels (data points) for reducing competition. However, these works mainly focus on finding either the aggregate nearest neighbors or the aggregate farthest neighbors. In reality, users not only have queries of aggregate nearest neighbors but also have queries of the aggregate farthest neighbors. He needs to make a decision through both aggregate nearest neighbors such as finding the objects that user prefer from the a set of data points and aggregate farthest neighbors which retrieves the objects that user dislike from another set of data points. In order to verify these two sets of query points, we named the objects which user prefer the Positive query set, and the objects that user dislike the Negative query set. Motivated by these observations, we propose a novel query by combining the aggregate nearest positive neighbor search and the aggregate farthest negative neighbor search together meaningfully. We name this query the Aggregate Nearest Positive and Farthest Negative Neighbors (ANPFNN) query. Given an object set Q = {q1, q2, ..., qi} where qi is a given object point, a positive query set P = {p1, p2, ..., px}, and a negative query set N = {n1, n2, ..., ny}, an ANPFNN query is to find the object points that are close to P and far from N. We propose a round-robin algorithm to retrieve the first aggregate nearest positive and farthest negative neighbors. Further, we use a pruning rule to efficiently filter out the answers. Our extensive evaluation results validate the effectiveness and efficiency of our algorithm.