Towards solving similarity search problems using fuzzy concept for multi-dimensional data

ABSTRACT

In this paper, we present continuous research on data analysis based on our previous work on similarity search problems. PanKNN[13] is a novel technique which explores the meaning of K nearest neighbors from a new perspective, redefines the distances between data points and a given query point Q, and efficiently and effectively select data points which are closest to Q. It can be applied in various data mining fields. In this paper, we applied the Fuzzy concept to improve the performance of PanKNN, targeting the better decision making for the calculation of the distance between a data point and Q. This approach can assist to improve the performance of existing data analysis approaches.

REFERENCES

• 1: 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
• 2: Elke Achtert , Christian Böhm , Peer Kröger , Peter Kunath , Alexey Pryakhin , Matthias Renz, Efficient reverse k-nearest neighbor search in arbitrary metric spaces, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142531]
• 3: C. C. Aggarwal. Towards meaningful high-dimensional nearest neighbor search by human-computer interaction. In ICDE, 2002.
• 4: Charu C. Aggarwal , Alexander Hinneburg , Daniel A. Keim, On the Surprising Behavior of Distance Metrics in High Dimensional Spaces, Proceedings of the 8th International Conference on Database Theory, p.420-434, January 04-06, 2001
• 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: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceedings of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 7: James C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Kluwer Academic Publishers, Norwell, MA, 1981
• 8: Bin Cui , Heng Tao Shen , Jialie Shen , Kian-Lee Tan, Exploring bit-difference for approximate KNN search in high-dimensional databases, Proceedings of the 16th Australasian database conference, p.165-174, January 01, 2005, Newcastle, Australia
• 9: R. Fagin, R. Kumar, and D. Sivakumar. Efficient similarity search and classification via rank aggregation, 2003.
• 10: 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
• 11: Alexander Hinneburg , Charu C. Aggarwal , Daniel A. Keim, What Is the Nearest Neighbor in High Dimensional Spaces?, Proceedings of the 26th International Conference on Very Large Data Bases, p.506-515, September 10-14, 2000
• 12: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, ACM SIGMOD Record, v.27 n.2, p.154-165, June 1998
• 13: Y. Shi and L. Zhang. A dimension-wise approach to similarity search problems. In the 4th International Conference on Data Mining (DMIN'08), 2008.
• 14: 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
• 15: L. A. Zadeh. Fuzzy sets. Information and Control, 8(3):338--353, 1965.

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Measurement, Performance