Toward Structured Retrieval in Semi-structured Information Spaces

1 Introduction

Decentralized information sharing architectures like the World Wide Web and Lotus Notes make it easy for individuals to add information, but as the space grows, retrieval becomes more and more difficult. Semi­ structured information sharing systems, including Lotus Notes and a variety of meta-tagging schemes being developed for the World Wide Web (e.g. Apple's Meta-Content Format), address part of this problem by providing the ability to structure local parts of the information space. In a semi-structured information space, documents are sectioned into weakly-typed fields according to user specifications, and documents with the same field structure can be grouped into collections. Within a collection, field values can be used as indexes

for easier retrieval.

Unfortunately, semi -structuring document collections does not solve the problem of retrieving information across a large information space. Even if individual collections are well designed for retrieval, users can be overloaded with the sheer number of collections. Retrieval across the entire space is difficult because it is highly heterogeneous. Each collection has its own local schema, and there are no enforced keys or formats for data items within or across collections.

In this paper, we address the problem of finding information across collections in a large semi-structured information space. Our goal is to provide querying that is more powerful and precise than full-text search, but without requiring the collections to be strongly typed, data normalized, and fully mapped to a global schema, as methods like multidatabase SQL require. In addition, to maintain the advantages of decentralized information sharing, we do not want to impose constraints like

integrity checks when users create new documents.

Our approach is to provide high quality retrieval of

information related to important entities in the information space. In our organization (a large professional services firm), important types of entities include people, companies, and consulting skills. A review of our largest collections revealed that nearly always, references to important entities are fielded rather than buried in free-running text. Because the same entity can be referred to in many different ways across a heterogeneous information space, our entity retrieval system normalizes references to entities in a heuristic, type-dependent manner. For instance, the person names "Mr. Bob Smith", "Smith, Robert" , and "R. J. Smith" are normalized such that a query for any one (or a number of other possible forms) will retrieve documents containing any of them.

In addition to normalization, there are two entity­ related retrieval filters provided by our retrieval system: entity roles and collection types. Entities often play identifiable roles within collections. For instance, a person can play the role of a partner on an engagement, a manager, a contact at a client, etc. ; a company can play the role of a client, a vendor, a newsmaker, etc. These can be useful in organizing or filtering retrieved information ("find mentions of IBM as a client").

Based on entities and roles they contain, collections as

a whole can be classified into a small number of collection types. Examples include client-engagements collections, which contain clients, partners, and managers; directories, which contain staff names and phone numbers, etc. Like roles, collection types provide a useful way to organize or filter retrieved documents.

We have implemented an entity-based retrieval system called PW Notes Explorer (NX) that operates over a large semi-structured information space. The space includes corporate Lotus Notes collections and a small set of web collections. NX provides full-text search entity-based search for people, companies, and skills: and role and collection-type organization and filtering of results. In addition, it uses meta-information about entity types such as phone numbers, office sites, and dollar amounts to allow queries for specific properties of entities (e.g. "find Bob Smith's phone number").

A key hypothesis behind this work is that a relatively small amount of meta-information- much less than that required to normalize and map collections to a global schema - can give a large gain in query power and precision over knowledge-free methods like full-text search. NX is one illustration of this hypothesis. It requires minimal meta-information about each collection - its collection type and an indication of fields containing entities in various roles - and uses it to produce a dramatic improvement in retrieval quality for entity-related queries. Much of the required meta­ information is inferred automatically based on field names and data within the collections, using a simple heuristic classifier (see section 3.1). .

In what follows, we first motivate entity-based retrieval with real-world example. Next, we describe the main components of our retrieval system, and present an empirical comparison between entity-based retrieval and full-text search for a set of typical queries. We conclude by discussing related and future work.

2 Entity-based retrieval

In a corporate setting, information in different documents is frequently linked through references to entities with business importance, such as people and companies. Often, users search for information about particular entities (e.g., "What is Bob Smith's phone number?" or "Who's the manager for the XYZ Co.

account?") as opposed to ungrounded, aggregate queries across sets of entities (e.g. "Show me all managers with more than five clients over $5 million in sales"). We designed NX to support this type of search.

Consider a typical example from our organization. A staff member is writing a proposal to XYZ Company for some consulting work on XYZ's new customer tracking system. She needs answers to questions like:

• (a) How large is XYZ Company? E.g. , what are their assets, revenues, etc.?
• (b) Does our organization have a prior relationship with XYZ? Have we done other consulting work for them in the past?
• (c) Who did that work, and how can they be contacted?
• (d) Do we have staff with expertise on customer tracking systems? How can they be contacted?

Each question refers to entities of various types - XYZ Company, staff members, phone numbers, skills, etc. - and these entities may be referred to differently in different documents. The entities play particular roles; for instance, XYZ as a client, but not as a vendor or a newsmaker. Some questions involve information that may be found in many collections of the same type - e.g., information about pri9r work for XYZ (b) might be found in numerous collections containing client engagements. Others involve linking information about XYZ with information about another entity -- e.g., question (c) requires finding staff names in documents that list XYZ engagements, and then finding contact information for those staff names.

To find answers using the source collections directly would require that the user:

• know the relevant collections and their locations.
• construct searches that accounts for different forms of an entity (e.g. "XYZ Corporation" vs. "X Y ZInc.").
• discard hits where entities play irrelevant roles (e.g. XYZ as a vendor in an engagement, not as the client), and hits in irrelevant types of collections · (e.g. XYZ mentioned in news rather than client engagements).

NX overcomes these requirements. The next section examines its key components.

3 PW Notes Explorer

NX operates over a semi-structured information space of hundreds of collections, currently containing about 300,000 documents. It is delivered over an intranet using HTML.

Figure 1 shows one of the system's search forms. The pick-box with "Analysts Reports" chosen allows a user to choose among collection types. The pick-boxes along the right side, such as the one with "a company" chosen, allow a user to choose an entity type for each search string; "a phrase" indicates that a full-text search for the string should be performed. Figure 2 shows part of the set of results retrieved by the search in Figure 1.

NX includes three main components:

!.Semi-automatic field classification. To build an index of entity references of different types, we must identify where those types occur within collections. NX's field classifier uses field names and sample values from a collection to classify fields as containing entity types (people's names, company names, phone numbers, dollar amounts, etc.) and roles. As classification is not 100% accurate or complete, an interface is provided to alter the entity and role types for each collection's fields.

1. Entity normalization. When collections are indexed, entity references are extracted from entity­ typed fi~lds and normalized in a heuristic manner, using formattu~g knowledge and synonym tables specific to each entity type. At retrieval time, entity search terms are normalized in the same way and used to find matches in the index.
2. Entity-related result organization and filtering. Once a set of documents is retrieved, it can be viewed or filtered based on entity roles, collection types, and frequently co-occurring entities.

Next, we give a brief description of each component.

3.1 Semi-automatic field classification

Field classification attempts to identify an entity type and role for each collection field. The current version recognizes person names, company names, telephone numbers, geographic locations, office names, and dollar amounts. As in [Li & Clifton, 1994], the attributes used by the classifier are the field name and sample values from the documents in the collection.

The field classifier proceeds in three steps:

1. Field name analysis: Field names are tokenized according to capitalization and other separators. The tokens are then analyzed using a domain-dependent dictionary of .entity types and roles. Tokens are matched against the entries in the dictionary using a set of matching heuristics that recognize different types of abbreviations. For instance, the tokens "Tel" and "Phone" match the entity type telephone, the token "Ptr" matches the entity role partner, and the token "Name" is indicative of a name of any type: person, company, or office. In addition, the field name analyzer uses a set of simple patterns. For instance, the token "By" in the last position of a field name can indicate an action (e.g.,
2. "ServedBy"), suggesting that the field contains person or company names, which are the primary actors in our domain. Field name analysis produces a weighted set of potential entity types.
3. Field value analysis: Sample data values drawn fro~ documents in the collection are analyzed in a type­ specific manner for each potential entity type produced by field name analysis. For each entity type, the sample values are analyzed to determine how confidently they can be considered that type of entity. These confidence levels are combined for each potential type. Three criteria are used to analyze values:
4. Value lookup: the system looks up field values in tables of common values for different entity types. These include peoples' first names, large company names, and office sites. The confidence level for value lookup is high.
5. Common keywords: the system looks for common words that appear in entity values. For instance, company names often contain "Co." or "Inc.". Person names can contain titles like "Mr." or "Ms.". The confidence level for common keywords is medium.
6. Formatting: type-dependent routines attempt to match common formats for values of each entity type. For instance, person names have a small number of capitalized words, possibly initials, etc. The confidence level for formatting criteria is low.

. If the confidence level returned by field name analysis IS low for a potential entity type, the system increases th~ number of sample values, in order to collect enough evidence to make a classification. An entity type is assigned if confidence exceeds a threshold.

1. Role identification: If an entity type is assigned the classifier attempts to assign a role to the field based on its type and a second set of field name patterns. For example, a field of type person name with tokens "editor", "author", or "owner" indicates the role author.

In a small test, the field classifier analyzed 670 fields in 26 collections. Of these, 159 were of recognizable types. The field classifier correctly classified 154 of the 159 (97%) . Most failures were due to failing to recognize tokens in the field name. Of the 154 classified fields, 61 were of the roles client, manager, partner, author, reviewer or vendor. The system correctly recognized 58 of these (95%).

More work is needed to extend the classifier's generality. It relies on a hand-built dictionary of entity type and roles, but it should be possible to use standard induction techniques to learn such a dictionary from examples. The field classifier may also be extended to recognize other types, such as skill descriptions, vendor products, and technical terminology.

3.2 Entity Normalization

In a standard relational database, tuples from different tables that contain information about the same entity eac~ c_ontain a key for that entity allowing the tuples to be JOmed. In a semi-structured document space, however, there are rarely unique keys shared by collections. Rather, entities are referred to within text strings in a variety of formats, with a variety of synonyms and abbreviations.

Therefore, to allow search over entities, entity references must be normalized and matched. For maximum retrieval speed, NX normalizes entity references at indexing time. Its entity index stores both the original form and a normalized form of each entity reference. At retrieval time, a normalized form of the user's search string is created and used to retrieve matches from the normalized entity index. In some cases, values are only partially normalized, and the original forms of retrieved matches and the search string are compared to verify the match.

Normalization and matching of strings that refer to entities has two important properties. First, it is heuristic. Generally, it is impossible to know with certainty whether two strings refer to the same entity. "Bob Smith" and "Robert A. Smith" may or may not be the same person; the retrieval system must make a reasonable guess.

Second, it is type dependent. Normalizing different types of entities requires different processing: e.g., normalizing person names is different than normalizing company names. Different variations in format are allowed for each type; "Smith, Bob" is a variation of "Bob Smith", but "Computer, Apple" is not a variation for "Apple Computer" . In addition, different synonyms, abbreviations, and stop words apply. For company names, for instance, including or omitting words like "Corp." is only a small variation; for person names, "Mr." is a small variation unless the other string contains a female designator like "Ms." NX employs different normalization routines for different types, including small tables of synonyms, abbreviations, and stop words.

Due to space limitations, we will only briefly describe NX's normalization routines here.

For company names, the string containing the entity reference is first processed to produce uniform capitalization, combine leading initials (e.g., "I B M" becomes "IBM"), and expand common abbreviations. Next, we look up the leading words of the string in a table of company name synonyms. If a match is found, a designated synonym is used as the normalized form of the string. For example, the normalized form of "IBM" is "International Business Machines This could result in the same normalized form for different names, the differences are accounted for at retrieval time as

described below.

At retrieval time, the search string for a company is normalized in the same way. Matches for the normalized form are retrieved from the entity index table. If the search string was found in the synonym table, all matches from the index are returned as retrieved matches, on the basis that appearing in the same synonym set implies a fairly strong match. For instance, all matches normalized to "International Business Machines" would be returned by a search for "IBM" . In cases where no synonym is found, entity strings with the same first word are retrieved from the index and scored against the search string on a word-by­ word basis. Words that appear in one but not the other reduce the match score by an amount proportional to the total number of words; common company words like "Corporation" are penalized less. Each entry with a match score over a threshold is returned as retrieved match. The search string "Foobaz Circuit Supply", for instance, matches "Foobaz Circuit Corp." but not "Foobaz Lawn and Garden Products".

The algorithm for person names is slightly more complex, since it must account for more possible variations in word-order, title words ("Dr.", etc.), generation designators ("Jr.", "III", etc.) and so on.

In addition, pre-processing is required to find the portions of the input string containing entity references. Often, a field will contain multiple entity values in a single string, with spurious information interspersed. For example, a typical person name field value might be "Bob J. Smith Jr. - partner; Sue Jones, 415-555-1212, Palo Alto." NX's normalization routines extract "Bob J. Smith Jr." and "Sue Jones" .out of this field value.

3.3 Entity-related result filtering

Documents that match a query can be filtered and sorted based on the collection types they . are drawn from, the roles played by entities in the documents, and other entities that co-occur in the documents. In addition, standard filters/sorts such as date ranges and relevance scores are provided.

In Figure 2, results are displayed sorted by the collection type and collections they are drawn from. Here, the search has been filtered using the "Analysts Reports" collection type. In cases where documents are retrieved from many collection types, the display provides a useful breakdown of the major kinds of information retrieved.

The buttons along the top of the page indicate alternative sortings. 'View by role' sorts the documents according to the roles of entities that matched the query within each document.

The 'What's related?' function retrieves the most frequently occurring other entities (people, companies, and skills) in the set of retrieved documents. Because they have been normalized, the co-occurring entities can be properly grouped independent of how they were referred to in the source documents. In essence, this uses the normalized entity index as a simple data warehouse, enabling an aggregation over. entities in document sets. Entity co-occurrence often indicates an ongoing relationship, such as partners with clients, staff

with skills, companies as industry peers, etc.

The "What's related?" function is a good example of entity-based retrieval's use of a small amount of meta­ information to go beyond knowledge-free methods like full-text search. A knowledge-free method cannot perform this type of function as meaningfully because it does not take advantage of the structure present in semi­ structured collections. "What's related?" is a step toward structured retrieval. It does not retrieve structured relationships between data items, but approximates them using co-occurrence.

4 Results

To evaluate NX's entity-based retrieval and filtering functionality, we used a typical set of user questions from our organization's staff (drawn from NX logs, consultant training material, and online bulletin boards). For each question, we tested four conditions:

1. Nal've full-text search: Our users are not sophisticated full-text users. Thus, we used simple full-text searches for the entities in the question.
2. Full-text search with collection-type filtering: To (1) , we added that only results from the appropriate collection type be returned.
3. Entity search: Instead of full-text search, we used NX's entity search for the entities in the question.
4. Entity search with collection-type filtering: To (3), we added that only results from the appropriate collection type be returned.

We tested these conditions for a set of 24 questions. The results are shown in Figure 3. Collection-type filtering produces a much smaller result set than full­ text search alone, and collection-type plus entity search reduces the result set further. The average nai:ve full­ text result set was 1358 documents from 15 collections; the average entity-search with collection-type filtering result set was 37 documents from 2 collections.

Without pre-scored document collections, it is difficult to obtain strong measures of recall and precision for large information spaces (too large to search by hand). In the absence of scored answer keys, we have resorted to approximate measures. One way to approximate recall is by comparing to a method known to produce high recall. In this case, the results returned by entity + filtering searches are basically equivalent to the results that would be found by a user submitting a query against each collection's local schema, if the user knew the proper collections, field names and synonymous field values for each query. Thus, entity + filtering search produces a comparable level of recall.

Assuming comparable recall levels, we can obtain a rough measure of precision by examining the total number of documents returned by each retrieval method. Our test questions called for fairly focused answers, as opposed to "deep background" questions, like "find all documents that mention the internet", and thus small result sets are appropriate. In practice, large result sets containing hundreds or thousands of documents are much less useful than small sets, because they require so much hand filtering. In this sense, we consider the dramatically smaller result sets produced by entity + collection filtered search to be a large improvement over nai:ve full-text search, for entity-related queries.

Because of the synonyming capability of entity search, there were often documents retrieved by entity searches that were not retrieved by nai:ve full-text searches. For the first ten questions, on average, 14% of the documents returned by entity searches were not returned by nai:ve full -text search. In some cases - in particular, searches for contact information for people - missed documents contained the crucial information to answer the question at hand.

5 Discussion and Future Work

The goal of our work is to provide better information retrieval across a large semi-structured space than full­ text search, while avoiding excessive meta-information overhead. Our approach is based on observing that in an information space used by a particular organization, important entity types link information together and can be used as a central retrieval cue. This data-driven approach can be contrasted with schema-driven approaches used by multidatabase systems (e.g., [Arens et al. , 1993 ]), and similar systems attempting to integrate structured world-wide web sources [Levy et al. , 1996; Farquhar et al., 1995] . In schema-driven approaches, each local schema is mapped to a central global schema, and mapping rules are used to translate between data formats used by different sources (e.g. [Collet et al. , 1991]). These approaches are appropriate for relatively small numbers of tables where the data within each table is well-specified; however, semi­ structured information spaces can include hundreds of sources, and data even within single sources can have multiple formats. A schema integration phase would be burdensome in such a large space [Gob et al. 1994] .

Instead, NX relies on heuristics to categorize fields into a small number of entity and role types, and normalizes entity values for retrieval (as in [Huffman and Steier, 1995]). The resulting retrieval system is more broadly applicable but less general than multidatabase systems, because queries must refer to an entity.

One area for future work is classification and normalization of a larger variety of entity types. New types we are considering include locations, product names, and technical terminology appearing in the body of a document. Field classification could be improved by using non-local information, such as data values' appearances in other collections. Indexing could be improved by extracting entity values from free-running text, in addition to tagged fields. This would require text processing tools like name finders [Rau, 1991; Hayes, 1994], technical-term extractors [Justeson and Katz, 1995; Chen and Chen, 1994], parsers that find characteristic phrases using fonts and other cues [Krulwich and Burkey, 1995], or shallow linguistic approaches such as those used by information extraction systems [MUC 93] .

A related idea we are experimenting with is using text classification and thesaurus induction methods (e.g. [Grefenstette, 1994]) to attach organization-wide categories to documents as a whole. These categories can be used as retrieval cues or filters, similar to roles.

Finally, we are investigating ways to move further towards structured retrieval by allowing users to retrieve specific types of information related to entities, rather than simply documents. For instance, since our meta­ information indicates which collections are directories and which fields within those collections contain people and phone numbers, it should be possible (with a small increment of additional meta-information) to allow users to retrieve a value for "Bob Smith's phone number" instead of just documents containing Bob Smith. Like the "What's related?" functionality, retrieval of specific related information makes use of the entity index as a data warehouse.

6 Conclusion

Semi-structured systems are an intermediate point between unstructured collections of textual documents (e.g., untagged Web pages) and fully structured tuples of typed data (e.g., relational databases). Our goal is to provide stronger retrieval than full-text search, but without requiring the strong typing, schema and data mapping needed for SQL-style querying. Based on observing how information is typically retrieved and used within our organization, we have developed an entity-based retrieval system over a large semi­ structured information space. The system incorporates semi-automatic classification of fields, normalization of field values, and filtered retrieval using entity roles and collection types. For typical queries containing entities, the system provides much more focused and normalized retrieval than full-text search.