An analysis of vector space models based on computational geometry

ABSTRACT

This paper analyzes the properties, structures and limitations of vector-based models for information retrieval from the computational geometry point of view. It is shown that both the pseudo-cosine and the standard vector space models can be viewed as special cases of a generalized linear model. More importantly, both the necessary and sufficient conditions have been identified, under which ranking functions such as the inner-product, cosine, pseudo-cosine, Dice, covariance and product-moment correlation measures can be used to rank the documents. The structure of the solution region for acceptable ranking is analyzed and an algorithm for finding all the solution vectors is suggested.

REFERENCES

• 1: P. Bollmann , S. K. M. Wong, Adaptive linear information retrieval models, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.157-163, June 03-05, 1987, New Orleans, Louisiana, United States [doi>10.1145/42005.42023]
• 2: William P. Jones , George W. Furnas, Pictures of relevance: a geometric analysis of similarity measures, Journal of the American Society for Information Science, v.38 n.6, p.420-442, Nov. 1987 [doi>10.1002/(SICI)1097-4571(198711)38:6<420::AID-ASI3>3.0.CO;2-S]
• 3: McGill, M.3., Koll, M., and Noreault, T. (1979). An evaluation off actors affecting document ranking by information retrieval systems. School of Information Studies, Syracuse University, Syracuse, New York 13210.
• 4: McMullen, P. and Shephard, G.C. (1971). Convex Polytope and the Upper Bound Conjecture, Cambridge: Cambridge University Press.
• 5: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 6: Raghavan, V.V. and Wong, S.K.M. (1986). A critical analysis of vector space model in information retrieval. Journal of the American Soczety for Information Science, 37, 279-287.
• 7: Roberts, F.S. (1976). Measurement Theory, New York: Academic Press.
• 8: G. Salton, The SMART Retrieval System—Experiments in Automatic Document Processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 9: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 10: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 11: Schneider, H.-J., Bollmann, P., Jochum, F., Konrad, E., I~einer, U., and Weissmann, V. (1986). Leislungsbewertung yon znformalzon relrzeval verfahren (LIVE). Projektbericht, Technische Universitat, Berlin.
• 12: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 13: S. J. Wan , S. K. M. Wong, A Partially Supervised Learning Algorithm for Linearly Separable Systems, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.10, p.1052-1056, October 1992 [doi>10.1109/34.159907]
• 14: Wong, S.K.M., Bollmann, P., and Yao, Y.Y. (1991). Information retrieval based on axiomatic decision theory. International Journal of General Systems, 19, 101-117.
• 15: S. K.M. Wong , Y. Y. Yao, Linear structure in information retrieval, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.219-232, May 1988, Grenoble, France [doi>10.1145/62437.62452]
• 16: S. K. M. Wong , Y. Y. Yao, A probability distribution model for information retrieval, Information Processing and Management: an International Journal, v.25 n.1, p.39-53, 1989 [doi>10.1016/0306-4573(89)90090-3]
• 17: Wong, S.K.M. and Yao. Y.Y. (1990). Query formulation in linear retrieval models. Journal of the American Society for Information Science, 41,334- 341.
• 18: S. K. M. Wong , Y. Y. Yao, A probabilistic inference model for information retrieval, Information Systems, v.16 n.3, p.301-321, 1991 [doi>10.1016/0306-4379(91)90003-R]
• 19: Wong, S.K.M., Yao. Y.Y., Salton, G. and Buckley, C. (1991). Evaluation of an adaptive linear model. journal of the American Society for Informatzon Science, 42, pp. 723-730.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models; Query formulation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory