Efficient bichromatic reverse search methods for multi-dimensional objects이종 데이터로 구성된 다차원 객체들을 대상으로 하는 효율적인 역 검색 기법

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 461
  • Download : 0
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.
Advisors
Song, Junehwaresearcher송준화researcherChung, Chin-Wanresearcher정진완researcher
Description
한국과학기술원 :전산학부,
Publisher
한국과학기술원
Issue Date
2016
Identifier
325007
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전산학부, 2016.8 ,[iv, 70 p. :]

Keywords

Multi-dimensional objects; Spatial Database; Reverse Search; Reverse Nearest Neighbor Search; Information Search; 다차원 객체; 공간 데이터베이스; 역검색; 역근접 검색; 정보 검색

URI
http://hdl.handle.net/10203/222405
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=663205&flag=dissertation
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0