학과소식

[2024.03] 네트워크 알고리즘 및 구조 연구실 학부생 최은지 학생 (임혜숙 교수) "Decoding Errors in Difference-Invertible Bloom Filter: Analysis and Re

  • 작성일 : 2024-04-01
  • 조회수 : 563
  • 작성자 : EWHAELEC


전자전기공학전공 학부생 최은지 학생은 임혜숙교수 연구실의 인턴으로 Invertible Bloom Filter (IBF)관련 연구에 참여하여제1저자로"Decoding Errors in Difference-Invertible Bloom Filter: Analysis and Resolution" 논문을 IEEE Access (IF3.9, 상위 36%)에 게재하였다. IBF는 프로그램된 원소를 복원하는기능을 갖는 매우 간단한 데이터 구조이다. 


주어진 두 개 집합이 각각 IBF에 프로그램되었을 때, IBF의 차연산을 통해 구해지는 Difference-Invertible Bloom Filter (d-IBF)에는 두 개 집합의 공통된 원소는 모두 제거되고 공통되지 않은 원소만 남게 되며, 디코딩 과정을 통하여 공통되지 않은 원소를 복원해 낼 수 있다.


본 논문에서는 IBF 디코딩과 동일한 과정을 d-IBF 디코딩에 적용하였을 때 생기는 에러를 분석하고, 에러를 극복하는 방법을 제안하였다. 본 논문에서 제안하는 디코딩 방법을 사용하면 두 개 집합의 공통되지 않은 원소 갯수에 비례하는 적은 수의 셀을 갖는 IBF에 대하여두 개 집합에 공통되지 않은 원소를 에러 없이 100% 복원해낼 수 있음을 보였다. 본 논문의 시뮬레이션에 사용된 VerilogHDL 코드는 소프트웨어 공개 사이트인 gittub (https://github.com/hyesooklim/d-IBF-Decoding-Implementation)에 공개되었다.