http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
손완빈(Wanbin Son),안희갑(Hee-Kap Ahn) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.1
본 논문은 도로 환경에서 주어진 자료점의 집합 P로부터 질의 집합 Q에 대해 이동에 필요한 소요 시간이 Skyline[1,2,3,4,5]의 성질을 만족하는 P의 부분 집합 S를 찾는 문제에 대해 연구한다. 본 논문은 단위 속력으로 수직, 수평 방향으로만 이동 가능한 2차원 공간에서 skyline을 찾는 문제에 대해 O( P log ) 시간 복잡도와 O( ) 공간 복잡도를 사용하는 알고리즘을 제시한다. 또한 이 평면상에 하나의 무한 길이의 수평 도로가 있을 때 skyline을 찾는 알고리즘을 제시한다. 도로상에서의 이동 속력이 무한일 때 모든 skyline S를 찾는데 O( S /log log ) 공간 복잡돌ㄹ 사용하는 알고리즘을 제시한다. 또한 도로상에서의 이동 속력이 상수일 때 모든 skyline을 찾는 O( Q min{ } ) 시간 복잡도와 O( /loglog ) 공간 복잡도를 사용하는 알고리즘을 제시한다. 또한 도로상에서의 이동 속력이 상수일 때 모든 skyline을 찾는 O( ) 공간 복잡도를 사용하는 알고리즘을 제시한다.
L1 메트릭에서의 이동 질의점에 대한 skyline 계산
손완빈(Wanbin Son),황승원(Seung-won Hwang),안희갑(Hee-Kap Ahn) 한국정보과학회 2012 한국정보과학회 학술발표논문집 Vol.39 No.1A
본 논문에서는 L₁ 메트릭을 사용하는 평면상에 주어진 자료점의 집합 P로부터 질의점의 집합 Q에 대해 skyline이 되는 점들을 계산하는 문제를 다룬다. L₁거리는 도로망이 잘 발달된 도시 내의 이동 시간을 근사화해 주는 것으로 알려져 있다. 이 문제에서 각각의 질의점은 수직 또는 수평 방향으로 단위속도로 움직인다고 가정한다. 본 논문에서는 시간 0에서 t₁사이에 움직이는 질의점들에 대해서 skyline의 변화를 모두 계산하는 알고리즘을 제시한다. 또한 이 알고리즘이 O(│P│²│Q│) 시간에 모든 skyline을 계산 가능함을 보인다.
City Metric에서 스카이라인을 계산하는 기하 알고리즘
손완빈(Wanbin Son),안희갑(Hee-Kap Ahn) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.2A
본 논문은 도로 환경의 모델링 중 하나인 City Metric에서 주어진 자료점의 집합 P로부터 질의 집합 Q에 대해 이동에 필요한 소요 시간이 스카이라인의 성질을 만족하는 P의 부분 집합 S를 찾는 문제에 대해 연구한다. 우리는 이 논문에서 시간 복잡도 O((|P|+|M|)|Q|log|M|+|P|log|P|+|S||M|(log|P|+log|M|))와 공간복잡도 O(|P|loglog|P|+|M||Q|)인 알고리즘을 제시한다. 또한 O((|P|+|M|)|Q|log|M|+|P|log|P|+|P||S||Q|) 시간복잡도와 O(|P||Q|+|M|) 공간 복잡도를 가진 알고리즘도 제시한다. 이 논문에서의 계산은 word의 크기가 log|P|와 log|M|보다 큰 unit-cost RAM에서 이루어진다고 가정한다.
L₁ 메트릭 공간에서 Skyline을 계산하는 기하 알고리즘
손완빈(Wanbin Son),황승원(Seung-won Hwang),안희갑(Hee-Kap Ahn) 한국정보과학회 2011 한국정보과학회 학술발표논문집 Vol.38 No.1B
본 논문은 평면상에 주어진 자료점의 집합 P로부터 질의 집합 Q에 대해 skyline을 성질을 만족하는 Q의 부분집합을 찾는 알고리즘을 제시한다. 이 때 P의 점들 간의 우위는 Q의 점에서의 거리를 이용하여 판단하는데 이 논문에서는 두 점간의 거리를 L₁거리로 정의한다. 이와 같은 환경 하에서 P ≥ Q 라고 가정할 때 우리는 O( log ) 시간에 모든 skyline을 찾는 알고리즘을 제시하였다.
김상섭(Sang-Sub Kim),손완빈(Wanbin Son),안희갑(Hee-Kap Ahn),유환조(Hwanjo Yu) 한국정보과학회 2010 한국정보과학회 학술발표논문집 Vol.37 No.1A
본 논문에서는 도로 네트워크에서 지배받지 않는(non-dominated) 점 집합을 찾는 문제를 다루었다. 지배받지 않는 자료는 다른 자료들에 비해 질의에 대해서 한 가지 조건이라도 우위에 있는 자료들을 의미한다. 본 논문에서 주어진 도로는 연결된 그래프의 형태로 주어지면 각 도로는 도로를 이용하는데 소요되는 시간을 가중치로 가진다. 우리는 지배성(dominance)과 지배받지 않는 자료의 성질을 이용하는 알고리즘을 우선 제시한다. 또한 이 방법이 지배받지 않는 점을 찾을 때 비효율적인 연산을 수행함을 보이고, 이 알고리즘과 시간복잡도는 동일하지만 비효율적인 부분을 개선하여 실제 수행시간이 향상된 알고리즘을 제시한다. 이와 함께 실험을 통해 개선된 수행성능을 보인다.