How 1000 Apps are using the FAROO Search API

 
During the last 9 months more than 1000 companies and developers subscribed to our API, with more than 100 new applications every month.

API subscriptions

Today we want to share what are the typical use cases for our search API:

commercial_use_by_segment

commercial_use_by_region

academic_use_by_region

An interesting discovery is the fact that our search API is mainly used to data mine the big data of the web, instead of plain web search.

We turn the whole web into a giant database which is queried and analyzed by AI services, Data mining and Business intelligence applications. Big data becomes accessible and can be queried within milliseconds. Apps save the lead time for crawling the vast amount of pages themselves.

FAROO introduces API keys

keyWith 1 million free queries per months we offer a really ample API rate limit. Three orders of magnitude of what the incumbents provide.

But some users still use multiple servers, fake user agents & referers to circumvent the already generous rate limit. Unfortunately it seems that abuse is proportional to freedom and goodwill. This is not only unfair, but also impacts reliability, performance and long term perspective of our free service for all users.

While the API stays free, from 1. July 2013 we are introducing API keys for better service protection. The new API key registration adds an extra step before using the API, but it offers also some benefits:

  • Better prevention of API abuse, ensuring a reliable service for everyone.
  • We can inform you whenever the API is about to change.
  • We can inform you when you are exceeding the rate limit, instead of blocking.
  • We can inform you about syntax or encoding problems of your query.
  • As reference for support requests.

If your application is using the FAROO API, and you do not have an API key yet, please register as soon as possible to ensure an uninterrupted service.

We hope you continue to enjoy our API and build the search you want!

Leistungsschutzrecht aus Sicht einer Suchmaschine

Lex Google from a search engines perspective – a German law threatening the internet as we know it.

Go directly to the robots.txt extension proposal ‘Freedom of Citation License v1.0″
disarm
Worum gehts

Leistungsschutzrecht für Presseverlage durch das Achte Gesetz zur Änderung des Urheberrechtsgesetzes

Hier die entscheidenden Passagen:

§ 87f (1) Der Hersteller eines Presseerzeugnisses (Presseverleger) hat das ausschließliche Recht, das Presseerzeugnis oder Teile hiervon zu gewerblichen Zwecken öffentlich zugänglich zu machen, es sei denn, es handelt sich um einzelne Wörter oder kleinste Textausschnitte. Ist das Presseerzeugnis in einem Unternehmen hergestellt worden, so gilt der Inhaber des Unternehmens als Hersteller.

§ 87g (2) Das Recht erlischt ein Jahr nach der Veröffentlichung des Presseerzeugnisses.

§ 87g (4) Zulässig ist die öffentliche Zugänglichmachung von Presseerzeugnissen oder Teilen hiervon, soweit sie nicht durch gewerbliche Anbieter von
Suchmaschinen oder gewerbliche Anbieter von Diensten erfolgt, die Inhalte entsprechend aufbereiten.

Dieses Gesetz tritt am … [einsetzen: erster Tag des dritten auf die Verkündung im Bundesgesetzblatt folgenden Kalendermonats] in Kraft.

Als Begründung für die Ausnahme einzelner Wörter oder kleinster Textausschnitte von der Vergütungspflicht (§ 87f – fett markiert) wurde das Grundrecht auf Information genannt und darauf verwiesen, dass der Bundesgerichtshof 2011 entschieden hatte, dass Google „Thumbnails“ genannte Vorschaubilder in Suchergebnissen zeigen darf.

Update Juni 2014
Trotzdem klagt die VG Media gegen Google auf Zahlungen nach dem Leistungschutzrecht. Laut Heise werden Forderungen auch gegenüber der Deutsche Telekom, Microsoft, Yahoo sowie 1&1 erhoben. An der VG Media sind die Verlage Springer (Bild, Welt), Burda (Focus), Funke (WAZ, Hamburger Abendblatt), Madsack (Hannoversche Allgemeine, Leipziger Volkszeitung), M. DuMont Schauberg (Kölner Stadtanzeiger, Express) und Aschendorff (Westfälische Nachrichten) beteiligt.
Dieser zu erwartende Rechtsstreit ist Folge der von uns kritisierten Unklarheit des Gesetzes bezüglich der vergütungsfreien Anzahl von Worten/Zeichen.

Unklarheit mit Methode

Ein Gesetz sollte Rechtssicherheit schaffen und nicht Unsicherheit und Grauzonen.
Rahmenbedingungen müssen klar definiert sein, und Angebote die darunter fallen gekennzeichnet werden, und zwar maschinenlesbar:

• Was ist ein Presseerzeugnis und wer ist damit ein Presseverleger (zählen Blogs dazu? Wenn ja, dann lehnt die Mehrheit der Presseverleger das Gesetz zu ihrem vermeintlichen Schutz ab, wenn nein weshalb wird dann eine Minderheit privilegiert und das gesamte Internet als Geisel zur Durchsetzung ihrer Interessen genommen)
• Welche Angebote stammen von einem Presseverleger und fallen damit unter das Gesetz, wenn deren Kennzeichnung nicht vorgeschrieben ist
• Wie viele Worte/Zeichen sind zulässig (ohne diese Angabe ist alles was länger als zwei Worte ist Russisch Roulette)
• Fallen Worte in einem Link (sprechende URL) auch unter die Beschränkung? Eventuell wird dadurch eine Verlinkung unmöglich.
• Dürfen Sprechende URL auch angezeigt werden, oder müssen sie vor dem Nutzer verborgen werden (der weiß dann nicht auf was er klickt)
• Werden Worte in einem Link (Sprechende URL) auch gezählt, wenn Titel und sprechende URL identisch sind, wird doppelt gezählt?
• Wann ist ein Jahr vorbei (wie erfährt man das Veröffentlichungsdatum, wenn dessen Angabe nicht vorgeschrieben ist)
• Was ist gewerbliche Nutzung? Ist der Blog eines Unternehmens eine solche, oder ein Blog mit Werbung? Oder definiert sich gewerbliche Nutzung über eine große Anzahl von Nutzern oder veröffentlichten Zitaten (analog Filesharing Urteilen)

Eine zentrale Clearingstelle sollte Angaben über Veröffentlichungsdatum und ob eine Seite dem Leistungsschutzrecht unterliegt manipulationssicher verwalten, um Abmahnfallen zu vermeiden.

Die Mär vom Parasiten

Die offizielle Begründung: „Der Presseverleger wird so vor der systematischen Nutzung seiner verlegerischen Leistung durch gewerbliche Anbieter von Suchmaschinen und von gewerblichen Diensten, die Inhalte entsprechend aufbereiten, geschützt, die ihr spezifisches Geschäftsmodell gerade auf diese Nutzung ausgerichtet haben.“

Nun, Suchmaschinen haben ihr Geschäftsmodell nicht auf die systematische Nutzung verlegerischer Leistung aufgebaut. Suchmaschinen gab es lange bevor die Presseverleger das Internet für sich entdeckt haben. Sie erbringen eine eigenständige Leistung der Indizierung von Informationen um deren quellenübergreifende Auffindbarkeit sicherzustellen. Die Mehrzahl der Suchergebnisse stammt eben nicht von den Presseverlegern, sondern von Blogs, Foren, Unternehmenswebseiten, Wikipedia, Quora, Stackoverflow, Linkedin, Amazon, Social Networks, Open Source Projekten, akademische Seiten, privaten Homepages¸ Vereinen, Schulen, Städten und Gemeinden um nur einige zu nennen.

Warum ist Google so erfolgreich? Weil es sich auf Kosten der Presseverleger bereichert? Nein, weil Millionen von Firmen so sehr von einer Auflistung in den Suchergebnissen profitieren, das sie bereit sind dafür viel Geld zu bezahlen. Sowohl für Adwords um in der Werbung aufzutauchen als auch für SEO, um in den organischen Ergebnissen vordere Plätze einzunehmen. Auch die Presseverleger profitieren so sehr von Google, den zusätzlichen Besuchern und Werbeerlösen, dass sie bisher die robots.txt nicht geändert haben, um Google an der „systematischen Nutzung ihrer verlegerischen Leistung“ zu hindern.

Ein alternatives Geschäftsmodell von Suchmaschinen ist übrigens „Paid Inclusion“, also die bezahlte Aufnahme einer Webseite in den Index einer Suchmaschine. Ein Geschäftsmodell das Suchmaschinen vor der systematischen Nutzung ihres Traffics durch gewerbliche Presseverleger schützt, die ihr spezifisches Geschäftsmodell gerade auf diese Nutzung ausgerichtet haben ;-)

Suchmaschinen und Aggregatoren sind nicht parasitär, sondern von allen Bürgern in einer Informationsgesellschaft dringend benötigte Tools um die Informationsflut beherrschen zu können, Vielfalt zu sichern und Bias zu vermeiden.

Presseverleger geben Geld aus um Content zu erstellen. Ein großer Teil der Besucher / des Umsatzes kommen über Suchmaschinen (Quelle: Verband Deutscher Zeitschriftenverleger)

Suchmaschinen geben Geld aus um Content durchsuchbar zu machen. Nur ein kleiner Teil der Suchergebnisse / des Umsatzes kommen von Presseverlegern.

Es gibt also eine Symbiose, bei der die Presseverleger von Suchmaschinen deutlich mehr profitieren als umgekehrt:
• wenn der Presseverleger an den Umsätzen der Suchmaschinen beteiligt werden will, müsste er die Suchmaschinen auch an seinen Umsätzen beteiligen
• wenn ein Presseverleger die Suchmaschinen an seinen Kosten beteiligen will, müssten die Suchmaschinen ihn auch an ihren Kosten beteiligen.
• wenn der Presseverleger eine Gebühr für Zitate erhebt, müsste er eine für das Listing seiner Seiten in der Suchmaschine bezahlen.

Wo bleibt das Leistungsschutzrecht für Suchmaschinen?

Entwicklung und Betrieb von Suchmaschinen kosten Geld. Viel Geld. Suchmaschinen sind für die Gesellschaft mindestens so systemrelevant wie Presseverleger, um Transparenz und Vielfalt von Informationen und die Auffindbarkeit vorhandenen Wissens zu sichern.
Warum sollen Presseverleger von den Investitionen der Suchmaschinen kostenlos profitieren, die Suchmaschinen von denen der Presseverleger aber nicht?
Nun gibt es in Deutschland mehr Presseverleger als Suchmaschinen. Werden deshalb Gesetze für Presseverleger und nicht für Suchmaschinen oder gar den Bürger gemacht?

Der Kuckuck im fremden Netz.

Das Internet wurde nicht von den Presseverlegern erfunden. Es wurde erfolgreich durch Offenheit, Austausch und Verlinkung. Den Walled-Garden Gegenentwurf Compuserve kennt heute kaum jemand mehr. Suchmaschinen gab es lange bevor die Presseverleger das Internet für sich entdeckt haben.
An den vielen Besuchern im Internet im Allgemeinen, und an den durch die Suchmaschinen generierten im Speziellen ist man natürlich interessiert, aber die Offenheit die dazu geführt hat will man beseitigen. Fail.

Der Effekt

Alle verlieren. Presseverleger, Suchmaschinen und vor allen die Nutzer.

Es ist kaum zu erwarten das die Suchmaschinen auf Basis eines einseitigen Gesetzes jetzt die Wirtschaftsförderung für Verlage und überholte Geschäftsmodelle übernehmen werden.

Möglicherweise werden jedoch Publikationen deutscher Presseverleger aus dem Index der Suchmaschinen verschwinden, und damit weiter an Bedeutung verlieren. Andererseits ist dies eine Chance für non-mainstream Medien und internationale Player, die Filter Bubble zu durchbrechen und die Informationsvielfalt zu stärken.

Oder Suchmaschinen ziehen sich aus Deutschland zurück, und betreiben den Service zukünftig aus Ländern mit liberaler Gesetzgebung. Wird dann der Zugang zu Google aus Deutschland blockiert wie in China, Nord Korea oder Iran? Endet Freiheit da, wo sie mit Lobbyinteressen kollidiert?

Durch deutsche Politik wird so Suchmaschinen-Innovation aus Deutschland behindert, und damit die Vormachtstellung von US Diensten in Deutschland zementiert.
Startups werden die Aufbürdung zusätzlicher Kosten und das finanzielle Risiko durch Abmahnungen vermeiden und Länder mit freiem Internet wählen. Wenn schon kein Hightech, dann wenigstens Wirtschaftsförderung für Anwälte, Gerichte und Abmahnindustrie.

Die Bundeskanzlerin eröffnet die CeBIT unter dem Motto “Shareconomy”, nachdem gerade ein Gesetz beschlossen wurde dass das Gegenteil bewirkt.

Das Ziel

Neben den ohnehin erheblichen Entwicklungs- und Betriebskosten sollen Suchmaschinen zukünftig auch noch dafür bezahlen, dass sie den Content der Presseverleger indizieren, ihnen Besucher zuführen, und damit deren Werbeumsätze erhöhen.

In einer Marktwirtschaft würden die Suchmaschinen dies zukünftig nur noch für den Großteil der Inhalte tun, die das Leistungsschutzrecht nicht betrifft (Blogs, Foren, Unternehmenswebseiten, Wikipedia, Amazon, Social Networks, Open Source, akademische Seiten, private Homepages¸ Vereine, Schulen, Städte und Gemeinden etc. ).
Die Verlagsangebote würden aus den Suchergebnissen verschwinden, und durch freie Inhalte ersetzt werden.

Die Schwammigkeit des Gesetzes führt jedoch zu Rechtsunsicherheit, die verhindert vom Gesetz betroffene Inhalte eindeutig zu identifizieren und auszuschließen.
Diese Unsicherheit zwingt die Suchmaschinen entweder zur vollständigen Aufgabe, macht sie zum permanenten Ziel der Abmahnindustrie, oder zwingt sie eben doch eine Art Schutzgebühr zu zahlen, selbst um unbehelligt auch nur den Großteil der vom Gesetz nicht berührten (aber als solche nicht identifizierbaren) Inhalte zu indizieren.

Natürlich sollte jeder das Verfügungsrecht über seine Inhalte haben. Dazu gibt es seit vielen Jahren die robots.txt, die von allen großen Suchmaschinen respektiert wird.
Die Presseverleger die sich gegen die kostenlose Nutzung ihrer Inhalte sträuben, haben also ein einfaches Mittel dieses zu verhindern, ganz ohne Gesetz. Sie setzen es jedoch nicht ein, da sie sich bewusst sind in welchem Maße sie von den Suchmaschinen profitieren.
Stattdessen nutzt diese kleine Minderheit der Inhaltsanbieter ihren Einfluss auf Politik und Gesetzgebung, um zusätzlich zum Besucherstrom auch noch einen Revenuestream von den Suchmaschinen zu erzwingen. Kollateralschäden, die die Grundfesten des Internets erschüttern werden dabei billigend in Kauf genommen. Im Ergebnis leiden alle User und Inhaltsanbieter unter der Beschränkung aller Suchergebnisse auf den Titel.

Das dies nicht nur die einseitige Sichtweise einer betroffen Suchmaschine ist zeigen die folgenden Pressestimmen:

Die Tageszeitung Grafschafter Nachrichten schreibt, im Streit mit Google “gehe es im Kern darum, dass der amerikanische Konzern ein Geschäftsmodell gefunden habe, das den deutschen Verlagen bislang fehle. Und anstatt sich selbst kreativ und mutig auf die gewaltigen Herausforderungen einzustellen, die der Medienwandel mit sich bringe, machten es sich viele Verlage und ihr Verband allzu leicht, indem sie sich zurücklehnen, die Hand aufhalten und vom Erfolg anderer profitieren wollen” .

Die ZEIT ONLINE schreibt “Um dieses Verbot [Presseerzeugnis oder Teile hiervon zu gewerblichen Zwecken öffentlich zugänglich zu machen] geht es den Verlagen gar nicht. Sie wollen ein anderes. Denn Verlage machen ihre Artikel und Geschichten im Internet bewusst jedem zugänglich und verdienen damit Geld. Allerdings gibt es jemanden, der noch viel mehr Geld verdient, da er anders als irgendwelche deutschen Medien weltweit agiert, mit einer Suchmaschine einen ziemlich sinnvollen Dienst bietet und Milliarden Menschen erreicht: Google. Von dem Geld dieses Unternehmens wollen Verlage etwas abhaben, auch wenn ihr Geschäftsmodell ein anderes ist als das der Suchmaschine.”

Ohne dass die Presseverleger gezwungen sind ihre Inhalte die unter das Leistungsschutzrecht fallen zu kennzeichnen wird das gesamte Internet als Geisel genommen.

Das dunkle Geheimnis

Die eigentliche Problematik des Leistungsschutzrechts bleibt bisher weitgehend unbemerkt. Die Unterscheidung der mehrheitlichen kostenlosen Inhalte von den kostenpflichtigen Inhalten ist nicht möglich.

Natürlich sollen Urheber oder Eigentümer über die Verwertung ihres Content entscheiden dürfen. Selbst wenn sie die Nutzung verbieten, und dies den Nutzern und der Gesellschaft schadet. Die Alternative ist ja nur einen Link entfernt. Selbst wenn sie einen Preis festlegen, der ungerechtfertigt oder zu hoch ist. Dann wird eben nicht gekauft. Schön wärs.

Das Leistungsschutzrecht legt zwar die Kostenpflicht bestimmter Angebote fest, nicht aber deren Kennzeichnung. Eine manuelle Abfrage der Kostenpflicht oder Vertragsverhandlung ist bei Millionen Anbietern (100 Milliarden Seiten von 200 Millionen Domains im Web) unmöglich. Und sich über einen Preis zu einigen bevor überhaupt bekannt ist wie häufig der Content in einem Suchergebnis auftaucht ist kaum möglich. Ein Großteil der potentiellen Suchergebnisse gehört zum Long Tail, wird also sehr selten oder nie angezeigt. Trotzdem soll dafür gezahlt werden.

Dadurch wird der rechtssichere Betrieb von Suchmaschinen unmöglich gemacht, sei denn man unterwirft sich einer pauschalen Zahlung, egal ob und in welchem Umfang man vom Gesetz betroffene Inhalte nutzt. Die naheliegende und legale Variante sich auf kostenfreie Angebote zu beschränken, wird durch deren fehlende Identifizierbarkeit verhindert. Sicher ein Versehen. Oder „ein Angebot, das man nicht ablehnen kann“™

Der Ausweg

Da die Presseverleger nicht die unter das Leistungsschutzrecht fallenden Inhalte markieren, hilft nur die maschinenlesbare Kennzeichnung nicht unter das Leistungsschutzrecht fallender Inhalte, durch eine Koalition von Inhaltanbietern und Suchmaschinen im Interesse aller Nutzer.

Die Anbieter können in einer maschinenlesbaren Lizenz die kostenlose Nutzung von Überschriften und Textausschnitten einer definierbaren Länge gestatten.

Maschinenlesbare Kennzeichnung durch Erweiterung der robots.txt:

Title-lenght: 80

Snippet-length: 160

Image-size: 200x200

SpeakingUrl-display: yes

Copyright: 'Freedom of Citation License v1.0: Free manual and/or 
automatized citation is granted for the content hosted on this 
domain, within the restrictions defined in disallowed,
titleLength, snippetLength, imageSize, speakingUrlDisplay as long 
as there is a link to the original source. 
All rights from the German Leistungsschutzrecht are waived.'
Ranking

Die Aufgabe einer Suchmaschine besteht darin, den Nutzer bei der Suche nach für Ihn relevanten Webseiten zu unterstützen. Die Suchmaschine übernimmt dabei einerseits eine Vorauswahl durch die angezeigte Ergebnisliste, andererseits entscheidet der Nutzer dann auf Basis der in Title, Snippet, Url und Thumbnail enthaltenen Informationen ob er einen Link aufruft.
Die Aufgabe der Suchmaschine besteht also auch darin den Nutzer bei seiner Entscheidung durch die Anzeige ausreichender Information über die Webseite zu unterstützen.

Webseiten, die nur begrenzte Information zur Verfügung stellen und damit eine informierte Entscheidung des Nutzers erschweren, und deren Relevanz für den Nutzer schwer ersichtlich ist, werden deshalb im Ranking abgewertet. An der Spitze der Suchergebnisseite werden Seiten angezeigt, bei denen der Anbieter die Suchmaschine dabei unterstützt, dass der Nutzer die für ihn relevantesten Informationen auszuwählen kann.

Was macht FAROO?

Wir passen unsere Suche kostenneutral an das Leistungsschutzrecht an:

  • für Nutzer außerhalb Deutschlands ändert sich nichts.
  • für Nutzer innerhalb Deutschlands bleiben jene Suchergebnisse unverändert, deren Quellen nicht unter das Leistungsschutzrecht fallen oder die eine kostenfreie Nutzung gestatten.
  • für Nutzer innerhalb Deutschlands wird für Suchergebnisse, deren Quellen unter das Leistungsschutzrecht fallen nur noch der Titel angezeigt. Der verminderte Informationsgehalt solcher Suchergebnisse führt zu einem schlechteren Ranking.
  • Für Quellen die unter das Leistungsschutzrecht fallen, und eine Anzeige eines Snippet in den Suchergebnissen wünschen, erheben wir eine Listungsgebühr in Höhe der dadurch im Rahmen des Leistungsschutzrechts entstehenden Kosten.
  • Für Top-News/Topic-Aggregationen werden Quellen die unter das Leistungsschutzrecht fallen, nur noch als ergänzender Link unter dem Titel und Snippet einer freien Quelle angezeigt.
Nicht unter das Leistungsschutzrecht fallenden Quellen werden wie folgt identifiziert:

  • eine manuell erstellte Whitelist
  • eine Erweiterung der robots.txt
Update: Inzwischen beziehen die ersten Verlage und Publikationen Stellung zum Leistungsschutzrecht und gestatten ausdrücklich die Nutzung von Snippets: Heise, Golem, Gamona, Winfuture, Techstage, PC-Welt, t3n, iBusiness, l-iz.
Dies ist ein erster wichtiger Schritt, aber für Dienste die Web-Scale arbeiten führt kein Weg an einer maschinenlesbaren Lizenz/Freigabe vorbei. Jeden Tag werden zwei Millionen neue Domains registriert. Die in Newsmeldungen enthaltenen Freigaben einiger Quellen sind da nur ein Tropfen auf den heißen Stein.

FAROO unterstützt IGEL, die Inititive gegen Leistungsschutzrecht.

DLD13: Next Generation Search

DLD13 Conference

Wolf Garbe (FAROO), Philip Inghelbrecht (Rockmelt) and Albert Wenger (Union Square Ventures) are discussing “Next Generation Search” at DLD13, moderated by Henry Blodget (Business Insider). Free Press Photo © Hubert Burda Media / picture alliance / Jan Haas.

While originally I was to talk about distributed search (you can see the slides here), our moderator suggested to focus on the recent developments of the big search brands instead.

So, what can we expect from the future of search?

From text to facts
Search will move from conventional text search towards understanding and combining facts.
Today’s search engines do a plain text search, returning links to documents. Future search will be able to identify entities (locations, dates, persons, companies, products). It then can use all known properties of those entities (price, date of birth, coordinates …), even if they are not stated in the current document.
This is the Semantic search we have been promised for quite some time. But that’s not the end. Combining facts scattered over different documents, deduction und predicate logic allows the search engine to come up with answers, which are not contained in any of the indexed documents, perhaps even not yet known to mankind.
Search assistants will do call backs to the user to clarify ambiguity, and automatically initiate follow up queries to gather, compare and combine additional information.

Implicit search
If we thinking of search today we have that search box in mind, where we type our keywords in. But tomorrow that will be dominated by implicit search.
Search engines, that see what we see (Google Glass), read what we read, and hear what we hear (Mindmeld). Which know our location, our interests, habits through the day, our calendar, and our personal preferences. Which come up automatically with the contextual information and warnings before we even know we will need that answer.
Imagine you are talking to somebody and you are presented his/her profile and calendar in your augmented reality glasses or you look at a product in a shop, and you are presented with information and price comparisons.

Augmented data
Today search engines are indexing existing documents. But in the future, search engines will control a global net of sensors, which for the first time also creates huge streams of additional data to be indexed.
This can be images and videos from augmented reality glasses, user location data from moving people and cars, usage data from video sites and web site statistics. Early forerunners might be Google Now & Google Goggles integrated into Google Glasses or a crowd sourced Streetview.
And more and more data which are isolated today will be incorporated to search: Crime and pollution data, medical records and income statistics, economics data, stock and weather data and much more.
This brings search closer to the real world. Those augmented date combined with reasoning, correlation, early-warning and prediction technologies will let pale the Delphic Sibyl.

Decentralization
Decentralization has been the foundation of the Internet. It fostered diversity and freedom of information. FAROO focuses on the decentralization of the search infrastructure.
But to the same extend the decentralization of data is important. A single instance owning and controlling the world’s data is infeasible and undesirable. With decentralized data sources like Google Glass and Smartphone GPS the creation and collection of data becomes decentralized. And perhaps the more sophisticated processing of data will be carried out in a worldwide distributed artificial brain.

Interoperability and ownership of data
People want more and more data to be integrated und utilized for search. They want to simplify their life. Flight data, hotel data, weather data, event data, recommendation, satisfaction and price data and much more.
Collecting, normalizing organizing and updating data is complex and comes with cost. But also integrating data, creating a unified marketplace and providing search has a price. So while the user really wants and needs the integration, data owner want to stay in control of the data and their monetization models.
We need not only to solve complexity and interoperability of data but also the interoperability of business models and monetization streams. Every party involved needs to be recompensated fairly. Even for relatively simple cases like a single music catalog, we had to wait for Apple to persuade all the market participants to agree to a user friendly model. The music is still owned by several labels, but there is a unified search and payment option available, and this made online music a success story.
The same will happen for search, companies pioneering a fair exchange model will win, while others staying isolated become obsolete.

Transparency, openness and neutrality
While the integration of data from many sources is desirable, it is important to prevent discrimination.
Sources shouldn’t be blocked or biased in ranking, nor search engines blocked or confronted with unreasonable access conditions.
Full integration is possible already today in web search, app stores and music catalogues.
This is a win-win model with more simplicity, diversity, transparency and more business. Let’s do it for the remaining data sources too.

Smart assistants
Just an example: Coordinating travel, hotel, meetings, events from different data sources, with multiple people and their calendars involved, reacting on flight delays and changing prices while giving the user a choice with different scenarios is possible only with a fully bidirectional data integration.
The user just can’t enter the same data again and again for different providers and different scenarios and fighting with different layouts.
Implicit search is only possible when data can flow freely and be automatically processed, without manual interaction required.
On the long run only those businesses can be only successful which adapt to the needs of the user. He wants to simplify his life and outsource tasks to smart assistant systems, which are the successors of today web search and much more.

Some echo in the press:
Focus: Die Zukunft der Internetsuche
Meedia: Suchexperten über die Zukunft von Search Engines
Futurezone: 6 Trends, die die Tech-Konferenz DLD aufzeigt
digital:next: DLD: Welche Websuche wird ein Hit?
internet world: Die nächste Generation der Suche
Deutschlandradio Kultur: Was tun mit Big Data?

Spelling correction, Query completion and Instant search

In the previous posts we described our new spelling correction algorithm, announced the release of the c# code as Open Source and presented some pretty compelling benchmark results.

FAROO: Spelling Correction and Query completion

Today we are introducing spelling correction, query completion and an improved instant search as integral part of our FAROO search service:

Spelling correction
For a misspelled term the suggested corrections are displayed in a dropdown list.

Query completion (aka query suggestions, autocomplete)
As you type a dropdown list of popular terms and combinations is displayed, which start with the letters you typed so far.

Improved instant search
Results are automatically displayed for the best suggestion/correction, “Enter” searches always for originally entered term.

 

Opposite to traditional implementations we are not using a predefined dictionary:

  • The whole web serves as a corpus, from which we automatically derive the spelling and completion dictionary.
  • The dictionary is automatically updated as part of the indexing process and learns new terms as they appear on the web.
  • The whole process is fully automated, no manual auditing steps are involved.

The algorithm is completely language independent (pure statistics, no linguistic knowledge).
Of course corrections and suggestions are given only within the scope of the selected search language.

 

Try it out at faroo.com

1000x Faster Spelling Correction: Source Code released

In a followup to our recent post 1000x Faster Spelling Correction algorithm we are releasing today a C# implementation of our Symmetric Delete Spelling Correction algorithm as Open Source:

Update: The source code is now also on GitHub.

// SymSpell: 1000x faster through Symmetric Delete spelling correction algorithm
//
// The Symmetric Delete spelling correction algorithm reduces the complexity of edit candidate generation and dictionary lookup 
// for a given Damerau-Levenshtein distance. It is three orders of magnitude faster and language independent.
// Opposite to other algorithms only deletes are required, no transposes + replaces + inserts.
// Transposes + replaces + inserts of the input term are transformed into deletes of the dictionary term.
// Replaces and inserts are expensive and language dependent: e.g. Chinese has 70,000 Unicode Han characters!
//
// Copyright (C) 2012 Wolf Garbe, FAROO Limited
// Version: 1.6
// Author: Wolf Garbe <wolf.garbe@faroo.com>
// Maintainer: Wolf Garbe <wolf.garbe@faroo.com>
// URL: http://blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/
// Description: http://blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/
//
// License:
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License, 
// version 3.0 (LGPL-3.0) as published by the Free Software Foundation.
// http://www.opensource.org/licenses/LGPL-3.0
//
// Usage: single word + Enter:  Display spelling suggestions
//        Enter without input:  Terminate the program

using System;
using System.Linq;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.IO;
using System.Diagnostics;

static class SymSpell
{
    private static int editDistanceMax=2;
    private static int verbose = 0;
    //0: top suggestion
    //1: all suggestions of smallest edit distance 
    //2: all suggestions <= editDistanceMax (slower, no early termination)

    private class dictionaryItem
    {
        public string term = "";
        public List<editItem> suggestions = new List<editItem>();
        public int count = 0;

        public override bool Equals(object obj)
        {
            return Equals(term, ((dictionaryItem)obj).term);
        }
     
        public override int GetHashCode()
        {
            return term.GetHashCode(); 
        }       
    }

    private class editItem
    {
        public string term = "";
        public int distance = 0;

        public override bool Equals(object obj)
        {
            return Equals(term, ((editItem)obj).term);
        }
     
        public override int GetHashCode()
        {
            return term.GetHashCode();
        }       
    }

    private class suggestItem
    {
        public string term = "";
        public int distance = 0;
        public int count = 0;

        public override bool Equals(object obj)
        {
            return Equals(term, ((suggestItem)obj).term);
        }
     
        public override int GetHashCode()
        {
            return term.GetHashCode();
        }       
    }

    private static Dictionary<string, dictionaryItem> dictionary = new Dictionary<string, dictionaryItem>();

    //create a non-unique wordlist from sample text
    //language independent (e.g. works with Chinese characters)
    private static IEnumerable<string> parseWords(string text)
    {
        return Regex.Matches(text.ToLower(), @"[\w-[\d_]]+")
                    .Cast<Match>()
                    .Select(m => m.Value);
    }

    //for every word there all deletes with an edit distance of 1..editDistanceMax created and added to the dictionary
    //every delete entry has a suggestions list, which points to the original term(s) it was created from
    //The dictionary may be dynamically updated (word frequency and new words) at any time by calling createDictionaryEntry
    private static bool CreateDictionaryEntry(string key, string language)
    {
        bool result = false;
        dictionaryItem value;
        if (dictionary.TryGetValue(language+key, out value))
        {
            //already exists:
            //1. word appears several times
            //2. word1==deletes(word2) 
            value.count++;
        }
        else
        {
            value = new dictionaryItem();
            value.count++;
            dictionary.Add(language+key, value);
        }

        //edits/suggestions are created only once, no matter how often word occurs
        //edits/suggestions are created only as soon as the word occurs in the corpus, 
        //even if the same term existed before in the dictionary as an edit from another word
        if (string.IsNullOrEmpty(value.term))
        {
            result = true;
            value.term = key;

            //create deletes
            foreach (editItem delete in Edits(key, 0, true))
            {
                editItem suggestion = new editItem();
                suggestion.term = key;
                suggestion.distance = delete.distance;

                dictionaryItem value2;
                if (dictionary.TryGetValue(language+delete.term, out value2))
                {
                    //already exists:
                    //1. word1==deletes(word2) 
                    //2. deletes(word1)==deletes(word2) 
                    if (!value2.suggestions.Contains(suggestion)) AddLowestDistance(value2.suggestions, suggestion);
                }
                else
                {
                    value2 = new dictionaryItem();
                    value2.suggestions.Add(suggestion);
                    dictionary.Add(language+delete.term, value2);
                }
            }
        }
        return result;
    }

    //create a frequency disctionary from a corpus
    private static void CreateDictionary(string corpus, string language)
    {
        if (!File.Exists(corpus))
        {
            Console.Error.WriteLine("File not found: " + corpus);
            return;
        }

        Console.Write("Creating dictionary ...");
        long wordCount = 0;
        foreach (string key in parseWords(File.ReadAllText(corpus)))
        {
            if (CreateDictionaryEntry(key, language)) wordCount++;
        }
        Console.WriteLine("\rDictionary created: " + wordCount.ToString("N0") + " words, " + dictionary.Count.ToString("N0") + " entries, for edit distance=" + editDistanceMax.ToString());
    }

    //save some time and space
    private static void AddLowestDistance(List<editItem> suggestions, editItem suggestion)
    {
        //remove all existing suggestions of higher distance, if verbose<2
        if ((verbose < 2) && (suggestions.Count > 0) && (suggestions[0].distance > suggestion.distance)) suggestions.Clear();
        //do not add suggestion of higher distance than existing, if verbose<2
        if ((verbose == 2) || (suggestions.Count == 0) || (suggestions[0].distance >= suggestion.distance)) suggestions.Add(suggestion);
    }

    //inexpensive and language independent: only deletes, no transposes + replaces + inserts
    //replaces and inserts are expensive and language dependent (Chinese has 70,000 Unicode Han characters)
    private static List<editItem> Edits(string word, int editDistance, bool recursion)
    {
        editDistance++;
        List<editItem> deletes = new List<editItem>();
        if (word.Length > 1)
        {
            for (int i = 0; i < word.Length; i++)
            {
                editItem delete = new editItem();
                delete.term=word.Remove(i, 1);
                delete.distance=editDistance;
                if (!deletes.Contains(delete))
                {
                    deletes.Add(delete);
                    //recursion, if maximum edit distance not yet reached
                    if (recursion && (editDistance < editDistanceMax)) 
                    {
                        foreach (editItem edit1 in Edits(delete.term, editDistance,recursion))
                        {
                            if (!deletes.Contains(edit1)) deletes.Add(edit1); 
                        }
                    }                   
                }
            }
        }

        return deletes;
    }

    private static int TrueDistance(editItem dictionaryOriginal, editItem inputDelete, string inputOriginal)
    {
        //We allow simultaneous edits (deletes) of editDistanceMax on on both the dictionary and the input term. 
        //For replaces and adjacent transposes the resulting edit distance stays <= editDistanceMax.
        //For inserts and deletes the resulting edit distance might exceed editDistanceMax.
        //To prevent suggestions of a higher edit distance, we need to calculate the resulting edit distance, if there are simultaneous edits on both sides.
        //Example: (bank==bnak and bank==bink, but bank!=kanb and bank!=xban and bank!=baxn for editDistanceMaxe=1)
        //Two deletes on each side of a pair makes them all equal, but the first two pairs have edit distance=1, the others edit distance=2.

        if (dictionaryOriginal.term == inputOriginal) return 0; else
        if (dictionaryOriginal.distance == 0) return inputDelete.distance;
        else if (inputDelete.distance == 0) return dictionaryOriginal.distance;
        else return DamerauLevenshteinDistance(dictionaryOriginal.term, inputOriginal);//adjust distance, if both distances>0
    }

    private static List<suggestItem> Lookup(string input, string language, int editDistanceMax)
    {
        List<editItem> candidates = new List<editItem>();

        //add original term
        editItem item = new editItem();
        item.term = input;
        item.distance = 0;
        candidates.Add(item);
 
        List<suggestItem> suggestions = new List<suggestItem>();
        dictionaryItem value;

        while (candidates.Count>0)
        {
            editItem candidate = candidates[0];
            candidates.RemoveAt(0);

            //save some time
            //early termination
            //suggestion distance=candidate.distance... candidate.distance+editDistanceMax                
            //if canddate distance is already higher than suggestion distance, than there are no better suggestions to be expected
            if ((verbose < 2)&&(suggestions.Count > 0)&&(candidate.distance > suggestions[0].distance)) goto sort;
            if (candidate.distance > editDistanceMax) goto sort;  

            if (dictionary.TryGetValue(language+candidate.term, out value))
            {
                if (!string.IsNullOrEmpty(value.term))
                {
                    //correct term
                    suggestItem si = new suggestItem();
                    si.term = value.term;
                    si.count = value.count;
                    si.distance = candidate.distance;

                    if (!suggestions.Contains(si))
                    {
                        suggestions.Add(si);
                        //early termination
                        if ((verbose < 2) && (candidate.distance == 0)) goto sort;     
                    }
                }

                //edit term (with suggestions to correct term)
                dictionaryItem value2;
                foreach (editItem suggestion in value.suggestions)
                {
                    //save some time 
                    //skipping double items early
                    if (suggestions.Find(x => x.term == suggestion.term) == null)
                    {
                        int distance = TrueDistance(suggestion, candidate, input);
                     
                        //save some time.
                        //remove all existing suggestions of higher distance, if verbose<2
                        if ((verbose < 2) && (suggestions.Count > 0) && (suggestions[0].distance > distance)) suggestions.Clear();
                        //do not process higher distances than those already found, if verbose<2
                        if ((verbose < 2) && (suggestions.Count > 0) && (distance > suggestions[0].distance)) continue;

                        if (distance <= editDistanceMax)
                        {
                            if (dictionary.TryGetValue(language+suggestion.term, out value2))
                            {
                                suggestItem si = new suggestItem();
                                si.term = value2.term;
                                si.count = value2.count;
                                si.distance = distance;

                                suggestions.Add(si);
                            }
                        }
                    }
                }
            }//end foreach

            //add edits 
            if (candidate.distance < editDistanceMax)
            {
                foreach (editItem delete in Edits(candidate.term, candidate.distance,false))
                {
                    if (!candidates.Contains(delete)) candidates.Add(delete);
                }
            }
        }//end while

        sort: suggestions = suggestions.OrderBy(c => c.distance).ThenByDescending(c => c.count).ToList();
        if ((verbose == 0)&&(suggestions.Count>1))  return suggestions.GetRange(0, 1); else return suggestions;
    }

    private static void Correct(string input, string language)
    {
        List<suggestItem> suggestions = null;
    
        /*
        //Benchmark: 1000 x Lookup
        Stopwatch stopWatch = new Stopwatch();
        stopWatch.Start();
        for (int i = 0; i < 1000; i++)
        {
            suggestions = Lookup(input,language,editDistanceMax);
        }
        stopWatch.Stop();
        Console.WriteLine(stopWatch.ElapsedMilliseconds.ToString());
        */
        
        //check in dictionary for existence and frequency; sort by edit distance, then by word frequency
        suggestions = Lookup(input, language, editDistanceMax);

        //display term and frequency
        foreach (var suggestion in suggestions)
        {
            Console.WriteLine( suggestion.term + " " + suggestion.distance.ToString() + " " + suggestion.count.ToString());
        }
        if (verbose == 2) Console.WriteLine(suggestions.Count.ToString() + " suggestions");
    }

    private static void ReadFromStdIn()
    {
        string word;
        while (!string.IsNullOrEmpty(word = (Console.ReadLine() ?? "").Trim()))
        {
            Correct(word,"en");
        }
    }

    public static void Main(string[] args)
    {
        //e.g. http://norvig.com/big.txt , or any other large text corpus
        CreateDictionary("big.txt","en");
        ReadFromStdIn();
    }

    // Damerau–Levenshtein distance algorithm and code 
    // from http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
    public static Int32 DamerauLevenshteinDistance(String source, String target)
    {
        Int32 m = source.Length;
        Int32 n = target.Length;
        Int32[,] H = new Int32[m + 2, n + 2];

        Int32 INF = m + n;
        H[0, 0] = INF;
        for (Int32 i = 0; i <= m; i++) { H[i + 1, 1] = i; H[i + 1, 0] = INF; }
        for (Int32 j = 0; j <= n; j++) { H[1, j + 1] = j; H[0, j + 1] = INF; }

        SortedDictionary<Char, Int32> sd = new SortedDictionary<Char, Int32>();
        foreach (Char Letter in (source + target))
        {
            if (!sd.ContainsKey(Letter))
                sd.Add(Letter, 0);
        }

        for (Int32 i = 1; i <= m; i++)
        {
            Int32 DB = 0;
            for (Int32 j = 1; j <= n; j++)
            {
                Int32 i1 = sd[target[j - 1]];
                Int32 j1 = DB;

                if (source[i - 1] == target[j - 1])
                {
                    H[i + 1, j + 1] = H[i, j];
                    DB = j;
                }
                else
                {
                    H[i + 1, j + 1] = Math.Min(H[i, j], Math.Min(H[i + 1, j], H[i, j + 1])) + 1;
                }

                H[i + 1, j + 1] = Math.Min(H[i + 1, j + 1], H[i1, j1] + (i - i1 - 1) + 1 + (j - j1 - 1));
            }

            sd[ source[ i - 1 ]] = i;
        }
        return H[m + 1, n + 1];
    }
}

Updated:
The implementation supports now edit distances of any size (default=2).

Benchmark:
With previous spell checking algorithms the required time explodes with larger edit distances. They try to omit this with early termination when suggestions of smaller edit distances are found.

We did a quick benchmark with 1000 lookups:

Term Best correction Edit distance Faroo
ms/1000
Peter Norvig
ms/1000
Factor
marsupilami no correction* >3 1,772 165,025,000 93,129
acamodation accommodation 3 1,874 175,622,000 93,715
acomodation accommodation 2 162 348,191 2,149
hous house 1 71 179 2
house house 0 0 17 n/a

*Correct word, but not in dictionary and there are also no corrections within an edit distance of <=3. This is a quite common case (e.g. rare words, new words, domain specific words, foreign words, names).

The speed advantage grows exponentially with the edit distance:
For an edit distance=1 it’s the same order of magnitude,
for an edit distance=2 it’s 3 orders of magnitude faster,
for an edit distance=3 it’s 5 orders of magnitude faster.

1000x Faster Spelling Correction algorithm

1000x faster

Update: We released a C# implementation as Open Source.
Update2: We are 100.000 times faster for edit distance=3.
Update3: Spelling correction is now also part of FAROO search.
Update4: The source code is now also on GitHub.

Recently I answered a question on Quora about spelling correction for search engines. When I described our algorithm I was pointed to Peter Norvig’s page where he outlined his approach.

Both algorithms are based on Edit distance (Damerau-Levenshtein distance).
Both try to find the dictionary entries with smallest edit distance from the query term.
If the edit distance is 0 the term is spelled correctly, if the edit distance is <=2 the dictionary term is used as spelling suggestion.
But our way to search the dictionary is different, resulting in a significant performance gain and language independence.

Three ways to search for minimum edit distance in a dictionary:

1. Naive approach
The obvious way of doing this is to compute the edit distance from the query term to each dictionary term, before selecting the string(s) of minimum edit distance as spelling suggestion. This exhaustive search is inordinately expensive.
Source: Christopher D. Manning, Prabhakar Raghavan & Hinrich Schütze: Introduction to Information Retrieval.

The performance can be significantly improved by terminating the edit distance calculation as soon as a treshold of 2 or 3 has been reached.

2. Peter Norvig
Generate all possible terms with an edit distance <=2 (deletes + transposes + replaces + inserts) from the query term and search them in the dictionary.
For a word of length n, an alphabet size a, an edit distance d=1, there will be n deletions, n-1 transpositions, a*n alterations, and a*(n+1) insertions, for a total of 2n+2an+a-1 terms at search time.
Source: Peter Norvig: How to Write a Spelling Corrector.

This is much better than the naive approach, but still expensive at search time (114,324 terms for n=9, a=36, d=2) and language dependent (because the alphabet is used to generate the terms, which is different in many languages and huge in Chinese: a=70,000 Unicode Han characters)

3. Symmetric Delete Spelling Correction (FAROO)
Generate terms with an edit distance <=2 (deletes only) from each dictionary term and add them together with the original term to the dictionary. This has to be done only once during a pre-calculation step.
Generate terms with an edit distance <=2 (deletes only) from the input term and search them in the dictionary.
For a word of length n, an alphabet size of a, an edit distance of 1, there will be just n deletions, for a total of n terms at search time.

This is three orders of magnitude less expensive (36 terms for n=9 and d=2) and language independent (the alphabet is not required to generate deletes).
The cost of this approach is the pre-calculation time and storage space of x deletes for every original dictionary entry, which is acceptable in most cases.

The number x of deletes for a single dictionary entry depends on the maximum edit distance: x=n for edit distance=1, x=n*(n-1)/2 for edit distance=2, x=n!/d!/(n-d)! for edit distance=d (combinatorics: k out of n combinations without repetitions, and k=n-d),
E.g. for a maximum edit distance of 2 and an average word length of 5 and 100,000 dictionary entries we need to additionally store 1,500,000 deletes.

Remark 1: During the precalculation, different words in the dictionary might lead to same delete term: delete(sun,1)==delete(sin,1)==sn.
While we generate only one new dictionary entry (sn), inside we need to store both original terms as spelling correction suggestion (sun,sin)

Remark 2: There are four different comparison pair types:

  1. dictionary entry==input entry,
  2. delete(dictionary entry,p1)==input entry
  3. dictionary entry==delete(input entry,p2)
  4. delete(dictionary entry,p1)==delete(input entry,p2)

The last comparison type is required for replaces and transposes only. But we need to check whether the suggested dictionary term is really a replace or an adjacent transpose of the input term to prevent false positives of higher edit distance (bank==bnak and bank==bink, but bank!=kanb and bank!=xban and bank!=baxn).

Remark 3: Instead of a dedicated spelling dictionary we are using the search engine index itself. This has several benefits:

  1. It is dynamically updated. Every newly indexed word, whose frequency is over a certain threshold, is automatically used for spelling correction as well.
  2. As we need to search the index anyway the spelling correction comes at almost no extra cost.
  3. When indexing misspelled terms (i.e. not marked as a correct in the index) we do a spelling correction on the fly and index the page for the correct term as well.

Remark 4: We have implemented query suggestions/completion in a similar fashion. This is a good way to prevent spelling errors in the first place. Every newly indexed word, whose frequency is over a certain threshold, is stored as a suggestion to all of its prefixes (they are created in the index if they do not yet exist). As we anyway provide an instant search feature the lookup for suggestions comes also at almost no extra cost. Multiple terms are sorted by the number of results stored in the index.

Reasoning
In our algorithm we are exploiting the fact that the edit distance between two terms is symmetrical:

  1. We can generate all terms with an edit distance <2 from the query term (trying to reverse the query term error) and checking them against all dictionary terms,
  2. We can generate all terms with an edit distance <2 from each dictionary term (trying to create the query term error) and check the query term against them.
  3. We can combine both and meet in the middle, by transforming the correct dictionary terms to erroneous strings, and transforming the erroneous input term to the correct strings.
    Because adding a char on the dictionary is equivalent to removing a char from the input string and vice versa, we can on both sides restrict our transformation to deletes only.

We are using variant 3, because the delete-only-transformation is language independent and three orders of magnitude less expensive.

Computational Complexity
Our algorithm is constant time ( O(1) time ), i.e. independent of the dictionary size (but depending on the average term length and maximum edit distance), whereas e.g. BK-Trees have a search time of O(log dictionary_size).

Application
Possible application fields of our algorithm are those of fast approximate dictionary string matching: spell checkers for word processors and search engines, correction systems for optical character recognition, natural language translation based on translation memory, record linkage, de-duplication, matching DNA sequences, fuzzy string searching and fraud detection.

———

BTW, by using a similar principle our web search is three orders of magnitude more efficient as well. While Google touches 1000 servers for every query, we need to query just one (server/peer).
That’s not because of DHT! Vice versa, because even for a complex query in a web scale index only one of the servers needs to be queried, it enables the use of DHT for web search.
Our algorithm improves the efficiency of central servers in a data center to the same extent.

Near Duplicate Detection

FAROO now has implemented a robust Near Duplicate Detection.
This promotes original content and diversity in results, while filtering out scraped or syndicated duplicates.

We had to solve two challenges:

  1. a robust algorithm, that identifies duplicates even if they appear within a different template with different menu, header or footer.
  2. do it web scale, i.e. every single new web page needs to be compared to the whole corpus of existing web pages
 

The screenshots below illustrate the effect of Near Duplicate Detection. See the difference between Google and FAROO results:

FAROO – with Near Duplicate Detection

FAROO: with NEAR Duplicate Detection

 

Google – without Near Duplicate Detection

Google: without Near Duplicate Detection