Challenges for HathiTrust full-text search

[1]  Providing language-specific processing on this scale is not practical.  Since we index all the languages in one index, we have to be careful not to implement features that would improve searching for English language materials that would hurt searching in other languages.  Because stop words in one language are content words in another language, we needed to implement an alternative to using stop words for dealing efficiently with queries containing common words. We ported the Nutch “CommonGrams” approach to Solr and contributed it to the Solr community.  See: http://www.hathitrust.org/blogs/large-scale-search/slow-queries-and-common-words-part-2

The content covers a wide range of time-periods and fields of learning so even for one language the vocabulary includes both historical word usage and spelling variants, and domain-specific terms.  This makes the use of dictionary-based natural language processing methods and standard stemming or synonym lists impractical.

[2] The full-text content consists of OCR of varying quality which has numerous adverse effects on retrieval and relevance ranking. The generally accepted information retrieval techniques for dealing with OCR errors, do not scale to large collections or to multilingual collections. Determining what approaches might work with collections like the HathiTrust collection is an open problem.

[3]  The unit of ingest is a bound volume; a volume might consist of a number of journal issues bound together, or two or more monographs bound together.  Because metadata indicating where chapters or articles begin and end is not very accurate we can’t do specific indexing or ranking on the chapter or article level.  Note that due to the size of the corpus and the lack of available ground truth, estimating the extent of errors in metadata indicating chapter or article beginnings and endings would be a research project in itself.

[4] One of the reasons for spreading a large index over a large number of machines is to be able to get the whole index either into memory  (as Google does) or onto Solid State Drives.  The other reason is to increase the available CPU cycles.  Sources:  Personal conversations with vendors using HathiTrust index and the following:  "Making the Interent Archive's full text search faster" ,  http://2010.lucene-eurocon.org/slides/Scaling-Solr-to-3Billion-Documents_Jason-Rutherglen.pdf.

Etsy has 20 million items and uses 2 clusters of 20 machines each.  CareerBuilder has about 1 billion documents indexed in thousands of indexes. 

[5] HathiTrust actually runs a full copy of the index at two sites, one in Michigan and one in Indiana.  Each site serves their copy of the index from 6 servers.  Due to our relatively low query load, budget concerns, and concerns about system administration resources and power use, early in the development process, we decided to go with a small number of high-end machines rather than a large number of commodity machines.

[6] We receive between ½ and 2 queries per second.  Average response time is under a second.  Our performance goals are to keep response time for all but the 10% slowest queries less than 10 seconds and response times for  the 1% slowest queries less than 30 seconds.  Commercial services serve queries in the range of hundreds to hundreds of thousands of queries per second with response times measured in milliseconds.

[7] For example, we would like to add a feature that ranks documents where all the query terms in a query occur on the same page higher than documents where some of the query words are on one page and the rest are on another page.  However, on current hardware, addition of this feature would cause unacceptable response time.   As another example,  a commonly used approach to add features to Solr is to copy the contents of a field to a new field for special processing.  Each use of this approach for the OCR field would double the size of the 12TB index.  Providing both case-sensitive and case insensitive search is one feature normally implemented using this approach.  Doubling the size of the index has performance implications as well as cost implications.  The implementation of Solr’s “more-like-this” feature would also require a significant increase in index size.  See   HathiTrust Large Scale Search: Scalability meets Usability. Code4Lib 2012. (February 2012) for more examples of features affected by scalability issues.  We also have had to radically change the default indexing settings to be able to index 16TB of OCR in a reasonable time.  See: http://www.hathitrust.org/blogs/large-scale-search/forty-days-and-forty-nights-re-indexing-7-million-books-part-1

[8] For example early tests of the Solr/Lucene wildcard feature indicated that  wildcard searches could take up to ten minutes and have significant adverse effects on every other query that hit Solr during that 10 minutes.  Similar problems exist for Solr’s fuzzy queries and other features that use multi-term queries.  We plan to test whether the new FST based indexing improves performance  to the point that we can enable these features.

[9] See:  http://www.hathitrust.org/blogs/large-scale-search/too-many-words , LUCENE-2257, http://www.hathitrust.org/blogs/large-scale-search/too-many-words-again, LUCENE-4635, LUCENE-6192, and Mike McCandless’ January 21,2015 Google plus post: https://plus.google.com/+MichaelMcCandless/posts/RQiF1J2XAzV

[10] In addition to blog posts and presentations, contributions include our early work on performance benchmarking: (Large-Scale Search Benchmarking. (December 2008) - Tom Burton-West, Jeremy York.), work on CommonGrams ( https://issues.apache.org/jira/browse/SOLR-908), contribution of a tool to help determine common words in a Solr/Lucene index (https://issues.apache.org/jira/browse/LUCENE-2393), work to improve CJK processing (LUCENE-2906, SOLR-3589), and implementation of an improvement to the BM25 ranking algorithm to deal with long documents (https://issues.apache.org/jira/browse/LUCENE-5175.)  Our INEX paper (Burton-West 2012) was used by one of the INEX Book Track participants, professor Michael Preminger, as an example of “practice based research” in a seminar he was teaching.

[11] Our early performance and scalability tests confirmed that we would need to modify Solr in order to scale up Solr to 5 million volumes.  Our tests showed that without modification queries containing common words would have unacceptable response times (1-2 minutes.)  We contributed the Solr CommonGrams code which solved our problem and is used by a large number of organizations using Solr.  We continue to test Solr features for scalability and performance.   Some of our more recent tests were tests of the performance of Solr faceting and grouping when we indexed one million documents at a page level (300 million pages) and grouped by document.

[12] Facets and advanced search options are the present mechanisms for interactively refining queries. Both of these could benefit from usability studies.  We also plan to implement “relevant facets”.  See  Burton-West(2012) HathiTrust Large Scale Search: Scalability meets Usability for more details.

[13] We have several examples of queries where very short documents are obviously ranked too high.  We also argue that Lucene’s default algorithm has the same bias towards short documents that was discovered in the Vector Space algorithm that Lucene’s default algorithm is based on.  See: http://www.hathitrust.org/blogs/large-scale-search/practical-relevance-ranking-11-million-books-part-3-document-length-normali

[14] See: https://www.hathitrust.org/blogs/large-scale-search/practical-relevance-ranking-11-million-books-part-2-document-length-and-rel.  Extensive investigation of the INEX Book Track test collections has revealed that the INEX collections are not appropriate for relevance testing of HathiTrust.  The 2007 queries are underspecified and both the 2007 and subsequent 2008-2010 collections have  issues with relevant unjudged documents.  See Kazai (2010) for discussion of issues with collecting enough relevance judgments for the INEX collection.

[15] We believe we have found a “good-enough” approach to a ranking algorithm that would solve this problem and significantly improve relevance ranking for HathiTrust search.  Our proposed approach is based on an approach suggested by Bendersky and Kurland (2010) for ranking documents based on relevance evidence from the documents constituent passages. The approach involves breaking HathiTrust volumes into sub-documents such as chapters, groups of pages, or pages, and using Solr’s grouping facility to rank volumes/documents based on a function of the scores of the sub-documents.  More details will be available in a forthcoming blog post

[16] We also suspect that the optimum weight depends on query intent.  In particular known items searches would probably benefit more from higher weights for the MARC metadata.  We hope to be able to gather information on known-item searches and ranking when we implement click-logging.

[17] Techniques such as ngrams or fuzzy matching will match too many volumes and will match words in other languages as well as OCR errors.  Techniques based on error correction or language models are not scalable to a collection of this size or a multilingual collection that spans multiple technical domains as well as multiple time periods.

[18] For example Arabic, Hebrew, Chinese and Japanese.

[19] In general, the same language-specific processing must be done on both the query and the document in order for good retrieval.   While language identification of long documents is feasible, language identification of queries is an open problem in the research literature.  Experiments with several state-of-the-art language identifier programs have confirmed that accurate identification of the language for HathiTrust queries is an open problem.  Even if we could solve the problem of identifying both query and document language accurately, indexing each of 400 languages in a separate index is not feasible and dealing with multilingual queries or queries for proper names would require combining searches and scores across indexes.  See Grainger and Potter (2014 Chapter 14) for an overview of current best practices for multi-lingual searching with Solr.  We currently use the ICUTokenizer and ICU filters which were designed by a group of multilingual unicode experts to work pretty well with a wide variety of languages and scripts.  We continue to investigate potential approaches that might scale to improve searching for perhaps the top 10 or 20 languages as well as any approaches that improve searching for a particular language that will not adversely impact searching in other languages.

[20] Character n-grams such as those used by McNamee and Mayfield (2009) take up to 6 times the space of regular word-based indexing.  Such an approach would require an index in excess of 60 TB for the HathiTrust index.  The truncation approach used by McNamee and Mayfield is unlikely to work with the long documents in the HathiTrust corpus due to problems with very high recall, and would not be applicable to a number of languages in HathiTrust including Arabic.

[21] Assuming the issues with identifying the language of queries were solved, the stemming and synonym features provided with Solr would not work well due to retrieval of inappropriate documents caused by large numbers of false matches.  These matches are due to overstemming  (i.e. search for “marinated vegatables” retrieves documents for “marine vegetation” because both phrases stem to “”marin vegat” ) or to synonyms that match the wrong word sense.  Techniques used in large web search engines such as context-sensitive stemming would be more appropriate(Peng et al. 2007).  Issues to be investigated include whether the amount of feature engineering and training for the machine learning algorithms to implement context-sensitive stemming would require more than the resources currently available for working on HathiTrust search and whether appropriate techniques can be found to deal with data sparsity.  It is an open question whether the size of the query and click logs available from HathiTrust search would be sufficient to train context-sensitive algorithms. ( Blog post in progress. )

[22] See http://www.hathitrust.org/blogs/large-scale-search/multilingual-issues-part-1-word-segmentation

[23] An additional issue not addressed here is that HathiTrust search consists of four different applications (with indexes at different scales).  These applications must appear to the user to work together seamlessly.   There are many complex UX issues involved .   The applications are:

1. HathiTrust full-text search
2. HathiTrust collection builder search
3. HathiTrust “search within a book”
4. HathiTrust catalog.

[24] In general we try to leverage features already available in the open-source Solr/Lucene software.  When necessary we work with others to make contributions to the software (for example our work with CommonGrams).  We worked extensively with Lucene/Solr committer Robert Muir, and Naomi Dushay at Stanford on CJK issues.  See blog post cited above, LUCENE-2906, SOLR-3589, and http://discovery-grindstone.blogspot.com/2014/01/searching-in-solr-analyzing-results-and.html

[25] Many of the Solr committers, in particular Robert Muir, Mike McCandless, Chris Hostetter, Andrzej Bialecki and Erik Hatcher have been particularly helpful.  Trey Grainger, Gheorghe Muresan , and other Solr/Lucene users at the Lucene Revolution conferences have also been helpful as have  Marijin Koolen and other participants at the INEX Book track. Thomas Emerson, an expert on CJK issues, now with EBSCO, provided helpful comments on our approach to CJK issues.  The IR evaluation team at the Royal Melbourne Institute of Technology, Professors Mark Sanderson and Falk Scholar and Research Fellow Timothy Jones gave helpful feedback on plans for click logging and the creation of a test collection.  Ian Soborof of the Retrieval Group at NIST and James Allan of the Center for Intelligent Information Retrieval, provided helpful advice on determining user tasks for creating a test collection.

[26] There is a large literature on searching book metadata using library catalogs, but not much on searching the full-text of books.  See Willis and Efron (2013) for a discussion of the book search literature.  Professor James Allan of CIIR confirmed that full-text book search is under-researched.(Personal conversation at SIGIR July 2018.)

[27] Results of tests on one collection can not be easily extrapolated to apply to other collections with different characteristics such as different types of materials, different sizes of the collection, or where the user task is different.  See Jones et al. 2014.

[28] We have implemented performance monitoring and testing.  We are currently doing A/B testing using interleaving in production.  See Chapelle et.al. 2012 for details on interleaving. More details on interleaving forthcoming in a future blog post.

[29]   We investigated various methods for low-cost creation of test collections, including crowdsourcing. (See Carterette et.al 2010 and Kazai 2010.) .  We also investigated A/B testing using interleaving (Chapele et. al. 2012).  See Ingersoll (2009) for an overview of various approaches used primarily in e-commerce.  I was particularly influenced by conversations with Ivan Provalov about his experience at Cengage http://www.slideshare.net/lucenerevolution/provalov-cengage-relevancecengageenglishnonenglish1eurocon2011

).  Ivan started by tuning algorithms on a TREC collection that was similar to Cengage’s content and then went on to develop a relevance testing framework to further tune the algorithms.  Conversations in sessions on relevance ranking and user testing at various Lucene/Solr and code4lib sessions through the years have been helpful.  Also helpful have been  conversations with presenters on relevance ranking issues at code4lib.  Some notable presentations are: the presentations from Tamar Sadeh of Ex Libris  (http://code4lib.org/files/relevance%20ranking%20Code4Lib%20f.pptx),  Raman Chandrsekar and Susan Price of Serials Solutions http://code4lib.org/conference/2013/chandrasekar-diamond, http://journal.code4lib.org/articles/8693 and Mike Schultz (formerly Summon architect) http://code4lib.org/files/code4libSchultz.pptx