질의범위측도를 이용한 K -최대근접질의 처리 방법에 관한 연구
A Study on the Processing of k -Nearest Neighbor Queries Using Range Measurement
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Queries on the k-nearest neighbors (kNN) algorithm frequently occur in geographic information system (GIS), pattern recognition, spatial data analysis, and image processing to find the k spatial objects that are closest to a given query point. To increase the efficiency of processing these queries, it is necessary to accurately measure their range and create the buckets to be considered spatial localities. In this paper, we propose a strategy of bucket-creation to minimize the processing cost of kNN queries. We do this by experimenting with a kNN query-processing algorithm that can accommodate a measurement to estimate the ranges to be used by the nearest neighbor queries. Results demonstrated that our kNN query algorithm, based on the range-estimation method, improved the number of accessible disks with increasing values of k.
Abstract
Queries on the k-nearest neighbors (kNN) algorithm frequently occur in geographic information system (GIS), pattern recognition, spatial data analysis, and image processing to find the k spatial objects that are closest to a given query point. To increase the efficiency of processing these queries, it is necessary to accurately measure their range and create the buckets to be considered spatial localities. In this paper, we propose a strategy of bucket-creation to minimize the processing cost of kNN queries. We do this by experimenting with a kNN query-processing algorithm that can accommodate a measurement to estimate the ranges to be used by the nearest neighbor queries. Results demonstrated that our kNN query algorithm, based on the range-estimation method, improved the number of accessible disks with increasing values of k.
참고문헌 (12)
- B. U. Pagel, "Deflating the Dimensionality Curse Using Multiple Fractal Dimension", Int. Cong. on Data Engineering, pp.589~598 (2000)
- A Framework for Accelerating High-dimensional NNQueries, "C. A. Lang", University of California, ~, pp.Technical Report TRCS01-04 (2001)
- D. Z. Liu, "Efficient k Nearest Neighbor Queries on Remote Spatial Databases Using Range Estimation", Int. Working Conf. on Scientific and Statistical Database Management (2002)
- H. Sato, "Intelligent Interactive Multimedia: Systems and Services", pp.385~397 (2012)
- M. Attique, "Efficient Processing of Continuous Reverse k Nearest Neighbor on Moving Objects in Road Networks", ISPRS Int. J. Geo-Inf (2016)
- N. Roussopoulos, "Nearest Neighbor Queries", Proc. of the ACM SIGMOD Int. Conf. pn Management pf Data, pp.71~79 (1995)
- S. Berchtols, "Indexing the Solution Space: A New Technique for Nearest Neighbor Search in High-dimensional Space", IEEE Trans. on Knowledge and Data Engineering, 12(1) (2000)
- N. Beckmann, "The R*-tree : an Efficient and Robust Access Method for Points and Rectangles", Proc. ACM SIGMOD Int. Conf. on Management of Data, pp.322~331 (1990)
- R. Benetis, "Nearest and Reverse Neighbor Neighbor Queries for Moving Objects", VLDB Journal, 15(3), pp.229~250 (2006)
- W. D. Bae, "Supporting Range Queries on Web Data Using k-Nearest Neighbor Search", Int. Sym. on Web and Wireless GIS, pp.61~75 (2007)
- Y. Wang, "Representing ordered order-k Voronoi diagrams", Int. Conf. on Advanced Information Management and Service (2011)
- 선휘준, "다차원 검색공간에서 공간관계를 고려한 공간색인방법", 산업기술연구논문지, 25(4), pp.107~115 (2020), 한국산업기술융합학회[DOI]