알고리즘의 성능은 여러 측면에서 측정할 수 있다. 하나의 질의 구성(Query Formulation) 알고리즘이 개발되었다고 가정할 때, 이 알고리즘 검색 성능의 효과성(재현율과 정확율)이 다른 알고리즘에 비해 우수하다 하여도 질의 작성 시간적인 측면, 즉 효율성에서 다른 알고리즘에 뒤진다면 모든면에서 우수하다고 평가하기는 어렵다. 본 연구에서는 질의나무(Query Tree)라고 불리는 자동 질의 재구성 알고리즘과 다른 2개의 알고리즘(DNF method, Dillon''s method)을 이론적 측면과 실시간 측정을 Sun SparcStation2를 이용하여 비교하여 보았다. 3가지 test set인 CACM, CISI, 그리고 Medlars를 이용하여 실험한 결과 질의나무 알고리즘이 이론적, 실시간 측면에서 가장 빠른 알고리즘이라는 결과가 나왔다.

Performance of an algorithm can be measured from several aspects. Suppose there is a query formulation algorithm. Even though this algorithm shows high retrieval performance, i.e., high recall and precision, retrieving items can take a long time. In this study, we analyze the time complexity of automatic query reformulation algorithms, named the Query Tree, DNF method, and Dillon''s method, and compare them in theoretical and practical aspects using a real-time performance(the absolute times for each algorithm to formulate a query) in a Sun SparcStation 2. In experiments using three test sets, CACM, CISI, and Medlars, the Query Tree algorithm was the fastest among the three algorithms tested.