DNN 모델을 이용한 기계 학습 기반 k-최근접 질의 처리 최적화 기법 = k-NN Query Optimization Scheme Based on Machine Learning Using a DNN Model

국문 초록 (Abstract)

본 논문에서는 고차원의 특징 벡터에서 질의와 가장 가까운 k개의 데이터를 찾는 k-최근접 질의 최적화 방법을 제안한다. k-최근접 질의는 k개의 데이터를 포함할 가능성이 있는 범위를 기반으로 범위 질의로 변환되어 처리하는 기법이다. 본 논문에서는 처리 비용을 감소시키고 검색 속도를 가속화 할 수 있는 최적의 범위를 도출하기 위해 k-최근접 질의 처리 시 DNN 모델을 이용한 최적화 기법을 제안한다. 제안하는 기법은 온라인 모듈과 오프라인 모듈로 구성된다. 온라인 모듈에서는 클라이언트로부터 요청을 받아 실제 질의를 처리한다. 오프라인 모듈에서는 과거 최적화 기법의 결과를 학습 로그로 사용한 DNN 모델로 최적의 범위를 도출하고 온라인 모듈로 전달한다. 제안하는 기법의 우수성 및 타당성의 입증을 위하여 다양한 성능 평가를 수행한다.

다국어 초록 (Multilingual Abstract)

In this paper, we propose an optimization scheme for a k-Nearest Neighbor(k-NN) query, which finds k objects closest to the query in the high dimensional feature vectors. The k-NN query is converted and processed into a range query based on the range that is likely to contain k data. In this paper, we propose an optimization scheme using DNN model to derive an optimal range that can reduce processing cost and accelerate search speed. The entire system of the proposed scheme is composed of online and offline modules. In the online module, a query is actually processed when it is issued from a client. In the offline module, an optimal range is derived for the query by using the DNN model and is delivered to the online module. It is shown through various performance evaluations that the proposed scheme outperforms the existing schemes.

참고문헌 (Reference)

1 최도진, "스파크 환경에서 내용 기반 이미지 검색을 위한 효율적인 분산 인-메모리 고차원 색인 기법" 한국정보과학회 47 (47): 95-108, 2020

2 H. V. Jagadish, "iDistance : An Adaptive B+-tree based Indexing Method for Nearest Neighbor Search" 30 (30): 364-397, 2005

3 Zhiyin Zhang, "Sextant: Grab's Scalable In-Memory Spatial Data Store for Real-Time K-Nearest Neighbour Search" 2019

4 H. J. Jang, "Nearest base-neighbor search on spatial datasets" 62 (62): 867-897, 2020

5 D. H. Yan, "K-nearest Neighbors Search by Random Projection Forests" 2019

6 Gallego, Antonio-Javier, "Insights into efficient k-Nearest Neighbor classification with Convolutional Neural Codes" 2020

7 K. Li, "Fast k-nearest neighbour search via prioritized DCI"

8 J. M. Lee, "Fast k-nearest neighbor searching in static objects" 93 (93): 147-160, 2017

9 J. Maillo, "Fast and Scalable Approaches to Accelerate the Fuzzy k-Nearest Neighbors Classifier for Big Data" 28 (28): 874-886, 2020

10 Abu-Aisheh, Zeina, "Efficient k-nearest neighbors search in graph space" 134 : 77-86, 2020

11 D. G. Lowe, "Distinctive image features from scale-invariant keypoints" 60 (60): 91-110, 2004

12 R. H. R. Hahnloser, "Digital Selection and Analogue Amplification Coexist in aCortex-Inspired Silicon Circuit" 405 : 947-951, 2000

13 J. Schmidhuber, "Deep Learning in Neural Networks : An Overview" 61 : 85-117, 2015

14 Peng Dai, "Combination of DNN and improved KNN for indoor location fingerprinting" 2019

15 H. C. V. Ngu, "B+-Tree Construction on Massive Data with Hadoop" 22 (22): 1011-1021, 2019

16 Wen Li, "Approximate nearest neighbor search on high dimensional data-experiments, analyses, and improvement" 2019

17 K. Atefi, "Anomaly Analysis for the Classification Purpose of Intrusion Detection System with K-Nearest Neighbors and Deep Neural Network" 2019

18 Utsav Sheth, "An Application of Storage-Optimal MatDot Codes for Coded Matrix Multiplication : Fast k-Nearest Neighbors Estimation" 1113-1120, 2018

19 Diederik P. Kingma, "Adam : A method for stochastic optimization"

20 Yiwei Pan, "A new fast search algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based check strategy" 189 : 105088-, 2020

21 H. Wei, "A kd tree-based Algorithm to Parallelize Kriging Interpolation of Big Spatial Data" 52 (52): 40-57, 2015

22 Vajda, Szilárd, "A fast k-nearest neighbor classifier using unsupervised clustering" Springer 2016

23 Mishra, Gaurav, "A fast hybrid clustering technique based on local nearest neighbor using minimum spanning tree" 132 : 28-43, 2019