Efficient query routing for information retrieval in semantic overlays

ABSTRACT

A fundamental problem in peer-to-peer networks is how to locate appropriate peers efficiently to answer a specific query request. This paper proposes a model in which semantically similar peers form a semantic overlay network and a query can be routed or forwarded to appropriate peers instead of broadcasting or random selection. We apply Latent Semantic Indexing (LSI) in information retrieval to reveal semantic subspaces of feature spaces from documents stored on peers. After producing semantic vectors through LSI, we train a support vector machine (SVM) to classify the peers into different categories based on the extracted vectors. Peers with close categories are defined as semantic similarity and form a semantic overlay. Experimental results show the model is efficient and performs better than other non-semantic retrieval models with respect to accuracy. In addition, our approach improves the recall rate nearly 100% while reducing message traffic dramatically compared with Gnutella.

REFERENCES

• 1: Michael W. Berry , Zlatko Drmac , Elizabeth R. Jessup, Matrices, Vector Spaces, and Information Retrieval, SIAM Review, v.41 n.2, p.335-362, June 1999 [doi>10.1137/S0036144598347035]
• 2: M. S. Deerwester, S. Dumais, G. Furnas, T. Landauer, and R. Harshman, "Indexing by Latent Semantic Analysis", Journal of American Society for Information Science, 41(6):391--407, 1990.
• 3: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 4: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 5: Chunqiang Tang , Zhichen Xu , Sandhya Dwarkadas, Peer-to-peer information retrieval using self-organizing semantic overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863976]
• 6: Bernhard E. Boser , Isabelle M. Guyon , Vladimir N. Vapnik, A training algorithm for optimal margin classifiers, Proceedings of the fifth annual workshop on Computational learning theory, p.144-152, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130401]
• 7: J. Broekstra, M. Ehrig, P. Haase, F. Harmelen, M. Menken, P. Mika, B. Schnizler, and R. Siebes, "Bibster - a Semantics-based Bibliographic Peer-to-Peer System", Proceedings of the WWW'04 Workshop on Semantics in Peer-to-Peer and Grid Computing, 2004.
• 8: Christoph Tempich , Steffen Staab , Adrian Wranik, Remindin': semantic query routing in peer-to-peer networks based on social metaphors, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988759]
• 9: Chunqiang Tang , Sandhya Dwarkadas , Zhichen Xu, On scaling latent semantic indexing for large peer-to-peer systems, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009014]
• 10: T. Kolda, Limited-Memory Matrix Methods with Applications, PhD thesis, 1997, University of Maryland at College Park.
• 11: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555 ]
• 12: David Hull, Improving text retrieval for the routing problem using latent semantic indexing, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.282-291, July 03-06, 1994, Dublin, Ireland

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Performance

Keywords:
information retrieval, query routing, semantic overlay