Mobile services discovery and selection in the publish/subscribe paradigm

ABSTRACT

In a publish/subscribe paradigm, user service discovery requires matching user preferences to available published services, e.g., a user may want to find if there is a Chinese restaurant close by. This is a difficult problem when users are mobile, wirelessly connected to a network, and dynamically roaming in different environments. The magnitude of the problem increases with respect to the number of attributes for each users' preference criteria, as matches must be done in real-time. We present an algorithm that uses Singular Value Decomposition to encode each service properties in a few values. Users' preference criteria are matched by using the same encoding to produce a value that can be rapidly compared to those of the services. We show that reasonable matches can be found in time O(m log n) where n is the number of publications and m the number of attributes in the preference criteria (subscription). This is in contrast to 'approximate nearest neighbor' techniques, which require either time or storage exponential in m.

REFERENCES

• 1: {1} B. Kantor, P. Lapsley, "Network News Transfer Protocol (NNTP)", RFC 977, February 1986.
• 2: Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603884]
• 3: {3} TIBCO Inc., TIBCO/Rendezvous Concepts, 2004, http://www.rv.tibco.com.
• 4: Eric N. Hanson , Moez Chaabouni , Chang-Ho Kim , Yu-Wang Wang, A predicate matching algorithm for database rule systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.271-280, May 23-26, 1990, Atlantic City, New Jersey, United States
• 5: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.115-126, May 21-24, 2001, Santa Barbara, California, United States
• 6: {6} F. Fabret, F. Llirbat, J. Pereira and D. Shasha, Efficient Matching for Content-based Publish/Subscribe Systems, Technical report, INRIA, 2000.
• 7: {7} M. Happner, R. Burridge, and R. Sharma. Java Message Service. Sun Microsystem Inc., Oct. 1998.
• 8: Nicholas Carriero , David Gelernter, Linda in context, Communications of the ACM, v.32 n.4, p.444-458, April 1989 [doi>10.1145/63334.63337]
• 9: Hubert Ka Yau Leung, Subject space: a state-persistent model for publish/subscribe systems, Proceedings of the 2002 conference of the Centre for Advanced Studies on Collaborative research, p.7, September 30-October 03, 2002, Toronto, Ontario, Canada
• 10: Hubert Ka Yau Leung , Hans-Arno Jacobsen, Efficient matching for state-persistent publish/subscribe systems, Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research, p.182-196, October 06-09, 2003, Toronto, Ontario, Canada
• 11: {11} I. Burcea, H.-A. Jacobsen, E. Lara, V. Muthusamy, M. Petrovic, "Disconnected Operation in Publish/Subscribe Middleware", IEEE MDM, p.39, Jan. 2004.
• 12: {12} G. H. Golub and C. F. Van Loan, Matrix Computations, The Johns Hopkins University Press, 1993.
• 13: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth , Ramasamy Uthurusamy, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 14: {14} T. M. Cover and P. E. Hart, "Nearest neighbor pattern classification", IEEE Trans. Inform. Theory, 13: pp.57-67, 1967.
• 15: Scott Cost , Steven Salzberg, A Weighted Nearest Neighbor Algorithm for Learning with Symbolic Features, Machine Learning, v.10 n.1, p.57-78, Jan. 1993 [doi>10.1023/A:1022664626993]
• 16: Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146 ]
• 17: Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
• 18: {18} S. Deerwester, S. T. Dumals, G. W. Furnas, T. K. Landauer, and R. Harshman, "Indexing by latent semantic analysis", Journal of the American Society for Inform. Science, 41(6): pp.391-407, 1990.
• 19: {19} L. Devroye and T. J. Wagner, Nearest neighbor methods in discrimination, In P. R. Krishnaiah and L. N. Kanal, editors, Handbook of Statistics, Vol. 2, North-Holland, 1982.
• 20: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 21: {21} D. Dobkin, R. Lipton, "Multidimensional search problems", SIAM J. Computing, 5: pp.181-186, 1976.
• 22: Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
• 23: Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.517-526, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129763]
• 24: A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]
• 25: Jiří Matoušek, Reporting points in halfspaces, Proceedings of the 32nd annual symposium on Foundations of computer science, p.207-215, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185370]
• 26: Jon Louis Bentley , Bruce W. Weide , Andrew C. Yao, Optimal Expected-Time Algorithms for Closest Point Problems, ACM Transactions on Mathematical Software (TOMS), v.6 n.4, p.563-580, Dec. 1980 [doi>10.1145/355921.355927]
• 27: Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
• 28: {28} R. F. Sproull, "Refinements to nearest-neighbor searching in k dimensional trees", Algorithmica, 6: pp.579-589, 1991.
• 29: Sunil Arya , David M. Mount , Onuttom Narayan, Accounting for boundary effects in nearest neighbor searching, Proceedings of the eleventh annual symposium on Computational geometry, p.336-344, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220315]
• 30: S. Meiser, Point location in arrangements of hyperplanes, Information and Computation, v.106 n.2, p.286-303, Oct. 1993 [doi>10.1006/inco.1993.1057 ]
• 31: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
• 32: Kenneth L. Clarkson, An algorithm for approximate closest-point queries, Proceedings of the tenth annual symposium on Computational geometry, p.160-164, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177609]
• 33: Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258653]
• 34: {34} M. W. Berry and R. D. Fierro, "Low-rank orthogonal decompositions for information retrieval applications", Numerical Linear Algebra with Applications, 3(4): pp.301-328, April 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Mobile processors

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Singular value decomposition

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

Keywords:
high dimensional data space, multidimensional search, nearest neighbor search, publish/subscribe, singular value decomposition