Dimensionality reduction for similarity searching in dynamic databases

ABSTRACT

Databases are increasingly being used to store multi-media objects such as maps, images, audio and video. Storage and retrieval of these objects is accomplished using multi-dimensional index structures such as R*-trees and SS-trees. As dimensionality increases, query performance in these index structures degrades. This phenomenon, generally referred to as the dimensionality curse, can be circumvented by reducing the dimensionality of the data. Such a reduction is however accompanied by a loss of precision of query results. Current techniques such as QBIC use SVD transform-based dimensionality reduction to ensure high query precision. The drawback of this approach is that SVD is expensive to compute, and therefore not readily applicable to dynamic databases. In this paper, we propose novel techniques for performing SVD-based dimensionality reduction in dynamic databases. When the data distribution changes considerably so as to degrade query precision, we recompute the SVD transform and incorporate it in the existing index structure. For recomputing the SVD-transform, we propose a novel technique that uses aggregate data from the existing index rather than the entire data. This technique reduces the SVD-computation time without compromising query precision. We then explore efficient ways to incorporate the recomputed SVD-transform in the existing index structure without degrading subsequent query response times. These techniques reduce the computation time by a factor of 20 in experiments on color and texture image vectors. The error due to approximate computation of SVD is less than 10%.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 2: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 3: S. Chandrasekaran , B. S. Manjunath , Y. F. Wang , J. Winkeler , H. Zhang, An eigenspace update algorithm for image analysis, Graphical Models and Image Processing, v.59 n.5, p.321-332, Nov. 1997 [doi>10.1006/gmip.1997.0425]
• 4: R. Degroat and R. Roberts. Efficient numerically stabilized rank-one eigenstructure updating. IEEE transactions on acoustic aria signat processing (T-ASSP), 38(2):301-316, 1990.
• 5: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, University of Maryland at College Park, College Park, MD, 1994
• 6: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 7: Michael Freeston, The BANG file: A new kind of grid file, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.260-269, May 27-29, 1987, San Francisco, California, United States
• 8: Michael Freeston, A general solution of the n-dimensional B-tree problem, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.80-91, May 22-25, 1995, San Jose, California, United States
• 9: M. W. Freeston. A new generic index technology. Proc. NASA Goddard Conf. on Mass Storage Technologies, September 1996.
• 10: 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]
• 11: G. H. Golub and C. F. van Loan. Matrix Computations. The John Hopkins Press, 1989.
• 12: M. Gu and S. C. Eisenstat. A stable and fast algorithm for updating the singuIar value decomposition. Technical Report YALEU/DCS/RR-966, Yale University, New Haven, CT, 1994.
• 13: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 14: 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
• 15: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 16: Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States
• 17: King Ip Lin , H. V. Jagadish , Christos Faloutsos, The TV-tree: an index structure for high-dimensional data, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 18: David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990 [doi>10.1145/99935.99949]
• 19: G. Mathew, V. U. Reddy, and S. Dasgupta. Adaptive estimation of eigenspaces. IEEE Transactions in Singnal Processing, 43(2):401-411, 1995.
• 20: R. Ng and A. Sedighian. Evaluating multi-dimensional indexing structures for images transformed by principle component analysis. Proc. of the SPIE, 2670:50-61, 1994.
• 21: W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, and P. Yanker. The QBIC project: Querying images by content using color, texture and shape. In Proc. of the SPIE Conf. I908 on Storage and Retrieval for Image and Video Databases, volume 1908, pages 173-187, Feb. 1993.
• 22: K. V. R Kanth , Divyakant Agrawal , Amr El Abbadi , Ambuj Singh, Dimensionality Reduction for Similarity Searching in Dynamic Databases, University of California at Santa Barbara, Santa Barbara, CA, 1998
• 23: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 24: D. White and R. Jain. Algorithms and strategies for similarity retrieval. Proc. of the SPIE Conference, 1996.
• 25: David A. White , Ramesh Jain, Similarity Indexing with the SS-tree, Proceedings of the Twelfth International Conference on Data Engineering, p.516-523, February 26-March 01, 1996
• 26: Daniel Wu , Ambuj Singh , Divyakant Agrawal , Amr El Abbadi , Terence R. Smith, Efficient retrieval for browsing large image databases, Proceedings of the fifth international conference on Information and knowledge management, p.11-18, November 12-16, 1996, Rockville, Maryland, United States [doi>10.1145/238355.238365]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

General Terms:
Experimentation, Measurement