Improved count suffix trees for natural language data

ABSTRACT

With more and more natural language text stored in databases, handling respective query predicates becomes very important. Optimizing queries with predicates includes (sub)string estimation, i.e., estimating the selectivity of query terms based on small summary statistics before query execution. Count Suffix Trees (CST) are commonly used to this end. While CST yield good estimates, they are expensive to build and require a large amount of memory to be stored. To fit in the data dictionary of database systems, they have to be severely pruned. Existing pruning techniques are based on suffix frequency or tree depth. In this paper, we propose new filtering and pruning techniques that reduce both the size of CST over natural-language texts and the cost of building them. The core idea is to exploit features of the natural language data, i.e., regarding only the suffixes that are useful in a linguistic sense. The most important innovations are (a) a new aggressive approximate syllabification technique to filter out suffixes, (b) a new affix and prefix stripping procedure that conflates more terms than conventional stemming techniques, (c) the deployment of state-of-the-art trigram techniques and a new syllable-based mechanism to filter out non-words (i.e., misspellings and other language anomalies like foreign words), which would cause an over-proportional growth of the CST otherwise. -- Our evaluation with large English text corpora shows that our new mechanisms in combination decrease the size of a CST by up to 80% and shorten the build phase significantly. From a different perspective, if storage space remains unchanged, the accuracy of selectivity estimates computed from the CST increases by up to 70%.

REFERENCES

• 1: Jinuk Bae , Sukho Lee, Substring Count Estimation in Extremely Long Strings*This work was supported in part by the Brain Korea 21 Project and in part by the Ministry of Information & Communications, Korea, under the Information Technology Research Center (ITRC) Support Program in 2005., IEICE - Transactions on Information and Systems, v.E89-D n.3, p.1148-1156, March 2006 [doi>10.1093/ietisy/e89-d.3.1148]
• 2: Stephane Bressan , Riky Irawan, Morphologic Non-Word Error Detection, Proceedings of the Database and Expert Systems Applications, 15th International Workshop, p.31-35, August 30-September 03, 2004 [doi>10.1109/DEXA.2004.108]
• 3: Surajit Chaudhuri , Venkatesh Ganti , Luis Gravano, Selectivity Estimation for String Predicates: Overcoming the Underestimation Problem, Proceedings of the 20th International Conference on Data Engineering, p.227, March 30-April 02, 2004
• 4: D. W. Cummings. American English Spelling: An Informal Description. Johns Hopkins University Press, 1988.
• 5: D. Graff. The aquaint corpus of english news text. Linguistic Data Consortium, Philadelphia, 2002.
• 6: H. V. Jagadish , Olga Kapitskaia , Raymond T. Ng , Divesh Srivastava, One-dimensional and multi-dimensional substring selectivity estimation, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.214-230, December 2000 [doi>10.1007/s007780000029]
• 7: P. Krishnan , Jeffrey Scott Vitter , Bala Iyer, Estimating alphanumeric selectivity in the presence of wildcards, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.282-293, June 04-06, 1996, Montreal, Quebec, Canada
• 8: Robert Krovetz, Viewing morphology as an inference process, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.191-202, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160718]
• 9: 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]
• 10: M. Lennon, D. Pierce, B. Tarry, and P. Willett. An evaluation of some conflation algorithms for information retrieval. Journal of Information Science, 3(177--183), 1981.
• 11: D. D. Lewis. Reuters-21578. http://www.daviddlewis.com/resources/testcollections/reuters21578/.
• 12: Franklin Mark Liang, Word hy-phen-a-tion by com-put-er (hyphenation, computer), Stanford University, Stanford, CA, 1983
• 13: J. B. Lovins. Development of a stemming algorithm. Mechanical Translation and Computational Linguistics, 11:22--31, 1968.
• 14: M. F. Porter. An algorithm for suffix stripping. Program, 14(3):130--137, 1980.
• 15: Yuanyuan Tian , Sandeep Tata , Richard A. Hankins , Jignesh M. Patel, Practical methods for constructing suffix trees, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.3, p.281-299, September 2005 [doi>10.1007/s00778-005-0154-8]
• 16: E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249--260, 1995.
• 17: Peter Weiner, Linear pattern matching algorithms, Proceedings of the 14th Annual Symposium on Switching and Automata Theory (swat 1973), p.1-11, October 15-17, 1973 [doi>10.1109/SWAT.1973.13]
• 18: E. M. Zamora, J. Pollock, and A. Zamora. The use of trigram analysis for spelling error detection. Information of Processing and Management, 17:305--316, 1981.
• 19: Craig Silverstein , Hannes Marais , Monika Henzinger , Michael Moricz, Analysis of a very large web search engine query log, ACM SIGIR Forum, v.33 n.1, p.6-12, Fall 1999 [doi>10.1145/331403.331405]
• 20: R. Giegerich, S. Kurtz, J. Stoye, Efficient Implementation of Lazy Suffix Trees, Software: Practice and Experience, Vol. 33, No 11, 2003

INDEX TERMS

General Terms:
Algorithms, Experimentation, Languages, Measurement, Theory

Keywords:
count suffix tree, pruning, query optimization, selectivity estimation, text data