Earticle

멀티미디어정보검색 응용분야에서 내용－본위 이미지 검색은 유사성이 높은 멀티미디어 문서를 검색하는데 있어서 필수적이다. 따라서, 본 논문은 픽셀 (Pixel) 단위의 본래 이미지가 자동적 혹은 수동적으로 아이콘(icon) 객체로 구성된 아이콘 이미지로 변환될 때, 아이콘 이미지의 효율적인 표현과 검색을 제공하기 위함이다. 이를 위해 먼저 아이콘 객체를 점 대신에 사각형으로 표현함으로써 아이콘들간의 공간관계를 정확하게 표현할 수 있는 새로운 공간 매치 표현 기법을 제안한다. 또한, 이미지의 검색을 가속화시키기 위해, 2차원 시그니쳐 화일 구성을 사용한 효율적인 검색기법을 설계한다. 마지막으로, 성능 실험을 통하여 제안한 공간 매치 표현 기법이 기존의 9-DLT 표현 기법보다 더 나은 검색 효율을 나타냄을 보인다.

In multimedia information retrieval applications, content-based image retrieval is essential for retrieving relevant multimedia documents. The purpose of our paper is to provide effective representation and efficient retrieval of images when a pixel-level original image is automatically or manually transformaed into its iconic image containing meaningful graphic descriptions, called icon objects. For this, we first propose new spatial match representationschemes to describe spatial relationships between icon objects accurately by expressing them as rectangles, rather than as points. In order to accelerate image searching, we also design an efficient retrieval method using a two-dimensional signature file organization. Finally, we show from our experiment that the proposed representation schemes achieve better retrieval effectiveness than the 9-DLT (Direction Lower Triangular) scheme.

Given a site set P and an object set R, Bichroamtic RkNN query of site q∈P finds objects that take q as k nearest neighbors, which can been used to evaluate the influence of q on objects. Existing methods execute RkNN query by pruning strategies based on spatial indexes. For any change of object datasets (like moving objects), these methods need to compute RkNN again. The paper proposes a new algorithm based on K-order Voronoi diagrams. For a fixed site q, its RkNN region does not change whatever object datasets are updated or not. So we only search objects in Voronoi region of q. In this paper, we first give some propositions that provide the searching bounds. Then, BRKVD algorithm is proposed for RkNN query based on R-Tree, which supports the frequent changes of datasets and k. The experimental results show that the proposed algorithm performs the existing algorithms on efficiency.

Density based clustering algorithm is one of the primary methods for clustering in data mining. The clusters which are formed based on the density are easy to understand and it does not limit itself to the shapes of clusters. This paper gives a detailed survey of the existing density based algorithms namely DBSCAN, VDBSCAN, DVBSCAN, ST-DBSCAN and DBCLASD based on the essential parameters needed for a good clustering algorithm. We analyse the algorithms in terms of the parameters essential for creating meaningful clusters.

With the advancement of cloud computing technologies and the propagation of location-based services, research on outsourced spatial databases has been spotlighted. Therefore, the traditional spatial databases owners want to outsource their resources to a service provider so that they can reduce cost for storage and management. However, the issue of privacy preservation is crucial in spatial database outsourcing since user location data is sensitive against unauthorized accesses. Existing privacy-preserving query processing algorithms encrypt spatial database and perform a query on encrypted data. Nevertheless, the existing algorithms may reveal the original database from encrypted database and the query processing algorithms fall short in offering query processing on road networks. In this paper, we propose a privacy-preserving query processing algorithm which performs on encrypted spatial database. A new node-anchor index is designed to reduce unnecessary network expansions for retrieving k-nearest neighbor (k-NN) objects from a query point. Performance analysis shows that our k-NN query processing algorithm outperforms the existing algorithm in terms of query processing time and the size of candidate result.

Selectivity estimation for spatial query is curial in Spatial Database Management Systems(SDBMS). Many works have been performed to estimate accurate selectivity. Although they deal with some problems such as false-count, multi-count arising from properties of spatial dataset, they can not get such effects in little memory space.* Therefore, we need to compress spatial dataset into little memory. In this paper, we propose a new technique called MW Histogram which is able to compress summary data and get reasonable results. Our method is based on two techniques:(a)MinSkew partitioning algorithm which deal with skewed spatial datasets. efficiently (b) Wavelet transformation which compression effect is proven. We evaluate our method via real datasets. The experimental result shows that the MW Histogram has the ability of providing estimates with low relative error and retaining the similar estimates even if memory space is small.

GML 데이터는 일반적인 문자, 숫자 형태의 데이터와는 다르게 공간데이터의 특징과 (준) 구조적인XML 데이터의 성격을 동시에 지니고 있어 표준 데이터베이스에서 관리되기 힘들다. XML 저장이 가능한 데이터베이스는 GML 데이터를 효율적으로 저장할 수 있지만, 공간데이터 처리 능력이 부족하고, 공간데이터베이스는 XML 데이터를 저장하기 어렵다. 본 논문에서는 GML. 데이터를 공간데이터베이스에 저장하여 기존의 문제점들을 해결하고자 한다. 이를 위하여 GML 응용스키마로부터 OGC에서 제시한 공간데이터베이스의 스키마로 변환할 수 있는 방법을 제안하고 PostgreSQL/SPE 시스템을 기반으로 프로토타입 시스템을 구현하였다. 그 결과 다양한 기하 모델과 XML문서의 구조 정보를 포함하고 있는 GML 데이터들이 제안된 기법을 통하여 공간 데이터베이스에 저장될 수 있었고 저장된 데이터의 크기는 GML 파일로 존재할 때 보다 현격하게 적은 공간을 차지하였다. 또한 저장된 데이터에 대하여 공간, 비 공간 및 혼합 질의를 수행하여 저장된 GML 데이터들이 빠르게 검색되고 복잡한 질의가 손쉽게 수행될 수 있음을 보였다.

Managing GML data in traditional database systems is not efficient since It has not only characteristics of spatial data but also features of (semi) structured n documents. XML enabled database systems can manage U data efficiently, however they cannot handle spatial data. Spatial database systems are good at spatial data handling but those are inefficient for XML data. This paper proposes a storage method of GML data for spatial database systems in order to solve the problems. The proposed method generates spatial database schemas from GML application schemas and store GML data into SDBMS through the generated schemas. A prototype of the storage method has been implemented on the Postgre SQ/SPE system to show the proposed method is appropriate for storing GML data. As a result, the implemented system was able to store various GML data which had diverse XML structures and different size. Stored data size was smaller than GML files. Furthermore, spatial, non-spatial, and mixed content queries could be performed over the stored GML data as quickly.

Given a positive integer k as input, a spatial preference query finds the k best data objects based on the scores (e.g., qualities) of feature objects in their spatial neighborhoods. Several solutions have been proposed for spatial preference queries in Euclidean space. A few algorithms study spatial preference queries in undirected spatial networks where each edge is undirected and the distance between two points is the length of the shortest path connecting them. However, spatial preference queries have not been thoroughly investigated in directed spatial networks where each edge has a particular orientation that makes the distance between two points noncommutative. Therefore, in this study, we present a new method called ALPS+ for processing spatial preference queries in directed spatial networks. We conduct extensive experiments with different setups to demonstrate the superiority of ALPS+ over conventional solutions.

This paper addresses the efficient processing of all-farthest-neighbors (AFN) queries in spatial network databases. Given a set of data points P={p₁,p₂,…,p_|p|} in a spatial network, where the distance between two data points p and s, denoted by dist (p,s), is the length of the shortest path between them, an AFN query is defined as follows: find the farthest neighbor ω(p)∈P of each data point p such that dist(p,ω(p)) ≥ dist(p,s) for all s∈P. In this paper, we propose a shared execution algorithm called FAST (for All-Farthest-neighbors Search in spatial neTworks). Extensive experiments on real-world roadmaps confirm the efficiency and scalability of the FAST algorithm, while demonstrating a speedup of up to two orders of magnitude over a conventional solution.

다중 공간 질의는 동시에 2개 이상 수행되는 영역 질의로 정의되며 인터넷 기반 지도 보기 응용의 주요 연산이 되므로, 질의 처리 속도의 향상을 위해서 병렬로 처리되어야 하고 디스크 입출력 비용을 최대한 줄일 필요가 있다. 그런데 다중 공간 질의는 디스크 입출력 비용을 개선하기 위해 다중 CPU/다중 디스크 구조 상에서 디클러스터링을 수행하더라도 디스크 임의 탐색이 발생하는 문제점이 있다. 이 논문에서는 디클러스터링 된 공간 데이터베이스에서 다중 공간 질의를 처리할 때 발생하는 문제점인 질의 간임의 탐색을 분석하고, 해결 방안으로 질의 간 위치 관련성과 질의 처리 이력을 이용한 질의 스케줄링 기법을 제안하고 구현하였다. 실험을 통한 성능 평가 결과, 질의 스케줄링을 수행 할 경우 디스크 입출력 비용을 줄일 수 있어 다중 공간 질의 처리시의 성능을 개선할 수 있는 것으로 나타났다.

일반적으로 공간질의 처리는 복잡한 대용량 공간데이타를 대상으로 수행하기 때문에 많은 비용과 시간이 필요하다. 특히, 클라이언트/서버 공간 데이터베이스 환경에서는 클라이언트가 자주 이용하는 질의를 반복하여 처리하는 경우에 서버의 부하가 증가되며 질의 응답시간도 길어지게 된다. 따라서 클라이언트/서버 공간 데이타베이스에서 클라이언트측의 공간질의를 효율적으로 처리하기 위해서는 데이터 캐싱 등의 기법이 필요하다. 이를 위하여 본 논문에서는 클라이언트에서 자주 이용되는 공간질의를 뷰로 정의하고 클라이언트에서 실체화하는 방법을 이용하여 데이터 캐싱을 처리한다. 그리고 클라이언트에 실체화된 뷰를 최대한으로 이용하기 위하여 질의 수정 기법을 적용한 공간질의 처리 방법을 제시한다.

분산 지리정보시스템을 구현하는데 가장 어려운 점 중의 하나는 공간데이타베이스의 불일치이다. 특히, 여러 가지 이유로 발생하는 분산 공간 데이타베이스 사이의 위치 불일치는 공간 질의의 결과를 부정확하게 만든다. 하나의 간단한 해결책은 가장 중요한 사이트에 따라 각 사이트의 공간데이타베이스에 있는 위치 데이타를 보정하는 것이다. 그러나, 이러한 방법은 각 사이트의 자율성이 중시되어야 하는 경우에는 실용적이지 않다. 본 논문에서는 위치 데이타가 불일치하는 여러 개의 공간데이타베이스에 대하여 공간질의를 처리하는 방법을 제시한다. 본 논문에서 제시하는 방법은 각 지역 공간데이타베이스를 수정하지 않고 자율성을 보장하는 방식으로 공간질의를 처리할 수 있도록 한다. 본 논문에서 제안하는 방법은 탄성변형방법을 이용하면서, 각 질의의 위치를 동적으로 변환하는 방법에 기초하고 있다. 이 방법의 정확성은 수학적으로 증명이 되었으며, 실험으로도 확인하였다. 더욱이, 이 방법의 유용성 검증을 위하여 상용 데이타베이스시스템을 이용하여 구현하였다.

One of the most difficult problems in building a distributed GIS lies in the heterogeneity of spatial databases. In particular, positional mismatches between spatial databases, which arise due to several reasons, may incur incorrect query results. They result in unreliable outputs of query processing. One simple solution is to correct positional data in spatial databases at each site, according to the most accurate one. This solution is however not practical in cases where the autonomy of each database should be respected. In this paper, we propose a spatial query processing method without correcting positional data in each spatial database. Instead of correcting positional data, we dynamically transform a given query region or position onto each space where spatial objects of each site are located. Our proposed method is based on an elastic transformation method by using delaunay triangulation. Accuracy of this method is proved mathematically, and is confirmed by an experiment. Moreover, we implemented using common use database system for usefulness verification of this method.

국토정보화의 기반준비 단계인 ‘1차 국가 GIS 사업’기간 동안, 상당량의 수치화된 공간 정보가 축적되었고 이들을 관리하기 위한 다양한 종류의 지리정보시스템이 국가기관에서 사용되었다. 그러나, 사용중인 지리정보시스템은 조직적 지리적으로 분산되어 있으며, 공간데이타베이스의 이질성 및 폐쇄성으로 인해, 공간정보의 상호운용 측면에서 한계성을 드러내고 있다. 본 연구에서는 이러만 한계점을 극복하고자 분산 이기종 공간데이타베이스에 저장된 공간정보를 표준화된 방법으로 통합검색하며, 상호운용 가능토록 하는 국가공간정보유통체계를 설계 및 구현한다. 본 시스템을 구성하고 있는 단일 유통게이트웨이, 복수개의 유통노드, 지리정보공급기관을 국가통신망을 통하여 상호 연결하고, 컴퓨팅 부하를 분산시키기 위한 방안으로 공간정보유통망을 검색망 및 전송망으로 분리 설계한다. 검색망에서는 메타데이타의 검색 및 전송을 위한 표준화된 방법으로서 OpenGIS OLE DB Provider 기반 데이터제공자 컴포넌트를 구현한다. 또한 데이터제공자 컴포넌트를 통해 전송된 이기종 공간데이타베이스로부터의 WKB 형태의 공간정보를 상호운용할 목적으로, 공간데이타 구조와 처리에 대한 인터페이스 표준화를 실시한 MapBase 컴포넌트를 활용하여 공간정보에 대한 통합검색, 분석 및 상호운용을 구현한다.

최근 유비쿼터스 관련 연구가 활발히 이루어지고 있으며 이를 활용한 응용분야들이 확대되고 있다. 대표적인 응용분야로는 GPS를 이용한 실외측위기술을 기반으로 발전한 위치기반서비스(LBS)가 있으며, 현재 많은 서비스들이 상용화 되어 있다. 최근 들어서는 대규모 실내공간과 실내에서의 사고의 증가와 함께 실내 공간을 대상으로 하는 서비스에 대한 관심이 증가하고 있으며 관련된 연구들이 진행되고 있다. 실내 공간 응용기술의 핵심은 3차원 실내 공간데이터의 모델링 기법과 이와 연동 가능한 센서기술이다. 하지만 아직은 실내위치기반서비스를 위한 측위기술 및 공간데이터에 대한 표준과 활용방안이 미비한 상태이다. 본 연구에서는 실내 위치기반서비스에서 사용 가능한 간단한 3차원 실내 공간 데이터 모델의 구축방법과 이를 활용할 수 있는 방법론을 제시하고자 한다. 본 연구에서 제시하는 모델은 2차원 기반의 multi-layered 구조를 가지며, 2차원 및 3차원으로 가시화가 가능하도록 하였다. 또한 제시한 3차원 실내 공간 모델의 실내 기반 서비스로의 적용을 테스트하기 위하여 CA(cellular automata)기반의 대피 시뮬레이터와 대피 경로 안내 시스템 그리고 실내센서(카메라)와의 연동 등 몇 가지 응용분야에 대한 테스트를 수행하였다.

There is a growing interest in ubiquitous-related research and applications. Among them, GPS-based LBS have been developed and used actively. Recently, with the increase of large size buildings and disastrous events, indoor spaces are getting attention and related research activities are being carried out. Core technologies regarding indoor applications may include 3D indoor data modeling and localization sensor techniques that can integrate with indoor data. However, these technologies have not been standardized and established enough to be applied to indoor implementation. Thus, in this paper, we propose a method to build a relatively simple 3D indoor data modeling technique that can be applied to indoor location based applications. The proposed model takes the form of 2D-based multi-layered structure and has capability for 2D and 3D visualization. We tested three prototype applications using the proposed model; CA(cellular automata)-based 3D evacuation simulation, network-based routing, and indoor moving objects tracking using a stereo camera.

공간 관계는 공간 데이터베이스에서 질의 최적화를 위해 중요한 역할을 한다. 만일 공간 객체간의 공간 관계를 미리 알 수 있다면, 비용이 많이 드는 질의 처리는 피할 수 있다. 공간 데이터에 대한 공간 관계의 질의를 효과적으로 답하기 위해서는 각 공간 객체들의 공간 관계 파악이 중요하다. 그러나 방대한 양의 공간 데이터에 대하여 객체간의 모든 공간 관계를 저장한다는 것을 사실상 불가능하다. 이러한 문제를 해결하기 위해서는 자주 사용하는 공간 관계를 저장하고 자주 사용하지 않는 관계는 필요시 생성하는 것이 효율적이다. 본 논문에서는 공간 관계가 일부 주어졌을 때 주어진 공간 관계로부터 새로운 공간관계를 추론하기 위한 공간 관계 추론 규칙을 제시하고자 한다.

ASTER 위성영상을 이용하여 팽창성 점토광물인 일라이트 인자 추출 및 SVM 통계분석을 통해 산사태 취약성을 평가하였다. 연구지역의 산사태 발생지역은 항공사진 판독 및 현장 조사를 통해 분석하였다. GIS 기반 공간데이터베이스로는 지형도, 토양도, 임상도, ASTER 위성사진을 이용하였다. 수치지형도에서는 경사 및 경사방향, 곡률도, 계곡과의 거리, 도로와의 거리, 토양도에서는 유효토심, 토질, 토양지형, 토양 배수정도 및 토양 모재, 임상도에서는 경급, 영급 및 밀도를 위성사진에서는 일라이트 인자를 추출하였다. 산사태 발생요인 데이터베이스와 SVM 통계분석 및 가중치 계산을 통해 각 요소간의 상관관계 취약성도를 구하였다. AUC 검증 결과 일라이트 인자 적용결과는 76.46%의 예측 정확도를 보였으며 일라이트 인자 미적용 모델은 74.09%의 예측 정확도를 나타내었다. 이는 일라이트 인자가 산사태 취약성도 작성에 있어 중요한 자료로 사용될 수 있음을 나타낸다.

This study evaluates landslide susceptibility using statistical analysis by SVM (support vector machine) and the illite index of clay minerals extracted from ASTER(advanced spaceborne thermal emission and reflection radiometer) imagery which can be use to create mineralogical mapping. Landslide locations in the study area were identified from aerial photographs and field surveys. A GIS spatial database was compiled containing topographic maps (slope, aspect, curvature, distance to stream, and distance to road), maps of soil properties (thickness, material, topography, and drainage), maps of timber properties (diameter, age, and density), and an ASTER satellite imagery (illite index). The landslide susceptibility map was constructed through factor correlation using SVM to analyze the spatial database. Comparison of area under the curve values showed that using the illite index model provided landslide susceptibility maps that were 76.46% accurate, which compared favorably with 74.09% accuracy achieved without them.

분산된 공간 데이터를 효과적으로 저장. 관리하고 공유하기 위하여 분산 공간 데이터베이스 시스템의 필요성이 대두되었다. 분산 공간 데이터베이스 시스템은 많은 변화가 있는 환경이기 때문에 최적화된 질의 플랜을 작성하기가 어렵고 또한 고비용의 공간 연산 비용을 고려해야 하는 문제를 가지고 있다. 본 논문은 질의 실행 시간이 변화된 분산 데이터베이스 환경을 고려하여 질의를 수행하며 공간 조인을 병렬적으로 수행하는 동적 콜렉터를 제안한다. 동적 콜렉터는 분산 데이터베이스 환경의 변화에 적응할 수 있으며 분산 공간 조인을 효율적으로 처리할 수 있다.

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.

본 논문에서는 공간 데이터가 여러 서버에 분산 저장되어 있을 때, 여러 클라이언트에서 동시에 변경 작업을 수행하기 위한 미들웨어 컴포넌트를 설계한다. OpenGIS 구현 명세에는 변경을 위한 미들웨어 인터페이스가 정의되어 있지 않다. OLE DB 데이터 제공자의 변경 인터페이스 사용을 고려 할 수 있으나, 공간 관련성을 가지는 공간 객체의 특징을 반영하고 협동 작업을 통한 동시성 지원을 위해서는 새로운 인터페이스의 설계가 필요하다. 왜냐하면, 기존의 프로토콜을 이용한 인터페이스 구현으로는 클라이언트가 미들웨어를 통해서 분산된 공간 데이터에 대한 변경 작업 수행이 어렵기 때문이다. 본 논문은 분산된 공간 데이터 변경을 위한 인터페이스를 가진 서비스 제공가작 미들웨어를 통한 분산 공간 데이터 변경 프로토콜을 설계하는 것을 목적으로 한다. 즉, 분산된 공간 데이터의 확장 잠금 기법을 통한 일관성 제어와 협동 변경 트랜잭션에 대한 인터페이스를 정의하고, 분산 환경을 고려한 변경 프로토콜을 설계한다.

비용모델과 측정(Cost Model and Estimation)은 모든 DBMS에서 성능 측정을 하기 위한 기본적인 도구이다. 지금까지의 질의 수행에 대한 비용모델을 제시하는 연구가 많이 있었지만 대부분의 연구가 특정 부분에 대한 비용-CPU비용, 색인 방법에 대한 I/O횟수, I/O비용 등만을 고려함으로써 질의를 수행하는데 필요한 전체적인 비용을 산출하는데 부족한 점이 있었다. 그리고 병렬 공간 DBMS에 대한 비용모델을 산출하는 연구가 아직까지 이루어지지 않았다. 이 논문에서는 병렬 공간 DBMS에서 질의를 처리하는데 드는 전체적인 비용을 산출하고 있다. 기존의 연구에서 제시하고 있는 비용모델을 적용하고, 병렬 컴퓨터와 공간 데이터가 결합되었을 때의 고려사항을 추가하여 병렬 공간 DBMS에 적합한 전체적인 비용모델을 산출함으로써 병렬 공간 DBMS에서의 효율적인 질의수행에 대한 다른 연구를 수행할 때 비용모델에 대한 초석을 제공한다.

최근 이동 객체를 위한 공간 데이터베이스에 관한 연구가 활발히 진행되어 왔다. 그러나, 주로 제한조건이 없는 이상적인 공간에서의 연구가 진행되어져 왔기 때문에, 도로나 철도와 같은 이미 정해진 공간 네트워크 상에 적용하는데는 문제점을 지니고 있다. 따라서, 본 논문에서는 기존 연구가 지니고 있는 문제점을 제시하고, 공간 네트워크 데이터베이스에 적합한 효율적인 질의 처리 알고리즘을 설계한다.