지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 정보과학회논문지 : 시스템 및 이론 정보과학회논문지 : 시스템 및 이론 제39권 제5호
- 발행연도
- 2012.10
- 수록면
- 306 - 312 (7page)
이용수
초록· 키워드
오류제보하기
Succinct 표현은 n개의 이산 객체를 O(n) 비트만을 사용하여 저장하는 공간 효율적인 방법으로, 일반적으로 succinct 표현은 이산 객체에 접근하기 위해 비트 스트링에 대한 효율적인 rank와 select함수를 필요로 한다. 현재 다양한 연구들에 의해 1차원 비트 스트링의 rank와 select함수는 o(n) 비트의 보조 자료 공간을 사용하여 O(1) 시간에 수행되고, 실용적인 구현이 가능하다. 반면에, 2차원 비트 행렬에 대한 연구는 아직 초기단계이다. 본 논문에서는 2차원 비트 행렬 상에서의 rank 및 select 함수를 새롭게 정의하고 처음으로 o(n<sup>2</sup>) 비트만을 사용하여 O(logn) 시간에 rank 질의를, 그리고 O(log<sup>2</sup>n) 시간에 select 질의를 수행할 수 있는 방법을 제안한다.
목차
요약
Abstract
1. 서론
2. 문제 정의
3. 공간 효율적 rank와 select
4. 결론 및 향후 연구
참고문헌
참고문헌 (9)
참고문헌 신청
1. [학술지(정기간행물)] - J. I. Munro / 2001 / Succinct representation of balanced parentheses, static trees and planar graphs / SIAM J. Computing 31 (3) : 762 ~ 776
2. [학위논문] - G. Jacobson / 1988 / Succinct static data structure / 박사 / Carnegie Mellon University
3. [학술대회논문] - R. Raman / 2003 / Succinct dynamic dictionaries and trees / Proc. 30th international conference on Automata, Languages and Programming : 357 ~ 368
4. [학술지(정기간행물)] - G. Turan / 1984 / Succinct representations of graphs / Discrete Applied Math 8 : 289 ~ 294
5. [학술대회논문] - G. Jacobson / 1989 / Space-efficient static trees and graphs / Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) : 549 ~ 554
2. [학위논문] - G. Jacobson / 1988 / Succinct static data structure / 박사 / Carnegie Mellon University
3. [학술대회논문] - R. Raman / 2003 / Succinct dynamic dictionaries and trees / Proc. 30th international conference on Automata, Languages and Programming : 357 ~ 368
4. [학술지(정기간행물)] - G. Turan / 1984 / Succinct representations of graphs / Discrete Applied Math 8 : 289 ~ 294
5. [학술대회논문] - G. Jacobson / 1989 / Space-efficient static trees and graphs / Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) : 549 ~ 554
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2014-569-001234072