Abstract: To deal with the problem of too many results obtained from a Web database in response to a user query, a novel approach is proposed to categorize the Web database query results automatically, i.e., to generate a labeled, hierarchical navigational tree dynamically over the query results. The hierarchy of the tree includes two processing steps. At the first step, the query histories of all users in the system are analyzed offline to cluster the similar queries semantically, then the original data are divided into multiple tuple clusters in accordance to the clustered queries, among which each tuple cluster corresponds to a certain type of user preferences. When a user queries about something, at the online step, a navigational tree over the clusters generated at the first step is provided for the user to enable him to select and locate the information he needs easier. Experimental results revealed that the categorization approach proposed can meet the user's personalized requirements effectively.