[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

KR101496179B1 - 데이터 부재 태깅 기반의 정보 검색 시스템 및 방법 - Google Patents

데이터 부재 태깅 기반의 정보 검색 시스템 및 방법 Download PDF

Info

Publication number
KR101496179B1
KR101496179B1 KR20130058950A KR20130058950A KR101496179B1 KR 101496179 B1 KR101496179 B1 KR 101496179B1 KR 20130058950 A KR20130058950 A KR 20130058950A KR 20130058950 A KR20130058950 A KR 20130058950A KR 101496179 B1 KR101496179 B1 KR 101496179B1
Authority
KR
South Korea
Prior art keywords
keyword
history table
search
stored
master filter
Prior art date
Application number
KR20130058950A
Other languages
English (en)
Other versions
KR20140137842A (ko
Inventor
윤일지
오보리
최재석
Original Assignee
삼성에스디에스 주식회사
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 삼성에스디에스 주식회사 filed Critical 삼성에스디에스 주식회사
Priority to KR20130058950A priority Critical patent/KR101496179B1/ko
Priority to CN201310681804.8A priority patent/CN104182435B/zh
Priority to PCT/KR2013/011541 priority patent/WO2014189190A1/ko
Priority to US14/141,788 priority patent/US20140351273A1/en
Publication of KR20140137842A publication Critical patent/KR20140137842A/ko
Application granted granted Critical
Publication of KR101496179B1 publication Critical patent/KR101496179B1/ko

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/33Querying
    • G06F16/335Filtering based on additional data, e.g. user or group profiles
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/33Querying
    • G06F16/3331Query processing
    • G06F16/334Query execution
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/33Querying
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/31Indexing; Data structures therefor; Storage structures
    • G06F16/316Indexing structures
    • G06F16/328Management therefor
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/33Querying
    • G06F16/3331Query processing

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computational Linguistics (AREA)
  • Business, Economics & Management (AREA)
  • General Business, Economics & Management (AREA)
  • Software Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

데이터 부재 태깅 기반의 정보 검색 시스템 및 방법이 개시된다. 본 발명의 일 실시예에 따른 정보 검색 시스템은, 데이터가 복수 개의 데이터 블록으로 구분되어 저장되는 데이터 저장 영역, 및 데이터 블록 별 키워드 부재 정보가 저장되는 메타데이터 영역을 포함하는 데이터베이스, 사용자로부터 검색 대상 키워드 및 검색 대상 구간을 포함하는 키워드 검색 요청을 수신하고, 요청된 키워드를 이용하여 상기 데이터베이스에 저장된 데이터를 검색하는 검색기, 및 상기 검색기로부터 키워드 검색 결과에 따른 키워드 부재 정보를 수신하고, 상기 데이터베이스에 상기 키워드 부재 정보를 기록하는 키워드 관리기를 포함한다.

Description

데이터 부재 태깅 기반의 정보 검색 시스템 및 방법{SYSTEM AND METHOD FOR SEARCHING INFORMATION BASED ON DATA ABSENCE TAGGING}
본 발명의 실시예들은 대용량 데이터의 효율적인 검색 기술과 관련된다.
전자상거래, SNS, VoIP 서비스 등 인터넷 서비스 시스템이 일반화되면서, 이들 서비스 시스템을 효과적으로 운용하기 위한 다양한 수단들이 개발되었다. 서비스 시스템의 경우 사용자들의 접속 기록, 에러 발생 기록 등의 로그 데이터, 또는 시스템 내에서 발생된 이벤트들을 기록한 이벤트 데이터 등을 저장 및 관리하는 것이 일반적이다. 이러한 데이터는 서비스 시스템이나 시스템 내 서비스 콤포넌트 등의 상태를 파악하고 발생된 문제에 대응하거나, 또는 문제 발생을 사전에 예측하는 데 유용하게 사용될 수 있다.
서비스 시스템이 복잡화, 대형화되고 이를 사용하는 사용자의 숫자가 증가할수록, 서비스 시스템에서 기록되는 데이터의 용량 또한 증가하게 된다. 따라서 이를 효과적으로 활용하기 위해서는 대용량 데이터로부터 원하는 키워드를 빠르고 효율적으로 탐색할 필요가 있다. 이를 위하여, 종래의 데이터 관리 시스템의 경우 데이터베이스의 자주 검색되는 특정 행(row) 또는 자주 검색되는 데이터블록에 대한 인덱스(index)를 생성하는 방식을 이용하였다. 그러나 사전에 사용자가 어떠한 데이터를 자주 검색할지를 예측하기란 매우 어려우며, 또한 인덱싱을 위해서는 별도의 하드웨어 자원을 소모하게 되므로 이와 같은 방법은 특히 대용량 데이터의 경우 비효율적이라는 문제가 있었다.
또한, 최근에는 대용량 데이터 관리를 위하여 NoSQL 등의 비정형 데이터베이스를 이용하는 경향이 증가하고 있는데, 이러한 비정형 데이터베이스의 경우 특정 데이터에 대한 자동 인덱싱을 지원하지 않으므로 인덱싱을 위해서는 인덱싱 알고리즘을 직접 구현해야 하는 문제점이 있었다.
본 발명의 실시예들은 로그 데이터 등의 대용량 데이터를 효과적으로 검색하기 위한 수단을 제공하기 위한 것이다.
본 발명의 일 실시예에 따른 정보 검색 시스템은, 데이터가 복수 개의 데이터 블록으로 구분되어 저장되는 데이터 저장 영역, 및 데이터 블록 별 키워드 부재 정보가 저장되는 메타데이터 영역을 포함하는 데이터베이스, 사용자로부터 검색 대상 키워드 및 검색 대상 구간을 포함하는 키워드 검색 요청을 수신하고, 요청된 키워드를 이용하여 상기 데이터베이스에 저장된 데이터를 검색하는 검색기, 및 상기 검색기로부터 키워드 검색 결과에 따른 키워드 부재 정보를 수신하고, 상기 데이터베이스에 상기 키워드 부재 정보를 기록하는 키워드 관리기를 포함한다.
상기 검색기는, 상기 데이터베이스에 기록된 상기 키워드 부재 정보로부터 수신된 검색 대상 구간 중 키워드의 부재 구간이 존재하는지의 여부를 판단하고, 만약 키워드의 부재 구간이 존재하는 경우, 검색 대상 구간 중 상기 키워드의 부재 구간을 제외한 나머지 구간에서 검색 대상 키워드를 이용하여 상기 데이터베이스를 검색할 수 있다.
상기 키워드 관리기는, 상기 검색기로부터 검색된 키워드의 검색 구간 및 해당 검색 구간에서의 키워드의 부재 정보를 수신하고, 복수 개의 데이터 블록 중 키워드가 존재하지 않는 블록에 대응되는 메타데이터 영역에 상기 검색된 키워드의 부재를 마킹할 수 있다.
상기 키워드 관리기는, 설정된 기간 동안 상기 검색기로부터 수신된 키워드가 저장되는 키워드 히스토리 테이블; 상기 키워드 히스토리 테이블에 저장된 키워드의 해시값이 저장되는 마스터 필터; 및 상기 검색기로부터 수신된 키워드 중, 상기 마스터 필터에 기 저장된 키워드와 충돌이 발생하는 키워드가 저장되는 충돌 키워드 히스토리 테이블을 각각 관리할 수 있다.
상기 마스터 필터는 카운팅 블룸 필터(Counting Bloom Filter)일 수 있다.
상기 키워드 관리기는, 상기 검색기로부터 수신된 키워드로부터 설정된 수의 서로 다른 해시값을 계산하고, 상기 마스터 필터의 각 셀(cell) 중 계산된 해시값에 대응되는 셀 값이 모두 0보다 큰 경우, 수신된 키워드를 상기 충돌 키워드 히스토리 테이블에 저장할 수 있다.
상기 키워드 관리기는, 계산된 해시값에 대응되는 상기 마스터 필터의 셀 값 중 적어도 하나가 0인 경우, 해시값에 대응되는 상기 마스터 필터의 셀 값을 각각 1 증가시키고, 수신된 키워드를 상기 키워드 히스토리 테이블에 저장할 수 있다.
상기 키워드 관리기는, 상기 키워드 히스토리 테이블에 저장된 키워드의 부재 정보를 상기 메타데이터 영역에 마킹할 수 있다.
상기 키워드 관리기는, 상기 키워드 히스토리 테이블에 저장된 특정 키워드가 기 설정된 기간 동안 사용되지 않은 경우, 상기 특정 키워드의 해시값에 대응되는 상기 마스터 필터의 셀 값을 1 감소시키고, 상기 특정 키워드를 상기 키워드 히스토리 테이블에서 삭제할 수 있다.
상기 키워드 관리기는, 상기 키워드 히스토리 테이블에 저장된 키워드가 삭제되는 경우, 상기 충돌 키워드 히스토리 테이블에 저장된 키워드 중 상기 마스터 필터에 기 저장된 키워드와 더 이상 충돌이 발생하지 않는 키워드를 삭제하고, 상기 충돌 키워드 키워드 히스토리 테이블에서 삭제된 키워드를 상기 키워드 히스토리 테이블 및 상기 마스터 필터에 등록할 수 있다.
상기 검색기는, 상기 마스터 필터를 이용하여 검색 대상 키워드의 부재 정보 마킹 여부를 판단하고, 검색 대상 키워드의 부재 정보가 상기 데이터베이스에 마킹된 것으로 판단되는 경우, 상기 데이터베이스의 메타데이터 영역을 검색하여 검색 대상 키워드의 부재 구간 정보를 획득할 수 있다.
한편, 본 발명의 일 실시예에 따른 정보 검색 방법은, 검색기에서 사용자로부터 검색 대상 키워드 및 검색 대상 구간을 포함하는 키워드 검색 요청을 수신하는 단계, 상기 검색기에서 요청된 키워드를 이용하여 데이터베이스에 저장된 데이터를 검색하는 단계, 및 키워드 관리기에서 키워드 검색 결과에 따른 키워드 부재 정보를 상기 데이터베이스에 기록하는 단계를 포함한다.
상기 정보 검색 방법은, 상기 데이터를 검색하는 단계의 수행 전, 상기 검색기에서 상기 데이터베이스에 기록된 키워드 부재 정보로부터 수신된 검색 대상 구간 중 키워드의 부재 구간이 존재하는지의 여부를 판단하는 단계를 더 포함하며, 상기 데이터를 검색하는 단계는, 상기 판단 결과 키워드의 부재 구간이 존재하는 경우, 상기 검색 대상 구간 중 키워드의 부재 구간을 제외한 나머지 구간에서 상기 검색 대상 키워드를 이용하여 상기 데이터베이스를 검색할 수 있다.
상기 키워드 부재 정보를 기록하는 단계는, 상기 검색기로부터 키워드 검색 구간 및 검색 결과를 수신하는 단계; 수신된 키워드가 마스터 필터에 기 저장된 키워드와 충돌이 발생하는지 여부를 판단하는 단계; 및 상기 판단 결과에 따라 키워드를 키워드 히스토리 테이블 또는 충돌 키워드 히스토리 테이블에 저장하는 단계를 더 포함할 수 있다.
상기 마스터 필터는 카운팅 블룸 필터(Counting Bloom Filter)일 수 있다.
상기 충돌이 발생하는지 여부를 판단하는 단계는, 상기 검색기로부터 수신된 키워드로부터 설정된 개수의 서로 다른 해시값을 계산하고, 상기 마스터 필터의 각 셀(cell) 중 계산된 해시값에 대응되는 셀 값이 모두 0보다 큰 값인지의 여부에 따라 상기 키워드가 상기 마스터 필터에 저장된 키워드와 충돌이 발생하는지의 여부를 판단할 수 있다.
상기 키워드를 저장하는 단계는, 상기 충돌 여부 판단 결과 계산된 해시값에 대응되는 상기 마스터 필터의 셀 값 중 적어도 하나가 0인 경우, 상기 해시값에 대응되는 상기 마스터 필터의 셀 값을 각각 1 증가시키고, 수신된 키워드를 상기 키워드 히스토리 테이블에 저장할 수 있다.
상기 키워드를 저장하는 단계는, 상기 충돌 여부 판단 결과 계산된 해시값에 대응되는 상기 마스터 필터의 셀 이 모두 0보다 큰 경우, 수신된 키워드를 상기 충돌 키워드 히스토리 테이블에 저장할 수 있다.
상기 정보 검색 방법은, 상기 키워드 부재 정보를 기록하는 단계의 수행 이후, 상기 키워드 히스토리 테이블에 저장된 특정 키워드가 기 설정된 기간 동안 사용되지 않은 경우, 상기 특정 키워드의 해시값에 대응되는 상기 마스터 필터의 셀 값을 1 감소시키고, 상기 특정 키워드를 상기 키워드 히스토리 테이블에서 삭제하는 단계를 더 포함할 수 있다.
상기 특정 키워드를 키워드 히스토리 테이블에서 삭제하는 단계는, 상기 충돌 키워드 히스토리 테이블에 저장된 키워드 중 상기 마스터 필터에 기 저장된 키워드와 더 이상 충돌이 발생하지 않는 키워드를 삭제하고, 상기 충돌 키워드 히스토리 테이블에서 삭제된 키워드를 상기 키워드 히스토리 테이블 및 마스터 필터에 등록할 수 있다.
본 발명의 실시예들에 따를 경우, 기 수행된 검색 결과를 이용하여 데이터베이스 내 특정 키워드의 부재 구간을 태깅함으로써, 키워드 검색 시 검색 수행 구간을 최소화하여 검색 효율을 향상할 수 있는 장점이 있다.
또한, 상기 데이터 부재 태깅 시 기존에 태깅된 키워드와 충돌이 발생하는 키워드들을 별도로 관리함으로써 부재 구간 검색 시 긍정 오류 발생을 사전에 차단할 수 있다.
도 1은 본 발명의 일 실시예에 따른 정보 검색 시스템(100)을 설명하기 위한 블록도이다.
도 2는 본 발명의 일 실시예에 따른 데이터베이스(102)의 상세 구성을 나타낸 블록도이다.
도 3은 본 발명의 일 실시예에 따른 검색기(104)의 상세 구성을 나타낸 블록도이다.
도 4는 본 발명의 일 실시예에 따른 키워드 관리기(104)의 상세 구성을 나타낸 블록도이다.
도 5는 본 발명의 일 실시예에 따른 키워드 관리기(106)에서 새로운 키워드를 추가하는 과정(500)을 설명하기 위한 순서도이다.
도 6은 본 발명의 일 실시예에 따른 마스터 필터를 예시한 도면이다.
도 7은 도 6에 도시된 마스터 필터에 새로운 키워드가 추가된 상태를 예시한 도면이다.
도 8은 본 발명의 일 실시예에 따른 키워드 관리기(106)에서 키워드를 삭제하는 과정(800)을 설명하기 위한 순서도이다.
도 9는 도 7에 도시된 마스터 필터로부터 특정 키워드가 삭제된 상태를 예시한 도면이다.
도 10은 본 발명의 일 실시예에 따른 키워드 검색 및 메타데이터 업데이트 과정(1000)을 설명하기 위한 순서도이다.
도 11은 본 발명의 일 실시예에 따른 키워드 부재 정보를 이용한 키워드 검색 과정(1100)을 설명하기 위한 순서도이다.
이하, 도면을 참조하여 본 발명의 구체적인 실시형태를 설명하기로 한다. 그러나 이는 예시에 불과하며 본 발명은 이에 제한되지 않는다.
본 발명을 설명함에 있어서, 본 발명과 관련된 공지기술에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략하기로 한다. 그리고, 후술되는 용어들은 본 발명에서의 기능을 고려하여 정의된 용어들로서 이는 사용자, 운용자의 의도 또는 관례 등에 따라 달라질 수 있다. 그러므로 그 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야 할 것이다.
본 발명의 기술적 사상은 청구범위에 의해 결정되며, 이하의 실시예는 본 발명의 기술적 사상을 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 효율적으로 설명하기 위한 일 수단일 뿐이다.
도 1은 본 발명의 일 실시예에 따른 정보 검색 시스템(100)을 설명하기 위한 블록도이다. 도시된 바와 같이, 본 발명의 일 실시예에 따른 정보 검색 시스템(100)은 데이터베이스(102), 검색기(104) 및 키워드 관리기(106)를 포함한다.
데이터베이스(102)는 검색 대상이 되는 데이터를 저장한다. 본 발명의 실시예에서, 데이터베이스(102)에 저장되는 상기 데이터는 예를 들어 인터넷 상에서 VoIP 등의 서비스를 제공하는 서비스 시스템의 운영 시 발생되는 접속 기록, 에러 발생 내역 등의 로그(log) 또는 이벤트 정보일 수 있다. 다만, 본 발명의 실시예들은 특정한 종류의 데이터에 한정되는 것은 아니며, 본 발명은 어떠한 종류의 데이터에도 적용 가능함을 유의한다. 데이터베이스(102)는 NoSQL 등의 비정형 데이터베이스로 구성될 수 있으나, 이와 달리 관계형 데이터베이스(RDBMS) 등으로 구성될 수도 있다.
검색기(104)는 사용자로부터 키워드 검색 요청을 수신하고, 상기 키워드 검색 요청에 포함된 검색 대상 키워드를 이용하여 데이터베이스(102)에 저장된 데이터를 검색한다. 상기 키워드는 예를 들어 데이터베이스(102)에 저장된 로그 또는 이벤트 메시지에 포함되어 있는 중요한 메시지 텍스트, 주요 모니터링 대상으로 사전에 등록된 사용자 계정(아이디) 등일 수 있다.
또한, 상기 키워드 검색 요청은 상기 검색 대상 키워드와 함께 검색 대상 키워드를 검색하기 위한 검색 대상 구간을 더 포함할 수 있다. 예를 들어, 상기 사용자는 특정 에러 메시지(예를 들어 “DBError” 등의 메시지), 또는 특정인의 접속 기록(예를 들어, 아이디가 “ABC”인 사용자의 접속 로그)이 최근 7일 간 데이터베이스(102)에 저장된 데이터에 포함되어 있는지의 여부에 대한 검색을 요청할 수 있다.
키워드 관리기(106)는 검색기(104)에서 수행된 키워드 검색 결과에 따라 검색기(104)로부터 키워드 부재 정보를 수신하고, 데이터베이스(102)에 상기 키워드 부재 정보를 기록한다. 예를 들어, 사용자의 검색 요청에 따른 검색 결과 “DBError” 메시지가 검색 기간인 최근 7일 중 첫번째 날에만 발생한 경우, 검색기(104)는 나머지 6일간은 “DBError” 메시지가 발생되지 않았음을 알리는 메시지(키워드 부재 정보)를 키워드 관리기(106)로 전송하고, 키워드 관리기(106)는 수신된 키워드 부재 정보를 데이터베이스(102)에 기록할 수 있다.
본 발명의 실시예에서 상기 키워드 부재 정보와 관련된 메시지는 다양한 형태로 구성될 수 있다. 예를 들어, 검색기(104)는 키워드 검색 결과에 따른 검색 결과 및 검색 구간을 그대로 키워드 관리기(106)로 전송할 수도 있고, 상기 검색 결과 및 검색 구간으로부터 키워드 부재 구간을 계산하여 이를 키워드 관리기(106)로 전송할 수도 있다.
검색된 키워드의 검색 결과에 따른 부재 정보가 데이터베이스(102)에 기록되면, 검색기(104)는 이후 동일한 키워드에 대한 검색 요청이 있을 경우 데이터베이스(102)에 기록된 키워드 부재 정보를 참조하여, 데이터 부재가 기록된 구간을 제외하고 요청된 키워드의 검색을 수행하게 된다. 예를 들어, 사용자로부터 “DBError” 키워드에 대한 검색 요청을 재차 수신한 경우, 검색기(104)는 데이터베이스(102)에 기록된 키워드 부재 정보를 이용하여 수신된 검색 대상 구간 중 키워드의 부재 구간이 존재하는지의 여부를 판단하고, 만약 키워드의 부재 구간이 존재하는 경우 이를 제외한 나머지 구간에서 검색 대상 키워드를 검색하게 된다. 이에 따라 본 발명의 실시예들에 따를 경우 특히 자주 검색되는 키워드에 있어 검색이 반복될수록 데이터 검색 속도를 향상할 수 있게 된다.
도 2는 본 발명의 일 실시예에 따른 데이터베이스(102)의 상세 구성을 나타낸 블록도이다. 도시된 바와 같이 본 발명의 일 실시예에 따른 데이터베이스(102)는 데이터 저장 영역(200) 및 메타데이터 영역(202)을 포함하여 구성된다.
데이터 저장 영역(200)은 검색 대상이 되는 데이터가 저장되는 영역이다. 데이터 저장 영역(200)은 상기 데이터를 복수 개의 데이터 블록으로 분할하여 저장하도록 구성될 수 있다. 예를 들어, 데이터 저장 영역(200)은 데이터의 발생 시점에 따라 이를 일별 또는 주별 등의 시간 단위로 분할하고, 분할된 데이터를 각각 다른 데이터 블록에 저장하도록 구성될 수 있다.
메타데이터 영역(202)은 데이터 저장 영역(200)에 저장된 데이터의 키워드 별 부재 정보가 저장되는 영역이다. 전술한 바와 같이 데이터 저장 영역(200)은 데이터를 복수 개의 블록으로 분할하여 저장할 수 있으며, 이 경우 메타데이터 영역(202)은 분할된 각 데이터 블록 별로 키워드의 부재 정보를 저장할 수 있다. 즉, 메타데이터 영역(202)을 참조할 경우, 검색하려는 데이터가 저장되어 있지 않은 데이터 블록을 용이하게 식별할 수 있다. 일 실시예에서, 메타데이터 영역(202)은 각 데이터 블록 별로 블룸 필터(Bloom Filter)를 이용하여 데이터 블록 별 키워드 부재 정보를 저장할 수 있으나, 본 발명은 키워드 부재 정보를 저장하기 위한 특정 자료 구조에 한정되는 것은 아니다.
도 3은 본 발명의 일 실시예에 따른 검색기(104)의 상세 구성을 나타낸 블록도이다. 도시된 바와 같이, 본 발명의 일 실시예에 따른 검색기(104)는 키워드 검색부(300), 메타데이터 검색부(302), 키워드 정보 등록 및 쿼리부(304)를 포함한다.
키워드 검색부(300)는 사용자로부터 키워드 검색 요청을 수신하고, 상기 키워드 검색 요청에 따라 하나 이상의 키워드를 이용하여 데이터베이스(102)의 데이터 영역(200)에 대한 검색을 수행하며, 검색 결과를 상기 사용자에게 반환한다.
메타데이터 검색부(302)는 데이터베이스(102)의 메타데이터 영역(202)을 검색하여 요청된 키워드의 검색 대상 구간 중 해당 키워드가 존재하지 않는 구간(키워드 부재 구간)이 존재하는지의 여부를 판단한다. 만약 메타데이터 영역(202) 검색 결과 검색 대상 구간 중 해당 키워드의 부재 구간이 존재하는 경우, 키워드 검색부(300)는 상기 부재 구간을 제외하고 나머지 구간에 대해서만 해당 키워드에 대한 검색을 수행한다.
키워드 정보 등록 및 쿼리부(304)는 키워드 검색부(300)에서 수행된 검색 결과를 포함하는 키워드 정보를 후술할 키워드 관리기(106)에 등록한다. 또한, 키워드 정보 등록 및 쿼리부(304)는 키워드 검색 요청을 수신하는 경우 수신된 검색 대상 키워드의 정보를 키워드 관리기(106)에 질의하고, 이에 대한 결과를 수신한다. 키워드 정보의 등록 및 질의(쿼리)와 관련된 상세 구성에 대해서는 후술하기로 한다.
도 4는 본 발명의 일 실시예에 따른 키워드 관리기(104)의 상세 구성을 나타낸 블록도이다. 도시된 바와 같이, 본 발명의 일 실시예에 따른 키워드 관리기(104)는 키워드 정보 관리부(400) 및 메타데이터 관리부(402)를 포함한다.
키워드 정보 관리부(400)는 키워드 정보 등록 및 쿼리부(304)로부터 수신되는 키워드 정보를 저장한다. 또한 키워드 정보 관리부(400)는 키워드 정보 등록 및 쿼리부(304)로부터 키워드 정보에 대한 요청이 수신되는 경우 해당 요청에 대응되는 키워드 정보를 제공한다. 또한, 메타데이터 관리부(402)는 키워드 정보 관리부(400)에서 수신한 각 키워드의 부재 정보를 데이터베이스(102)의 메타데이터 영역(202)에 마킹한다.
본 발명의 실시예에서, 키워드 정보는 현재 데이터베이스(102) 에 사용되고 있는 키워드에 대한 일종의 히스토리 정보를 의미한다. 즉, 로그 데이터 등의 경우 최신 데이터가 이전의 데이터보다 더 많이, 그리고 더 빈번하게 검색되는 특징이 있으므로, 현재 시점에서 자주 검색되는 키워드들에 대한 정보를 저장하여 둠으로써 보다 효율적인 검색이 가능하도록 한 것이다.
일 실시예에서, 키워드 정보 관리부(400)는 키워드 정보의 관리를 위하여 키워드 히스토리 테이블, 마스터 필터, 및 충돌 키워드 히스토리 테이블을 포함하는 3개의 자료 구조를 이용할 수 있다.
먼저, 키워드 히스토리 테이블은 정해진 기간 동안 검색기(104)로부터 수신된 키워드를 저장하기 위한 자료 구조이다. 예를 들어, 키워드 히스토리 테이블은 최근 7일간 검색기(104)로부터 수신된 키워드를 저장하도록 구성될 수 있다. 실시예에 따라, 상기 키워드 히스토리 테이블은 최근 검색 키워드뿐만 아니라, 과거의 검색 키워드를 모두 포함하도록 구성될 수도 있다. 예를 들어, 키워드 히스토리 테이블은 복수 개의 블록을 포함할 수 있으며, 이 중 첫 번째 블록에는 가장 최근 기간(예를 들어, 최근 7일간)의 검색 키워드, 두 번째 블록에는 그 이전 기간(8~14일), 세 번째 블록에는 그 이전 기간(15~21일)의 검색 키워드가 저장되도록 구성될 수도 있다. 이 경우 첫 번째 블록에 저장된 키워드들을 현재 활발하게 검색되고 있는 키워드들로 간주할 수 있다.
마스터 필터는 상기 키워드 히스토리 테이블에 저장된 키워드들의 해시값이 저장되는 필터이다. 상기 마스터 필터는, 예를 들어 카운팅 블룸 필터(Counting Bloom Filter)를 이용하여 구현될 수 있다. 전술한 바와 같이, 키워드 히스토리 테이블이 과거에 검색되었던 키워드들까지를 모두 포함할 경우, 마스터 필터는 이 중 가장 최근 기간 동안에 검색된 키워드들만을 저장할 수 있다. 만약 상기 마스터 필터에 저장된 키워드가 일정 기간 동안 사용되지 않은 경우 해당 키워드는 상기 마스터 필터로부터 삭제될 수 있다.
충돌 키워드 히스토리 테이블은 검색기(104)로부터 수신된 키워드 중, 마스터 필터에 기 저장된 키워드와 충돌이 발생하는 키워드가 저장되는 자료 구조이다. 구체적으로, 키워드 정보 관리부(400)는 검색기(104)로부터 키워드가 수신되는 경우, 먼저 해당 키워드를 마스터 필터에 저장할 수 있는지의 여부를 판단하고, 마스터 필터에 저장 가능한 경우 해당 키워드를 키워드 히스토리 테이블에 저장하고, 저장 불가능한 경우 충돌 키워드 히스토리 테이블에 저장한다.
이하 도 5 내지 9를 참조하여 상기 키워드 히스토리 테이블, 마스터 필터 및 충돌 키워드 히스토리 테이블을 이용한 키워드의 추가 및 삭제 과정을 설명한다.
도 5는 본 발명의 일 실시예에 따른 키워드 관리기(106)에서 새로운 키워드를 추가하는 과정(500)을 설명하기 위한 순서도이다. 먼저 검색기(104)로부터 이전에 사용되지 않은 키워드가 새로 수신된 경우(502), 키워드 관리기(106)의 키워드 정보 관리부(400)는 수신된 키워드에 사전에 설정된 개수의 서로 다른 해시 함수를 적용하여 복수 개의 해시값을 계산하고(504), 계산된 각 해시값에 대응되는 마스터 필터의 각 셀 값에 따라 상기 수신된 키워드를 마스터 필터에 추가할 수 있는지의 여부를 결정한다(508).
예를 들어, 키워드 정보 관리부(400)에 이전에 저장되지 않은 새로운 키워드 “abc”가 검색기(104)로부터 새로 수신된 경우를 가정하자. 키워드 정보 관리부(400)는 수신된 키워드 “abc”에 서로 복수 개의 다른 해시 함수를 적용하여 복수 개의 해시값을 계산한다. 예를 들어, 상기 키워드에 서로 다른 3개의 해시 함수를 적용한 결과가 각각 3, 6, 100이라고 가정하자. 그러면 키워드 정보 관리부(400)는 마스터 필터의 3번째, 6번째, 및 100번째 셀(cell)에 기 저장된 값을 각각 읽어들인 뒤, 각 셀의 값이 각각 0보다 큰 지의 여부에 따라 상기 수신된 키워드를 마스터 필터에 추가할 수 있는지의 여부를 결정한다.
구체적으로, 키워드 정보 관리부(400)는 계산된 해시값에 대응되는 마스터 필터의 셀 값 중 적어도 하나가 0인 경우, 해시값에 대응되는 마스터 필터의 셀 값을 각각 1 증가시킴으로써 해당 키워드를 마스터 필터에 저장한다(510).
도 6 및 도 7은 키워드 정보 관리부(400)에서의 마스터 필터 업데이트 과정을 예시한 것이다. 도면에서 각각의 사각형은 마스터 필터의 각 셀을, 사각형 내부의 숫자는 각 셀의 값을, 아래의 숫자는 각 셀의 일련번호를 각각 의미한다. 예를 들어, 도 6에 도시된 바와 같이 마스터 필터의 3번째, 6번째 100번째 셀의 값이 각각 1, 0, 2인 경우, 키워드 정보 관리부(400)는 도 7에 도시된 바와 같이 해시값에 대응되는 각 셀의 값을 1씩 증가시킨다. 즉, 이 경우 마스터 필터의 3번째, 6번째 100번째 셀의 값은 각각 2, 1, 3이 된다.
또한, 상기와 같이 마스터 필터에 새로운 키워드가 추가된 경우, 키워드 정보 관리부(400)는 새로 추가된 키워드를 키워드 히스토리 테이블에 저장하게 된다(512).
그러나 이와 달리, 마스터 필터의 각 셀(cell) 중 계산된 해시값에 대응되는 셀 값이 모두 0보다 큰 경우, 키워드 정보 관리부(400)는 해당 키워드를 마스터 필터에 추가할 수 없게 된다. 이 경우는 블룸 필터, 또는 카운팅 블룸 필터에서 해당 키워드를 추가하지 않더라도 해당 키워드에 대한 질의 시 참(True)이 반환되는, 다시 말해 해당 키워드에 대한 긍정 오류(positive false)가 발생하는 경우이기 때문이다. 따라서 이 경우, 키워드 정보 관리부(400)는 해당 키워드를 충돌 키워드 히스토리 테이블에 저장하게 된다(514).
이와 같은 과정을 거쳐 신규 키워드가 키워드 히스토리 테이블 또는 충돌 키워드 히스토리 테이블 중 어느 하나에 저장되면, 마지막으로 메타데이터 관리부(402)는 새로 저장된 키워드의 부재 정보를 데이터베이스(102)의 메타데이터 영역(202)에 마킹함으로서 메타데이터 영역(202)을 업데이트한다(516).
본 발명의 실시예에서, 마스터 필터 이외에 별도의 충돌 키워드 히스토리 테이블을 관리하는 이유는 다음과 같다. 전술한 바와 같이, 마스터 필터의 경우 자료구조로 카운팅 블룸 필터를 이용하는 바, 실제로 키워드가 저장되어 있지 않더라도 키워드 질의에 대해 참(True)을 반환하는 긍정 오류가 발생할 가능성이 있다. 그런데, 본 발명에서 카운팅 블룸 필터는 특정 키워드의 존재가 아닌 “부재”를 나타내기 위하여 사용된다는 점에서 문제가 발생할 수 있다. 즉, 카운팅 블룸 필터의 특성인 긍정 오류에 의하여 실제로는 키워드가 존재하는 구간이 키워드 부재 구간으로 잘못 판단될 수 있으며, 이 경우 부재 구간으로 잘못 판단된 구간에 대해서는 키워드의 탐색 자체가 이루어지지 않으므로 검색 결과가 왜곡될 가능성이 존재한다. 따라서 본 발명에서는 기 저장된 키워드와 충돌이 발생하여 추가가 불가능한 키워드를 충돌 키워드 히스토리 테이블에 별도로 저장함으로써 긍정 오류가 발생하는 것을 사전에 방지하도록 구성된 것이다.
도 8은 본 발명의 일 실시예에 따른 키워드 관리기(106)에서 키워드를 삭제하는 과정(800)을 설명하기 위한 순서도이다.
키워드 관리기(106)의 키워드 정보 관리부(400)는, 키워드 히스토리 테이블에 저장된 특정 키워드가 기 설정된 기간 동안 사용되지 않은 키워드를 삭제 대상 키워드로 지정하고, 상기 삭제 대상 키워드로부터 복수 개의 해시값을 계산한다(802). 이후, 키워드 관리기(106)는 계산된 해시값에 대응되는 마스터 필터의 각 셀 값을 추출하고(804), 각 셀 값의 크기에 따라 해당 키워드의 삭제 가능 여부를 판단한다(806).
만약 추출된 마스터 필터의 셀 값 중 어느 하나라도 0인 셀이 존재하는 경우에는 해당 키워드를 마스터 필터에서 삭제할 수 없는 경우이므로, 키워드 정보 관리부(400)는 해당 키워드의 삭제가 불가능함을 알리는 에러 메시지를 출력한다(808). 그러나 이와 달리 추출된 마스터 필터의 셀 값이 모두 0보다 큰 경우, 키워드 정보 관리부(400)는 계산된 해시값에 대응되는 마스터 필터의 셀 값을 1만큼 감소시킴으로써, 상기 삭제 대상 키워드를 키워드 히스토리 테이블에서 삭제한다(810). 도 9는 이와 같은 과정을 거쳐 도 7에 도시된 것과 같은 마스터 필터에서 키워드 “abc”를 삭제한 상태를 예시한 것이다. 즉, 키워드 정보 관리부(400)는 키워드 “abc”에 대응되는 마스터 필터의 3번째, 6번째 100번째 셀 값을 2, 1, 3에서 1, 0, 2로 감소시키게 된다.
한편, 이 경우 키워드 정보 관리부(400)는 마스터 필터에서 키워드가 삭제되는 경우, 충돌 키워드 히스토리 테이블에 저장된 키워드들 중 상기 키워드 삭제로 인하여 더 이상 충돌이 발생하지 않는 키워드를 충돌 키워드 히스토리 테이블에서 삭제하고 새로 마스터 필터에 추가할 수 있다(812).
도 10은 본 발명의 일 실시예에 따른 키워드 검색 및 메타데이터 업데이트 과정(1000)을 설명하기 위한 순서도이다.
먼저, 검색기(104)는 사용자로부터 수신된 검색 대상 키워드 및 검색 대상 구간 정보를 이용하여 데이터베이스(102)에 키워드 검색 질의를 전송하고(1000), 데이터베이스(102)는 수신된 키워드 검색 질의에 따라 검색을 수행한 뒤 검색 결과를 반환한다(1004).
이후, 검색기(104)는 수신된 상기 검색 결과에 따른 키워드 부재 정보를 키워드 관리기(106)로 전송하고(1006), 키워드 관리기(106)는 수신된 상기 키워드 부재 정보에 따라 데이터베이스(102)의 메타데이터 영역(202)에 키워드 부재 정보를 마킹하게 된다(1008).
도 11은 본 발명의 일 실시예에 따른 키워드 부재 정보를 이용한 키워드 검색 과정(1100)을 설명하기 위한 순서도이다.
먼저, 검색기(104)는 사용자로부터 검색 대상 키워드 및 검색 대상 구간을 포함하는 키워드 검색 요청을 수신하고, 수신된 상기 검색 요청에 포함된 검색 대상 키워드의 정보를 키워드 관리기(106)로 질의한다(1102).
상기 질의를 수신한 키워드 관리기(106)는 수신된 검색 대상 키워드가 마스터 필터 또는 충돌 키워드 히스토리 테이블 중 어느 하나에 저장되어 있는지의 여부를 탐색하고, 상기 탐색 결과를 검색기(104)로 전송한다(1104).
만약 상기 질의 결과 해당 검색 대상 키워드가 마스터 필터에 저장되어 있는 경우, 검색기(104)는 데이터베이스(102)의 메타데이터 영역(202)을 탐색하여 해당 키워드의 부재 구간을 검색하여 검색 대상 키워드의 부재 구간 정보를 획득하고(1106, 1108), 획득된 부재 구간을 제외한 나머지 구간에서 검색 대상 키워드의 검색을 수행한다(1110, 1112). 즉, 이 경우는 해당 키워드의 부재 정보가 데이터베이스(102)에 마킹되어 있는 경우이므로, 메타데이터를 이용하여 부재 구간을 제거하고 나머지 구간에서만 검색을 수행하게 된다.
그러나, 이와 달리 해당 검색 키워드가 충돌 키워드 히스토리 테이블에 저장되어 있거나, 키워드 관리기(106)에 저장된 내역이 없는 경우는 충돌로 인하여 해당 키워드를 마킹할 수 없었거나 또는 이전에 검색된 내역이 없는 경우이므로, 검색기(104)는 검색 대상 구간 전체에서 검색 대상 키워드에 대한 검색을 수행하게 된다.
한편, 본 발명의 실시예는 본 명세서에서 기술한 방법들을 컴퓨터상에서 수행하기 위한 프로그램을 포함하는 컴퓨터 판독 가능 기록매체를 포함할 수 있다. 컴퓨터 판독 가능 기록매체는 프로그램 명령, 로컬 데이터 파일, 로컬 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 매체는 본 발명을 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 분야에서 통상의 지식을 가진 자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체, CD-ROM, DVD와 같은 광 기록 매체, 플로피 디스크와 같은 자기-광 매체, 및 롬, 램, 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함할 수 있다.
이상에서 대표적인 실시예를 통하여 본 발명에 대하여 상세하게 설명하였으나, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 상술한 실시예에 대하여 본 발명의 범주에서 벗어나지 않는 한도 내에서 다양한 변형이 가능함을 이해할 것이다.
그러므로 본 발명의 권리범위는 설명된 실시예에 국한되어 정해져서는 안 되며, 후술하는 특허청구범위뿐만 아니라 이 특허청구범위와 균등한 것들에 의해 정해져야 한다.
100: 정보 검색 시스템
102: 데이터베이스
104: 검색기
106: 키워드 관리기
200: 데이터 저장 영역
202: 메타데이터 영역
300: 키워드 검색부
302: 키워드 정보 등록 및 쿼리부
304: 메타데이터 검색부
400: 키워드 정보 관리부
402: 메타데이터 관리부

Claims (20)

  1. 데이터가 복수 개의 데이터 블록으로 구분되어 저장되는 데이터 저장 영역, 및 데이터 블록 별 키워드 부재 정보가 저장되는 메타데이터 영역을 포함하는 데이터베이스;
    사용자로부터 검색 대상 키워드 및 검색 대상 구간을 포함하는 키워드 검색 요청을 수신하고, 요청된 키워드를 이용하여 상기 데이터베이스에 저장된 데이터를 검색하는 검색기; 및
    상기 검색기로부터 키워드 검색 결과에 따른 키워드 부재 정보를 수신하고, 상기 데이터베이스에 상기 키워드 부재 정보를 기록하는 키워드 관리기를 포함하는 정보 검색 시스템.
  2. 청구항 1에 있어서,
    상기 검색기는, 상기 데이터베이스에 기록된 상기 키워드 부재 정보로부터 수신된 검색 대상 구간 중 키워드의 부재 구간이 존재하는지의 여부를 판단하고,
    만약 키워드의 부재 구간이 존재하는 경우, 검색 대상 구간 중 상기 키워드의 부재 구간을 제외한 나머지 구간에서 검색 대상 키워드를 이용하여 상기 데이터베이스를 검색하는, 정보 검색 시스템.
  3. 청구항 1에 있어서,
    상기 키워드 관리기는, 상기 검색기로부터 검색된 키워드의 검색 구간 및 해당 검색 구간에서의 키워드의 부재 정보를 수신하고,
    복수 개의 데이터 블록 중 키워드가 존재하지 않는 블록에 대응되는 메타데이터 영역에 상기 검색된 키워드의 부재를 마킹하는, 정보 검색 시스템.
  4. 청구항 3에 있어서,
    상기 키워드 관리기는,
    설정된 기간 동안 상기 검색기로부터 수신된 키워드가 저장되는 키워드 히스토리 테이블;
    상기 키워드 히스토리 테이블에 저장된 키워드의 해시값이 저장되는 마스터 필터; 및
    상기 검색기로부터 수신된 키워드 중, 상기 마스터 필터에 기 저장된 해시값에 해당하는 키워드와 충돌이 발생하는 키워드가 저장되는 충돌 키워드 히스토리 테이블을 각각 관리하는, 정보 검색 시스템.
  5. 청구항 4에 있어서,
    상기 마스터 필터는 카운팅 블룸 필터(Counting Bloom Filter)인, 정보 검색 시스템.
  6. 청구항 5에 있어서,
    상기 키워드 관리기는, 상기 검색기로부터 수신된 키워드로부터 설정된 개수의 서로 다른 해시값을 계산하고,
    상기 마스터 필터의 각 셀(cell) 중 계산된 해시값에 대응되는 셀 값이 모두 0보다 큰 경우, 수신된 키워드를 상기 충돌 키워드 히스토리 테이블에 저장하는, 정보 검색 시스템.
  7. 청구항 6에 있어서,
    상기 키워드 관리기는, 계산된 해시값에 대응되는 상기 마스터 필터의 셀 값 중 적어도 하나가 0인 경우, 해시값에 대응되는 상기 마스터 필터의 셀 값을 각각 1 증가시키고, 수신된 키워드를 상기 키워드 히스토리 테이블에 저장하는, 정보 검색 시스템.
  8. 청구항 7에 있어서,
    상기 키워드 관리기는, 상기 키워드 히스토리 테이블에 저장된 키워드에 대응되는 키워드 부재 정보를 상기 메타데이터 영역에 마킹하는, 정보 검색 시스템.
  9. 청구항 5에 있어서,
    상기 키워드 관리기는, 상기 키워드 히스토리 테이블에 저장된 특정 키워드가 기 설정된 기간 동안 사용되지 않은 경우, 상기 특정 키워드의 해시값에 대응되는 상기 마스터 필터의 셀 값을 1 감소시키고, 상기 특정 키워드를 상기 키워드 히스토리 테이블에서 삭제하는, 정보 검색 시스템.
  10. 청구항 9에 있어서,
    상기 키워드 관리기는, 상기 키워드 히스토리 테이블에 저장된 키워드가 삭제되는 경우, 상기 충돌 키워드 히스토리 테이블에 저장된 키워드 중 상기 마스터 필터에 기 저장된 해시값에 해당하는 키워드와 더 이상 충돌이 발생하지 않는 키워드를 삭제하고, 상기 충돌 키워드 히스토리 테이블에서 삭제된 키워드를 상기 키워드 히스토리 테이블 및 상기 마스터 필터에 저장하는, 정보 검색 시스템.
  11. 청구항 4에 있어서,
    상기 검색기는, 상기 마스터 필터를 이용하여 검색 대상 키워드의 부재 정보가 상기 데이터베이스에 마킹된 것인지의 여부를 판단하고, 검색 대상 키워드의 부재 정보가 상기 데이터베이스에 마킹된 것으로 판단되는 경우, 상기 데이터베이스의 메타데이터 영역을 검색하여 검색 대상 키워드의 부재 구간 정보를 획득하는, 정보 검색 시스템.
  12. 검색기에서, 사용자로부터 검색 대상 키워드 및 검색 대상 구간을 포함하는 키워드 검색 요청을 수신하는 단계;
    상기 검색기에서, 요청된 키워드를 이용하여 데이터베이스에 저장된 데이터를 검색하는 단계; 및
    키워드 관리기에서, 키워드 검색 결과에 따른 키워드 부재 정보를 상기 데이터베이스에 기록하는 단계를 포함하는 정보 검색 방법.
  13. 청구항 12에 있어서,
    상기 데이터를 검색하는 단계의 수행 전, 상기 검색기에서 상기 데이터베이스에 기록된 키워드 부재 정보로부터 수신된 검색 대상 구간 중 키워드의 부재 구간이 존재하는지의 여부를 판단하는 단계를 더 포함하며,
    상기 데이터를 검색하는 단계는, 상기 판단 결과 키워드의 부재 구간이 존재하는 경우, 상기 검색 대상 구간 중 키워드의 부재 구간을 제외한 나머지 구간에서 상기 검색 대상 키워드를 이용하여 상기 데이터베이스를 검색하는, 정보 검색 방법.
  14. 청구항 12에 있어서,
    상기 키워드 부재 정보를 기록하는 단계는,
    상기 검색기로부터 키워드 검색 구간 및 검색 결과를 수신하는 단계;
    수신된 키워드가 마스터 필터에 기 저장된 해시값에 해당하는 키워드와 충돌이 발생하는지 여부를 판단하는 단계; 및
    상기 판단 결과에 따라 키워드를 키워드 히스토리 테이블 또는 충돌 키워드 히스토리 테이블에 저장하는 단계를 더 포함하는, 정보 검색 방법.
  15. 청구항 14에 있어서,
    상기 마스터 필터는 카운팅 블룸 필터(Counting Bloom Filter)인, 정보 검색 방법.
  16. 청구항 15에 있어서,
    상기 충돌이 발생하는지 여부를 판단하는 단계는,
    상기 검색기로부터 수신된 키워드로부터 설정된 개수의 서로 다른 해시값을 계산하고, 상기 마스터 필터의 각 셀(cell) 중 계산된 해시값에 대응되는 셀 값이 모두 0보다 큰 값인지의 여부에 따라 상기 키워드가 상기 마스터 필터에 저장된 키워드와 충돌이 발생하는지의 여부를 판단하는, 정보 검색 방법.
  17. 청구항 16에 있어서,
    상기 키워드를 저장하는 단계는, 상기 충돌 여부 판단 결과 계산된 해시값에 대응되는 상기 마스터 필터의 셀 값 중 적어도 하나가 0인 경우, 상기 해시값에 대응되는 상기 마스터 필터의 셀 값을 각각 1 증가시키고, 수신된 키워드를 상기 키워드 히스토리 테이블에 저장하는, 정보 검색 방법.
  18. 청구항 16에 있어서,
    상기 키워드를 저장하는 단계는, 상기 충돌 여부 판단 결과 계산된 해시값에 대응되는 상기 마스터 필터의 셀 이 모두 0보다 큰 경우, 수신된 키워드를 상기 충돌 키워드 히스토리 테이블에 저장하는, 정보 검색 방법.
  19. 청구항 17에 있어서,
    상기 키워드 부재 정보를 기록하는 단계의 수행 이후,
    상기 키워드 히스토리 테이블에 저장된 특정 키워드가 기 설정된 기간 동안 사용되지 않은 경우, 상기 특정 키워드의 해시값에 대응되는 상기 마스터 필터의 셀 값을 1 감소시키고, 상기 특정 키워드를 상기 키워드 히스토리 테이블에서 삭제하는 단계를 더 포함하는, 정보 검색 방법.
  20. 청구항 19에 있어서,
    상기 특정 키워드를 키워드 히스토리 테이블에서 삭제하는 단계는,
    상기 충돌 키워드 히스토리 테이블에 저장된 키워드 중 상기 마스터 필터에 기 저장된 해시값에 해당하는 키워드와 더 이상 충돌이 발생하지 않는 키워드를 삭제하고, 상기 충돌 키워드 히스토리 테이블에서 삭제된 키워드를 상기 키워드 히스토리 테이블 및 마스터 필터에 저장하는, 정보 검색 방법.
KR20130058950A 2013-05-24 2013-05-24 데이터 부재 태깅 기반의 정보 검색 시스템 및 방법 KR101496179B1 (ko)

Priority Applications (4)

Application Number Priority Date Filing Date Title
KR20130058950A KR101496179B1 (ko) 2013-05-24 2013-05-24 데이터 부재 태깅 기반의 정보 검색 시스템 및 방법
CN201310681804.8A CN104182435B (zh) 2013-05-24 2013-12-12 基于数据缺失标记的信息检索系统及方法
PCT/KR2013/011541 WO2014189190A1 (ko) 2013-05-24 2013-12-12 데이터 부재 태깅 기반의 정보 검색 시스템 및 방법
US14/141,788 US20140351273A1 (en) 2013-05-24 2013-12-27 System and method for searching information

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR20130058950A KR101496179B1 (ko) 2013-05-24 2013-05-24 데이터 부재 태깅 기반의 정보 검색 시스템 및 방법

Publications (2)

Publication Number Publication Date
KR20140137842A KR20140137842A (ko) 2014-12-03
KR101496179B1 true KR101496179B1 (ko) 2015-02-26

Family

ID=51933723

Family Applications (1)

Application Number Title Priority Date Filing Date
KR20130058950A KR101496179B1 (ko) 2013-05-24 2013-05-24 데이터 부재 태깅 기반의 정보 검색 시스템 및 방법

Country Status (4)

Country Link
US (1) US20140351273A1 (ko)
KR (1) KR101496179B1 (ko)
CN (1) CN104182435B (ko)
WO (1) WO2014189190A1 (ko)

Families Citing this family (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104866502B (zh) * 2014-02-25 2020-10-13 深圳市中兴微电子技术有限公司 数据匹配的方法及装置
US10693786B2 (en) * 2015-11-26 2020-06-23 International Business Machines Corporation Efficient size reduction of a bloom filter
US10235431B2 (en) * 2016-01-29 2019-03-19 Splunk Inc. Optimizing index file sizes based on indexed data storage conditions
US11113732B2 (en) * 2016-09-26 2021-09-07 Microsoft Technology Licensing, Llc Controlling use of negative features in a matching operation
KR102594022B1 (ko) * 2016-11-24 2023-10-26 삼성전자주식회사 전자 장치 및 그의 채널맵 업데이트 방법
CN108334520A (zh) * 2017-01-19 2018-07-27 北京京东尚科信息技术有限公司 社交网络数据处理方法、装置、存储介质及电子设备
US10698898B2 (en) 2017-01-24 2020-06-30 Microsoft Technology Licensing, Llc Front end bloom filters in distributed databases
CN107273481A (zh) * 2017-06-10 2017-10-20 苏州唯亚信息科技股份有限公司 适用于企业用户研发数据库的维护方法
CN110751565A (zh) * 2019-09-18 2020-02-04 深圳市融壹买信息科技有限公司 数据计算方法及装置
KR102708772B1 (ko) * 2021-06-07 2024-09-20 주식회사 카카오헬스케어 코호트 추출 방법, 이를 구현한 코호트 추출 장치 및 코호트 추출 프로그램
CN113608955B (zh) * 2021-06-30 2024-01-26 北京新氧科技有限公司 一种日志记录方法、装置、设备及存储介质

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2007068741A1 (fr) * 2005-12-16 2007-06-21 Thales Procede de classification non supervisee lineaire et stable sur l'ordre des objets
KR20090112256A (ko) * 2008-04-24 2009-10-28 주식회사 다음커뮤니케이션 검색 히스토리 서비스 방법 및 시스템
US20110251873A1 (en) * 2008-10-09 2011-10-13 Nhn Business Platform Corporation Method, system, and computer readable recording medium for generating keyword pairs for search advertisements based on advertisement purchase history
KR20120053351A (ko) * 2010-11-17 2012-05-25 송유진 검색 히스토리 서버 및 이를 이용한 정보 제공 방법

Family Cites Families (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
IT1205383B (it) * 1983-04-11 1989-03-15 Rosso Ind Spa Dispositivo rivoltacalze
US6480836B1 (en) * 1998-03-27 2002-11-12 International Business Machines Corporation System and method for determining and generating candidate views for a database
JP3693958B2 (ja) * 2001-04-05 2005-09-14 松下電器産業株式会社 分散型文書検索方法及び装置、並びに分散型文書検索プログラム及びそのプログラムを記録した記録媒体
US6801904B2 (en) * 2001-10-19 2004-10-05 Microsoft Corporation System for keyword based searching over relational databases
US7548908B2 (en) * 2005-06-24 2009-06-16 Yahoo! Inc. Dynamic bloom filter for caching query results
KR20080062989A (ko) * 2006-12-28 2008-07-03 신용호 웹사이트검색기를 이용한 실시간 웹사이트 검색 시스템 및그 방법
US9256686B2 (en) * 2008-09-15 2016-02-09 International Business Machines Corporation Using a bloom filter in a web analytics application
US20130297581A1 (en) * 2009-12-01 2013-11-07 Topsy Labs, Inc. Systems and methods for customized filtering and analysis of social media content collected over social networks
CN101826107B (zh) * 2010-04-02 2015-08-05 华为技术有限公司 哈希数据处理方法和装置
US8612423B2 (en) * 2010-10-29 2013-12-17 Microsoft Corporation Search cache for document search
US20130173853A1 (en) * 2011-09-26 2013-07-04 Nec Laboratories America, Inc. Memory-efficient caching methods and systems
KR20130050705A (ko) * 2011-11-08 2013-05-16 삼성전자주식회사 키워드 검색 방법 및 장치
CN103793439B (zh) * 2012-11-05 2019-01-15 腾讯科技(深圳)有限公司 一种实时检索信息获取方法、装置及服务器
CN103020300B (zh) * 2012-12-28 2017-04-12 杭州华三通信技术有限公司 一种信息检索方法和设备

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2007068741A1 (fr) * 2005-12-16 2007-06-21 Thales Procede de classification non supervisee lineaire et stable sur l'ordre des objets
KR20090112256A (ko) * 2008-04-24 2009-10-28 주식회사 다음커뮤니케이션 검색 히스토리 서비스 방법 및 시스템
US20110251873A1 (en) * 2008-10-09 2011-10-13 Nhn Business Platform Corporation Method, system, and computer readable recording medium for generating keyword pairs for search advertisements based on advertisement purchase history
KR20120053351A (ko) * 2010-11-17 2012-05-25 송유진 검색 히스토리 서버 및 이를 이용한 정보 제공 방법

Also Published As

Publication number Publication date
KR20140137842A (ko) 2014-12-03
CN104182435B (zh) 2017-09-22
WO2014189190A1 (ko) 2014-11-27
US20140351273A1 (en) 2014-11-27
CN104182435A (zh) 2014-12-03

Similar Documents

Publication Publication Date Title
KR101496179B1 (ko) 데이터 부재 태깅 기반의 정보 검색 시스템 및 방법
CN109684333B (zh) 一种数据存储及裁剪方法、设备和存储介质
US7765215B2 (en) System and method for providing a trustworthy inverted index to enable searching of records
US9116968B2 (en) Methods and apparatus related to graph transformation and synchronization
CN106294772B (zh) 分布式内存列式数据库的缓存管理方法
US8938430B2 (en) Intelligent data archiving
US10089334B2 (en) Grouping of database objects
US10013312B2 (en) Method and system for a safe archiving of data
US10417265B2 (en) High performance parallel indexing for forensics and electronic discovery
US10552460B2 (en) Sensor data management apparatus, sensor data management method, and computer program product
US10614069B2 (en) Workflow driven database partitioning
US20140229496A1 (en) Information processing device, information processing method, and computer program product
JP5146020B2 (ja) 情報処理装置、リソース同定プログラム、リソース同定方法
US8055646B2 (en) Prevention of redundant indexes in a database management system
US8909681B2 (en) Gap detection in a temporally unique index in a relational database
US10019483B2 (en) Search system and search method
KR20160050930A (ko) 대용량 분산 파일 시스템에서 데이터의 수정을 포함하는 트랜잭션 처리 장치 및 컴퓨터로 읽을 수 있는 기록매체
US20210004360A1 (en) Indexing structured data with security information
US11151178B2 (en) Self-adapting resource aware phrase indexes
CN111400249A (zh) 一种易于统计文件数量的文件存储系统及存储方法
US20190197108A1 (en) Method for managing semantic information on m2m/iot platform
KR20190129474A (ko) 데이터 검색 장치 및 방법
Jota et al. A physical design strategy on a nosql dbms
US20240012627A1 (en) Entity search engine powered by copy-detection
US10713305B1 (en) Method and system for document search in structured document repositories

Legal Events

Date Code Title Description
A201 Request for examination
E902 Notification of reason for refusal
GRNT Written decision to grant
FPAY Annual fee payment

Payment date: 20171213

Year of fee payment: 4

LAPS Lapse due to unpaid annual fee