Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-11-03
2002-11-12
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C704S007000
Reexamination Certificate
active
06480843
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to field of indices and queries applied to a collection of documents in a database. More specifically, this invention relates to efficient expansion and processing of the queries, to reducing the size of indices used to perform the query expansion and to progressive query processing.
2. Description of the Related Art
Conventional retrieval systems, by which documents may be retrieved through the application of queries, are based on a common set of principles and methodologies of categorizing documents. Documents are normally indexed manually by subject experts or librarians using pre-specified and controlled vocabularies. Alternatively, documents can be indexed based on the words included in the documents. Users can search documents using terms from the accepted vocabularies, together with appropriate boolean operators between them. In this type of system, an exact match strategy is used. Although this approach has many advantages, such as simplicity and high precision, it suffers from the problem of word mismatch.
The problem of word mismatch in information retrieval occurs because people often use different words to describe concepts in their queries than authors use to describe the same concepts in their documents.
FIG. 1
shows that words used in HyperText Markup Language (HTML) documents related to the words “car” and “dealer” may vary from one document to another. Languages other than HTML, such as Extensible Markup Language (XML) and Standard Generalized Markup Language (SGML), may be used. If a user uses a query with the words “automobile” and “dealer,” he or she cannot retrieve all the relevant documents due to word mismatch problems.
Query expansion has been suggested as a technique for dealing with this problem. Such an approach would expand queries using semantically similar words (e.g. synonyms or other semantically related words) and syntactically related words (e.g. words co-occurring in the same document above a certain frequency are syntactically co-occurring words) to those words in the query to increase the chances of matching words in relevant documents. When query expansion is used, the “car dealer” query is expanded as follows to include terms with similar meanings:
Line 1. [(“car” OR “automobile” OR “auto” OR “sedan” ) OR
Line 2. (“Ford” OR “Buick”)] AND
Line 3. (“Dealer” OR “Showroom” OR “SalesOffice”)
There are two types of query expansion involved in this example. The query expansions in Line 1 and Line 3 are adding additional words related to car and dealer by lexical semantics, i.e. words which are semantically similar. Automobile, auto, and sedan are words having a similar meaning to the word car. Similarly, Showroom and SalesOffice have meanings similar to the word dealer. The other type of query expansion, shown in Line 2, is by, for example, syntactical co-occurrence relationships. A large number of the words used on the World Wide Web (“the Web”) are actually proper names, which cannot be found in lexical dictionaries. Examples of proper names include Ford, Buick, NBA, and National Football League. As noted above, syntactical co-occurrence relationships are derived from analysis on the frequency of two words co-occurring in the same document. This is based on the assumption that there is a higher chance that two words are related if they appear frequently together in the same document. For example, the co-occurring words with Ford could be dealer, body shop, Mustang, Escort, etc.
To support query expansion, indices of words related by lexical semantics and syntactical relationships, such as co-occurrence, need to be maintained. The indices for related words by lexical semantics can be constructed as a hierarchical structure (see e.g. W. Li et al., “Facilitating Multimedia Database Exploration through Visual Interfaces and Perpetual Query Reformulations,” Proceedings of the 23rd International Conference on Very Large Data Bases, pages 538-547, Athens, Greece, August 1997), a semantics network (see e.g. G. A. Miller, “Nouns in WordNet: A Lexical Inheritance System” In International Journal of Lexicography 3 (4), 1990, pages 245-264), or hierarchical clusters of associated words (see e.g. G. Salton et al., “The SMART and SIRE Experimental Retrieval Systems,” pages 118-155, McGraw-Hill, New York, 1983). Since syntactical relationships, such as syntactical co-occurrence relationships, are binary, the size of syntactical relationship indices can be extremely large. Some techniques have been proposed for stemming. See e.g., G. Grefenstette, “Use of syntactic context to produce term association lists for text retrieval,” Proceedings of the Fifteenth Annual International ACM SIGIR Conference, Denmark, 1992; J. Xu et al., “Query Expansion Using Local and Global Document Analysis,” Proceedings of the 19th Annual International ACM SIGIR Conference, Zurich, Switzerland, 1996; and C. Jacquemin, “Guessing Morphology from Terms and Corpora,” Proceedings of the 20th Annual International ACM SIGIR Conference, Philadelphia, Pa., USA, 1997. Such techniques include analysis of occurrence frequency, and employing morphological rules (e.g. converting all words to root form) or lexical dictionaries. However, the size of indices for words associated by syntactical co-occurrence relationships is too large to search efficiently.
A substantial amount of work on the problem of word mismatch has been done in the area of information retrieval (IR). See e.g. G. Salton et al., “Introduction to Modern Information Retrieval,” McGraw-Hill Book Company, 1983; G. Salton, “Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer,” Addison-Wesley Publishing Company, Inc., 1989; and K. Sparck Jones et al., “Readings in Information Retrieval” Morgan Kaufinann, San Francisco, Calif., USA, 1997. However, much of the work has been directed to the study of retrieval measures such as recall and precision. Although some work has suggested ways to efficiently support query expansion (see e.g. C. Buckley et al., “Automatic Query Expansion Using SMART,” Proceedings of the 3rd Text Retrieval Conference, Gaithersburg, Md., 1993) and indexing mechanisms, two problems have persisted without an acceptable solution. First, index size is extremely large since many words in a document collection (e.g. the Web) are distinct proper names and each word has a number of semantically similar and syntactically related words. Second, query processing is expensive since queries are expanded by adding additional words.
These problems get worse when dealing with document information collected from the Web since the number of documents is very large and the words used are extremely diverse, inconsistent, and sometimes incorrect (e.g., typographical errors). A study has shown that most user queries on the Web typically involve two words. See B. Croft et al., “Providing Government Information on the Internet: Experiences with THOMAS,” Proceedings of Digital Libraries (DL '95), 1995. However, with query expansion, query lengths increase substantially. As a result, most existing search engines on the Web do not provide query expansion functionality.
An overview of existing work in the area of query expansion will now be presented. Query expansion has received a significant attention in the field of IR. However, the focus in the past has been to evaluate the improvements in retrieval measures, i.e., precision and recall, as a result of query expansion. Another research focus has been in the direction of building dictionaries so as to identify a set of similar terms for a given query word. However, the existing work has done little to address the problem of efficient processing of queries when they undergo query expansion or to reduce the size of the indices used to perform query expansion and processing. Furthermore, the issue of ranking documents on the basis of exact and similarity matches remains a difficult problem.
SMART is one of the best known advanced information retri
Homere Jean R.
NEC USA Inc.
Sughrue & Mion, PLLC
Wassum Luke S
LandOfFree
Supporting web-query expansion efficiently using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Supporting web-query expansion efficiently using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Supporting web-query expansion efficiently using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2990868