공간 데이타베이스에서 최근접 K쌍을 찾는 효율적 기법

신효섭(Hyoseop Shin),이석호(Sukho Lee) 한국정보과학회 2000 정보과학회논문지 : 데이타베이스 Vol.27 No.2

R 트리와 같은 다차원 인덱스로 구성된 2개의 공간 데이타 집합들에 대하여 거리가 가까운 순서대로 점진적으로 객체 쌍을 찾는 거리조인(distance join) 알고리즘이 이전에 제안된 바 있다. 본 논문에서는 찾고자 하는 객체 쌍의 개수 K를 미리 정할 때 거리 우선순위 큐를 이용한 효율적인 K-거리조인 기법을 제안한다. 특히 양쪽 노드 확장 방식과 스위핑 축 및 방향의 선택 기법을 이용한 최적화된 평면스위핑 가지치기 기법을 통한 거리조인 알고리즘을 개발한다. 실제 지리정보 데이타 집합을 가지고 실험을 수행하여 본 논문에서 제안한 알고리즘이 기존의 알고리즘들보다 좋은 성능을 나타냄을 확인한다. The distance join has been introduced previously, which finds nearest pairs in the order of distance incrementally among two spatial data sets built with multidimensional indexes like R-trees. We propose efficient K-distance joins when the number(K) of pairs to find is preset. Especially, we develop a distance join algorithm with bi-directional expansion and optimized plane sweeping using selection method of sweep axis and direction. The experiments on real spatial data sets show that the proposed algorithm is much better than the former algorithms.

암시조인과 명시조인의 완전 순차를 고려한 OQL 질의 최적기의 설계 및 구현

신효섭(Hyoseop Shin),나연묵(Yunmook Nah),이석호(Sukho Lee) 한국정보과학회 1997 정보과학회논문지(B) Vol.24 No.8

차세대 객체지향 데이타베이스 표준안으로서 ODMG(Object Database Management Group)가 널리 주목을 받고 있다. 본 논문은 ODMG의 표준 질의어인 OQL(Object Query Language)을 사용자 언어로 제공하는 객체지향 데이타베이스 시스템을 위한 질의 최적기를 설계하고 구현하였다. 제안된 질의 최적기에서 제공하는 질의 그래프는 동일 클래스가 중복 접근되는 것을 막고, 은닉된 클래스들 간의 조인관계를 명시적으로 보여주는 구조를 가진다. 또한 최적기의 탐색 엔진 측면에서는 명시조인을 고려하지 않은 암시조인 순회 위주의 탐색 기법은 최적의 계획과는 거리가 먼 수행 계획을 생성한다는 점을 지적하고, 이 문제를 해결하기 위하여 암시조인과 명시조인의 완전 조인 순차를 고려하였다. 구체적 방안으로서 세분화된 논리 연산자 규칙과 물리 연산자 규칙을 정의하였고, 이들을 동적 프로그래밍 탐색 전략에 적용하는 알고리즘을 개발하였다. 구현된 최적기에 대한 실험 결과를 토대로 제안된 기법이 최적기의 성능을 개선할 수 있음을 검증하였다. ODMG, as a standard for the next-generation object-oriented databases, attracts wide attention. This paper proposes a query optimizer for object-oriented databases which have ODMG-OQL interfaces. The optimizer generates a query graph whose structure prevents classes from being accessed redundantly and shows clearly join relationships between classes, which may be hidden in query. And in designing a search engine of a optimizer, this paper shows that search algorithms, which focus on ordering of implicit joins and do not consider explicit joins, may generate plans which are far from optimal. So, we propose a technique considering total ordering of implicit and explicit joins. To achieve this, a set of logical and physical operator rules about implicit joins, explicit joins and etc. is presented and an algorithm which applies these rules to dynamic programming search strategy is developed. Finally, we implemented an OQL query optimizer to experimentally validate the ideas of this paper. The experiment shows that this technique can significantly improve the performance of a query optimizer.

적응적 다단계 거리 조인의 최적화 기법

신효섭(Hyoseop Shin),문봉기(Boongki Moon),이석호(Sukho Lee) 한국정보과학회 2001 정보과학회논문지 : 데이타베이스 Vol.28 No.3

거리조인은 두 공간 데이타 집합 사이의 데이타쌍을 거리 상 가까운 순으로 검색하는 공간조인이다. 본 논문에서는 [1]에서 제시한 적응식 다단계 거리 조인 기법을 최적화하기 위한 기법들을 제안한다. 첫째, 평면 스위핑에서 스위핑 축 선택을 위해 사용되는 스위핑 인덱스 공식을 최적화한다. 둘째, 노드쌍을 관리하는데 사용하는 메인큐의 성능 향상을 위하여 노드쌍의 최대 거리값을 큐의 2차 우선 순위로 적용하는 기법을 제안한다. 또한, 균등 분포 및 비균등 분포 가정하의 한계 거리값 예측 기법의 장단점을 비교한다. 실험 결과는 제안하는 기법들을 통하여 알고리즘의 성능이 CPU 비용과 I/O 비용 면에서 크게 향상되었음을 보여 준다. The distance join is a spatial join which finds data pairs in the order of distance when associating two spatial data sets. This paper proposes several methods to optimize the adaptive multi-stage distance join, presented in [1]. First, we optimize the sweeping index formula which is used for selecting sweeping axis during plane sweeping. Second, to improve the performance of a priority queue used for maintaining node pairs, we propose to use the maximum distance of a node pair as the second priority of the queue. Moreover, we compare trade-offs in estimating the cut-off distance between under uniformity assumption of data distribution and non-uniformity assumption. The experiments show that the proposed methods greatly improve the performance of the algorithm in CPU cost as well as in I/O cost.

웹 환경에서 AOD 서버의 설계 및 구현

신효섭(Hyoseop Shin),이태원(Taewon Lee),이석호(Sukho Lee) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.1B

본 논문에서는 웹 응용의 일종으로 AOD(주문형 오디오) 서버를 설계하고 구현하였다. 오디오 데이타는 CD음질의 오디오를 네트워크 상에서 실시간으로 디코딩이 가능한 MPEG 오디오 Layer-3 MP3 화일포맷을 사용하였다. AOD 서버는 웹 응용 중에서 특히 수 M바이트에 이르는 대용량의 화일을 서비스한다는 점, 그리고 데이타베이스를 연동하여 운영된다는 점 등을 특징으로 들 수 있는데, 본 논문은 대규모 사용자를 지원하기 위한 서버를 구축하는 데 필요한 성능을 고려한 설계 기법을 제시한다.

객체지향 질의어 α - OQL 을 위한 질의 처리기

신효섭(Hyoseop Shin),박한묵(Hanmook Park),이석호(Sukho Lee) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.2A

멀티미디어 데이타베이스 시스템 ALPHA[1]는 객체 지향 개념을 모델의 근간으로 삼고 있다. α-OQL은 이러한 모델적 특성을 고려하여 설계된, 객체의 검색, 삽입, 삭제, 갱신 등을 사용자가 친숙하게 이용할 수 있는 선언적인 언어로서 ODMG-OQL을 기반으로 설계되었다. α-OQL로 표현된 질의는 보통 여러 클래스가 암시 조인을 통하여 네트워크 형태로 복잡하여 얽혀있다. 따라서 조인 기법이나 순차를 정하는 탐색 공간(search space)이 크다. 본 논문에서는 인덱스 정보를 토대로 클래스를 그룹화하는 방법을 통하여 탐색 공간을 줄이는 휴리스틱 기법을 제안한다. 또한 질의 처리기의 전체 구조는 경로식에 기반한 해석식 접근법을 쓰지 않고, 객체 지향 질의를 위한 연산자들을 정의하고 이들로 구성된 수행 가능한 연산자 트리를 생성해내는 대수적 접근법을 쓰고 있는 특징을 가지고 있다.

다차원 공간에서 거리조인 질의처리를 위한 R - 트리의 효율적 접근

신효섭(Hyoseop Shin),문봉기(Boongki Moon),이석호(Sukho Lee) 한국정보과학회 2002 정보과학회논문지 : 데이타베이스 Vol.29 No.1

거리조인은 R-트리를 사용하여 두 공간 데이타 집합 사이의 데이타쌍을 거리 상 가까운 순으로 검색하는 공간조인이다. 거리조인은 R-트리를 하향식으로 순회하면서 생성되는 노드쌍들을 거리값 순으로 우선순위 큐에 저장한다. 본 논문에서는 거리조인 처리시 우선순위 큐 안에서 동점자 노드쌍들의 우선 순위 정책이 알고리즘의 성능을 많이 좌우할 수 있음을 보여주고, 이를 위한 최적화된 2차 우선 순위기법을 제안한다. 실험을 통하여, 제안한 기법이 다른 기법에 비하여 항상 좋은 성능을 나타냄을 보여준다. The distance join is a spatial join which finds data pairs in the order of distance between two spatial data sets using R-trees. The distance join stores node pairs in a priority queue, which are retrieved while traversing R-trees in a top-down manner, in the order of distance. This paper first shows that a priority strategy for the tied pairs in the priority queue during distance join processing has much effect on its performance, and then proposes an optimized secondary priority method. The experiments show that the proposed method is always better than the other methods in the performance perspectives.

복수 데이타베이스에서 링크를 이용한 연관 규칙 탐사

배진욱,신효섭,이석호(Jinwook Bae),Hyoseop Shin,Sukho Lee 한국정보과학회 1999 정보과학회논문지(B) Vol.26 No.8

데이타마이닝 분야에서는 대용량의 트랜잭현 데이타베이스와 같은 하나의 데이타베이스로부터 연관 규칙을 찾는 연구가 많이 수행되어왔다. 그러나, 창고형 할인매장이나 백화점 같이 고객 카드를 이용하는 판매점의 등장으로, 단지 트랜잭션에 대한 분석 뿐만이 아니라, 트랜잭션과 고객과의 관계에 대한 분석 또한 요구되고 있다. 즉, 두 개의 데이타베이스로부터 연관 규칙을 찾는 연구가 필요하다. 이 논문에서는 두 데이타베이스 사이에 링크를 생성하여 연관 항목집합을 찾는 알고리즘을 제안한다. 실험 결과, 링크를 이용한 알고리즘은 고객 데이타베이스가 메모리에 거주가능한 크기라면 시간에 따른 분석에 유용함을 보여주었다. There have been a lot of researches of mining association rules from one database such as transaction database until now. But as the large discount store using customer card emerges, the analysis is not only required about transactions, but also about the relation between transactions and customer data. That is, it is required to search association rules from two databases. This paper proposes an efficient algorithm constructing links from one database to the other. Our experiments show the algorithm using link is useful for temporal analysis of memory-resident customer database.

지자기센서기반 차량검지시스템과 R을 이용한 교통정보모델링

손석현(Seokhyun Son),신효섭(Hyoseop Shin),송병훈(Byunghun Song),정지은(Ji-eun Jung) 한국정보과학회 2013 한국정보과학회 학술발표논문집 Vol.2013 No.6

온라인 커뮤니티에서 전문성과 대중성에 기반한 사용자 생성 컨텐츠의 랭킹

이지훈 ( Jeehoon Lee ),신효섭 ( Hyoseop Shin ) 한국정보처리학회 2009 한국정보처리학회 학술대회논문집 Vol.16 No.2

오늘날 웹 상에는 수 많은 온라인 커뮤니티들이 존재하고, 그 안에서 유저들이 올린 게시글(이하 포스트)를 효과적으로 검색하는 것은 중요한 이슈가 되고 있다. 만약 검색하는 유저들이 각기 다른 성향을 갖고 있다면 그에 맞는 검색 결과를 제공하는 것이 효과적인 검색의 한 예라 할 수 있겠다. 이 논문에서는 이러한 유저 성향 기반의 효과적인 검색을 위하여 유저의 “전문성”과 “대중성”을 정의하고 그에 기반한 포스트 랭킹을 한다. 또한 서로 다른 유저의 성향은 매우 다른 검색 결과를 나타낸다는 우리의 주장을 실험결과로 뒷받침 한다.

R을 이용한 대용량 교통정보모델링 연구

김선홍(Sunhong Kim),신효섭(Hyoseop Shin),손석현(Seokhyun Son) 한국정보과학회 2013 한국정보과학회 학술발표논문집 Vol.2013 No.11