메인 메모리에서 선반입을 사용한 확장된 R-Tree 색인 기법

강홍구,김동오,홍동숙,한기준,Kang, Hong-Koo,Kim, Dong-O,Hong, Dong-Sook,Han, Ki-Joon 한국공간정보학회 2004 개방형지리정보시스템학회 논문지 = Journal of the Korea Open Geogr Vol.6 No.1

최근 메인 메모리 기반에서 R-Tree의 성능을 개선하기 위해 캐시를 고려한 색인 구조들이 제안되었다. 이들 색인 구조의 일반적인 캐시 성능 개선 방법은 엔트리 크기를 줄여 펜-아웃(fanout)을 증가시키고 하나의 노드에 더 많은 엔트리를 저장함으로써 캐시 실패를 최소화하는 것이다. 그러나 이러한 방법은 갱신시 줄어든 엔트리 정보를 복원하는 추가 연산으로 갱신 성능이 떨어지고, 노드간 이동시 발생하는 캐시 실패는 여전히 성능 저하의 큰 문제가 되고 있다. 본 논문은 이러한 문제점을 개선하기 위해 메인 메모리에서 R-Tree에 선반입을 적용한 확장된 메인 메모리 기반 R-Tree 색인 기법인 PR-Tree를 제안하고 평가하였다. PR-Tree는 R-Tree의 근본적인 변형없이 노드 크기를 선반입에 최적화되도록 확장하고, 노드간 이동시 자식 노드를 선반입하여 캐시 실패를 최소화하였다. PR-Tree는 실험에서 R-Tree보다 검색 연산에서는 최대 38%의 성능 향상을 보였고, 갱신 연산에서는 최대 30%의 성능 향상을 보였고, 또한 노드 분할 연산에서는 최대 67%의 성능 향상을 보였다. Recently, studies have been performed to improve the cache performance of the R-Tree in main memory. A general mothed to improve the cache performance of the R-Tree is to reduce size of an entry so that a node can store more entries and fanout of it can increase. However, this method generally requites additional process to reduce information of entries and do not support incremental updates. In addition, the cache miss always occurs on moving between a parent node and a child node. To solve these problems efficiently, this paper proposes and evaluates the PR-Tree that is an extended R-Tree indexing method using prefetching in main memory. The PR-Tree can produce a wider node to optimize prefetching without additional modifications on the R-Tree. Moreover, the PR-Tree reduces cache miss rates that occur in moving between a parent node and a child node. In our simulation, the search performance, the update performance, and the node split performance of the PR-Tree improve up to 38%. 30%, and 67% respectively, compared with the original R-Tree.

공간 센서 데이타의 효율적인 실시간 처리를 위한공간 DSMS의 개발

강홍구,박치민,홍동숙,한기준,Kang, Hong-Koo,Park, Chi-Min,Hong, Dong-Suk,Han, Ki-Joon 한국공간정보학회 2007 한국공간정보시스템학회 논문지 Vol.9 No.1

최근 센서 장치의 발달은 무선 센서 네트워크와 같은 진보된 기술에 대한 연구를 가속화시켰다. 뿐만 아니라, GPS(Global Positioning System) 기능을 보유한 공간 센서는 공간 정보와 비공간 정보를 동시에 사용하는 유비쿼터스 시대를 이끌어가고 있다. 이러한 새로운 시대에 있어서, 공간 센서 데이타에 대한 실시간 처리 시스템은 필수적이다. 이 때문에, DSMS(Data Stream Management System)라 불리는 새로운 개념의 데이타 처리 시스템이 많은 연구자들에 의해 연구되고 있다. 그러나 대부분의 DSMS들이 공간 센서 데이타 처리를 위한 공간 함수를 지원하지 않기 때문에 유비쿼터스 컴퓨팅에 적합하지 않다. 그러므로, 본 논문에서는 이러한 문제를 해결하고자 STREAM(STanford stREam datA Manager)을 확장한 공간 DSMS를 설계 및 구현하였다. 즉, Geometry 타입과 공간 함수를 공간 센서 데이타 처리를 위해 추가하였고, 또한 시스템에서 공유되는 공간 객체를 효율적으로 관리하기 위한 공간 객체 관리자를 추가하였다. 특히, 상호운용성을 위하여 OGC(Open Geospatial Consortium)에서 제시한 Simple Features Specification for SQL을 구현하였고, GEOS(Geometry Engine Open Source)의 알고리즘을 본 시스템에 적용하였다. Recently, the development of sensor devices has accelerated researches on advanced technologies like Wireless Sensor Networks. Moreover, spatial sensors using GPS lead to the era of the Ubiquitous Computing Environment which generally uses spatial information and non-spatial information together. In this new era, a real-time processing system for spatial sensor data is essential. In this reason, new data processing systems called DSMS(Data Stream Management System) are being developed by many researchers. However, since most of them do not support geometry types and spatial functions to process spatial sensor data, they are not suitable for the Ubiquitous Computing Environment. For these reasons, in this paper, we designed and implemented a spatial DSMS by extending STREAM which stands for STanford stREam datA Manager, to solve these problems. We added geometry types and spatial functions to STREAM in order to process spatial sensor data efficiently. In addition, we implemented a Spatial Object Manager to manage shared spatial objects within the system. Especially, we implemented the Simple Features Specification for SQL of OGC for interoperability and applied algorithms in GEOS to our system.

데이타 중심 센서 네트워크에서 에너지 효율성을 고려한 비균등 네트워크 분할 기법

강홍구,김정준,한기준,Kang, Hong-Koo,Kim, Joung-Joon,Han, Ki-Joon 한국공간정보학회 2007 한국공간정보시스템학회 논문지 Vol.9 No.3

데이타 중심 센서 네트워크에서는 측정된 데이타의 값에 따라 데이타를 저장하는 센서 노드가 결정되기 때문에 같은 값을 갖는 데이타가 빈번하게 발생하면 이를 저장하는 센서 노드에 부하가 집중되어 에너지가 빠르게 고갈되는 문제가 있다. 또한 센서 네트워크가 확장되면 데이타 저장 및 질의 처리시 목적 센서 노드로의 라우팅 거리가 멀어져 센서 네트워크의 통신비용이 증가되는 문제가 있다. 그러나 기존 연구들은 데이타 저장의 효율적인 관리에만 치우쳐 이와 같은 문제를 효율적으로 해결하지 못하고 있다. 본 논문에서는 데이타 중심 센서 네트워크에서 센서 노드의 부하를 분산시키고 센서 네트워크의 확장에 따른 통신비용을 효율적으로 줄이기 위한 비균등 네트워크 분할(Non-Uniform Network Spilt: NUNS) 기법을 제안한다. NUNS는 센서 네트워크를 센서 노드 개수와 분할된 영역 크기의 차이가 최소가 되도록 비균등 크기의 Partition으로 분할하고 각 Partition에서 발생한 데이타를 각 Partition 내의 센서 노드가 저장함으로써 센서 노드의 데이타 저장 부하를 분산시키고 센서 네트워크의 확장에 따른 통신비용을 줄인다. 또한 NUNS는 각 Partition을 분할된 영역 크기 차이가 최소가 되도록 센서 노드 개수만큼 Zone으로 비균등하게 분할하여 각 센서 노드의 처리 영역으로 할당함으로써 센서 노드에 부하가 집중되는 것을 막고 불필요한 라우팅 비용을 줄인다. In a data centric sensor network, a sensor node to store data is determined by the measured data value of each sensor node. Therefore, if the same data occur frequently, the energy of the sensor node to store the data is exhausted quickly due to the concentration of loads. And if the sensor network is extended, the communication cost for storing data and processing queries is increased, since the length of the routing path for them is usually in the distance. However, the existing researches that generally focus on the efficient management of data storing can not solve these problems efficiently. In this paper, we propose a NUNS(Non-Uniform Network Split) method that can distribute loads of sensor nodes and decrease the communication cost caused by the sensor network extension. By dividing the sensor network into non-uniform partitions that have the minimum difference in the number of sensor nodes and the splitted area size and storing the data which is occurred in a partition at the sensor nodes within the partition, the NUNS can distribute loads of sensor nodes and decrease the communication cost efficiently. In addition, by dividing each partition into non-uniform zones that have the minimum difference in the splitted area size as many as the number of the sensor nodes in the partition and allocating each of them as the processing area of each sensor node, the NUNS can protect a specific sensor node from the load concentration and decrease the unnecessary routing cost.

데이타 중심 저장 방식의 센서 네트워크를 위한 비균등 영역 분할 기법

강홍구,전상훈,홍동숙,한기준,Kang, Hong-Koo,Jeon, Sang-Hun,Hong, Dong-Suk,Han, Ki-Joon 한국공간정보시스템학회 2006 한국공간정보시스템학회 논문지 Vol.8 No.3

A sensor network which uses DCS(Data-Centric Storage) stores the same data into the same sensor node. Thus it has a hot spot problem when the sensor network grows and the same data arise frequently. In the past researches of the sensor network using DCS, the hot spot problem caused by growing the sensor network was ignored because they only concentrated on managing stored sensor data efficiently. In this paper, we proposed a non-equal region split method that supports efficient scalability on storing multi-dimensional sensor data. This method can reduce the storing cost, as the sensor network is growing, by dividing whole space into regions which have the same number of sensor nodes according to the distribution of sensor nodes, and storing and managing sensor data within each region. Moreover, this method can distribute the energy consumption of sensor nodes by increasing the number of regions according to the size of the sensor network, the number of sensor nodes within the sensor network, and the quantity of sensor data. Therefore it can help to increase the life time and the scalability of the sensor network. 데이타 중심 저장(Data-Centric Storage: DCS) 방식의 센서 네트워크는 같은 값의 데이타를 같은 노드에 저장하기 때문에 센서 네트워크가 확장되거나 같은 값의 데이타가 빈번하게 발생하면 특정 센서 노드에 저장 부하가 집중되어 에너지 효율성이 나빠지는 문제가 발생한다. 기존의 데이타 중심 저장 방식에 대한 연구들은 저장 데이타의 효율적인 관리에만 치우쳐 센서 네트워크의 확장에 따른 에너지 효율성 문제를 고려하지 않았다. 본 논문에서는 다차원 센서 데이타 저장의 효율적인 확장성(Scalability)을 지원하는 비균등 영역 분할(Non-Equal Region Spilt) 기법을 제안한다. 제안한 기법은 센서 네트워크를 센서 노드의 분포에 따라 같은 센서 노드 개수를 갖도록 서로 다른 크기의 영역으로 분할하고 분할된 각 영역 내에서 측정된 데이타를 해당 영역에서 저장 및 관리함으로써 센서 네트워크의 확장에 따른 저장 비용을 줄였다. 또한 분할 영역 개수를 센서 네트워크의 크기와 센서 노드 개수, 센서 데이타 발생량에 비례하게 증가시켜 센서 노드의 에너지 소모를 분산시킴으로써 센서 네트워크의 수명 연장과 확장성을 높였다.

한국성인 정상교합자와 부정교합자의 연조직 측모에 관한 두부방사선 계측학적 비교연구

강홍구,윤태호,Kang, Hong-Koo,Yoon, Tae-Ho 대한심미치과학회 1995 Journal of the Korean Academy of Esthetic Dentistr Vol.4 No.1

The purpose of this artic1e is to compare soft tissue profiles between Korean adults with normal occ1usion and malocclusin and to identify the differences between them. The subjects of this cephalometric study were 40 males with normal occlusion(Group 1), 27 females with normal occlusion(Group 2), 28 adults with Angle's Class II malocclusion(Group 3) and 41 adults with Angle's Class III malocclusion(Group 4). The results of this study were as follows ; 1) People with Angle's Class II malocclusion had tendency to have more labial tipping of lower teeth than people with normal occ1usion. Through NOA angle measurement, it was determined that people with Angle's Class II malocclusion had more protruding midface than people with normal occlusion and people with Angle's Class III malocclusion had retruding midface. 2) Through Powell's esthetic triangle analysis, it was determined that people with Angle's Class II malocclusion had retruding chin and protruding nose. 3) No significant differences between people with normal occlusion and maloclusion could be identified by measuring soft tissue profile angle basis of S-NS plane. 4) There were significant differences between groups with normal occlusion and malocclusion by measuring Facial convexity angle(Significance level 99%). 5) By measuring the distance between each landmark basis of N-Pog plane, People with Angle's Class II malocclusion were identified as having more protruding midface, but there were no significant differences between people with normal occlusion and Angle's Class III malocclusion. 6) By measuring the vertical dimension of the face, it was determined that the lower facial height was higher than the upper facial height in all groups, particularly in group with Angle's Class III malocclusion. 7) By measuring the lips basis of E-line and S-line, it was determined that people with Angle's Class III malocclusion had more, protruding lower lips than people with normal occlusion, while people with normal occlusion, while people with Angle's Class II malocclusion had more protruding upper lips. By measuring the distance between the superior sulcus and inferior sulcus basis of H-line, people with Angle's Class II malocclusion had thicker upper lips than the other's.

SQR-Tree : 효율적인 공간 질의 처리를 위한 하이브리드 인덱스 구조

강홍구,신인수,김정준,한기준,Kang, Hong-Koo,Shin, In-Su,Kim, Joung-Joon,Han, Ki-Joon 한국공간정보학회 2011 한국공간정보학회지 Vol.19 No.2

대표적인 트리 기반 공간 인덱스 구조는 크게 R-Tree와 같은 데이타 분할 기반 인덱스 구조와 KD-Tree와 같은 공간 분할 기반 인덱스 구조로 구분되며, 최근에는 이들의 장점을 결합한 하이브리드 인덱스 구조에 대한 연구가 활발히 진행되고 있다. 그러나, 기존 연구에서는 공간 객체가 삽입되는 노드의 분할 경계 확장이 다른 이웃 노드에 연쇄적으로 전파되어 노드간 겹침이 증가하고 질의 처리 비용이 높아지는 문제가 있다. 본 논문에서는 이러한 문제를 해결하기 위하여 효율적인 질의 처리를 위한 하이브리드 인덱스 구조인 SQR-Tree를 제시한다. SQR-Tree는 크기를 갖는 공간 객체 처리에 적합하도록 Quad-Tree를 확장한 SQ-Tree(Spatial Quad-Tree)와 SQ-Tree의 리프 노드마다 연계되어 실제로 공간 객체를 저장하는 R-Tree가 결합된 인덱스 구조이다. SQR-Tree는 노드마다 하위 노드를 포함하는 MBR을 가지고 있기 때문에 노드의 분할 경계 확장이 독립적으로 이루어지도록 하여 노드간 겹침을 줄였다. 그리고 SQR-Tree에서 공간 객체는 분할된 데이타 공간마다 존재하는 여러 R-Tree에 분산 저장되며 SQ-Tree가 분할된 데이타 공간을 식별하는 기능을 수행한다. 따라서 공간 질의 처리시 질의 영역에 해당하는 R-Tree만 접근하면 되기 때문에 질의 처리 비용을 줄일 수 있다. 마지막으로 실험을 통해 SQR-Tree의 우수성을 입증하였다. Typical tree-based spatial index structures are divided into a data-partitioning index structure such as R-Tree and a space-partitioning index structure such as KD-Tree. In recent years, researches on hybrid index structures combining advantages of these index structures have been performed extensively. However, because the split boundary extension of the node to which a new spatial object is inserted may extend split boundaries of other neighbor nodes in existing researches, overlaps between nodes are increased and the query processing cost is raised. In this paper, we propose a hybrid index structure, called SQR-Tree that can support efficient processing of spatial queries to solve these problems. SQR-Tree is a combination of SQ-Tree(Spatial Quad- Tree) which is an extended Quad-Tree to process non-size spatial objects and R-Tree which actually stores spatial objects associated with each leaf node of SQ-Tree. Because each SQR-Tree node has an MBR containing sub-nodes, the split boundary of a node will be extended independently and overlaps between nodes can be reduced. In addition, a spatial object is inserted into R-Tree in each split data space and SQ-Tree is used to identify each split data space. Since only R-Trees of SQR-Tree in the query area are accessed to process a spatial query, query processing cost can be reduced. Finally, we proved superiority of SQR-Tree through experiments.

Mr-Tree: 효율적인 공간 검색을 위한 매핑 기반 R-Tree

강홍구,신인수,김정준,한기준,Kang, Hong-Koo,Shin, In-Su,Kim, Joung-Joon,Han, Ki-Joon 대한공간정보학회 2010 한국공간정보학회지 Vol.18 No.4

Recently, due to rapid increasement of spatial data collected from various geosensors in u-GIS environments, the importance of spatial index for efficient search of large spatial data is rising gradually. Especially, researches based R-Tree to improve search performance of spatial data have been actively performed. These previous researches focus on reducing overlaps between nodes or the height of the R -Tree. However, these can not solve an unnecessary node access problem efficiently occurred in tree traversal. In this paper, we propose a MR-Tree(Mapping-based R-Tree) to solve this problem and to support efficient search of large spatial data. The MR-Tree can improve search performance by using a mapping tree for direct access to leaf nodes of the R-Tree without tree traversal. The mapping tree is composed with MBRs and pointers of R-Tree leaf nodes associating each partition which is made by splitting data area repeatedly along dimensions. Especially, the MR-Tree can be adopted in various variations of the R-Tree easily without a modification of the R-Tree structure. In addition, because the mapping tree is constructed in main memory, search time can be greatly reduced. Finally, we proved superiority of MR-Tree performance through experiments. 최근, u-GIS 환경에서 다양한 지오센서 (Geosensor)의 활용으로 수집되는 공간 데이터의 양이 급증하면서 대용량 공간 데이타의 효율적인 검색을 위한 공간 인덱스의 중요성이 높아지고 있다. 특히, 공간 데이타의 검색 성능을 높이기 위해 R-Tree를 기반으로 한 공간 인덱스에 대한 연구가 활발히 진행되고 있다. 그러나 기존 연구는 R-Tree에서 노드 사이의 겹침이나 트리의 높이를 줄임으로써 어느 정도 검색 성능을 향상시켰지만 트리 순회(tree traversal)에서 발생하는 불필요한 노드 접근 문제를 효율적으로 해결하지 못하고 있다. 본 논문에서는 이러한 문제를 해결하기 위하여 대용량 공간 데이타의 효율적인 검색을 위한 매핑 기반 R-Tree인 MR-Tree(Mapping based R-Tree)를 제안한다. MR-Tree는 R-Tree 순회 없이 리프 노드를 직접 접근하도록 하는 매핑 트리를 이용함으로써 검색 성능을 향상시킨다. 매핑 트리는 데이타 공간을 차원에 따라 반복적으로 분할한 각 파티션(Partition)과 연계되는 R-Tree 리프 노드의 MBR과 포인터를 이용하여 구성된다. 특히, MR-Tree는 기존 R-Tree에 큰 변경없이 구현이 가능하고, 다양한 R-Tree 변형에도 쉽게 적용할 수 있으며, 또한 매핑 트리를 메인 메모리에 상주시킴으로써 검색 시간을 단축시킬 수 있다. 마지막으로 실험을 통해 기존 인덱스보다 MR-Tree 성능의 우수성을 보였다.

HSQR-tree : R-tree 기반의 하이브리드 인덱스 구조

강홍구(Hong-Koo Kang),김범진(Bum-Jin Kim),한기준(Ki-Joon Han) 대한공간정보학회 2009 한국지형공간정보학회 학술대회 Vol.2009 No.9

오늘날 LBS, Telematics, ITS와 같은 GIS 응용 기술과 RFID, GPS, Digital 카메라, CCTV 등과 같은 Geosensor 기술의 발전으로 대용량의 공간 데이타를 빠르게 처리할 수 있는 공간 인덱스의 중요성이 높아지고 있다. 최근 대표적인 공간 인덱스 구조인 R-tree를 기반으로 KD-tree나 Quad-tree와 같은 공간 분할 특성을 이용하여 인덱싱 성능을 향상시키기 위한 연구가 활발히 진행되고 있다. 본 논문에서는 기존에 제시된 R-tree 기반 인덱스 구조인 HR-tree와 SQR-tree의 장점을 결합하여 대용량 공간 데이타를 보다 효율적으로 처리하는 인덱스 구조인 HSQR-tree(Hash-based SQR-tree)를 제시한다. HR-tree는 R-tree에 대해서 리프 노드를 직접 접근할 수 있는 해시 테이블을 적용한 인덱스 구조이고, SQR-tree는 Quad-tree를 확장한 SQ-tree와 SQ-tree의 리프 노드마다 실제로 공간 객체를 저장하는 R-tree가 연계된 인덱스 구조이다. 본 논문에서 제시하는 HSQR-tree는 SQR-tree를 기본 구조로 가지고 R-tree마다 해시 테이블이 적용된 인덱스 구조이다. 따라서, HSQR-tree에서는 SQR-tree와 같이 여러 R-tree에서 질의가 분산 처리되고, HR-tree와 같이 해시 테이블을 통해 R-tree 리프 노드의 빠른 접근이 가능하다. 마지막으로 성능 실험을 통해 HSQR-tree의 우수성을 입증하였다.

신속한 공간 검색을 위한 파티션 매핑 기반 R-tree

강홍구(Hong-Koo Kang),김정준(Joung-Joon Kim),한기준(Ki-Joon Han) 대한공간정보학회 2009 한국지형공간정보학회 학술대회 Vol.2009 No.9

최근 u-GIS 환경에서는 RFID, GPS. Digital 카메라 등과 같은 다양한 Geosensor의 활용으로 위치 및 경계 데이타를 포함하여 수집되는 공간 데이타가 크게 증가하면서 대용량 공간 데이타의 신속한 검색을 위한 공간 인덱스의 중요성이 높아지고 있다. 특히, 대표적인 공간 인덱스인 R-tree를 기반으로 검색 성능을 높이기 위한 연구가 활발히 진행되고 있다. 그러나, 기존 연구는 R-tree에서 노드 간의 겹침이나 트리 높이를 줄임으로써 검색 성능을 향상시켰지만 트리 검색에서 발생하는 불필요한 노드 접근 문제를 효율적으로 해결하지 못하고 있다. 본 논문에서는 이러한 문제를 해결하고 R-tree에서 대용량 공간 데이타의 신속한 검색을 제공하는 인덱스로서 PMR-tree(Partition Mapping-based R-tree)를 제시한다. PMR-tree는 트리 검색 없이 R-tree 리프 노드를 직접 접근할 수 있는 매핑 트리를 이용함으로써 R-tree의 검색 성능을 높인다. 매핑 트리는 데이타 공간을 차원에 따라 반복적으로 분할한 파티션과 대응되는 R-tree 리프 노드의 MBR과 포인터를 이용하여 구성된다. 그리고 단순히 분할된 데이터 공간을 나타내는 파티션과 R-tree 리프 노드 간의 매핑 정보를 가지는 매핑 트리를 메인 메모리에 상주시킴으로써 R-tree 리프 노드의 접근 속도를 향상시킨다. 또한, 이러한 PMR-tree의 매핑 트리는 다양한 R-tree 변형 구조에도 쉽게 적용될 수 있는 장점이 있다. 마지막으로 성능 실험을 통하여 PMR-tree의 우수성을 입증하였다.

API 유사도 분석을 통한 악성코드 분류 기법 연구

강홍구 ( Hong-koo Kang ),조혜선 ( Hyei-sun Cho ),김병익 ( Byung-ik Kim ),이태진 ( Tae-jin Lee ),박해룡 ( Hae-ryong Park ) 한국정보처리학회 2013 한국정보처리학회 학술대회논문집 Vol.20 No.2

최근 인터넷 사용이 보편화됨과 더불어 정치적, 경제적인 목적으로 웹사이트와 이메일을 악용한 악성코드가 급속히 유포되고 있다. 유포된 악성코드의 대부분은 기존 악성코드를 변형한 변종 악성코드이다. 이에 변종 악성코드를 탐지하기 위해 유사 악성코드를 분류하는 연구가 활발하다. 그러나 기존 연구에서는 정적 분석을 통해 얻어진 정보를 가지고 분류하기 때문에 실제 발생되는 행위에 대한 분석이 어려운 단점이 있다. 본 논문에서는 악성코드가 호출하는 API(Application Program Interface) 정보를 추출하고 유사도를 분석하여 악성코드를 분류하는 기법을 제안한다. 악성코드가 호출하는 API의 유사도를 분석하기 위해서 동적 API 후킹이 가능한 악성코드 API 분석 시스템을 개발하고 퍼지해시(Fuzzy Hash)인 ssdeep을 이용하여 비교 가능한 고유패턴을 생성하였다. 실제 변종 악성코드 샘플을 대상으로 한 실험을 수행하여 제안하는 악성코드 분류 기법의 유용성을 확인하였다.