Graph-based ranking algorithms for text processing

Data processing: speech signal processing – linguistics – language – Linguistics

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C704S009000, C715S200000, C715S211000

Reexamination Certificate

active

07809548

ABSTRACT:
The present invention provides a method of processing at least one natural language text using a graph. The method includes determining a plurality of text units based upon the natural language text, associating the plurality of text units with a plurality of graph nodes, and determining at least one connecting relation between at least two of the plurality of text units. The method also includes associating the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes and determining a plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge. The method can also include a graphical visualization of at least one important text unit in a natural language text or collection of texts. Methods for word sense disambiguation, keyword extraction, and sentence extraction are also provided.

REFERENCES:
patent: 6112203 (2000-08-01), Bharat et al.
patent: 6285999 (2001-09-01), Page
patent: 6480843 (2002-11-01), Li
patent: 7286977 (2007-10-01), Carter et al.
patent: 7403890 (2008-07-01), Roushar
patent: 7519613 (2009-04-01), Guha et al.
patent: 2003/0226100 (2003-12-01), Farahat et al.
patent: 2005/0246328 (2005-11-01), Zhang et al.
patent: WO 02/10985 (2002-02-01), None
Christiane Fellbaum, Derek Gross, and Katherine Miller, Adjectives in WordNet, 1993, pp. 26-39.
Lawrie, D., Croft, W. B., and Rosenberg, A. 2001. Finding topic words for hierarchical summarization. In Proceedings of the 24th Annual international ACM SIGIR Conference on Research and Development in information Retrieval (New Orleans, Louisiana, United States). SIGIR '01. ACM, New York, NY, 349-357. DOI= http://doi.acm.org/10.1145/383952.384022.
Varadarajan, R. and Hristidis, V. 2005. Structure-based query-specific document summarization. In Proceedings of the 14th ACM international Conference on information and Knowledge Management (Bremen, Germany, Oct. 31-Nov. 5, 2005). CIKM '05. ACM, New York, NY, 231-232. DOI= http://doi.acm.org/10.1145/1099554.1099602.
Erkan, G. and Radev, D. R. 2004. LexRank: graph-based lexical centrality as salience in text summarization. J. Artif. Int. Res. 22, 1 (Jul. 2004), 457-479.
Toutanova, K., Manning, C. D., and Ng, A. Y. 2004. Learning random walk models for inducing word dependency distributions. In Proceedings of the Twenty-First international Conference on Machine Learning (Banff, Alberta, Canada, Jul. 4-8, 2004). ICML '04, vol. 69. ACM, New York, NY, 103. DOI= http://doi.acm.org/10.1145/1015330.1015442.
Brew, C. and Schulte im Walde, S. 2002. Spectral clustering for German verbs. In Proceedings of the Acl-02 Conference on Empirical Methods in Natural Language Processing—vol. 10 Annual Meeting of the ACL. Association for Computational Linguistics, Morristown, NJ, 117-124. DOI= http://dx.doi.org/10.3115/1118693.1118709.
Salton, G., Singhal, A., Mitra, M., and Buckley, C. 1997. Automatic text structuring and summarization. Inf. Process. Manage. 33, 2 (Mar. 1997), 193-207. DOI= http://dx.doi.org/10.1016/S0306-4573(96)00062-3.
Marti Hearst , Christian Plaunt. Subtopic Structuring for Full-Length Document Access (1993).
International PCT Search US2005/015630 Report dated May 5, 2005.
G. Ramakrishnan et al., “Text Representation with WordNet Synsets using Soft Sense Disambiguation” Jun. 2003Natural Language Processing and Information Systems, 8thInternational Conference on Applications of Natural Language to Information Systems, Burg (Spreewald) Germany XP002383976.
M. Galley et al., “Improving Word Sense Disambiguation in Lexical Chaining” Aug. 2003,Proceedings the 18thInternational Joint Conference on Artificial Intelligence(IJCAI-03), Acapulco, Mexico, XP002383977.
M. Sussna, “Word Sense Disambiguation for Free-Text Indexing Using a Massive Semantic Network” 1993,ACM Press, Proceedings of the Second International Conference on Information and Knowledge Management, pp. 67-74, Washington, D.C., USA XP002383978.
K. Fragos et al., “Word Sense Disambiguation using Wordnet Relations” Oct. 2003Proceedings of 1stBalkan Conference in InformaticsThessaloniki Greece XP002383979.
Rada Mihalcea et al., “PageRank on Semantic Networks, with application to Word Sense Disambiugation” Aug. 2004,Proceedings of the 20th International Conference on Computational Linguistics(Coling 2004), Geneva Switzerland , XP002383980.
S. Brin et al., “The Anatomy of a Large Scale Hypertextual Web Search Engine” Apr. 1998,Computer Networks and ISDN Systems, North Holland Publishing, Amsterdam, NL. pp. 107-117, XP004121435.
M. Lesk, “Automatic Sense Disambiguation using Machine Readable Dictionaries: How to Tell a Pine Cone from an Ice Cream Cone” 1986,Proceedings of the Annual International Conference on Systems Documentation, pp. 24-26, XP002224563.
Brill, E., Transformation-based error driven learning and natural language processing: A case study in part-of-speech tagging.Computational Linguistics 21, 4 (Dec. 1995), 543-566.
Brin, S., and Page, L., The anatomy of a large-scale hypertextual Web search engine.Computer Networks and ISDN Systems 30, 1-7 (1998), 107-117.
Cowie, J., Guthrie, L., and Guthrie, J. Lexical disambiguation using simulated annealing. InProceedings of the 5th International Conference on Computational Linguistics COLING-92(1992), pp. 157-161.
DUC. Document understanding conference 2002.
Erkan, G. and Radev, D. LexRank: Graph-based Lexical Centrality as Salience in Text Summarization. InJournal of Artificial Intelligence, Dec. 2004.
Frank, E., Paynter, G.˜W., Witten, I.˜H., Gutwin, C., and Nevill-Manning, C.˜G. Domain-specific keyphrase extraction. InProceedings of the 16th International Joint Conference on Artificial Intelligence(1999), Morgan Kaufmann Publishers Inc., pp. 668-673.
Gale, W., Church, K., and Yarowsky, D. One sense per discourse. InProceedings of the DARPA Speech and Natural Language Workshop(Harriman, New York, 1992).
Herings, P., van der Laan, G., and Talman, D. Measuring the power of nodes in digraphs.Tech. rep., Tinbergen Institute, 2001.
Hobbs, J. A model for natural language semantics. Part I: The model.Tech. rep., Yale University, 1974.
Hulth, A. Improved automatic keyword extraction given more linguistic knowledge. InProceedings of the 2003 Conference on Empirical Methods in Natural Language Processing(Japan, Aug. 2003).
Kamvar, S., Haveliwala, T., Manning, C., and Golub, G. Extrapolation methods for accelerating PageRank computations. InProceedings of the 12th International World Wide Web Conference(2003).
Kilgarriff, A., and Rosenzweig, R. Framework and results for English Senseval.Computers and the Humanities 34(2000), 15-48.
Kleinberg, J. Authoritative sources in a hyperlinked environment.Journal of the ACM 46, 5 (1999), 604-632.
Lesk, M. Automatic sense disambiguation using machine readable dictionaries: How to tell a pine cone from an ice cream cone. InProceedings of the SIGDOC Conference 1986(Toronto, Jun. 1986).
Lin, C., and Hovy, E. Automatic evaluation of summaries using n-gram co-occurrence statistics. InProceedings of Human Language Technology Conference(HLT-NAACL 2003) (Edmonton, Canada, May 2003).
Lin, C., and Hovy, E. The potential and limitations of sentence extraction for summarization. InProceedings of the HLT/NAACL Workshop on Automatic Summarization(Edmonton, Canada, May 2003).
Lin, D. Principar—an efficient, broad-coverage, principle-based parser. InIn Proceedings of the Fifteenth International Conference on Computational Linguistics COLING-ACL '94(Kyoto, Japan, 1994), pp. 42-48.
Miller, G., Leacock, C., Randee, T., and Bunker, R.} A semantic concordance. InProceedings of the 3rd DARPA Workshop on Human Language Technology(Plainsboro, New Jersey, 1993), pp. 303-308.
Morris, J., and Hirst, G. Lexical cohesion, the thesaurus, and the structure of text.Computational Linguistics 17, 1 (1991), 21-48.
Patwardhan, S., Banerjee, S., and Pedersen, T. Using measures of semantic relatedness for word sense disambiguation. InProceedings of

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Graph-based ranking algorithms for text processing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Graph-based ranking algorithms for text processing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph-based ranking algorithms for text processing will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-4208903

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.