비 정렬 이산 데이터 공간에서 유사 질의어 처리를 위한 효과적인 빈티지 포인트 생성 기법
An Effective Vantage Point Selection Method for Processing Similarity Queries in Non-ordered Discrete Data Space
- 주제(키워드) 멀티미디어 데이터베이스 , 비 정렬 이산 공간 , 범위 질의어 , 빈티지 포인트 , 거리기반 공간 변환
- 발행기관 서강대학교 일반대학원
- 지도교수 정성원
- 발행년도 2017
- 학위수여년월 2017. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000061236
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권보호를 받습니다.
초록/요약
최근 유사 질의어를 이용한 응용분야에서 데이터베이스의 크기가 증가하고 데이터 객체가 갖는 속성 값이 다양해짐에 따라서 효과적인 유사 질의어 처리를 위한 기술 개발이 요구되고 있다. 특히 DNA등의 순서가 없는 비 정렬 이산 데이터가 많아짐에 따라 해당 데이터를 이용하는 서비스에 대한 수요가 급증하고 있다. 비 정렬 이산 데이터는 순서가 존재하지 않기 때문에 유사 질의어 처리를 효율적으로 할 수 있는 기존의 데이터 인덱싱 방법을 사용 할 수 없는 문제점이 있다. 한편 빈티지 포인트에 의한 공간 변환은 데이터 객체간의 복잡한 거리 계산이 필요 없는 효율적인 유사 질의어 (범위 질의, kNN 질의) 처리에 적합한 거리 기반 벡터 공간으로 변환시킨다. 그런데 기존에 제안된 공간 변환 기법들은 데이터 사이의 순서가 존재하는 연속 공간에서 연속 공간으로의 공간 변환이기 때문에 비 정렬 이산 공간 데이터에는 적용하기 어렵다는 문제가 있었다. 위와 같은 문제를 해결하기 위하여 본 논문에서는 먼저 거리 카디널리티를 최대로하는 탐욕적 알고리즘 기반의 빈티지 포인트 선택 기법을 제안하고, 변환된 공간에서의 범위 질의와 kNN 질의 처리 알고리즘을 개발하였다. 실험 결과는 제안된 기법이 기존 비 정렬 이산 공간에서의 유사질의어 처리 성능에 비해 더 효과적인 성능을 보여준다.
more초록/요약
On the application field of similarity query, the size of database is increasing and the attribute value of data objects is becoming various. Accordingly, a request for development on the technology to process similarity query is rising. Among them, NDDS(Non-ordered Discrete Data Spaces) has the problem of not being able to use the existing data indexing method which can effectively process similarity query, because the data does not have any orders. There is a problem in that it is impossible to use an existing data indexing method which can efficiently process similar query terms because unordered discrete data does not exist in the order. On the other hand, space transformation by vantage point convert into vector space which is appropriate for efficient similarity query since it does not require complex distance calculations between data objects. However, space transformation method that previously suggested had a problem that is hard to apply on NDDS. To solve this type of problem, this paper proposes a vantage point selection method NDVPS with maximum cardinality based on greedy-algorithm, and developed a similarity query processing algorithm in the transformed space. The experiment result shows that our proposed method processes range query more efficiently in NDDS than the existing works.
more