Dimensionality reduction using magnitude and shape approximations

ABSTRACT

High dimensional data sets are encountered in many modern database applications. The usual approach is to construct a summary of the data set through a lossy compression technique, and use this lower dimensional synopsis to provide fast, approximate answers to the queries. In this paper, we develop a novel dimensionality reduction technique based on partitioning the high dimensional vector space into orthogonal subspaces. First, we find a relation between the Euclidian distance of two n-dimensional vectors and the Euclidian distances of their projections on the orthogonal subspaces. Then, based on this relation we develop a method to approximate the Euclidian distance using novel inner product approximation. This process allows us to incorporate the shape information of the vectors to this approximation. While the inner product approximation is symmetric, i.e., captures only the magnitude information of the data, the proposed method takes both the magnitude and shape information of the original vectors into account through partitioning. In the experiments, we demonstrate the effectiveness of our technique by comparing it with commonly used methods.

REFERENCES

• 1: Anurag Acharya , Mustafa Uysal , Joel Saltz, Active disks: programming model, algorithms and evaluation, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.81-91, October 02-07, 1998, San Jose, California, United States
• 2: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 3: A. Baruffolo. R-trees for astronomical data indexing. ASP Conf. Ser., Astronomical Data Analysis Software and Systems VIII , 172:375, 1999.
• 4: Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263671]
• 5: 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
• 6: Stefan Berchtold , Hans-Peter Kriegel, S3: similarity search in CAD database systems, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.564-567, May 11-15, 1997, Tucson, Arizona, United States
• 7: Phil Bernstein , Michael Brodie , Stefano Ceri , David DeWitt , Mike Franklin , Hector Garcia-Molina , Jim Gray , Jerry Held , Joe Hellerstein , H. V. Jagadish , Michael Lesk , Dave Maier , Jeff Naughton , Hamid Pirahesh , Mike Stonebraker , Jeff Ullman, The Asilomar report on database research, ACM SIGMOD Record, v.27 n.4, p.74-80, Dec. 1998 [doi>10.1145/306101.306137]
• 8: Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
• 9: Kenneth R. Castleman, Digital image processing, Prentice Hall Press, Upper Saddle River, NJ, 1996
• 10: The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces, Proceedings of the 15th International Conference on Data Engineering, p.440, March 23-26, 1999
• 11: S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Launder, and R. Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41:391--407, 1990.
• 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
• 13: S. T. Dumais. Improving the retrieval of information from external sources. Behavior Research Methods, Instruments and Computers, 23:229--236, 1991.
• 14: Ömer Egecioglu, Parametric Approximation Algorithms for High-Dimensional Euclidean Similarity, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.79-90, September 03-05, 2001
• 15: Ömer Eğecioğlu , Hakan Ferhatosmanoğlu, Dimensionality reduction and similarity computation by inner product approximations, Proceedings of the ninth international conference on Information and knowledge management, p.219-226, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354822]
• 16: Omer Egecioglu, How to Approximate the Inner-product: Fast Dynamic Algorithms for Euclidean Similarity, University of California at Santa Barbara, Santa Barbara, CA, 1999
• 17: C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
• 18: 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
• 19: Hakan Ferhatosmanoglu , Divyakant Agrawal , Amr El Abbadi, Optimal Partitioning for Efficient I/O in Spatial Databases, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.889-900, August 28-31, 2001
• 20: Hakan Ferhatosmanoglu , Ertem Tuncel , Divyakant Agrawal , Amr El Abbadi, Approximate Nearest Neighbor Searching in Multimedia Databases, Proceedings of the 17th International Conference on Data Engineering, p.503-511, April 02-06, 2001
• 21: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 22: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 23: Informix. http://www.ibm.com/software/data/informix/blades/spatial/rtree.html, 2002.
• 24: Nuggehally S. Jayant , P. Noll, Digital Coding of Waveforms: Principles and Applications to Speech and Video, Prentice Hall Professional Technical Reference, 1990
• 25: T. Kailath. Modern Signal Processing. Springer Verlag, 1985.
• 26: K. V. Ravi Kanth , Divyakant Agrawal , Ambuj Singh, Dimensionality reduction for similarity searching in dynamic databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.166-176, June 01-04, 1998, Seattle, Washington, United States
• 27: Ravi Kanth V Kothuri , Siva Ravada , Daniel Abugov, Quadtree and R-tree indexes in oracle spatial: a comparison using GIS data, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564755]
• 28: H. Karhunen. Uber lineare methoden in der wahrscheinlich-keitsrechnung. Ann. Acad. Science Fenn , 1947.
• 29: 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
• 30: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 31: Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
• 32: 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
• 33: M. Loeve. Fonctions aleatoires de seconde ordre. Processus Stochastiques et Mouvement Brownien , 1948.
• 34: 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. 1908 on Storage and Retrieval for Image and Video Databases , volume 1908, pages 173--187, February 1993.
• 35: Alan V. Oppenheim , Ronald W. Schafer, Discrete-time signal processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 36: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 37: Thomas Seidl , Hans-Peter Kriegel, Efficient User-Adaptable Similarity Search in Large Multimedia Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.506-515, August 25-29, 1997
• 38: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 39: V. S. Subrahmanian, Principles of multimedia database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 40: Michail Vlachos , Carlotta Domeniconi , Dimitrios Gunopulos , George Kollios , Nick Koudas, Non-linear dimensionality reduction techniques for classification and visualization, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775143]
• 41: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 42: A. J. Wicenec and M. Albrecht. Methods for structuring and searching very large catalogs. ASP Conf. Ser., Astronomical Data Analysis Software and Systems VII, 145:512, 1998.
• 43: 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

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
high dimensional data, shape approximation, similarity search