블로그 이미지
충남대학교대학원 컴퓨터공학과 박사1년차 석박사통합과정 데이터베이스시스템연구실 Yim, Hyung-jun
 

'Research & Paper'에 해당되는 글 6건

  1. 2009/09/30 DFA and NFA
  2. 2009/09/29 Hash Operations in Database System
  3. 2009/09/23 Performance Analysis
  4. 2009/09/18 Challenge in 20s Ph.D. (2)
  5. 2009/08/03 EndNote X2 사용기
  6. 2008/09/30 VLDB, SIGMOD, ICDE Paper Search
 

DFA and NFA

Research & Paper | 2009/09/30 18:33 | Posted by Yim, Hyung-jun
DFA (Deterministic Finite Automata): 결정적 유한 오토마타
DFA의 표현
M = (Q, ∑, δ, q0, F)
- Q: 상태들의 유한집합(Finite set of states)
- ∑: 입력 알파벳이라고 불리는 유한개의 심볼들의 집합
- δ: Q X ∑ → Q인 전이 함수(transition function)
- q0: q0 ∈ Q인 시작 상태(start state)
- F: F ⊆ Q인 최종 상태의 집합(set of final state

- example DFA model

- State Diagrams



NFA (Nondeterministic Finite Automata): 비결정적 유한 오토마타
- NFA의 표현
M = (Q, ∑, δ, q0, F)
δ: Q X ( ∑ ∪ { λ }) → 2Q
- 2Q 란 수학적으로 P(Q)인 멱집합(Power set)인데 Q의 모든 부분집합의 집합을 의미
- NFA의 두 가지 형태로는
- 첫째, 어떤 상태에서 입력이 중복되어 나타나는 경우
- 둘째, λ-전이가 있는 경우

DFA and NFA
- 차이점
 ■ 치역
   @ NFA에서의 치역이 멱집합 2Q 내에 있고, 그 값이 Q의 단일 원소가 아닌 Q의 부분집합
 ■ NFA에서 전이함수의 인수로 허용
   @ 입력 심볼을 읽지 않고도 전이가 가능함
 ■ NFA에서는 집합 (qi, a)가 공집합을 허용
   @ 특정 상황에 대하여 정의된 전이가 없을 수 있음

'Research & Paper' 카테고리의 다른 글

DFA and NFA  (0) 2009/09/30
Hash Operations in Database System  (0) 2009/09/29
Performance Analysis  (0) 2009/09/23
Challenge in 20s Ph.D.  (2) 2009/09/18
EndNote X2 사용기  (0) 2009/08/03
VLDB, SIGMOD, ICDE Paper Search  (0) 2008/09/30
TAG automata, Deterministic, DFA, finite, nfa, Nondeterministic, 결정적, 비결정적, 오토마다, 유한, 대한민국>대전광역시>유성구>궁동>충남대학교>공과대학 2호관>332호>데이터베이스시스템연구실
Trackback (0) : Comment (0)

Hash Operations in Database System

Research & Paper | 2009/09/29 17:32 | Posted by Yim, Hyung-jun

[용어]

- table(relation): DB를 이루는 기본적인 단위
- tuple(row, record): table의 각 행
- attribute(column, field): relation을 구성하는 요소
- bucket: 하나의 주소를 갖는 파일의 한 구역을 의미(한 개 혹은 보다 많은 레코드를 저장할 수 있는 저장 공간의 단위), 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미
- slot: 한 개의 레코드를 저장할 수 있는 공간으로, n개의 슬롯이 모여 하나의 버킷을 형성
- collision: 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
- synonym: 같은 home address를 갖는 레코드들의 집합
- overflow: 계산된 home address의 bucket을 구성하는 slot이 여러 개 일 때 collision은 발생해도 overflow는 발생하지 않을 수 있음

[Hash]

- 키값을 난수로 변환하여 필요한 주소를 산출하는 직접 주소법
- 해시 함수를 이용하여 데이터베이스에서 자료를 색인하고 신속하게 자료를 검색하는데 사용

[Hash Function]

- 임의의 길이에 이진 문자열을 고정된 길이의 이진 문자열로 매핑하여 주는 함수
- 검색키에 있는 문자를 이진으로 표현한 후에 계산 수행
- h는 K를 B에 대응시키는 함수
 ■ K: 모든 검색키 값의 집합
 ■ B: 모든 버켓 주소의 집합
 ■ h: 해시 함수
- 레코드 키 값(k) → 해싱 함수 h(k)→ 해상표의 상대주소
- hash의 사용
 ■ 해시 파일 구조: 레코드의 검색키 값에 대한 함수 계산을 통해 원하는 레코드를 가진 디스크 블록의 주소를 직접 얻을 수 있음
 ■ 해시 인덱스 구조: 검색키들과 관련된 포인터들을 해시 파일 구조로 조직화할 수 있음

[Hash File Organization]

- 해시 파일 구조는 이름을 키로 갖는 account 파일의 해시 함수는 다음과 같다.
- 레코드의 분배가 균등해야 함 (그렇지 않으면, 하나의 버켓에 몰려있는 현상이 있을 수 있어 특정 버켓에 있는 레코드를 모두 검색해야 하는 문제점이 있을 수 있음)



[Hash Index]

- 검색키, 이와 연관된 포인터를 해시 파일 구조 안에 구성
- 2차 해시 인덱스는 다음과 같다.


[Hash Table]

- 레코드의 저장을 위한 자료구조로써 해상함수로부터 계산된 함수값에 해당하는 위치에 각 레코드를 한 개 이상 보관할 수 있는 버켓(bucket)들로 구성된 기억 공간이며, 주어진 key값을 가지고 해당 레코드를 빠르게 검색하기 위한 수단을 제공하며 레코드의 삽입과 삭제가 용이
- 해시 테이블은 파일의 레코드의 키 값에 대응하는 해시주소와 레코드를 저장하는 공간은 버켓으로 구성
- 포인터를 사용하여 구현하는 경우에는 실제의 레코드 대신에 레코드가 저장되어있는 메모리 포인터를 저장
- 파일 내의 키 값에 해시함수를 적용하여 해시주소를 생성



- 해슁의 절차
 ■ 파일 내 모든 레코드의 키 값을 해시함수를 사용해 해시주소Hash Address를 구한다. 
 ■ 해시주소로 해시 테이블을 구성, 해시주소의 버켓에 레코드를 입력한다. 
 ■ 검색대상 레코드의 키 값에 해시함수를 적용, 해시주소를 구한다. 
 ■ 해시 테이블에서 해시주소로 레코드를 검색 

- 해시 테이블: 해시 테이블의 크기는 파일의 크기보다 커야한다. 왜냐하면, 주어진 n개의 레코드에 대해 n개의 해시주소를 생성하기 위한 해시함수는 찾는 것은 불가능하기 때문이다. 대부분의 경우에는 일정한 범위에 산발적으로 데이터가 분포하기 때문에 이러한 분포를 가진 데이터를 함수를 적용하여 최대한 밀집된 범위의 주소로 매핑하는 것은 한계가 있다.
- 해시 테이블의 크기가 적어지는 경우에는 서로 다른 키 값에 대해 동일 해시주소가 생성되는 경우가 발생하는데 이러한 현상을 해시충돌Hash Collision이라고 한다.

- 해시 테이블의 검색 속도는 O(1+n/m)으로 표현
 ■ m은 slot의 개수
 ■ n은 원소의 개수
 ■ n/m은 흔히 load factor로 표현




[참고]
- 해시: http://internet512.chonbuk.ac.kr/datastructure/hash/hash1.htm
- 해시 애니메이션 툴: http://www.engin.umd.umich.edu/CIS/course.des/cis350/hashing/WEB/HashApplet.htm
- 해시 애니메이션 툴 자바: http://www.engin.umd.umich.edu/CIS/course.des/cis350/hashing/Source/HashApplet.java 
- 바게의 열린공간, 해시함수(Hash function): http://blog.bagesoft.com/876
- hash: http://burtleburtle.net/bob/hash/doobs.html
- hash table: http://www.itl.nist.gov/div897/sqg/dads/HTML/hashtab.html
- gwLee's study: http://www.thegreatgoodplace.com/tt/study/103

'Research & Paper' 카테고리의 다른 글

DFA and NFA  (0) 2009/09/30
Hash Operations in Database System  (0) 2009/09/29
Performance Analysis  (0) 2009/09/23
Challenge in 20s Ph.D.  (2) 2009/09/18
EndNote X2 사용기  (0) 2009/08/03
VLDB, SIGMOD, ICDE Paper Search  (0) 2008/09/30
TAG Attribute, bucket, collision, column, Database, Field, HASH, hash function, hash index, hash table, record, relation, Row, Slot, table, Tuple, 해쉬, 해쉬함수, 대한민국>대전광역시>유성구>궁동>충남대학교>공과대학 2호관>332호>데이터베이스시스템연구실
Trackback (0) : Comment (0)

Performance Analysis

Research & Paper | 2009/09/23 18:22 | Posted by Yim, Hyung-jun
Performance Analysis
- Space Complexity
S(P) = c + Sp(I)
S(P): Total Space Requirement
c: 고정 기억 사용량
Sp(I): 특정 instance I 값에 따라 달라지는 변수에 필요한 기억 공간

- Time Complexity
[Asymptotic Analysis]: 정확한 step count 계산은 쉬운일이 아니기 때문에, step 자체가 정확한 time을 나타내지 않으므로 근사치를 사용
즉, 어느 지점으로 근접해 간다고 보면 된다. 근사치에는 다음의 3개의 notation이 존재한다.

Ο(Big-O)
- definition: f(n)=O(g(n)) iff f(n) <= c*g(n), for all n>=n0 (if n > 0, n is natural number)

- example
■ f(n) = 3n + 2, g(n) = 4n, f(n) <= g(n), 3n +2 <= 4n, for all n >= 2
[f(n)의 가장 큰 차수의 계수에 +1를 한  g(n)이 f(n)보다 항상 커지게 되는 n을 구한다.]

■ f(n^2) = 10n^2 + 4n + 2, g(n^2) = n^2,
f(n^2) <= g(n^2),
10n^2 + 4n + 2 <= 11n^2,
for all n >= 5
[if n = 5, f(5) = 250 + 20 + 2 = 272, g(5) = 275
if n = 6, f(6) = 360 + 24 + 2 = 386, g(6) = 396
for all n >= 5]

■ f(2^n) = 6 * 2^n + n^2, g(2^n) = 7 * 2^n,
f(2^n) <= g(2^n),
6 * 2^n + n^2 <= 7 * 2^n,
for all n >= 4
[if n = 4, f(4) = 96 + 16 = 112, g(4) = 112
if n = 5, f(5) = 192 + 25 = 217, g(5) = 224
for all n >= 4]

- The mean of the expression
■ O(1) = constant
■ O(n) = linear
■ O(log n)
■ O(nlog n)
■ O(n^2) = polynomial
■ O(2^n) = exponential

■ sublinear
f(x + y) <= f(x) + f(y), for all x, y
■ superlinear
f(x + y) >= f(x) + f(y), for all x, y

(a) sublinear (b) exponential (c) superlinear (d) Collapse characterizes superlinear dynamics when resources are scarce


(a) superlinear (b) linear (c) sublinear

- Order
■ O(1) >= O(log n) >= O(n) >= O(nlog n) >= O(n^2) >= O(2^n) >= O(n!)

- Growth Rates


- Summary
■ Big-O(O) notation is the upper bound of time complexity
■ f(n) ⊂ g(n), f(n) is big-O of g(n)
■ f(n)은 아무리 오래 걸려도 g(n)보다는 빠르다.

Ω(Omega)
- definition: f(n)=Ω(g(n)) iff f(n) >= c*g(n), for all n>=n0 (if n > 0, n is natural number)

- example
■ f(n) = 3n + 2, g(n) = 3n, f(n) >= g(n), 3n +2 >= 3n, for all n >= 1
[O(n)의 가장 큰 차수의 계수와 동일하게 g(n)을 만들어 f(n)이 g(n)보다 항상 커지게 되는 n을 구한다.]

■ f(n^2) = 10n^2 + 4n + 2, g(n^2) = n^2,
f(n^2) >= g(n^2),
10n^2 + 4n + 2 >= 10n^2,
for all n >= 1
[if n = 1, f(1) = 10 + 4 + 2 = 16, g(1) = 10, for all n >= 1]

■ f(2^n) = 6 * 2^n + n^2, g(2^n) = 7 * 2^n,
f(2^n) >= g(2^n),
6 * 2^n + n^2 <= 6 * 2^n,
for all n >= 1
[if n = 1, f(1) = 12 + 1 = 13, g(1) = 12, for all n >= 1]

- Summary
■ Omega(Ω) notation is the lower bound of time complexity
■ g(n) ⊂ f(n), g(n) is Omega of f(n)
■ f(n)은 아무리 적게 걸려도 g(n)보다는 느리다.

Θ(Theta)
- definition: f(n)=Θ(g(n)) iff c1g(n) <= f(n) <= c2g(n), for all n >= n0 (if n > 0, n is natural number)

- example
■ f(n) = 3n + 2, c1g(n) = 3n, c2g(n) = 4n, c1g(n) <= f(n) <= c2g(n), 3n <= 3n+2 <= 4n, for all n >= 2
[n이 커짐에 따라 상수는 Time Complexity에 크게 영향을 주지 못하므로 c1, c2 사이로 계산된다.]

■ f(n^2) = 10n^2 + 4n + 2, c1g(n^2) = 10n^2, c2g(n^2) = 11n^2,
c1g(n^2) <= f(n^2) <= c2g(n^2),
10n^2 <= 10n^2 + 4n + 2 <= 11n^2,
for all n >= 5
[if n = 5, c1g(5) = 250, f(5) = 250 + 20 + 2 = 272, c2g(5) = 275, for all n >= 1]

■ f(2^n) = 6 * 2^n + n^2, c1g(2^n) = 6 * 2^n, c2g(2^n) = 7 * 2^n,
c1g(2^n) <= f(2^n) <= c2g(2^n),
6 * 2^n <= 6 * 2^n + n^2 <= 7 * 2^n, for all n >= 1
[if n = 1, c1g(1) = 12, f(1) = 12 + 1 = 13, c2g(1) = 14, for all n >= 1]

- Summary
■ Theta(Θ) notation is the good position of time complexity between upper bound and lower bound

References
* doAsYouWant, Performance Analysis, http://blog.naver.com/zephyehu?Redirect=Log&logNo=150007785290

'Research & Paper' 카테고리의 다른 글

DFA and NFA  (0) 2009/09/30
Hash Operations in Database System  (0) 2009/09/29
Performance Analysis  (0) 2009/09/23
Challenge in 20s Ph.D.  (2) 2009/09/18
EndNote X2 사용기  (0) 2009/08/03
VLDB, SIGMOD, ICDE Paper Search  (0) 2008/09/30
Trackback (0) : Comment (0)

Challenge in 20s Ph.D.

Research & Paper | 2009/09/18 11:10 | Posted by Yim, Hyung-jun

우연히, 박사과정 연구에 대한 웹 검색을 해보니 http://gogunhwa.tistory.com 이 분의 블로그에 대한 내용이 들어왔다.
그 동안 이런 노력도 안했으면서 좋은 연구를 하기만 바랬던가,

글에는 특히 미국대학에 진학하는 박사과정들에게 유용하다고 했지만, 읽어 볼 가치는 충분히 있는 것 같다.

Applying to Ph.D. Programs in Computer Science.pdf

http://www.cs.cmu.edu/~harchol/gradschooltalk.pdf

또한, How to write a great research paper 이것도 확인해야 할 듯
How to write a great research paper.pdf

http://research.microsoft.com/en-us/um/people/simonpj/papers/giving-a-talk/writing-a-paper-slides.pdf

마지막으로, http://gogunhwa.tistory.com/11 대학원생 서바이벌 가이드 총망라에 제가 찾아보고 싶은 내용들이 잘 정리되어 있네요, 감사합니다.

Before you go to a graduate school
 - Applying to Ph.D. Programs in Computer Science - Mor Harchol-Balter
General Graduate School Survival Guide
 - Some Modest Advice for Graduate Students - Stephen C. Stearns
 - How to Be a Good Graduate Student - Marie desJardins
 - So long, and thanks for the Ph.D.! (a.k.a. "Everything I wanted to know about C.S. graduate school at the beginning but didn't learn until later") - Ronald T. Azuma
Writing Guide
 - The Science of Scientific Writing - George D. Gopen and Judith A. Swan

'Research & Paper' 카테고리의 다른 글

DFA and NFA  (0) 2009/09/30
Hash Operations in Database System  (0) 2009/09/29
Performance Analysis  (0) 2009/09/23
Challenge in 20s Ph.D.  (2) 2009/09/18
EndNote X2 사용기  (0) 2009/08/03
VLDB, SIGMOD, ICDE Paper Search  (0) 2008/09/30
TAG paper, Ph.D., research, 고군화, 논문, 박사과정, 연구
Trackback (0) : Comment (2)

EndNote X2 사용기

Research & Paper | 2009/08/03 16:28 | Posted by Yim, Hyung-jun

예전부터 한 번 봐두어야 할 프로그램이었지만, 미루고미루다 보니 지금까지 왔다.
앞으로 논문을 작성할 경우에 사용해야 겠다.
웹에서 검색해서 바로 참고문헌 목록으로 만들어 주기도 하고, 참고 문헌 관리에 좀 더 편리하고 확실하게 할 수 있다.
따로 관리하던 것을 없애고 이 프로그램으로 와야 겠다.

학교에서 프로그램이 지원이 되기 때문에 더욱이 써볼만하다.
자세한 사용법은 아래의 참고 자료를 이용하기 바랍니다.
EndNote X2 사용법

19_EndNote_X2_QRG[1].pdf


EndNote Web 사용법

EndNote Web QuickRef.Guide(2007.6).pdf
EndNoteWebGuide2(2007.6).ppt


라이브러리를 생성하게 되면 다음 그림과 같이 참고문헌을 추가할 수 있도록 한다.
사용자가 그룹을 만들게 되면 Custom Group으로 생성이 된다.


EndNote X2를 설치하면, Word 프로그램 안에도 다음과 같이 연동할 수 있도록 제공된다.

'Research & Paper' 카테고리의 다른 글

DFA and NFA  (0) 2009/09/30
Hash Operations in Database System  (0) 2009/09/29
Performance Analysis  (0) 2009/09/23
Challenge in 20s Ph.D.  (2) 2009/09/18
EndNote X2 사용기  (0) 2009/08/03
VLDB, SIGMOD, ICDE Paper Search  (0) 2008/09/30
TAG EndNote X2, paper, References, 관리, 논문, 참고문헌, 대한민국>대전광역시>유성구>궁동>충남대학교>공과대학 2호관>332호>데이터베이스시스템연구실
Trackback (0) : Comment (0)

VLDB, SIGMOD, ICDE Paper Search

Research & Paper | 2008/09/30 20:19 | Posted by Yim, Hyung-jun

VLDB, SIGMOD, ICDE Paper Search

1. VLDB (Very Large Data Bases) Conference
- http://www.vldb.org
- 무료로 Proceeding과 Journal을 볼 수 있게 한 학회
- Proceeding: http://www.vldb.org/dblp/db/conf/vldb/index.html
- Journal: http://www.vldb.org/dblp/db/journals/vldb/index.html

2. SIGMOD (International Conference on Management of Data)
- http://www.sigmod.org
- Proceeding: ACM Digital Library Home → Proceeding → SIGMOD
- ACM Digital Library: http://portal.acm.org/dl.cfm

3. ICDE (International Conference on Data Engineering)
- http://ieeexplore.ieee.org/servlet/opac?punumber=1000178

4. UbiComp
- Springer Search: www.springer.com
- 온라인으로 볼 수 있는 방법은? 추후 알아봐야 할 것

5. PerCom (Pervasive Computing and Communications)
- http://www2.computer.org/portal/web/csdl/proceedings/p#2
- Proceeding: IEEE Computer Society Digital Library → Proceeding → "P" → PerCom
- IEEE Computer Society Digital Library: http://www2.computer.org/portal/web/csdl

6. Pervasive (International Conference on Pervasive Computing)
- A+

7. ICSPC (International Conference on Security in Pervasive Computing)
- A

8. Mobiquitous (International Conference on Mobile and Ubiquitous Systems: Networks and Services)
- A

- 논문 주제 선정
 * Conference Proceeding의 논문 제목과 Abstract 정도만 발췌
 * Journal은 논문 주제가 선정되면 관련 분야로 볼 것
 * 연구실 일과 관련된 주제로 선정
 * 참신한 주제 (참신하다고 생각되면 1~3년 정도의 Proceeding을 확인)
 * 최근에 발행된 Proceeding 부터 확인
 * VLDB, SIGMOD 위주의 논문 보기
 * ICDE는 시간이 날 경우 챙겨 볼 것
 * 1~2명 정도의 인원이 구현해 볼만한 규모

- 논문 주제 선정 후
 * 깊게 파고 들 것
 * Reference에 대한 추적 필요

- 논문에 사용된 용어
 * Wikidepia 참고: 알고리즘이나 개념

- Conference Ranking
 * Computer Science Conference Ranking
  # http://cs-conference-ranking.org/conferencerankings/alltopics.html
  # 국제 학회에 대한 평가
  # 1점 만점에 대한 점수 부여
 
 * Computing Research & Education
  # http://www.core.edu.au/rankings/Conference%20Ranking%20Main.html
  # A+ (6%), A (27%), B (31%), C (29%), L (6%)
  # 학회에 대한 점수 부여보다는 등급으로 표시

Conference Ranking
http://www3.ntu.edu.sg/home/ASSourav/crank.htm

개인적인 자료입니다.
참고하실 분만 하시되 책임은 지지 않습니다.


'Research & Paper' 카테고리의 다른 글

DFA and NFA  (0) 2009/09/30
Hash Operations in Database System  (0) 2009/09/29
Performance Analysis  (0) 2009/09/23
Challenge in 20s Ph.D.  (2) 2009/09/18
EndNote X2 사용기  (0) 2009/08/03
VLDB, SIGMOD, ICDE Paper Search  (0) 2008/09/30
TAG acm, Computer Society, Conference, ICDE, IEEE, Journal, paper, PerCom, proceeding, Ranking, research, SIGMOD, UbiComp, VLDB, 논문, 논문지, 대한민국>대전광역시>유성구>궁동>충남대학교>공과대학 2호관>332호>데이터베이스시스템연구실
Trackback (0) : Comment (0)