Autocomplete with 5 million+ proper names

The Library of the Technical University Delft (TUDelft) added an autocomplete function on their Discover site using Meresco. It suggests search terms using the full corpus of all their databases.  Also, it suggests more specific terms when users use fields in their query.

Proper names

TUDelfts’ databases contain many technical terms and other proper names such as structured chemical names.  Discover uses these to suggest search terms instead of history from users’ queries.  The example below shows a user typing tri and the autocomplete suggesting chemical names such as tri-0-acetyl and triacyglycerol from over 5.000.000 available terms.

Faceted Search integration

The autocomplete is fully integrated with the facets in Discover. As a result it is able to show exactly how many results a user can expect for each suggested term given the current selection of facets and of course it does not suggests terms that yield no results.

Suggestions for Fields

As an option, users can use fields to limit the range for specific keywords.  For example the query author=johnson will search for johnson only in the field author.  The search box automatically detects fields and applies the proper suggestions for that field.  The example below show a user searching for author=nahu with the search box suggesting 3 different spelling variants together with the amount of results to expect.

Implementation

Discover’s autocomplete has been implemented with Meresco’s autocomplete and facetting.  The autocomplete is capable of handling millions of terms under a high userload due to it implementation of a Burst Trie which is integrated with the facet index. On the client side it uses JQuery and CSS to present the autocomplete search box.

Discover – TU Delft

Discover is een mooi resultaat van een goede samenwerking met deskundige ontwikkelaars.

Discover is de zoekmachine achter de inhoud van de bibliotheek van TU Delft. Het bibliotheekmateriaal was verspreid over verschillende databases. We hebben een systeem ontwikkeld die collecties kan integreren. Een portal met een aantal innovatieve features rondom het zoeken en leggen van koppelingen naar de achterliggende datasystemen. Het project Discover stond bol van de uitdagingen. Veel features waren volledig nieuw.

Did you mean
Via een ‘Did you mean’-functie in je zoekmachine kun je de gebruiker een zoeksuggestie doen: “Bedoelde je soms dit…”. Wij hadden dat nog niet eerder gemaakt en dergelijke functies waren destijds nog niet gebruikelijk. Het werkt echter totaal anders dan Google. Google doet suggesties door wat anderen hebben ingetypt, dus wat de meerderheid vindt is goed. Onze ‘Did you mean’-functie baseert zich echter op gegevens die zich in databases van de TU bevinden. Die data gebruiken we om goede suggesties te doen. Dat betekende zorgvuldig algoritmes tunen, inhoudelijk kijken wat er in de collecties zat en wat de verwachtingen waren. Je wilt uiteraard suggesties doen die echt kloppen.

Autocomplete
Voor de autocomplete feature heb je een specifieke datastructuur nodig, TRIE, maar die structuren zijn duur en ze kosten veel geheugen. De TRIE datastructuur is al zo oud als computers zelf zijn. Ondanks die ouderdom, zijn er nog steeds vakmensen mee aan het werk om het systeem te verbeteren. Na 30 jaar gebruik, kwam er alsnog een doorbraak, een nieuwe TRIE die minder geheugen gebruikt, het is heel snel voor alle gekke woorden die je er instopt. Er was nog geen robuuste implementatie, dus dat hebben we zelf gedaan.

Facetten, maar dan anders
We hebben facetten gekoppeld aan andere algoritmes dan gebruikelijk. Termen worden meestal geteld, maar de meest voorkomende term levert soms maar weinig inperking op de hoeveelheid zoekresultaten. In samenwerking met het NWO CATCH Project, hebben we discriminerende facetten ontwikkeld die gebruik maken van algoritmes zoals information gain. Je geeft een machine een aantal documenten en het systeem bepaalt zelf wat daarin de meest onderscheidende zoektermen zijn. Discover doet dit on-the-fly en presenteert dit als facet.

Gebruikersonderzoek
Karin, de projectleidster, had een team van vakmensen samengesteld. Twee dames deden een gebruikersonderzoek en Karin vertaalde dat naar concrete features voor Discover. Dat was geweldig werken voor ons. Je voelt je zeer nuttig omdat je echt bezig bent voor de eindgebruiker. Je stelt mensen voorop, in plaats van een systeem.

Gedurfde stap
Er was geen alternatief voor Discover en ook was er geen uitgebreid plan. Ze leken te denken: we hebben een budget en we gaan het doen. Een managementlaag wil soms zekerheden en dikwijls denkt men dat te bereiken door veel papierwerk. In de praktijk zie je dat mensen op een lager niveau in de organisatie vervolgens bergen papier moeten produceren. Het hele proces wordt groter, duurder en langzamer. Bij Discover was het plan in hoofdlijnen bekend. Ze wisten goed wat ze wilden, maar hebben de verleiding weerstaan om dat tot op detailniveau uit te werken. Het projectteam stond open voor suggesties. Op die manier was er veel meer ruimte om samen creatief te zijn en tot de beste oplossing te komen.

Looptijd
Vanaf mei 2008