그래프상에서 샘플링된 신호로부터 원신호를 복원하기 위한 저 복잡도를 갖는 샘플링 기술에 대해 연구하였다. 기존의 샘플링 기술에서 사용되는 탐욕 알고리즘은 매 단계마다 비용함수 (예를들어, 복원오차)가 최소가 되는 한 개의 노드를 선택하기 위해, 현 단계에서 남아있는 모든 노드들에 대해 비용함수를 계산하게 된다. 이는 샘플링 알고리즘의 복잡도를 높이는 주요 원인이 되며, 이를 해결하기 위해 매 단계 제한적 탐색 범위내에서 최적의 노드를 찾는 저 복잡도 알고리즘을 제안하였다. 탐색 범위를 결정하기 위해 이전 단계에서 계산된 비용함수를 활용하여 다음 단계에서 선택될 가능성이 높은 노드들로 탐색 범위를 제한하고, 또한 비용함수가 계산되는 업데이트 간격을 조정하여 복원성능 저하 없이 고속 샘플링 작업을 수행하게 된다. 다양한 그래프상에서 실험을 통해 기존 샘플링 기술 대비 복원성능을 유지하면서 약 1.5배 이상 빠른 실행시간을 보임을 확인하였다.