跳到主要內容

臺灣博碩士論文加值系統

(3.236.84.188) 您好!臺灣時間:2021/08/05 01:19
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:沈奕廷
研究生(外文):I-TingShen
論文名稱:尋找距離正向集合最近且距離負向集合最遠之鄰居
論文名稱(外文):Finding both Aggregate Nearest Positive and Farthest Negative Neighbors
指導教授:李強李強引用關係
指導教授(外文):Chiang Lee
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:52
中文關鍵詞:集合正向最近以及負向最遠鄰居查詢集合最近鄰居查詢集合最遠鄰居查詢
外文關鍵詞:aggregate nearest positive and farthest negative neighbor searchnearest neighborfarthest neighboraggregate nearest neighboraggregate farthest neighborskyline
相關次數:
  • 被引用被引用: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.
[1] J. Zhang, M. Zhu, D. Papadias, Y. Tao, and D. L. Lee, “Location-based spatial queries, in Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pp. 443–454, 2003.
[2] N. Roussopoulos, S. Kelley, and F. Vincent, “Nearest neighbor queries, in Proceedings of the 1995 ACM SIGMOD international conference on Management of data, pp. 71–79, 1995.
[3] F. Korn, N. Sidiropoulos, C. Faloutsos, E. Siegel, and Z. Protopapas, “Fast nearest neighbor search in medical image databases, in Proceedings of the 22nd International Conference on VLDB, pp. 215–226, September 1996.
[4] K. Mouratidis and D. Papadias, “Continuous nearest neighbor queries over sliding windows, IEEE Transactions on Knowledge and Data Engineering, June 2007.
[5] T. Seidl and H. Kriegel, “Efficient user-adaptable similarity search in large multimedia database, in Proceedings of International Conference on VLDB, pp. 506–515, August 1997.
[6] U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, “Advances in knowledge discovery and data mining, in AAAI Press/MIT Press, 1996.
[7] B. Cui, B. C. Ooi, J. Su, and K.-L. Tan, “Indexing high-dimensional data for efficient in-memory similarity search, IEEE Transactions on Knowledge and Data Engineering, vol. 17, March 2005.
[8] H. Lu, B. C. Ooi, H. T. Shen, and X. Xue, “Hierarchical indexing structure for efficient similarity search in video retrieval, IEEE Transactions on Knowledge and Data Engineering, vol. 18, 2006.
[9] C. Bohm, B. C. Ooi, C. Plant, and Y. Yan, “Efficiently processing continuous k-nn queries on data streams, in Proceedings of IEEE 23rd International Conference on Data Engineering, April 2007.
[10] B. Zheng, J. Xu, W. chien Lee, and D. L. Lee, “Energy conserving air indexes for nearest neighbor search, in Proceedings of the 9th International Conference on Extending Database Technology, pp. 48–66, March 2004.
[11] Y. Tao, D. Papadias, and Q. Shen, “Continuous nearest neighbor search, in Proceedings of the 28th international conference on Very Large Data Bases, August 20-23 2002.
[12] X. Xiong, M. F. Mokbel, and W. G. Aref, “Sea-cnn: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases, in Proceedings of 21st International Conference on Data Engineering, pp. 643–654, April 2005.
[13] D. Papadias, Y. Tao, K. Mouratidis, and C. Hui, “Aggregate nearest neighbor queries in spatial databases, ACM Transactions on Database Systems, vol. 30(2), June 2005.
[14] M. Yiu, N. Mamoulis, and D. Papadias, “Aggregate nearest neighbor queries in road networks, IEEE Transactions on Knowledge and Data Engineering, vol. 17(6), June 2005.
[15] Y. Gao, L. Shou, K. Chen, and G. Chen, “Aggregate farthest-neighbor queries over spatial data, Lecture Notes in Computer Science, vol. 6588/2011, 2011.
[16] S. Borzsonyi, D. Kossmann, and K. Stocker, “The skyline operator, in Proceedings of 17th International Conference on Data Engineering, pp. 421–430, 2001.
[17] F. Aurenhammer, “Voronoi diagrams -a survey of a fundamental geometric data structure, ACM Computing Surveys, vol. 23(3), September 1991.
[18] H. Samet, “The design and analysis of spatial data structures, Addison-Wesley, ISBN 0-201-50255-0, 1990.
[19] H. Samet, “Application of spatial data structure, Addison-Wesley, ISBN 0-201-50300-X, 1990.
[20] A. Guttman, “R-trees: A dynamic index structure for spatial searching, in Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984.
[21] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seege, “The r*-tree: an efficient and robust access method for points and rectangles, in Proceedings of the 1990 ACM SIGMOD international conference on Management of data, 1990.
[22] G. Hjaltason and H. Samet, “Distance browsing in spatial databases, ACM Transactions on Database Systems, vol. 24(2), June 1999.
[23] J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, “Skyline with presorting, in Proceedings of the 19th International Conference on Data Engineering, March 2003.
[24] H. Lu and M. L. Yiu, “On computing farthest dominated locations, IEEE Transactions on Knowledge and Data Engineering, vol. 23(6), pp. 928–941, June 2011.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top