Complexity reduction in lattice-based information retrieval : theory, prototype development, and evaluation

格模式信息檢索系統複雜性簡化 : 理論, 原型建立及評估

Student thesis: Doctoral Thesis

View graph of relations


  • Siu King Karen CHEUNG

Related Research Unit(s)


Awarding Institution
  • Douglas VOGEL (Supervisor)
Award date4 Oct 2004


Though lattice-based information representation has the advantage of providing an information-rich user interface, the complexity of a lattice may grow rapidly with the size of the database. In this thesis an analogy between the vector space model and formal concept lattice is formally drawn from which the notion of term-document lattice is introduced as a model for information retrieval. The notion of quotient lattices is further proposed to reduce the complexity of a term-document lattice. The equivalence relation required to construct the quotient lattice is obtained by performing singular value decomposition on the original term-document matrix. A prototype system has been designed and constructed to realize the conceptual framework of complexity reduction of term-document lattices using the theory of quotient lattices. The central component of the system is a procedure of reducing the complexity of the term-document lattice of a real database for information retrieval. Three types of user interface, namely, reduced lattice interface, non-reduced lattice interface, and text-based interface, are provided to the users. A usability study has been conducted to investigate the usability of the above three user interfaces. In particular, the retrieval performance of the reduced lattice interface is compared with that of the non-reduced lattice interface and the text-based interface. We are also interested in examining the user satisfaction with and the user preference towards each search interface. Three sets of analysis (Analysis 1, Analysis 2, Analysis 3) have been carried out in order to analyze the results of the information retrieval performance of the users. Whereas the results of Analysis 1 indicate that the users who use the text-based interface obtain better score in recall, precision, and search time compared to that of the non-reduced lattice and reduced lattice interfaces, Analysis 2 is designed to detect the possible presence of ordering effect, and the results reveal that ordering effect does exist in the study. It is followed by Analysis 3 for comparing the relationship between user interfaces and users’ information retrieval performance in an ordering-effect-free environment. The results of Analysis 3 indicate that the reduced lattice interface outperforms the non-reduced lattice interface in both the recall and precision measures. Though the search time required by the reduced lattice interface is longer, and the number of documents retrieved is larger than that of the text-based interface, the former interface has a better recall performance than the latter. Results from the user satisfaction and user preference questionnaires show that users are more satisfied with and prefer the text-based interface relative to the nonreduced lattice and reduced lattice interfaces. An interview has also been administered in order to understand the subjects’ underlying behavior and responses during the usability study. The results of this interview provide further findings on the usability of the reduced lattice interface, and the users’ degree of satisfaction and preference towards the text or lattice-based user interfaces for information retrieval. It has been found that the users’ familiarity of the conventional text-based interface has significant effects on many results of these studies, most of these effects act unfavorably to reduced lattice. Nevertheless, our research has also revealed the potential of reduced lattice interface in the future development of information retrieval systems. Directions of further research have been given along this line of effort.

    Research areas

  • Lattice theory, User interfaces (Computer systems), Information storage and retrieval systems