Summary

  • Author initials appeared in about 20% of queries to CiteSeer's demonstration database, giving common surnames a useful companion.
  • A 1999 test brought mean time for initial-bearing queries from 1.91 seconds to 0.26 seconds by caching positions and looking them up by document.

A surname can fill a reading list. An initial can make it useful. CiteSeer, the early Web index of scientific papers, discovered that this small service came with an irritating bill: queries containing author initials were much slower than ordinary searches. The alphabet was holding up the library.

The problem appears in a 1999 project paper by Steve Lawrence, Kurt Bollacker and C. Lee Giles at NEC Research Institute. Its examples are wonderfully modest: m jordan and m i jordan. Nobody was asking the machine to understand a whole discipline. They wanted a letter near a surname.

The nuisance was part of the name

Search indexes often omit very common words to save work. CiteSeer kept them. A citation might give only a researcher's surname and initials; throwing out the little tokens would discard part of the reader's evidence. A common surname made that evidence especially valuable. Phrase and proximity searches let the reader specify how the pieces should sit together.

By then, CiteSeer was already dealing with scholarly publishing's untidy handwriting in machine-readable form. The team's 1998 account described extracting references from papers on the Web, grouping differently written citations to the same work and connecting papers through those references. A bibliography was becoming a route through the literature.

Getting there involved unglamorous housekeeping. The June 1999 account in Computer describes converting PostScript and PDF into text, finding reference lists and separating citations using their tags, spacing or indentation. Some PostScript documents even needed their pages put back into reading order. The future of the digital library included sorting out files that arrived backwards.

Initials created a different difficulty. A single letter occurred in a great many citations. Checking whether it appeared near the requested surname could involve searching a long list of documents and positions. In the demonstration database, queries with author initials accounted for about 20% of requests. This was a recurring piece of readers' work, large enough to spoil the service if treated as an eccentric edge case.

Give the letter a drawer

The 1999 CIKM paper reports a test database of about 200,000 documents containing more than 2.5 million citations. The authors randomly selected 25 queries without initials and 25 with them. Mean execution time was 0.28 seconds for the former and 1.91 seconds for the latter. The paper rounded the gap to sevenfold.

The repair retained the query. CiteSeer cached lists of word positions and built a lookup table for each initial, keyed by document identifier. Once a candidate document was in view, the system could reach the initial's positions there without ordinarily inspecting the whole document list. The expensive little letter got its own well-organised drawer.

The initial-bearing group then averaged 0.26 seconds. The table captures a useful reversal: the troublesome group became slightly faster than the comparison group. Those are results from fifty selected queries in the project's historical test, with a mechanism precise enough to explain why the change helped.

CiteSeer also gave readers ways to inspect what the machinery had assembled. A result's Context link showed the surrounding citation passage; Check exposed the individual citation strings grouped as one paper. A researcher could inspect both the use of a paper and the evidence behind the grouping. The initial narrowed the hunt. The surviving references gave the reader something to check when the hunt ended.