정리 노트

이 포스트는 국민대학교 소프트웨어학부 '데이터베이스' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! Database(DB) 관련된 데이터들의 집합을 의미하며, 아래 4가지의 개념을 만족해야 합니다. 공용 데이터(shared data): 여러 사람이 같이 사용할 수 있는 데이터야 합니다. 통합 데이터(integrated data): 중복된 데이터를 철저히 제거해야 하나, 중복을 의도해서 남겨야 할 때가 있는데 이 때는 최소화 해야 합니다. 그리고 이러한 중복에 대해 알고 있으며 컨트롤할 수 있어야 합니다. 저장 데이터(stored data): 컴퓨터가 접근할 수 있는 매체에 저장돼야 합니다. 운영 데이터(operational ..

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 문제 상황 크기가 N인 집합에 속한 원소들만 담은 스트림이 있다고 합시다. 이 스트림에서 서로 다른 원소들의 개수를 구하려면 집합을 만들어 스트림의 모든 아이템을 집합에 넣으면 됩니다. 집합은 동일한 아이템을 원소로 가지지 않기 때문에 이를 통해 쉽게 찾을 수 있습니다. 하지만 생성해야 할 집합의 크기가 너무 커져 메모리에 올릴 수 없는 정도라면 어떻게 찾아야 할까요? Flajolet-Martin(ver. 1) Flajolet-Martin 알고리즘을 통해 이를 대략적으로 구할 수 있습니다. 이 알고리즘을 위해 아이템을 \(..

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 문제 상황 (key, value)의 tuple로 이루어진 스트림이 있다고 합시다. 그러면, key 값들이 담긴 집합 S가 있을 때, 스트림 내의 임의의 튜플이 집합 S에 존재하는지 확인하려면 어떻게 해야 할까요? 가장 쉽게 생각할 수 있는 방법은 집합 S를 hash table에 모두 저장하는 방법입니다. 하지만 스트림으로 들어오는 튜플들의 수가 너무 많다면, 그 많은 튜플들을 하나씩 다 S에 탐색하는데 시간이 오래 걸릴 것입니다. 비트 배열을 사용한 필터링 비트 배열을 사용해 필터링을 하는 방법이 있습니다. 필터링을 해서 ..

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 문제 상황 0과 1로만 이루어져 있는 bit들의 stream이 입력으로 들어오는 상황에서 최근 들어온 k개의 bit 중 1의 개수를 구해야 하는 상황이 있다고 합시다. 가장 쉽게 생각할 수 있는 방법은 최근 k개의 bit들을 저장해서 개수를 세는 방법입니다. 새로운 bit가 들어오면 가장 예전의 bit를 버린다면 스트림으로 들어오는 입력에서 1의 개수를 셀 수 있을 것입니다. 자료구조 queue를 사용한다면 어렵지 않은 해결책입니다. 하지만, 저장해야 할 bit 용량이 너무 커서 메모리에 담을 수 없다면 어떻게 해야 할까요..

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다!Reservoir sampling은 데이터 스트림에서 임의의 개수의 데이터를 추출하는 방법입니다. 이를 이해하기 위해서는 data stream에 대해 알아야 할 필요가 있습니다.Data Stream데이터 스트림은 끊임없이 입력되는 데이터를 얘기합니다. 이 데이터는 외부에서 발생해 하나 이상의 경로를 통해 빠르게 입력이 되고, 발생 속도와 빈도가 외부에서 결정됩니다. 대표적인 예시로 은행 거래 내역, 서버 로그 데이터 등이 있습니다. 데이터 스트림에 하는 질의는 주로 2가지로 분류할 수 있습니다.1회성 질의(Ad-hoc que..

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 이전의 포스트에서 자카드 유사도로 문서 간의 유사도를 계산했고, LSH(Local Sensitive Hashing)를 통해 탐색 속도를 높였습니다. 유사도를 계산할 때 코사인 유사도를 사용한다면, LSH도 이에 맞게 바뀌어야 합니다. 코사인 유사도에 대한 설명은 제가 저번에 적었던 포스트의 마지막 부분을 참고하시면 됩니다. 따라서 이번 포스트에서 코사인 유사도를 사용할 때 LSH가 어떻게 이루어지는지 알아보겠습니다. Bag of Words 알아보기 전에 문서를 표현했던 방법에 대해 다시 한번 봅시다. 이전 포스트에서처럼 문..

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 이 포스트의 흐름은 전에 작성한 Min-Hashing 포스트에서 이어집니다. 따라서 이 포스트를 보기 전에, 아래의 포스트를 읽어보는 것을 추천합니다. Min-Hashing 이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 왜 study-note-99.tistory.com 왜 필요한가? Min-Hashing 포스트에서는 자카드 유사도 계산을 더 빠르지만 덜 정확하게 계산해서 문서 간 유사도 ..

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 왜 필요한가? 문서함에 수많은 문서가 있고, 각 문서에는 많은 단어들이 적혀있다고 가정합시다. 이 문서함에서 우리가 가지고 있는 하나의 문서와 가장 유사도가 높은 문서를 찾아봅시다. 이때 가장 먼저 떠오르는 방법은 각 문서와 하나씩 유사도를 계산하는 방법일 것입니다. 이 포스트에서 유사도 계산할 때 자카드 유사도를 사용합니다. 자카드 유사도의 계산 식은 아래와 같습니다. 문서함에 있는 문서의 개수를 d, 문서에 적힌 평균 단어 개수를 n이라고 하면, 자카드 유사도 계산의 시간 복잡도가 O(N)이므로 총 O(nd)의 시간 복..