Type-based categorization of relational attributes

ABSTRACT

In this work we concentrate on categorization of relational attributes based on their data type. Assuming that attribute type/characteristics are unknown or unidentifiable, we analyze and compare a variety of type-based signatures for classifying the attributes based on the semantic type of the data contained therein (e.g., router identifiers, social security numbers, email addresses). The signatures can subsequently be used for other applications as well, like clustering and index optimization/compression. This application is useful in cases where very large data collections that are generated in a distributed, ungoverned fashion end up having unknown, incomplete, inconsistent or very complex schemata and schema level meta-data. We concentrate on heuristically generating type-based attribute signatures based on both local and global computation approaches. We show experimentally that by decomposing data into q-grams and then considering signatures based on q-gram distributions, we achieve very good classification accuracy under the assumption that a large sample of the data is available for building the signatures. Then, we turn our attention to cases where a very small sample of the data is available, and hence accurately capturing the q-gram distribution of a given data type is almost impossible. We propose techniques based on dimensionality reduction and soft-clustering that exploit correlations between attributes to improve classification accuracy.

REFERENCES

• 1: AT&T Inc. Business listings from YellowPages.com. proprietary.
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: L. Douglas Baker , Andrew Kachites McCallum, Distributional clustering of words for text classification, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.96-103, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290970]
• 4: James C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Kluwer Academic Publishers, Norwell, MA, 1981
• 5: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 6: J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143--154, 1979.
• 7: C. Clifton, E. Housman, and A. Rosenthal. Experience with a combined approach to attribute-matching across heterogeneous databases. In In Proc. of the IFIP Working Conference on Database Semantics (IFIP DS), 1997.
• 8: Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534]
• 9: Edith Cohen , Mayur Datar , Shinji Fujiwara , Aristides Gionis , Piotr Indyk , Rajeev Motwani , Jeffrey D. Ullman , Cheng Yang, Finding Interesting Associations without Support Pruning, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.64-78, January 2001 [doi>10.1109/69.908981]
• 10: W. Colley and P. Lohnes. Multivariate data analysis. John Wiley & Sons, 1971.
• 11: Bing Tian Dai , Nick Koudas , Beng Chin Ooi , Divesh Srivastava , Suresh Venkatasubramanian, Rapid Identification of Column Heterogeneity, Proceedings of the Sixth International Conference on Data Mining, p.159-170, December 18-22, 2006 [doi>10.1109/ICDM.2006.132]
• 12: B. T. Dai, N. Koudas, D. Srivastava, A. K. H. Tung, and S. Venkatasubramanian. Validating multi-column schema matchings by type. In Proc. of International Conference on Data Engineering (ICDE), pages 120--129, 2008.
• 13: Tamraparni Dasu , Theodore Johnson , S. Muthukrishnan , Vladislav Shkapenyuk, Mining database structure; or, how to build a data quality browser, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564719]
• 14: AnHai Doan , Alon Y. Halevy, Semantic-integration research in the database community, AI Magazine, v.26 n.1, p.83-94, March 2005
• 15: J. C. Dunn. A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters. Journal of Cybernetics, 3:32--57, 1973.
• 16: I. P. Fellegi and A. B. Sunter. A theory for record linkage. Journal of the American Statistical Association, 64(328):1183--1210, 1969.
• 17: 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
• 18: Mauricio A. Hernández , Salvatore J. Stolfo, Real-world Data is Dirty: Data Cleansing and The Merge/Purge Problem, Data Mining and Knowledge Discovery, v.2 n.1, p.9-37, January 1998 [doi>10.1023/A:1009761603038]
• 19: Ykä Huhtala , Juha Kärkkäinen , Pasi Porkka , Hannu Toivonen, Efficient Discovery of Functional and Approximate Dependencies Using Partitions, Proceedings of the Fourteenth International Conference on Data Engineering, p.392-401, February 23-27, 1998
• 20: I. T. Jolliffe. Principal Component Analysis. Springer, second edition, October 2002.
• 21: Vipul Kashyap , Amit Sheth, Semantic and schematic similarities between database objects: a context-based approach, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.276-304, December 1996 [doi>10.1007/s007780050029]
• 22: V. Keselj, F. Peng, N. Cercone, and C. Thomas. N-gram-based author profiles for authorship attribution. In Proc. of the Conference Pacific Association for Computational Linguistics (PACLING), pages 255--264, 2003.
• 23: M. Ley. DBLP database. http://dblp.uni-trier.de/xml.
• 24: A. E. Monge and C. Elkan. The field matching problem: Algorithms and applications. In Proc. of ACM Knowledge Discovery and Data Mining (SIGKDD), pages 267--270, 1996.
• 25: Noam Slonim , Nir Friedman , Naftali Tishby, Multivariate information bottleneck, Neural Computation, v.18 n.8, p.1739-1789, August 2006 [doi>10.1162/neco.2006.18.8.1739]
• 26: Noam Slonim , Naftali Tishby, Document clustering using word clusters via the information bottleneck method, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.208-215, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345578]