1. NCCU Academic Hub
  2. 學術產出
  3. College of Informatics
  4. Proceedings
  5. Item

學術產出-Proceedings

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

題名 Finding targets with the nearest favor neighbor and farthest disfavor neighbor by a skyline query
作者 Lin, Y.-W.;Wang, E.T.;Chiang, Chieh-Feng;Chen, Arbee L. P.
陳良弼
貢獻者 資科系
關鍵詞 Algorithms; Experiments; Houses; Data points; Dominance rules; Farthest neighbors; Nearest neighbors; Skyline query; Skyline query processing; Spatial database; Synthetic data; Query processing
日期 2014-04
上傳時間 16-Jun-2015 15:57:19 (UTC+8)
摘要 Finding the nearest neighbors and finding the farthest neighbors are fundamental problems in spatial databases. Consider two sets of data points in a two-dimensional data space, which represent a set of favor locations F, such as libraries and schools, and a set of disfavor locations D, such as dumps and gambling houses. Given another set of data points C in this space as houses for rent, one who needs to rent a house may need a recommendation which takes into account the favor and disfavor locations. To solve this problem, a new two-dimensional data space is employed, in which dimension X describes the distance from a data point c in C to its nearest neighbor in D and dimension Y describes the distance from c to its farthest neighbor in F. Notice that the larger value is preferred in dimension X while the smaller value is preferred in dimension Y. Following the above dominance rule, the recommendation for the house renting can be achieved by a skyline query. A naïve method to processing this query is 1) to find the nearest neighbor from D and the farthest neighbor from F for each data point in C and then 2) to construct a new two-dimensional data space based on the results from 1) and to apply any of the existing skyline algorithms to get the answer. In this paper, based on the quad-tree index, we propose an efficient algorithm to answer this query by combining the above two steps. A series of experiments with synthetic data and real data are performed to evaluate this approach and the experiment results demonstrate the efficiency of the approach. Copyright 2014 ACM.
關聯 Proceedings of the ACM Symposium on Applied Computing, 2014, Pages 821-826, 29th Annual ACM Symposium on Applied Computing, SAC 2014; Gyeongju; South Korea; 24 March 2014 到 28 March 2014; 代碼 106778
資料類型 conference
DOI http://dx.doi.org/10.1145/2554850.2554863
dc.contributor 資科系
dc.creator (作者) Lin, Y.-W.;Wang, E.T.;Chiang, Chieh-Feng;Chen, Arbee L. P.
dc.creator (作者) 陳良弼zh_TW
dc.date (日期) 2014-04
dc.date.accessioned 16-Jun-2015 15:57:19 (UTC+8)-
dc.date.available 16-Jun-2015 15:57:19 (UTC+8)-
dc.date.issued (上傳時間) 16-Jun-2015 15:57:19 (UTC+8)-
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/75850-
dc.description.abstract (摘要) Finding the nearest neighbors and finding the farthest neighbors are fundamental problems in spatial databases. Consider two sets of data points in a two-dimensional data space, which represent a set of favor locations F, such as libraries and schools, and a set of disfavor locations D, such as dumps and gambling houses. Given another set of data points C in this space as houses for rent, one who needs to rent a house may need a recommendation which takes into account the favor and disfavor locations. To solve this problem, a new two-dimensional data space is employed, in which dimension X describes the distance from a data point c in C to its nearest neighbor in D and dimension Y describes the distance from c to its farthest neighbor in F. Notice that the larger value is preferred in dimension X while the smaller value is preferred in dimension Y. Following the above dominance rule, the recommendation for the house renting can be achieved by a skyline query. A naïve method to processing this query is 1) to find the nearest neighbor from D and the farthest neighbor from F for each data point in C and then 2) to construct a new two-dimensional data space based on the results from 1) and to apply any of the existing skyline algorithms to get the answer. In this paper, based on the quad-tree index, we propose an efficient algorithm to answer this query by combining the above two steps. A series of experiments with synthetic data and real data are performed to evaluate this approach and the experiment results demonstrate the efficiency of the approach. Copyright 2014 ACM.
dc.format.extent 176 bytes-
dc.format.mimetype text/html-
dc.relation (關聯) Proceedings of the ACM Symposium on Applied Computing, 2014, Pages 821-826, 29th Annual ACM Symposium on Applied Computing, SAC 2014; Gyeongju; South Korea; 24 March 2014 到 28 March 2014; 代碼 106778
dc.subject (關鍵詞) Algorithms; Experiments; Houses; Data points; Dominance rules; Farthest neighbors; Nearest neighbors; Skyline query; Skyline query processing; Spatial database; Synthetic data; Query processing
dc.title (題名) Finding targets with the nearest favor neighbor and farthest disfavor neighbor by a skyline query
dc.type (資料類型) conferenceen
dc.identifier.doi (DOI) 10.1145/2554850.2554863
dc.doi.uri (DOI) http://dx.doi.org/10.1145/2554850.2554863