[논문]그래프이론에 의한 데이터베이스 세그먼트 분산 알고리즘

김중수

doi:10.9717/kmms.2019.22.2.225

그래프이론에 의한 데이터베이스 세그먼트 분산 알고리즘
Database Segment Distributing Algorithm using Graph Theory 원문보기

멀티미디어학회논문지 = Journal of Korea Multimedia Society, v.22 no.2, 2019년, pp.225 - 230

김중수 (Dept. of Computer Engineering Andong National University)

Abstract ▼ AI-Helper

There are several methods which efficiencies of database are uprise. One of the well-known methods is that segments of database satisfying a query was rapidly accessed and processed. So if it is possible to search completely parallel multiple database segment types which satisfy a query, the response time of the query will be reduced. The matter of obtaining CPS(Completely Parallel Searchable) distribution without redundancy can be viewed as graph theoretic problem, and the operation of ring sum on the graph is used for CPS. In this paper, the parallel algorithm is proposed.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문은 그래프이론을 이용하여 완전 병렬 접근이 가능한 데이터베이스 세그먼트 분배 알고리즘을 Gr1 개발하고 그 수행과정을 예시하였다. 이 알고리즘도 세그먼트의 중복없이 각 기기에 분배될 수 있도록 개발되었다.

제안 방법

이 알고리즘도 세그먼트의 중복없이 각 기기에 분배될 수 있도록 개발되었다. 알고리즘 Gr1의 시간 및 공간 복잡도를 고찰하였다.

성능/효과

따라서 알고리즘 Gr1의 시간 복잡도는 알고리즘 1, M1의 O(n³)인데 비해서 O(n²)으로 감소함을 보였다.
각 이 필요로 하는 데이터베이스 세그먼트들이 평행검출이 가능하도록 분배가 되면 쿼리에 대한 응답 시간을 줄일 수 있다. 이러한 문제를 해결하기 위하여 그래프이론을 이용하여 만든 데이터베이스 세그먼트 분배알고리즘 Gr1의 시간 복잡도가 행렬을 이용하여 만든 알고리즘 1과 M1의 시간 복잡도 O(n³)에서 O(n²)으로 감소함을 보였고, 또 공간 복잡도에서는 알고리즘 Gr1은 알고리즘 1보다는 효율이 좋으나 알고리즘 M1보다는 뒤떨어진다. 그러나 효율적인 분배에서는 알고리즘 M1에 가까이 감을 보였다.

질의응답

핵심어	질문	논문에서 추출한 답변
	본 논문에서 소개한 데이터베이스에서 쿼리의 빠른 처리를 하기 위하여 각 세그먼트의 분배문제를 해결하기 위하여 노력한 연구들은?	그리고 데이터베이스에서 쿼리의 빠른 처리를 하기 위하여 각 세그먼트의 분배문제를 해결하기 위하여 노력한 연구들도 있다.Ghosh는 하나의 을 만족하는 데이터 베이스 세그먼트들을 중복 없이 분배하는 방법으로 알고리즘1, 2를 제안[9]하였고, Srinivasan과 Sankar는 이 알고리즘을 보다 수행속도가 개선된 알고리즘 M1, M2[10]를 발표했다. 이 방법들은 하나의 쿼리을 처리하기 위하여 각 세그먼트를 중복없이완전 병렬로 접근이 가능하도록 각 세그먼트를 분배할 수 있 알고리즘들이다.
	바이오 데이터를 처리하는 방법 중 중복처리감소를 위한 데이터셋은?	또 공간관계와 공간조인을 위하여 중복 및 이중 데이터 처리방법을 보여주고 있다[5]. 바이오 데이터를 처리하는 방법으로 중복처리감소를 위한 단백질 순서데이타셋(protein sequence datasets)를 소개하기도 하였다[6]. 검색능력과 불필요한 중복간의 상쇄[tradeoff] 관계를 보여주고 또한 정보의 이론적인 특징 평가 전략을 제시 하였다[7].
	Ghosh가 제안한 데이터 베이스 세그먼트 방법의 특징은?	그리고 데이터베이스에서 쿼리의 빠른 처리를 하기 위하여 각 세그먼트의 분배문제를 해결하기 위하여 노력한 연구들도 있다.Ghosh는 하나의 을 만족하는 데이터 베이스 세그먼트들을 중복 없이 분배하는 방법으로 알고리즘1, 2를 제안[9]하였고, Srinivasan과 Sankar는 이 알고리즘을 보다 수행속도가 개선된 알고리즘 M1, M2[10]를 발표했다. 이 방법들은 하나의 쿼리을 처리하기 위하여 각 세그먼트를 중복없이완전 병렬로 접근이 가능하도록 각 세그먼트를 분배할 수 있 알고리즘들이다.

참고문헌 (12)

P.A. Berstein, V. Hadzilacos, and N. Goodman, Concurrency Control and Recovery in Data-Base Systems, Addison-Wesley, Boston, 1987.
P.A. Berstein and E. Newcomer, Principles of Transaction Processing, Morgan Kaufmann, San Francisco, 1996.
T.W. Ling, M.L. Lee, and G. Dobbie, Semistructured Database Design, Springer, Berlin, 2005.
D.B. Little, S, Farmer, and Q. El-Hilali, Digital Data Integrity : The Evolution from Passive Protection to Active Management, John Wiley and Sons ltd, Symantec Corporation, Wiley, 2007.
D. Dittrich and B. Seeger, "Data Redundancy and Duplicate Detection in Spatial Join Processing," Preceeding of International Conference on Data Engineering, pp. 535, 2000.
K. Sikic and O. Carugo, "Protein Sequence Redundancy Reduction: Comparison of Various Method," Bioinformation, Vol. 5, No. 6, pp. 234-239, 2010.

상세보기
C. Hazirbas, J. Diebold, and M. Cremers, "Optimizing the Relevance-Redundancy Tradeoff for Efficient Semantic Segmentation," Proceeding of International Conference on Scale Space and Variational Methods in Computer Vision, pp. 243-255, 2015.
A.S. Oh and O.H. Kwon, "Database Construction for Design of the Components Software by Using an Incremental Update Propagation," Journal of Korea Multimedia Society, Vol. 6, No. 4, pp. 583-593, 2003.

원문보기 상세보기
S. Ghosh, “Distribution a Database with Logical Associations on a Computer Network for Parallel Searching,” IEEE Transactions on Software Engineering, Vol. SE-2, No. 2, pp. 106-113, 1976.

상세보기
B. Srinivasan and R. Sankar, “Algorithms to Distribute a Database for Parallel Searching,” IEEE Transactions on Software Engineering, Vol. 7, No. 1, pp. 112, 1981.

상세보기
N. Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice Hall, New Jersey, 1974.
J.L. Gros and J .Yellen, Graph Theory and Its Application, CRC Press, Boca Raton, 2005.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증