In previous time, databases were used to store numeric or string data. But recently, people want to use databases to store other various data type: image, video, web documents, and financial time-series data, and so on. As a result, the dimensionality of data is increased rapidly. It causes a problem, ’curse of dimensionality’. Increasing of data dimensionality causes poor performance of index structures, which are used to search data in databases efficiently. To overcome ’curse of dimensionality’, the research on search space reduction has been conducted. However, some reducing methods do not guarantee no false dismissals. And some other methods incurs high computational cost.
This paper proposed a search space reduction technique which guarantees no false dismissals. It uses the cosine similarity values and the length of data vectors. First, to find a superset of the answer sets of queries, it uses the index which has the cosine similarity values between each vectors and predefined axes as its key values. And then, it uses the length of vectors in the superset to prune data vectors which are not in the answer sets of queries. And we develop query processing algorithms that uses proposed method. Our experimental results on real data sets show its performance.
And proposed method also can find the answer sets of queries in cosine similarity metric using the existing indexes in Euclidean distance metric. It may use for high dimensional data in cosine similarity metric, because it already contains a mechanism for dimension reduction.
이전의 데이터베이스는 숫자 혹은 문자로 된 데이터를 저장하는데 사용되어왔다. 하지만 최근들어 사람들은 사진이나 동영상, 웹문서, 재정적인 time-series 데이터 증 다양한 데이터를 저장하고 싶어 한다. 그 결과 데이터의 차원은 급격히 증가하였고, 이는 \\\\`curse of dimensionality\\\\` 문제를 야기했다. 데이터의 차원이 증가할수록 기존에 사용하던 인덱스의 성능은 급격히 저하되게 된다. 이러한 \\\\`curse of dimensionality\\\\`를 극복하기 위해 다양한 방법들이 연구되어 왔다. 하지만 많은 방법들은 \\\\`no false dismissal\\\\`을 보장하지 못하고, 몇몇은 복잡한 계산과정이 필요하다. 본 논문에서는 코사인 유사도와 데이터 벡터의 길이를 이용하여 \\\\`no false dismissal\\\\`을 보장하는 검색 공간 축소 기법을 제안하였다. 질의가 들어오면 인덱스를 이용하여 먼저 질의의 검색 결과를 모두 포함하는 superset을 찾는다. 이 때 인덱스는 미리 정의된 어떤 축과 데이터 벡터 간의 코사인 유사도를 key 값으로 사용한다. 그 후 데이터 벡터의 길이를 이용하여 질의의 검색 결과에 포함될 수 없는 데이터를 가려낸다. 본 논문에서는 이러한 기법을 이용한 질의 처리 알고리즘을 개발하였고 또 실제 데이터를 이용한 실험 결과를 통해 성능을 보였다. 그리고 제안된 방법은 많이 사용되는 Euclidean 거리함수 대신 코사인 유사도를 이용하는 질의에 대한 검색 결과도 찾을 수 있다. 그리고 이미 차원 축소 기법을 포함하고 있기 때문에 코사인 유사도를 이용한 다차원 데이터에 대해서도 사용이 가능하다.
