*경* 스토어

*경*

개인

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

2개
전체 판매량

0개
최근 3개월 판매량

0개
자료후기 점수

평균A
자료문의 응답률

-

전체자료 2개

[알고리즘]External Search

External SearchContentsSequential Search1.1 정의 및 특성Indexed Sequential Search정의 및 특성자료 형태 및 검색자료 삽입자료 삭제M-Way Search 트리정의 및 특성성능B-트리정의 및 특성자료 삽입자료 삭제B*-트리정의 및 특성B-트리와의 비교B+-트리정의 및 특성B-트리 대비 B+-트리의 장점ConclusionReference1. Sequential Search1.1 정의 및 특성- 특정 레코드를 찾기 위해 파일상의 각 레코드에 대한 키를 처음부터 순차적으로 비교해 가면서 조사하는 방법- 주로 일괄처리 작업에 사용되며 어떠한 저장매체(주로 자기테이프)에서도 탐색이 가능2. Indexed Sequential Search2.1 정의 및 특성- 레코드들이 저장되는 단위별로 인덱스를 생성하고 이를 이용해 자료의 대략적인 위치를 먼저 검색하는 방법2.2 자료 형태 및 검색0123456A AB CC DE FG HI JK LM NO PQ RS TU VW XY ZC0F1J2N3R4V5Z62.3 자료 삽입0123456A AB CC DE FG HI JK LM NO PQ RS TU VW XY ZI- insert C,D,SCDS- insert T- 노드가 꽉 차 있으므로 분할이 일어남SCDT-insert ASACDT-insert M- 노드가 꽉 차 있으므로 분할되고 D가 부모 노드로 상승함DSACMT4.3 자료 삭제현재 노드가 리프노드가 아닌 동안- 현재 노드가 루트노드가 아니면서 [m-2]개의 키를 가지고 있으면 키 수를 증가시킴. (형제에게 빌리거나 형제와 결합하는 방법)- 현재 노드에 삭제키가 있으면 대체 키를 찾아 대체, 삭제키를 대체키로 바꿈.- 삭제키와 현재 노드의 키들을 비교해서 자식노드로 이동현재의 리프노드가 [m/2]개의 키를 가지고 있으면 키 수를 증가시킨다.(형제에게 빌리거나 형제와 결합하는 방법)리프노드에서 삭제키를 삭제.ex>- delete J- delete M- immediate successor와 대체- delete R- 형제 노드로부터 키를 빌려옴- delete A- 형제노드와 결합하여 하나의 노드가 됨- 리프노드에는 문제가 없으나 부모노드에 underflow 발생- 0, 1, 2 노드의 결합- 결과적으로 트리의 깊이가 줄어듦5. B*-트리정의 및 특성루트노드는 2 ~┗(2m-2)/3┛+1개의 자식 노드 보유내부노드는 최소한 ┏(2m-1)/3┓개의 자식 노드 보유트리의 모든 단말노드는 동일한 Level에 존재포인터가 i개인 비단말 노드는 i-1개의 키를 갖는다.B-트리와의 비교B-트리의 내부노드는 최소한 반이 차고, B*-트리는 최소한 2/3이 찬다. 따라서 노드의 개수가 같은 경우 트리의 높이가 낮을 확률이 높고, 탐색시간이 향상된다. 또한 키의 삽입시 B-트리 보다 분리횟수를 줄일 수 있다.6. B+-트리6.1 정의 및 특성루트노드는 0,2, 또는 m/2과 m개 사이의 서브트리를 갖는다.루트와 리프를 제외한 모든 노드는 최소 m/2개, 최대 m개의 서브트리를 가진다.모든 리프노드는 같은 레벨에 있다.리프가 아닌 노드에 있는 키 값의 개수는 그 노드의 서브트리수보다 하나 적다.리프노드는 데이터 파일의 순차세트를 나타내면 모두 리스트로 연결되어있다.6.2 B-트리 대비 B+-트리의 장점- 진정한 인덱스 순차 접근 방법을 제시- 인덱스 집합이 오직 분리자만을 담고 있기 때문에 B-트리보다 B+-트리를 생성하는 것이 쉽다. 그리고 더 낮은 높이의 트리를 형성한다.7. Conclusion순차 검색은 구현이 간단해서 사용하기 쉽다는 장점이 있지만 데이터 집합의 크기가 커질수록 이에 비례해서 검색에 필요한 연산의 반복 횟수가 증가하기 때문에 시간적인 면에서 비효율적이다.이 단점을 보완하기 위해서 소개된 아이디어가 인덱스 순차 검색인데, 여기에서는 인덱스 정보를 이용하여 원하는 데이터가 저장된 위치를 대략적으로 먼저 알아낸다. 따라서 일반 순차 검색 보다는 조금 더 효율적이지만 자료의 삽입, 삭제가 빈번히 일어나는 동적 데이터 집합인 경우에는 적합하지 못하다.반면 B트리는 외부장치로의 액세스를 최소화하도록 디자인 되어 있기 때문에 외부 검색에서 가장 널리 쓰인다. B트리는 새로운 데이터의 삽입이나 삭제가 일어나도 몇 가지 속성을 항상 만족시키도록 되어 있기 때문에 어떤 경우에도 최적의 외부탐색을 보장한다.일반 B트리 이외에도 몇 가지 특화된 B트리가 있는데 바로 B*트리와 B+트리다. B트리의 노드가 절반 이상 차있는 반면, B*트리는 2/3 이상 채우는 것을 조건으로 하기 때문에 저장공간의 효율성 측면에서 좀더 낫다. 또한 일반적으로 B 트리보다 높이가 낮을 가능성이 있기 때문에 탐색시간이 어느 정도 향상된다.B+트리는 적어도 1/2가 찬다는 것에서 B트리와 동일하지만 단말 노드에만 파일의 레코드 주소를 포함한다. 따라서 레코드로의 직접 접근 뿐만 아니라 순차 접근도 가능하게 한다.8. Reference- C로 설명한 알고리즘: 정익사 황종선, 정영직 공저 1996- C언어로 설명한 자료구조론: 정익사 황종선, 손진곤 공저 2000-알고리즘: 사이텍미디어 Neapolitan등 저/도경구 역1999- Algorithms(The Sprit of Computing 2nd Ed.): Addison-Wesley. David Harel. 1992.- Algorithms in C++: Addison-Wesley, Robert Sedgewick. 1992- The ubiquitous B-트리: Computing Surveys. D. Corner. 1979- Extendible Hashing – a fast access method for dynamic files.: ACM Transactions on Database Systems. R. Fagin, J. Nievergelt, N. Pippenger and H. R. Strong. 1979- Handbook of Algorithms and Data Structure: Addison-Wesley, G. H. Gonnet. 1984- Data Structures andAlgorithms 1(Sorting and Searching): SpringerVerlag, Berlin. K. Mehihorn. 1984- Principles of Database Systems: Computer Science Press, Rockville, MD. J. D. Ullman. 1982- Data Structure: Ellis Horowitz and Sartaj Sahni. 1984- B+ 트리s and indexed sequential files(A performance comparison): ACM SIGMOD. Batory. 1981

공학/기술| 2006.05.15| 6페이지| 1,000원| 조회(586)

알고리즘, 검색, search, external

미리보기

닫기
[데이터베이스] Data Warehouse & Data Mining 평가A좋아요

Data Warehouse데이터 웨어하우스는 1980년 중반 IBM이 Information warehouse라는 용어를 통해 처음으로 그 개념이 도입했고, 1980년 후반 Inmon이 데이터 접근 전략으로 이 개념을 사용함으로서 집중을 받게 되었다.1. Data Warehouse의 정의- 기억의 의사 결정 과정을 지원하기 위한 주제 중심적이고 통합적이며 시간성을 가지는 비휘발성 자료의 집합 (Inmon, 1992)- 기업 내의 의사 결정 지원 어플리케이션들을 위한 정보기반을 제공하는 하나의 통합된 데이터 저장 공간 (Kelly, 1994)- 의사 결정 지원에 효과적으로 사용될 수 있도록 다양한 운영 시스템으로부터 추출, 변환, 통합, 요약된 읽기 전용 데이터베이스 (Poe, 1994)2. Data Warehouse의 특성- 올바른 정보를 올바른 형태로 필요한 때에 맞춰 제공하기 위해 대량의 원시 데이터를 유용한 정보로 변환하는 엔진- 여러 개의 개별적인 운영시스템으로부터 많은 양의 데이터가 공급되며, 기본 자료구조가 운영시스템과 다르기 때문에 데이터들이 웨어하우스로 이동될 때에는 반드시 재구조화되어야 한다.- 전사적 모델에 기초하여 통합된다. 운영시스템의 대부분은 동일한 내용에 대해 다수의 버전이 존재하게 되는 반면 데이터 웨어하우스는 신뢰할 수 있는 하나의 버전을 사용자에게 제공한다.- 데이터들은 날짜 등의 정의된 기간과 관련되어 저장되므로 시간성을 가진다. 운영시스템의 데이터는 사용자가 사용하는 바로 그 순간의 정확성이 요구되지만, 웨어하우스의 데이터는 특정 시점을 기준으로 정확하다.- 접근이 용이해야 한다. 컴퓨터 시스템이나 자료구조에 대한 지식이 없는 사용자들의 PC가 웨어하우스에 연결되어 데이터에 접근하는 경우가 많으므로 그 과정이 신속하고 어렵지 않아야 한다.- 읽기 전용 데이터베이스이기 때문에 갱신이 일어나지 않는다.3. Data Warehousing의 등장 배경기존의 정보시스템은 단편적인 필요성에 의해 구축되었기 때문에 통합적이지 못했다. 또한 데이터와 어플리케이션의 밀접한 관계로 인해 데이터의 유지가 어렵고, 동일한 데이터가 여러 장소에 중복되어 존재하여 유지비용이 많이 드는 문제점이 있었다. 이는 데이터의 신뢰성, 생산성 측면에서 여러 장애를 가져왔고, 이런 문제점들을 해결하고자 데이터 웨어하우스라는 패러다임이 등장하게 되었다.4. Data Warehouse의 구조- Meta Data- 데이터 웨어하우스에 어떤 데이터를 어떻게 저장할지를 세부적으로 기술한 것.- 운영시스템의 데이터 구조를 데이터 웨어하우스의 구조로 매핑하는데에 필요한 알고리즘을 포함한다.- Current Detail Data- 일반적으로 디스크에 저장되며, 최근 변경된 내용이 반영되어 있다.- 최하위 레벨에 위치하기 때문에 양이 많다.- Older Detail Data- 가끔씩 필요한 데이터로 테이프 등의 장치에 저장한다.- Current Detail Data도 정의되는 시간 개념에 따라 Older Detail Data로 바뀐다.- Lightly Summarised Data- Current Detail Data를 약간 요약한 것으로 대개 디스크에 저장된다.- Highly Summarised Data- 약간 요약된 데이터를 다시 한번 요약한 것으로 주로 디스크에 저장된다.- 간결성 덕분에 액세스가 용이함.5. Data Warehousing의 구조데이터 웨어하우징 환경에서 정보의 흐름은 하나의 상품이 제조되어 소비자에 의해 이용되기까지의 과정과 비슷하다.- Source Data Layer- 운영데이터와 백업용 파일 등으로 구성되며, 가장 원시적인 정보의 집합장소이다.- Data Warehouse- 일반적으로 Data Mart를 통해 사용자가 접근하며, 데이터 마트를 구성하는 정보를 제공하는 역할도 담당한다.- Data Mart- 관계형 DB등을 이용하여 구축되며, 주제에 따른 data와 이를 업데이트 하는 프로세스 등으로 구성된다.- 사용자의 업무 구조를 반영한 구조를 갖고 있어서 일반 사용자들도 쉽게 액세스할 수 있으며, 시스템의 반응 속도가 빠르다.- Client System Layer- 사용자는 데이터 마이닝 어플리케이션, 웹브라우저 등을 이용하여 데이터 웨어하우스나 데이터 마트를 이용한다. 특히 웹브라우저의 경우 데이터 웨어하우스에 저장되어 있는 전사 혹은 부분 데이터를 전세계 어디서나 공유할 수 있다는 점 때문에 잠재시장이 크다.Data Mining1. Data Mining의 개념데이터 마이닝은 이전까지는 제기되지 않았던 질문에 대한 답을 제공한다. 즉, 지금까지 발전되지 않았던 데이터 사이의 상호관계를 분석하고, 그 패턴 및 규칙을 추론함으로써 의사결정을 지원하고 그 효과를 예측하기 위한 기법이라고 할 수 있다. 마이닝은 효과적으로 밝혀낼 수 없었던 데이터 웨어하우스 내의 정보를 다각도에서 분석하고 유용한 정보로 요약하는 과정이다.2. Data Mining의 지식 프로세스- 데이터의 추출 및 변형- 웨어하우스에서 시스템으로 데이터를 추출하고, 변형하여 로드하는 첫 과정- 샘플링 : 방대한 양의 데이터를 모두 분석하지 않고 샘플링을 통해 분석한다.- 정제 : 데이터의 정확도를 높이기 위해 오류나 중복된 데이터를 제거하는 작업.- 탐색 : DB를 살펴보는 작업으로 이미 알고 있는 사실의 수치화뿐만 아니라 다른 변수들 사이의 관계를 알아보기도 한다.- 보완 : 데이터의 양과 깊이를 더하는 단계로 정보의 품질 향상에 기여함.- 데이터의 저장 및 관리 : 다차원 DBS에 데이터를 저장, 관리하는 단계- 데이터의 분석 : 가장 중요한 단계로 선행 단계에서 정해진 주요 변수를 이용해 예측력이 뛰어난 것을 선택- 데이터의 전시 : 마이닝의 수행 결과를 사용자들이 보기에 편하고 이해하기 쉬운 형태로 바꿔 제공3. Data Mining의 모델- Association (연합) : 하나의 이벤트가 다른 이벤트와 상호 관련성이 있는 경우(예) 분유 구입자가 기저귀를 함께 구입하는 것과 같이 동시에 구매될 가능성이 큰 상품들을 찾아내는 것- Sequence (연속) : 하나의 이벤트가 뒤를 잇는 다른 이벤트를 일어나도록 하는 경우(예) 청소기를 구입한 구입자가 후에 필터를 추가로 구입하는 것

공학/기술| 2004.09.13| 4페이지| 1,000원| 조회(676)

Database, 데이터 마이닝, 데이터 웨어하우스, data warehous..

미리보기

닫기