度量空間中可調整距離函數之反向最近臨點查詢

近年來，反向K最近臨點(RkNN)的問題受到了合理的觀注，因為它可以被用在商業地點的選擇、以profile為基礎的行銷、或者資料探勘的用途上。然而，先前在度量空間中的RkNN演算法都不能允許使用者在每次查詢時使用不同的距離函式。在這篇論文中，我們定義了可調整距離函式之RkNN問題，並且提供一個完整的解決方案。

關鍵字

度量空間；反向最近臨點

並列摘要

In recent years, the reverse k-nearest neighbor (RkNN) problem in metric spaces has attracted reasonable attention because it can be applied to business location planning, profile-based marketing, clustering and outlier detection. However, previous works on the RkNN problem in metric spaces cannot allow users to assign different distance functions for distinct queries. In this thesis, we define the problem on RkNN query with adjustable functions. That is, for each distinct query, it can have its own distance function. To the best of our knowledge, this thesis is the first work solving the problem of RkNN with adjustable distances in metric spaces. We propose a generic framework to handle the RkNN queries with different distance functions. In our framework, a new index structure is built by using multiple distance functions. Therefore, some pruning rules determined by calculating the correlation between the distance function assigned by the user and those used to build the index structure can be provided to prune the irrelevant data points and then, the remainder candidates are really checked to see whether they are real results. The correctness of our pruning strategies is proved and the experiment results demonstrate the efficiency and effectiveness of our approach.

並列關鍵字

Metric Space ； Reverse Nearest Neighbor

參考文獻

Matthias Renz: “Efficient reverse k-nearest neighbor search in arbitrary metric

Matthias Renz, “Approximate reverse k-nearest neighbor queries in general

Efficient Model for Similarity Search in DNA Sequence Databases, ” SIGMOD

Record, Volume 33, pp. 39-44, 2004.

[4] Paolo Ciaccia, Marco Patella, “Searching in metric spaces with user-defined and

國際替代計量

度量空間中可調整距離函數之反向最近臨點查詢

未授權

主題瀏覽