In recent years, by the advance of the information techniques, the information of multi-dimensional objects and spatial objects is available in the major Web service companies such as Google, Naver, Facebook, Twitter, Coupang, Amazon.com and etc. It gives us diverse opportunities for devising advanced search methods which satisfy the promising demands of the users of diverse online services. For the last decade, as an advanced search method, reverse searches have been introduced in the database area. The purpose of the reverse search is, given a query object, find the other objects which consider the query object as one of the their most favorite objects. For example, there are restaurants and users. Given a restaurant, the reverse search finds all the users such that the restaurant is one of their most attractive restaurants. We can utilize the reverse search for market analysis, advertisement targets recommendation, assisting resource allocation and etc. Because the dataset consists of two types of objects (e.g., restaurant and user), the search of the example is formally called a bichromatic reverse search. This dissertation deals with the problems of bichromatic reverse searches for multi-dimensional objects and spatial objects.
First, we study the reverse nearest neighbor search problem considering not only the spatial distance but also the non-spatial aspect. With the recent surge in the use of the location-based service(LBS), the importance of spatial database queries has increased. The reverse nearest neighbor (RNN) search is one of the most popular spatial database queries. In most previous studies, the spatial distance is used for measuring the distance between objects. However, as the demands of users of the LBSs are becoming more complex, considering only the spatial factor as a distance measure is not sufficient. For example, through a hotel finding service, users want to choose a hotel considering not only the spatial distance, but also the non-spatial aspect of the hotel such as the quality which can be represented by the number of stars. Therefore, services that consider both spatial and non-spatial factors in measuring the distance are more useful for users. In such a case, techniques proposed in the previous studies cannot be used since the distance measure is different. In this dissertation, we propose an efficient method for the RNN search in which a distance measure involves both the spatial distance and the non-spatial aspect of an object.
Second, we extends the reverse search by using multi-dimensional objects that are more general than the spatial objects with a non-spatial aspect. The reverse top-k search problem has been an active topic in recent years, as a variant of the top-k search problem. Suppose that there are a set of objects and a set of weight vectors in the d-dimensional space. Then, given a query object, the reverse top-k(RTOPk) search is to find a subset of weight vectors such that, for each weight vector in the set, the query object’s ranking score is better than the score of at least one object in the top-k search result. The applications of the RTOPk search include the analysis of advertisement targets and product influences. Many studies on the RTOPk search have been conducted in the last few years. However, the existing methods for the RTOPk search only focus on how to efficiently process multiple evaluations of the weight vectors which check whether the weight vectors are included in the result without efficient pruning methods. We propose an efficient method for the RTOPk search that prunes weight vectors and objects before the main query processing step in order to avoid unnecessary evaluations and unnecessary visits to the objects which cannot affect the result of the weight vector evaluations. In contrast to existing approaches, the proposed method prunes each unnecessary weight vectors without traversing objects, and filters out unnecessary objects without considering the weight vectors. In addition, we propose an efficient algorithm to process the RTOPk search, which improves the efficiency by reducing the gap between the estimated bounds and the real bounds of the ranking score by using an angle-based approach.
From extensive experimental results, we show that the proposed methods are more efficient than comparison methods. For the reverse nearest neighbor search with a non-spatial aspect, the experimental results show that the proposed method is significantly efficient and scalable than adapted versions of existing methods. For the reverse top-k search, the experimental results based on synthetic datasets and a real dataset show that the efficiency of the proposed method is better than existing methods for the RTOPk search.
최근 정보 기술의 발달로 구글, 네이버, 페이스북, 트위터, 쿠팡, 아마존 닷컴 등의 주요 웹 서비스 회사들은 다차원 객체와 공간 객체에 대한 정보들을 수집하여 활용할 수 있게 되었다. 이로 인해 다양한 온라인 서비스의 사용자들이 요구하는 점들을 충족하는데 필요한, 보다 더 진보된 검색을 할 수 있는 기회를 얻게 되었다. 지난 수년간 데이터베이스 분야에서는 진보된 검색으로서 역검색 방법들이 소개되어왔다. 역검색의 목적은 질의 객체가 주어졌을 때, 해당 질의 객체를 가장 흥미로운 객체 중의 하나로 여기는 다른 모든 객체를 찾는 것이다. 예를 들어 레스토랑들과 레스토랑을 이용하고자 하는 고객들이 있다고 가정하자. 질의로 한 레스토랑이 주어진다면, 역 검색의 목적은 이 질의 레스토랑을 가장 좋게 평가하는 모든 고객들의 리스트를 찾는 것이다. 역검색은 시장분석, 출시상품의 예상 파급력,광고 대상 추천, 최적화된 자원 배치등의 문제에 활용할 수 있다. 앞의 예에서 보았듯이,레스토랑과 고객으로 데이터 셋이 두 가지의 데이터로 구성되어 있는데, 우리는 이와 같은 검색을 이종 데이터로 구성된 다차원 객체들을 위한 역검색이라 부른다. 본 학위 논문은 이종 데이터로 구성된 다차원 객체들을 위한 역검색 문제를 다룬다.
첫째, 공간 정보 뿐만 아니라, 비공간 정보를 고려하는 역근접 검색을 효율적으로 처리하는 방법을 연구한다. 최근 위치기반서비스의 발전으로, 공간 데이터베이스 질의들의 중요도가 높아졌다. 역근접 검색을 그 중에 가장 유명한 공간 데이터베이스 검색들 중에 하나이다. 대부분의 기존 연구에서는 객체들 간의 거리를 계산하는데 유클리디안 디스턴스를 기반으로 하는 공간거리만을 고려하였다. 하지만 위치기반서비스 사용자들의 요구가 복잡해짐에 따라 객체들 간의 거리를 측정하는데 공간 거리만을 활용하는 것은 충분하지 못하다. 예를 들어, 여행지에서 호텔을 찾는 서비스가 있다고 하자. 사용자들은 여행지로부터의 거리만을 고려하는 것이 아닌, 별의 갯수로 표현되는 서비스 등급 등을 함께 고려하게 된다. 따라서 공간적인 요소뿐만 아니라 비공간적인 요소를 함께 고려하는 것은 웹 사용자들에게 더욱 유용한 서비스를 제공할 수 있다. 하지만 이런 경우, 기존의 공간거리만을 기반으로 한 역근접 검색 방법들은 무용지물이 되므로, 효율적인 검색을 위해서는 새로운 질의처리 방법을 고안해야 한다. 본 학위 논문에서는 이 문제를 해결하기 위하여 공간 및 비공간적인 요소들을 모두 고려하는 새로운 거리 측정 방법을 제안한다. 또한, 이를 기반으로 하는 역근접 검색질의를 효율적으로 처리하는 방법을 제안한다.
둘째, 앞의 역근접 검색 문제를 다차원 객체를 사용하는 역검색 문제로 확장한다. 다차원 객체는 앞서 살펴본 공간 및 비공간 정보를 모두 포함하는 데이터의 일반적인 형태로 볼 수 있다. 이 검색 방법을 역순위 검색 방법으로 명명한다. 역순위 검색 방법은 순위 검색 연구의 변형으로서 활발히 연구가 되고 있는 분야이기도 하다. 다차원 공간에 표현되는 객체들의 집합과 가중치 벡터들의 집합이 존재하며, 질의 객체가 주어졌다고 가정하자. 이러한 환경에서, 역순위 검색은 질의 객체의 랭킹스코어가 전체 객체들 중에 상위 몇 번째 이내의 순위를 가지게 하는 모든 가중치 벡터들을 찾는 문제이다. 역순위 검색은 아이템의 광고 타겟을 결정하거나 제품의 영향력을 구하는데 활용이 되고 있다. 지난 몇 년간 역순위 검색을 효율적으로 처리하기 위한 다양한 방법들이 고안되었다. 하지만 기존의 방법들은 효율적인 프루닝 방법을 고려하지 않은 상태에서 가중치 벡터들을 기반으로 객체에 대한 여러번의 랭킹스코어 계산을 빠르게 해결하려는 시도에 국한이 되었다. 우리는 객체들의 집합과 가중치 벡터들의 집합 각각을 프루닝하기 위해 서로를 탐색할 필요 없는 효율적인 프루닝 기법을 고안하여,질의처리 결과에 영향을 주지 않는 객체 및 가중치벡터들을 검색 대상에서 이른시간에 제외할 수 있는 방법을 제안한다.
끝으로, 본 논문에서 제안하는 방법들이 효율적이고 확장성이 있는지를 검증하기 위해 여러 가지 실험을 수행한다. 역근접 질의 연구에서의 실험에서는 제안한 방법을 비슷하지만 다른 문제를 해결한 방법과 비교 하였다. 이를 위해 비교 방법이 본 문제를 해결할 수 있도록 변경했다. 이 비교에서 제안한 방법이 기존의 방법보다 더욱 효율적이고 더욱 좋은 확장성을 가지고 있다는 것을 보였다. 또한 역순위 검색 연구에서는 대용량의 가상 데이터 및 실데이터를 활용하여 실험을 진행했다. 실험결과를 통하여 제안한 방법이 역순위검색을 해결한 기존의 가장 좋은 방법보다 더욱 효율적이라는 것을 확인할 수 있다.
