Efficient Fuzzy Type Ahead Search in XML Data

Abstract:       

In a traditional keyword-search system over XML data, a user composes a 

keyword query, submits it to the system, and retrieves relevant answers. In 

the case where the user has limited knowledge about the data, often the user 

feels “left in the dark” when issuing queries, and has to use a try-and-see 

approach for finding information. In this paper, we study fuzzy type-ahead 

search in XML data, a new information-access paradigm in which the system 

searches XML data on the fly as the user types in query keywords. It allows 

users to explore data as they type, even in the presence of minor errors of 

their keywords. Our proposed method has the following features: 

1) Search as you type: It extends Auto complete by supporting queries with multiple keywords in XML data. 

2) Fuzzy: It can find high-quality answers that have keywords matching query keywords approximately. 

3) Efficient: Our effective index structures and searching algorithms can achieve a very high interactive speed. 

We study research challenges in this new search framework. We propose 

effective index structures and top-k algorithms to achieve a high interactive 

speed. We examine effective ranking functions and early termination 

techniques to progressively identify the top-k relevant answers. We have 

implemented our method on real data sets, and the experimental results show 

that our method achieves high search efficiency and result quality.