# Presentation: 022395

## Creating Search Technology for E-Discovery

- Douglas W. Oard
- College of Information Studies
- Institute for Advanced Computer Studies
- University of Maryland, College Park

- Thanks to: Simon Attfield, Jason Baron, Jack Conrad, Tamer Elsayed, Bruce Hedin
-                   David Lewis, Paul Thompson, Stephen Tomlinson, Lidan Wang

- Partnerships in Innovation

- October 8, 2008

## Taking The Consumer’s View

## Picking up on David Giaretta’s Point ...

- Mitigating risks to future use
- What to keep?
- What to keep with it?
- Learning by doing
- Finding what we want
- Making sense of what we find
- Seeing what was never there

## 1. Finding what we want

**Clinton ****White House**

**Tobacco Policy**

**search request**

**hired 25 persons**

**32 million emails**

**200,000**

**80,000**

**for 6 months ...**

**Notes:**
There are problems in the real world that involve searching thru millions to return tens of thousands of results and we have to better tools to do that than we have now. 
Millions and we have to produce tens of thiusands and we have to have better tools because we cannot afford to hire 25 for 6 months.

There is a collection of 32 million emails deposited to National Archives of US by Clinton (administration /) White house. That’s only from presidential records and federal records from the executive office of the president. But of course the entire rest of the government will in the future be making similar deposits. So this 32 m emails is Larger collection than NA is able to handle/review but is not nearly as large as what they have to be able to handle in the future. 
Since this collection is not public yet, NARA got a legal request asking for emails that talk about tobacco. In response, NARA 
They got a request (because it’s not yet public) that went to the archivists that have them doing searches for a law suit about tobacco settlement / so they wanted to find things talking about tobacco policy in this 32 m emails. Hired 50 lawyers worked for 6 months they reviewed 200 thousand emails (which is less than 1% of the collection size) of which 80 thousands were released to the people requesting. We cannot continue to do this. We must have more effective techniques for this kind of problem.

So, it is clear that searching or making sense of such large scale of collection needs new set of tools that can help in that situation.

poses challenges

Using boolean
NOT SCALABLE
------------------
-------
Imagine u have a  large collection of email (millions of emails) and u want to make an exploratory search / make sense of this collection. If u were not actually participating in such informal form of communication, u would have very hard time understanding/recognizing (it would be very hard to realize) who is talking to whom and about who. For example, NA has 32 million emails from Clinton and expecting more than 150 millions from the current admin. Such large scale of collection needs new set of tools that can help in that situation. 
In this work we explore one of the capabilities that such tools will need: computational model of identity.

## Federal Rules of Civil Procedure (as amended 12/1/06)

*Rule 26(f)*
- 	At the parties’ planning meeting, issues expected to be discussed include:
- “Any issues relating to disclosure or discovery of _***electronically stored information***_, including the form or forms in which it should be produced”
- “Any issues relating to preserving discoverable information”

## E-Discovery: Process Perspective

- Jack G. Conrad, “E-Discovery Revisited:  A Broader Perspective for Researchers,” DESI-1

## Desiderata in the Legal Realm

- Two-party
- Negotiated (_not_ one-sided) information needs
- Recall-oriented
- “Smoking gun detection” + completeness
- Explainable
- Quantifiable comparison to present best practice
- Affordable
- Minimize amount of human review on back end

## Goals
Foster development of research communities
Create “benchmark” evaluation resources
Establish “baseline” results

History
Sponsored by NIST since 1992
“Legal Track” started in 2006 with an E-Discovery focus

- Foster development of research communities
- Create “benchmark” evaluation resources
- Establish “baseline” results
- History
- Sponsored by NIST since 1992
- “Legal Track” started in 2006 with an E-Discovery focus

- Text Retrieval Conference (TREC)

## Documents

- Legacy Tobacco Documents Library [UCSF]
- 6,877,327 documents released in lawsuits
- Variety of corporate document types
- Range of printing technologies and handwriting
- Complex Document Information Processing (CDIP) collection [IIT]
- 42 million page images:	1.5 TB (TIFF)
- OCR:				 50 GB (ASCII)
- Metadata: 			   5 GB (XML)

**Notes:**
Previous test collection efforts have cost hundreds of thousands or millions of dollars; we’ve been able to leverage existing data, volunteer efforts, and coordination with other ongoing projects to make progress at much less cost 

## Sample Document

## Sample Document

## Example Document

**Title:** *CIGNA WELL-BEING NEWSLETTER - FUTURE STRATEGY*
**Organization Authors:** *PMUSA, PHILIP MORRIS USA*
**Person Authors:** *HALLE, L*
**Document Date:** *19970530*
**Document Type:** *MEMO, MEMORANDUM*
**Bates Number:** *2078039376/9377*
**Page Count:** *2*
**Collection:** *Philip Morris*

- Philip Moxx's. U.S.A. x.dr~am~c. cvrrespoaa.aa
- Benffrts Departmext Rieh>pwna, Yfe&ia
- Ta: Dishlbutfon Data aday 90,1997.
- From: Lisa Fislla
- Sabj.csr CIGNA WeWedng Newsbttsr -Yntsre StratsU
- During our last CIGNA Aatfoa Plan meadng, tlu iasuo of wLetSae to i0op per'Irw+ng
- artieles aod discontinue mndia6 CIGNA Well-Being aawslener to om employees was a
- msiter of disanision . I Imvm done somme reaearc>>, and wanted to pruedt you with my
- Sadings and pcdiminary recwmmeadatioa for PM's atratezy Ieprding l4aas aewelattee* .
- I believe .vayone'a input is valusble, and would epproolate hoarlng fmaa aaeh of you on
- whetlne you concur with my reeommendatioa
**...**

_**Scanned**_

_**OCR**_

_**Metadata**_

## Legal Track Tasks

- One-shot “ad hoc” task
- Hold topic constant, try many system designs
- Sampling enables recall-oriented evaluation
- Automatic iterative “relevance feedback” task
- Models multi-stage meet and confer
- Manual iterative “interactive” task
- “Topic authority” available for clarification
- Fewer topics enable much richer sampling

## A “Production Request”

- RequestText:	**Please produce any and all documents that discuss the use**
**	****	****or introduction of high-phosphate fertilizers (HPF) for the **
**	****	****specific purpose of boosting crop yield in commercial**
**	**** ****	****agriculture.**
- Proposal:	**"high-phosphate fertilizer!" AND (boost! w/5 "crop yield")**
**	****	****AND (commercial w/5 agricultur!)**
- Rejoinder: 	**(phosphat! OR hpf OR phosphorus OR fertiliz!) **
**	****	****AND (yield! OR output OR produc! OR crop OR crops)**
- FinalQuery:	**(("high-phosphat! fertiliz!" OR hpf) OR **
**	****	****((phosphat! OR phosphorus) w/15 (fertiliz! OR soil))) AND**
**	**** ****	****(boost! OR increas! OR rais! OR augment! OR affect! OR**
** ****	****	****effect! OR multipl! OR doubl! OR tripl! OR high! OR greater)**
**	**** ****	****AND (yield! OR output OR produc! OR crop OR crops)**
- B: 		**3078**

## Research Teams

- Carnegie Mellon U
- Dartmouth College
- Long Island U
- Sabir Research, Inc.
- U Iowa
- U Massachusetts
- U Maryland
- U Missouri, Kansas City
- U Washington
- Ursinus College

- Fudan U (CN)
- National U of Singapore (SG)
- Open Text Corporation (CA)
- U Amsterdam (NL)
- U Waterloo (CA)

## Deconstructing “Concept Search”

**“****Features”**

**“****Method”**

**“****Specification”**

**“****Result”**

## Representing “Documents”

- Content
- Count the words
- Weight the words
- Ascribe meaning to words
- Context
- Who said this?
- When was it said?
- Who did they say it to?
- Description
- What was said about it?
- Behavior
- What was done with it?

**“****Features”**

## Controlling the Search System

- Proactive
- “Keyword” query
- “Boolean” query
- Query by example
- Reactive
- Ranked list selection
- “More like this” query
- Category exploration
- Social network exploration
- Iterative
- Query refinement
- “Search within” query

**“****Specification”**

## Generating Results

- Logic
- Similarity
- Probability

- Result set
- Ranked list
- Classification
- Clustering
- Visualization

**“****Features”**

**“****Method”**

**“****Specification”**

**“****Result”**

## Relevance Assessment

- Bank of America
- Department of Justice
- FTI Consulting
- H5 Technologies Inc.
- NARA
- Lewis & Roca LLP
- New Mexico Attorney General
- Preston Gates LLP
- Reasonable Discovery LLC
- SAIC
- Private individuals (CA, UK)

_**Law Schools**_
- Boston University
- Case Western Reserve
- George Mason
- George Washington
- Loyola-Los Angeles
- Loyola-New Orleans
- U Dayton
- U Indiana-Indianapolis
- U Maryland
- U Texas**  **

## Nobody Finds Everything

**Source: TREC 2006 Legal Track**

## Metadata-Based Expansion

- Corrupted

- Retrievable

- Document image from archives

- Retrievable

- Query

- Corrupted

- How to retrieve corrupted documents?

- Expand query with author and recipient names

## Leveraging the “Social Network”

- +63%

## E-Discovery as Sensemaking

- Simon Attfield and Ann Blandford, “E-Discovery Viewed as Integrated Human-Computer Sensemaking,” DESI-2

## Date: Wed Dec 20 08:57:00 EST 2000
From: Kay Mann <kay.mann@enron.com>
To: Suzanne Adams <suzanne.adams@enron.com>
Subject: Re: GE Conference Call has be rescheduled

Did Sheila want Scott to participate? Looks like the 
call will be too late for him.

***From*****: Kay Mann <kay.mann@enron.com>**
***To*****: Suzanne Adams <suzanne.adams@enron.com>**
***Subject*****: Re: GE Conference Call has be rescheduled**
**Did Sheila want Scott to participate? Looks like the **
**call will be too late for him.**

**Sheila**

- 2. Making Sense of What We Find

**WHO?**

**Notes:**
And one of the task those searaches may is what we call identity resolution
So given an email and a mention to person in that email, u wann disambiguate it, or resolve it to a full name or at least to an email address.

Let’s see an example from an organizational collection.
Let’s say a historian is exploring this collection and found that email.

And there are other specific problems we could work one but we picked one specific and one general

Who is being talked about or mentioned
Resolve “named” reference  NOT “nay” reference

The first question indicates on side of the problem which is : ,and the second indicates/flags the other side of the problem which is content res.
And we work on both problems.

The first is concerned with modeling and resolving the identity of the involved participants
(i.e., who sent email, received email, or were mentioned in email), and the second is concerned
with expanding the email content based on its context, hence helping user to pose queries
that match emails effectively.
-------
By resolving identity, we aim to determine the true referent of a given reference or
mention in the collection.

By resolving content, we seek to efficiently retrieve emails that are on-topic but may not
match the query terms.

## Where to Look for Evidence

**Socially-related Conversations**

- Contextual Space

## Contextual Resolution

- “Sheila”

***social***

***conversational***

***social***

***topical***

***social***

***topical***

***topical***

- “Sheila Tweed”

- “sheila”

- “jsheila@enron.com”

- “sg”

- “Sheila Walton”

- “Sheila”

**Context-Free****Resolution**

***Elsayed, Oard and Namata***
***ACL/HLT 2008***

## Enron Test Collection(s)

| Collection | Emails | Identities | Mention | Candidates |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  |  |  | Queries | Min. | Avg. | Max. |
| Sager | 1,628 | 627 | 51 | 1 | 4 | 11 |
| Shapiro | 974 | 855 | 49 | 1 | 8 | 21 |
| Enron-subset | 54,018 | 27,340 | 78 | 1 | 152 | 489 |
| Enron-all | 248,451 | 123,783 | 78 | 3 | 518 | 1,785 |

**Sager**

**Shapiro**

**Enron-subset**

**Enron-all**

**Notes:**
Sager and Shapiro collections are each one mailbox of the entire collection
Removed cc headers

We evaluate our mention resolution approach using 4 test collections, all of which are
based on the CMU version of the Enron collection. Each of the test collections that we
used was created by selecting a subset of that collection, selecting a set of query-mentions
within emails from that subset, and creating an answer key in which each query-mention is
associated with a single email address.
The first two test collections were created by Minkov et al [32]. These test collections
correspond to two email accounts, “sager-e” (the “Sager” collection) and “shapiro-r” (the
“Shapiro” collection). Minkov et al preprocessed the emails found in those accounts to
remove ”.com” emails not from Enron, emails from certain large mailing lists, forwarded and
quoted portions of each email, and all addresses in the cc header field of the mention-emails.
Their mention-queries and answer keys were generated automatically by identifying name
mentions that correspond uniquely to individuals referenced in the cc header, and eliminating
that cc entry from the header. The ”Sager” test collection includes 62 mention-queries,
of which we used the 51 for which Minkov reported experiment results. The “Shapiro”
collection includes 60 mention-queries, of which we used the same 49 on which Minkov
reported results.
The third test collection, which we call the “Enron-subset” is an extended version of the
test collection created by Diehl at al [16]. Emails from all top-level folders were included
in the collection, but only those that were both sent by and received by at least one email
address of the form <name1>.<name2>@enron.com were retained. A set of 78 querymentions
were manually selected and manually associated with the email address of the
true referent by a graduate student in the Computer Science Department at University of
Maryland10 by using an interactive search system developed specifically to support that
task. The set of query-mentions was limited to those that resolve to an address of the
form <name1>.<name2>@enron.com. Names found in salutation or signature lines or that
exactly match <name1> or <name2> of any of the email participants were not selected as
query-mentions. Our set of 78 query-mentions include the 54 used by Diehl et al. and an
additional 24 created for our experiments using the same process.
For our fourth test collection (“Enron-all”), we used the same 78 mention-queries and
the answer key from the Enron-subset collection, but we used the full CMU version of the
Enron collection (with duplicates removed). We use this collection to assess the scalability
of our techniques. It is important to recognize, however, that all four of our collections focus
the mention-queries on Enron employees, for which there is likely to be a substantial amount
of evidence in Enron email. Extending the Enron-all collection to include mention-queries
for which less evidence is available will be a focus for future work as proposed in section
3.9.4.
Some descriptive statistics for each test collection are shown in Table 3.4.11 The number
of emails is the total number after duplicate removal and the number of threads includes
trivial (single-email) threads. Different subsets yield different sets of identity models, which
in turn can yield different candidate lists for the same query-mention. The Sager and
Shapiro test collections are typical of personal collections, while Enron-subset and Enron-all
represent organizational collections. These two types of collections differ markedly in the
number of known identities and the candidate list sizes. Table 3.4 shows the total number
of identity models after automatic construction using only information from within that
collection. The table also characterizes the candidate list size, averaged over that collection’s
mention-queries and as a range. The smaller test collections naturally tend to have smaller
candidate lists. Indeed, 14 of 51 mention-queries in Sager and 11 of 59 mention-queries in
Shapiro have only a single candidate. Most mention-queries in the Enron-all collection, by
contrast, have more than 200 candidates.

## Which Context is the best?

**Sager**

**Shapiro**

**Enron-sub**

**Enron-all**

**Notes:**
Baseline is high in the small collections and very low in the large collections
Social context is always the best
Drop in both social and topical in large collection
Topical is hard to get it right in large collections (drop in the large) – harder problem 
Conv improves . One explanation is that more email that are pruned??

## 3. Seeing What Was Never There

## For Further Information    

*Sedona Best Practices Commentary on the Use of Search and Information Retrieval Methods in E-Discovery*, _[http://www.thesedonaconference.org](http://www.cs.ucl.ac.uk/staff/S.Attfield/desi/)_
- Second Workshop on Discovery of Electronically Stored Information (DESI), _[http://www.cs.ucl.ac.uk/staff/S.Attfield/desi/](http://www.cs.ucl.ac.uk/staff/S.Attfield/desi/)_
- Posters and demos by:
- Tamer Elsayed
- Lidan Wang
- Doug Oard