FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets

ABSTRACT

A very promising idea for fast searching in traditional and multimedia databases is to map objects into points in k-d space, using k feature-extraction functions, provided by a domain expert [25]. Thus, we can subsequently use highly fine-tuned spatial access methods (SAMs), to answer several types of queries, including the 'Query By Example' type (which translates to a range query); the 'all pairs' query (which translates to a spatial join [8]); the nearest-neighbor or best-match query, etc.However, designing feature extraction functions can be hard. It is relatively easier for a domain expert to assess the similarity/distance of two objects. Given only the distance information though, it is not obvious how to map objects into points.This is exactly the topic of this paper. We describe a fast algorithm to map objects into points in some k-dimensional space (k is user-defined), such that the dis-similarities are preserved. There are two benefits from this mapping: (a) efficient retrieval, in conjunction with a SAM, as discussed before and (b) visualization and data-mining: the objects can now be plotted as points in 2-d or 3-d space, revealing potential clusters, correlations among attributes and other regularities that data-mining is looking for.We introduce an older method from pattern recognition, namely, Multi-Dimensional Scaling (MDS) [51]; although unsuitable for indexing, we use it as yardstick for our method. Then, we propose a much faster algorithm to solve the problem in hand, while in addition it allows for indexing. Experiments on real and synthetic data indeed show that the proposed algorithm is significantly faster than MDS, (being linear, as opposed to quadratic, on the database size N), while it manages to preserve distances and the overall structure of the data-set.

REFERENCES

• 1: 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
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: S.F. Altschul, W. Gish, W. Miller, E.W. Myers, and D.J. Lipman. A basic local alignment search tool. Journal of Molecular Biology, 215(3):403-410, 1990.
• 5: Manish Arya, William Cody, Christos FaIoutsos, Joel Richardson, and Arthur Toga. Qbism: a prototype 3-d medical image database system. IEEE Data Engineering Bulletin, 16(1):38-42, March 1993.
• 6: Ricardo A. Baeza-Yates , Walter Cunto , Udi Manber , Sun Wu, Proximity Matching Using Fixed-Queries Trees, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, p.198-212, June 05-08, 1994
• 7: 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
• 8: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, Multi-step processing of spatial joins, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.197-208, May 24-27, 1994, Minneapolis, Minnesota, United States
• 9: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 10: W. A. Burkhard , R. M. Keller, Some approaches to best-match file searching, Communications of the ACM, v.16 n.4, p.230-236, April 1973 [doi>10.1145/362003.362025]
• 11: Mathematical Committee on Physical and NSF Engineering Sciences. Grand Challenges" High Performance Computing and Communications. National Science Foundation, 1992. The FY 1992 U.S. Research and Development Program.
• 12: R.O. Duda and P.E. Hart. Pattern Classification and Scene Analysis. Wiley, New York, 1973.
• 13: Susan T. Dumais. Latent semantic indexing (LSI) and TREC-2. In D. K. Harman, editor, The Second Text Retrieval Conference (TREC-2), pages 105-115, Gaithersburg, MD, March 1994. NIST. Special Publication 500- 215.
• 14: C. Faloutsos , S. Roseman, Fractals for secondary key retrieval, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.247-252, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73746]
• 15: 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
• 16: Peter W. Foltz , Susan T. Dumais, Personalized information delivery: an analysis of information filtering methods, Communications of the ACM, v.35 n.12, p.51-60, Dec. 1992 [doi>10.1145/138859.138866]
• 17: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 18: Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982 [doi>10.1145/358728.358741]
• 19: G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press, Baltimore, second edition, 1989.
• 20: 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
• 21: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 22: K. Hinrichs and J. Nievergelt. The grid file: a data structure to support proximity queries on spatial objects. Proc. of the WG'83 (Intern. Workshop on Graph Theoretic Concepts in Computer Science), pages 100-113, 1983.
• 23: H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States
• 24: H. V. Jagadish, Spatial Search with Polyhedra, Proceedings of the Sixth International Conference on Data Engineering, p.311-319, February 05-09, 1990
• 25: H. V. Jagadish, A retrieval technique for similar shapes, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.208-217, May 29-31, 1991, Denver, Colorado, United States
• 26: Mark A. Jones, Guy A. Story, and Bruce W. Ballard. Integrating multiple knowledge sources in a bayesian ocr post-processor. In First International Conference on Document Analysis and Recognition, Saint-Malo, France, September 1991. to appear.
• 27: Ibrahim Kamel , Christos Faloutsos, Hilbert R-tree: An Improved R-tree using Fractals, Proceedings of the 20th International Conference on Very Large Data Bases, p.500-509, September 12-15, 1994
• 28: Joseph B. Kruskal. Nonmetric multidimensional scaling. Psychometrika, 29"1-27, 1964.
• 29: Joseph B. Kruskal and Myron Wish. Multidimensional scaling. SAGE publications, Beverly Hills, 1978.
• 30: Karen Kukich, Technique for automatically correcting words in text, ACM Computing Surveys (CSUR), v.24 n.4, p.377-439, Dec. 1992 [doi>10.1145/146370.146380]
• 31: 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]
• 32: F. Murtagh. A survey of recent advances in hierarchical clustering Mgorithms. The Computer Journal, 26(4):354-359, 1983.
• 33: A. Desai Narasimhalu , Stavros Christodoulakis, Multimedia Information Systems: The Unfolding of a Reality, Computer, v.24 n.10, p.6-8, October 1991 [doi>10.1109/2.97253]
• 34: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 35: Wayne Niblack, Ron Barber, Will Equitz, Myron Flickner, Eduardo Glasman, Dragutin Petkovic, Peter Yanker, Christos Faloutsos, and Gabriel Taubin. The QBIC project: Querying images by content using color, texture and shape. SPIE 1993 Intl. Symposium on Electronic Imaging: Science and Technology, Conf. 1908, Storage and Retrieval for Image and Video Databases, February 1993. Also available as IBM Research Report RJ 9203 (81511), Feb. 1, 1993, Computer Science.
• 36: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 37: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• 38: Jack Orenstein, A comparison of spatial query processing techniques for native and parameter spaces, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.343-352, May 23-26, 1990, Atlantic City, New Jersey, United States
• 39: William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipes in C. Cambridge University Press, 1988.
• 40: A. Ravishankar Rao and Jerry Lohse. Identifying high level features of texture perception. In SPIE Conference, San Jose, February 1992.
• 41: A. Kimball Romney, Roger N. Shepa~d, and Sara Beth Nel:love. Multidimensional scaling: Theory and applications in the behavioral sciences : vol II- Applications. Seminar Press, New York, 1972.
• 42: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 43: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 44: David Sankoff and Joseph B. Kruskal. Time Warps, String Edits and Macromolecules: the Theory and Practice o} Sequence Comparisons. Addison-Wesley Publishing Company, Inc., Reading, MA, 1983.
• 45: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 46: Marvin Shapiro, The choice of reference points in best-match file searching, Communications of the ACM, v.20 n.5, p.339-343, May 1977 [doi>10.1145/359581.359599]
• 47: Dennis Shasha , Tsong-Li Wang, New techniques for best-match retrieval, ACM Transactions on Information Systems (TOIS), v.8 n.2, p.140-158, Apr. 1990 [doi>10.1145/96105.96111]
• 48: R. N. Shepard. The analysis of proximities: Multidimensional scaling with an unknown distance i and ii. Psychometrika, 27:125-140, 219-246, 1962.
• 49: Gilbert Strang. Linear Algebra and its Applications. Academic Press, 1980. 2nd edition.
• 50: A.W. Toga, P.K. Banerjee, and E.M. Santori. Warping 3d models for interbrain comparisons. Neurosc. A bs., 16:247, 1990.
• 51: W. S. Torgerson. Multidimensional scaling: I. theory and method. Psychometrika, 17:401-419, 1952.
• 52: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 53: Dimitris Vassiliadis. The input-state space approach to the prediction of auroral geomagnetic activity from solar wind variables. Int. Workshop on Applications o/ Artificial Intelligence in Solar Terrestrial Physics, September 1993.
• 54: Stephen Wolfram. Mathematica. Addison Wesley, 1991. Second Edition.
• 55: Forrest W. Young. Multidimensional scaling : Hzstory, Theory and Applications. Lawrence Erlbaum associates, Hillsdale, New Jersey, 1987.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation, Theory, Verification