Recently, facilitated by the improvement of the mobile environment and the growing number of mobile users, the location-based service(LBS) has become more attractive and widely used. In LBS, the skyline query has been often used to select interesting objects which have spatial attributes.
In this thesis, the problem, named the Skyline Query for Multiple User Preferences(SQMUP), is addressed. Given a group of participants, i.e. the users specified in a query, SQMUP finds skyline objects incorporating user-dependent attributes (user preferences and the distance to the user location) for all participants and user-independent attributes (objective characteristics) in order to recommend suitable objects for all participating users.
In order to solve SQMUP, an efficient and progressive approach is introduced, that reduces query time and maintains a reasonable index size based on a graph summarizing the dominance relations and the R-trees. In addition, the results of extensive experiments show that the proposed method outperforms a comparison method.
위치기반 서비스(LBS: Location-based service)는 최근 들어 모바일 환경의 개선과 함께 사용자들이 자발적으로 공유한 풍부한 경험들을 기반으로 급격히 성장해왔다. 하지만, 너무 많은 양의 정보는 사용자들이 정보를 얻는데 오히려 방해가 되곤 한다. 스카이라인 질의는 다차원 객체들에 대해 열세적인 데이터들을 없애고 한 차원에서라도 우세한 데이터들을 뽑아주는 쿼리이다. 이러한 방식으로, 스카이라인 질의는 고려할 필요 없는 객체들을 추려준다.
위치기반 서비스에는 위치정보, 가격정보 같은 수많은 식당 객체들에 대한 유용한 정보들이 존재한다. 해당 정보들은 크게 두 가지 속성으로 분류될 수 있다. 두 속성은 가격정보 등의 식당 자체의 객관적인 정보를 표현하는 사용자 독립적인 속성(User-independent attributes)과 사용자에 따라 변할 수 있는 거리 정보, 브랜드 선호도 정보 같은 사용자에 주관적인 사용자 의존적인 속성(User-dependent attributes)이다. 사용자들은 이런 모든 유용한 정보들을 고려하여 자신에게 적합한 식당들을 찾을 수 있기를 원하기 때문에, 스카이라인 질의를 이용하여 수많은 장소들 중 사용자가 고려할만한 장소를 추려주는 것은 사용자에게 큰 도움이 될 것이다.
본 연구에서는 질의에 속한 참여자들의 집합이 주어지면, 그들에게 적절한 객체를 추천해주기 위해 모든 참여자들에 대한 사용자 의존적인 속성과 사용자 독립적인 속성 모두를 고려하는 스카이라인 질의 문제를 제안한다. 이 문제를 해결하기 위해, 객체들 간의 우세 정보 관계를 요약한 인덱스 구조를 제안하고, 이를 기반으로 효율적인 알고리즘을 제안한다. 결론적으로 실험을 통해, 제안된 알고리즘이 기존의 방법을 적용한 방법에 비해 좋은 성능을 보임을 검증하였다.
