비트펀넬

BitFunnel
비트펀넬
개발자마이크로소프트
초기 릴리즈2016; 6년 전(2016년)
리포지토리github.com/BitFunnel
기록 위치C++
플랫폼Windows, MacOS, Ubuntu
유형검색 엔진 인덱싱 알고리즘
면허증MIT 라이선스
웹사이트bitfunnel.org

비트펀넬(BitFunnel)은 2016년 오픈소스로 만들어진 빙 검색엔진에서 사용되는 검색엔진 인덱싱 알고리즘과 구성요소 세트다.[1][2]비트펀넬은 운영비 절감을 위해 역지수 대신 비트슬라이징 서명을 사용한다.[3]

역사

비트펀넬 구현에 대한 진전은 2016년 초 공개돼 그해 말 사용 가능한 구현이 있을 것으로 기대했다.[4]2016년 9월 GitHub를 통해 소스 코드를 사용할 수 있게 되었다.[5]비트펀넬 알고리즘과 구현을 논하는 논문이 2017년 컴퓨터기계협회 정보검색특별이익그룹을 통해 공개돼 최우수 논문상을 수상했다.[3][6]

구성 요소들

BitFunnel은 다음과 같은 3가지 주요 구성 요소로 구성된다.[1]

  • BitFunnel – 텍스트 검색/회수 시스템 자체
  • WorkBench – BitFunnel에서 사용할 텍스트를 준비하는 도구
  • NativeJIT – C 데이터 구조를 사용하는 표현식을 취하여 고도로 최적화된 어셈블리 코드로 변환하는 소프트웨어 구성 요소

알고리즘.

초기 문제 및 솔루션 개요

BitFunnel 논문은 알고리즘이 키워드 사용을 통해 문서를 식별해야 할 때 발생하는 '매칭 문제'를 설명한다.문제의 목표는 검색할 말뭉치와 비교할 키워드 용어의 질의를 주어진 일련의 일치 항목을 식별하는 것이다.이 문제는 일반적으로 검색 가능한 각 항목이 키워드 맵으로 유지되는 역지표를 통해 해결된다.[3]

이와는 대조적으로 BitFunnel은 서명을 통해 검색 가능한 각 항목을 나타낸다.서명은 주어진 검색 가능한 항목에서 검색 가능한 용어의 블룸 필터를 설명하는 비트 시퀀스다.블룸 필터는 해싱을 통해 여러 비트 위치를 통해 생성된다.[3]

비트 문자열 서명의 이론적 구현

문서(D)의 서명은 문서 서명의 논리적 또는 용어 서명의 논리적이라고 설명할 수 있다.

마찬가지로 문서(Q)에 대한 질의를 조합으로 정의할 수 있다.

또한 문서 D는 다음 조건이 충족될 때 설정된 M'의 구성원이 된다.

그런 다음 이 지식을 결합하여 다음과 같은 쿼리 서명과 일치하는 문서에 의해 M'이 식별되는 공식을 만든다.

이러한 단계와 그 증거는 2017년 논문에서 논의된다.[3]

비트 문자열 서명에 대한 유사 코드

이 알고리즘은 2017년 논문에 기술되어 있다.[3]

참조

  1. ^ a b Yegulalp, Serdar (September 6, 2016). "Microsoft open-sources Bing components for fast code compilation". InfoWorld.
  2. ^ Verma, Arpit (2016-09-07). "Microsoft Open Sources Major Components Of Bing Search Engine, Here's Why It Matters". Fossbytes. Retrieved 2020-06-12.
  3. ^ a b c d e f Goodwin, Bob; Hopcroft, Michael; Luu, Dan; Clemmer, Alex; Curmei, Mihaela; Elnikety, Sameh; He, Yuxiong (2017-08-07). "BitFunnel". Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, NY, USA: ACM: 605–614. doi:10.1145/3077136.3080789. ISBN 978-1-4503-5022-8.
  4. ^ "When will BitFunnel be usable? · BitFunnel". bitfunnel.org. Retrieved 2020-06-12.
  5. ^ BitFunnel/BitFunnel, BitFunnel, 2020-05-12, retrieved 2020-06-12
  6. ^ "SIGIR Best Paper Awards". ACM. Retrieved 8 July 2020.

외부 링크