AJAX Incremental Search Revisited

How Structured Data Matching Engines Enable
a Revolutionary Incremental Search Interface

This paper is also available in PDF format: AJAX Incremental Search Revisited

Table of Contents

I. Introduction and Context

II. AJAX Incremental Search Detailed Features and Characteristics

A. Basic AJAX Incremental Search Described

Key Benefits of Basic AJAX Incremental Search

Shortcomings of Basic AJAX Incremental Search

B. AJAX Incremental Search Powered a Structured Data Search Engine

Example: Yellow-White Pages Search Interface

Interface Design Features of AJAX Incremental Search Interfaces

Example: Advanced Incremental Travel Search

C. Systems Architecture of an Advanced AJAX Incremental Search

Performance Issues with Incremental Search

Improving, Not Replacing Delimited Search

III. Business Performance, Risks and Cost of AJAX Incremental Search Systems

A. Benefits of Various Incremental Search Systems

Benefits  to the Users

Benefits to the Content Service Operators

Example: Price Comparison Portal

B. Cost and Risk Analysis

Cost Matrix of Incremental Search System Types

Optimizing the Cost vs. Feature Richness Dilemma of Incremental Search Interfaces

IV. Other applications of AJAX Incremental Search Powered by Data Matching Servers

back to top ^

I. Introduction and Context

Example of Incremental Search Interface

The Internet software community has come to appreciate and recognize the unique benefits of AJAX incremental search interfaces.  AJAX interfaces enable client-side interactive web applications capable of retrieving data from the server asynchronously in the background without interfering with the display and behavior of the web page.  They offer users immediate suggestions for what they might be searching for as the user types his query.  Such search query suggestions are usually displayed in the form of a drop-down box and have appeared on most large online public search services in the recent years. 

These incremental search interfaces are inherently limited by the speed and sophistication of the underlying index and data recall mechanisms.  Many rely on simple client-side JavaScript programs offering access to a limited list of popular query suggestions (example current eBay.com incremental search widget).  Some are server-side databases or flat-file lists limited by their response time latency and their capacity to display complex results sets (ranked, faceted, real-time, from large data sets, etc.) as a user types his query.

back to top ^

One of its most impressive benefits is its ability to automate the search of content users do not suspect is in existence.  “Large bodies of content are mostly composed of text and data records of which users do not suspect the existence.  Only a very fast approximate search engine can display these suggested matches with the speed and relevance incremental search requires.”

Exorbyte’s search software expertise is in the area of structured data and semi-structured data (database, directories, XML feeds, etc.) is recognized by a diverse worldwide customer base and has led to the development of MatchMaker, its structured data search engine.  MatchMaker’s uniqueness comes from its ability to process very complex algorithmic, phonetic, and otherwise scripted queries at record speeds over very large data sets.  In search environments, MatchMaker usually serves as an API-accessible backend for user-facing applications or as a search engine for structured data (e-commerce, directories, etc.). 

An AJAX search interface tied to a MatchMaker structured data search engine with a sophisticated configuration offers users a very interactive, instant and unprecedented view of the deepest most complex data sets possible.  Much more than a “typeahead” or “autosuggest” like those offered by most search engines today, this sort of implementation can tremendously enhance the ability of users to validate their queries, explore deep data structures and the ability of administrators to customize search interfaces with little development effort for both structured and unstructured data sets.

The name given to the MatchMaker extensions for incremental search discussed in this paper are SearchNavigator and FlexSearch. They are two unique AJAX frameworks³  and search interfaces combining the proven benefits of AJAX incremental search with its highly versatile structured data search engine: Matchmaker.  Exorbyte’s AJAX frameworks’ most impressive ability is that they give users a stunningly informative bird’s eye view into large and complex data sets. Such a view is only achievable because of the speed and versatility of the underlying MatchMaker engine.  The possibilities offered by the infinite combination of search query parameters available in MatchMaker and the very intuitive interface of the AJAX frameworks appear to be limitless. Such an interface improves the traditional search experience with query rewriting through dynamic suggestions.  It also allows the display of advanced search results ahead of query submissions.  Users can finally click on the suggested results and navigate straight to content, thereby bypassing entirely the traditionally cumbersome and costly search steps that often lead users to dissatisfaction and online business to lost transactions and lost revenue.  The experience gained with SearchNavigator already shows tremendous search behavior changes that will profit both users and content publishers whether they offer search within full-text web pages or enterprise-scale relational databases (ecommerce, etc.). 

back to top ^

II. AJAX Incremental Search Detailed Features and Characteristics

A. Basic AJAX Incremental Search Described

An AJAX incremental search interface starts with a number of simple characteristics:

• Looks and behaves like any other classical search query interface.  
• Does not require software / internet users to adjust their behavior if they prefer not to.  
• Does not require any user education or explanations.  
• Only adds new functions to a very familiar classical search query interface.

A classical delimited search query interface

• As a user types text in a search query field, and gets instant feedback before getting to a whole new user interface: the search results page.  This simple and intuitive feedback usually includes suggestions drawn from a limited set of normalized queries, popular search queries, or a dictionary-style list of terms.

Basic Google search suggestions, drawn from a set of most popular queries.

There are a couple of key technical constraints posed by even the most simple incremental search systems as described above:

• Highly increased number of queries per second generated by each keystroke (or at least each stroke with pause⁴) compared to just one query by submission.  This is particularly relevant for AJAX client-server systems where server load and bandwidth have a significant cost.
• Absolute necessity of advanced approximate matching capability.  An incremental search system not capable of matching partial words or misspellings would have little to no utility.

back to top ^

Key Benefits of Basic AJAX Incremental Search

The basic implementation of an AJAX incremental search described above offer a number of new advantages for their users and those operating web content services.  The main advantages can be summed up as follow:

• Search suggestions: Users get suggestions for search query terms they may have misspelled (a sort of user-assisted “query-rewriting”).
• Implementation requires little or no incremental development by operators of content search services since it works in parallel with underlying search engine.
• Users get a limited view of what others might be looking for and how others formulate multi-word queries.
• Some query misspellings can be caught by the stemming⁵ effect of the interface when a word is not yet fully typed.

Shortcomings of Basic AJAX Incremental Search

It is also important to note that a number of problems remain for content service operators and for users of such basic AJAX Incremental Search systems:

• These suggestions come from a data set that needs to be regularly updated, maintained and normalized.  Not doing so, may lead to “no result” search results page, popular misspelled queries being suggested, and no suggestions for seasonal or news-related search queries. 
• Such an implementation unless in very low usage environments (intranets, single user, etc.) is either:
• a light client-side system which can hardly be based on more than a few thousands records or be difficult to serve as web content,
• or a client-server system requiring a structured data search engine capable of handling each  character stroke queries fast enough to diminish latency.
• This implementation is not drawing results from the actual index or an underlying searchable database.  Users could assume that each suggestion will lead to a meaningful result.  That’s often not the case.
• In general this implementation does not give users any real sense of the results they might find if they chose any of the suggestions returned.  It can mislead users in thinking suggestions come from searchable content, but can never give them a sense of what, in the searchable content, resembles what they are looking for.

back to top ^

B. AJAX Incremental Search Powered a Structured Data Search Engine

The last of the shortcoming cited above for basic AJAX Incremental Search interfaces is at the core of most of the improvements of advanced AJAX Incremental Search interfaces like Exorbyte’s SearchNavigator.  The pairing of an AJAX Incremental Search interface with an advanced structured data search engine like Exorbyte MatchMaker allows a groundbreaking improvement: the incremental search interface then becomes more than a way to “search” for content; it also enables “direct navigation” to target content.  Such a system reliably serves faceted search and content suggestions to millions of users, from millions of searchable indexed records, using algorithmic, phonetic and any other advanced scripted match sequence in an AJAX suggestion interface.

In industries such as ecommerce an advanced search system has a direct impact on measurable business performance variables like revenues, conversion rates, average purchase value, repeat purchases, sales of rare items, sales of difficult to find items, user satisfaction and loyalty, etc.  Implementing and maintaining such interfaces offer measurable cost benefits over other approaches.  We will look at what financial performance impact the use of such advanced search interface can have in these settings.

back to top ^

Example: Yellow-White Pages Search Interface

Before highlighting specific features of advanced AJAX incremental search applications such as Exorbyte SearchNavigator, here is a description of of these interfaces.

In this first example, we examine a public web directory called Genialotel⁶ which allows searching through to about 40 million German name/phone/address listings for individuals and businesses in Germany. 

Genialotel offers a simple who/where two field search interface featured in Figure 1.  Here are some specific features which differentiate this first example from previous AJAX incremental search interfaces discussed in this paper (see cross-references in Figure 1):

(1) Dual purpose: This incremental search query interface is and remains a classical search form if users choose to use is as such and ignore the suggestions presented.

(2) Virtually no performance-related query parameter limitations: In most directory search systems, searching for a partial name plus two letters of the city name as in the example in Figure 1 (“FR”) is impossible with 40 millions records.  Computing latency would be too long if at all possible without failure.  Here the results are returned fast enough to be updated at every key stroke (few milliseconds).

Figure 1 - GenialoTel suggestions drawn from real content, faceted, ranked, taxonomized, counted, and more.

back to top ^

(3) Advanced approximate matching allows finding content the user didn’t suspected existed: Results are approximate: the result set displayed is not only the product of exact match or basic stemming and other simple close matching routines.  It comes from a complex sequence of string matching and data matching rules associated with this particular search mode. 

(4) Search results are categorized, faceted, ranked, or displayed in any other advanced way. 

(a) Search results are presented ranked according to relevance, proximity, or any other parameter. 

(b) The search results in this example are also presented in two possible layouts : restricted by current “where” value or unrestricted “Best name matches in other locations”. 

(c) The possible results behind each suggested query offer a count of possible matches.

(d) More results can be displayed in needed.

(e) “Best matches” suggestion are displayed with associated zip code and city for each record to ensure disambiguation by user. 

(5) Parametric incremental search results for all possible usages of the query form.  Whether users choose to start with “where” or “who/what” field, the AJAX incremental search system (SearchNavigator) always passes on a query to the underlying engine (MatchMaker) and returns customized suggestions results from the full data set.  Not visible here on the form but visible by visiting the Genialotel  site.

(6) Custom interface: Interface design is fully customized: There is no risk of users thinking this is just a Windows or Internet Explorer suggestion set from cache memory.  Colors and well structured design attract their attention to the suggestions presented.

(7) Direct Navigation – When search results can be displayed in lists of best unique matches with little ambiguity, it is possible and of course recommended that users clicking the item be directed straight to the target item’s content page (in this example the full directory phone data for that record).  Alternatives, such as filling the search form with the item’s data, or sending the user to a search result page, don’t make much interface design sense.  Whenever clicks and ambiguity can be eliminated, they should be.

back to top ^

Example: Advanced Incremental Travel Search

As the previous example of an AJAX incremental search shows, such systems can actually show any number of parametric, faceted, categorized, and ranked results in a instant interactive interface during the user query formulation stage of the search process.  This immediate feedback can be tailored to the specific form field, and combination of form fields that a user has filled.  This combination of capabilities naturally led Exorbyte engineers to a more advanced version of SearchNavigator for particularly complex “advanced search” user interfaces:  FlexSearch.  Examples of applications are notoriously difficult search interfaces such as online travel search, online job search, and any other search requiring a large number of inter-dependent variables (form fields). 

To illustrate such an application we will look at public implementation on the leading European travel service L’Tur⁸. 

The legacy L’Tur search user interface is complex

Because the L’Tur service is focused on last minute travel packages it was important that users be able to find travel package inventory items “buried deep” in the L’Tur catalog.  It was also the desire of L’Tur to offer a single interface for searching within flights, hotels, cars, packages.  With FlexSearch below, exorbyte was able to provide L’Tur with am AJAX-based configurable interactive search configurator capable of guiding users through the complexity of building a travel search just like a live sales person could.

back to top ^

The FlexSearch Interface on L’Tur guides users intuitively to precisely what is available in the catalog.  Price, service levels, hotel and other subcomponents, durations, locations, and all other trip variables are proposed to users based on their desired inputs.

The Exorbyte FlexSearch incremental search implementation above demonstrates the synergistic combination of an advanced data search infrastructure (matchmaker) paired with an AJAX interface (FlexSearch).  It not only allows displaying the most advanced types of search results instantly as users formulate their search queries, but it also:

• Changes nothing to the legacy search systems but adds value to the search experience.
• Extrapolates “long” or “advanced” advanced queries suggestions which users may not formulate spontaneously from few characters already typed.
• Assists user in building multi-variable queries with complex decision logic preprogrammed in the FlexSearch configuration.
• Eliminates “not founds” due to query and data misspellings or typos by relying on advanced approximate algorithmic string matching algorithms.
• Displays suggestions from actual catalog or index data along with associated key attributes (price, hits, and matching categories).
• Eliminates the need for Search “Back-and-Forthing” from query to results and back to refine query enough to hit a rare content target.
• Ensures even the rarest of items are found by allowing biased ranking of items in suggestions.

back to top ^ 

C. Systems Architecture of an Advanced AJAX Incremental Search

Performance Issues with Incremental Search

As mentioned before advanced incremental search clients generate a high number of queries to the server (potentially one call for every user keyboard stroke in search field).  The design of these interfaces is also likely to create a natural expectation of approximate matching:  Partially typed search terms are sent to the server and need to be matched.  Users also expect misspelling suggestions and  more advanced systems such as Exorbyte SearchNavigator and FlexSearch even provide the user with suggestions semantically relevant to their partially search term (through taxonomies, aliases, synonyms, etc.).   

These factors tend to be extremely costly in hardware resources and only a high performance structured data search engine like MatchMaker can truly handle such throughput and scale with the surrounding web applications.  Hardware optimization and specialized indexing architecture allow resolving many of the issues which would slow down or fail a traditional search engine.  A high performance approximate search system like MatchMaker must be architected with such considerations in mind.  The chart on the following page shows the typical layout of such a solution.

Architecture of an AJAX incremental search system powered by a structured data search engine

back to top ^ 

Improving, Not Replacing Delimited Search

It is also important to note that the implementation of an incremental search interface, even one powered by an advanced data matching server like Exorbyte MatchMaker, is an addition to, not a replacement of existing search systems.  As shown on the chart on the next page, the delimited search queries may still flow through the existing search systems after AJAX incremental search has been implemented. 

From a UI design point of view, the two search systems are very much related.  For instance, the incremental search user interface should not display search results that may not be easily found by a similar delimited search query.  However, from a systems stand point, the only two points of contact between the delimited search systems and the incremental search systems are:

• a data integration point allowing the incremental search index to always be the same as the delimited search index,
• and some client-side (JavaScript) widget allowing the existing search form to generate incremental search queries so users can see real-time results ahead of submitting their final search query and being routed to search results of the target content item itself.

While delimited search requests may still be directed to the legacy search engine, to a database or to other content management applications, incremental search calls to the server are made through asynchronous JavaScript and XML (AJAX) HHTP requests to the structured data search engine.  That specialized search engine holds a partial, complete or even enriched copy of the main index (ecommerce catalog, directory, or any other structured content type).  It is able to process vastly more complex error tolerant requests with partially typed form inputs and return suggestions within a few milliseconds for every user character stroke.

back to top ^

III. Business Performance, Risks and Cost of AJAX Incremental Search Systems

An AJAX incremental search and data matching engine implementation require careful planning and configuration to ensure optimal results.  While the cost of such systems usually represents a small portion of a larger online content delivery deployment (online media, major yellow pages sites, etc.), many businesses today pay close attention to the costs and benefits associated with each of their IT investments.  It is therefore important to define how content services operators can approach the questions of cost, risk and performance when planning such deployments. 

In his 2000 book The Humane Interface, interface design expert Jef Raskin says "from the point of view of interface engineering, the advantages of incremental searching are so numerous and the advantages of delimited searches so few that I can see almost no occasions when a delimited search would be preferred."  While this qualitative endorsement by a renowned expert is significant, it doesn’t tell business operators what the impact and cost of implementing incremental search may be.

A. Benefits of Various Incremental Search Systems

Improving content search applications (directories, ecommerce catalogs, travel services, e-government, vertical search engines, online media, etc.) usually requires a carefully planned redeployment of backend systems and back-office processes; thus generating significant indirect costs.  However, all costs and risks associated with such deployments should be offset by the benefits of a better search and navigation experience.  It is difficult to quantify in advance the benefits to be expected from the redeployment as well as the maintenance cost of the systems and specialized content it may require.  Exorbyte’s experience has showed a number of constants that emerge from most implementations.  These lessons drawn from fact can help organizations conceive a framework to approach the cost/benefits questions when conceiving a new or improved incremental search system.

back to top ^

Benefits  to the Users

The addition of incremental search to an existing content search interface creates some clear improvement for users:

• Incremental search diminishes or eliminates “not found” search results because incremental search allows users to validate a query string based on existing matches or likely matches from the search content.
• Incremental search allows users to have a bird’s eye view of complex bodies of searchable content through incremental displaying of exact matches and approximate matches based on string matching techniques, taxonomies, and faceted search techniques.
• Incremental search eliminates misspellings, typos, and other data entry errors in the search query strings or the searchable content.
• Incremental search diminishes user flight (dissatisfaction with search leads users to leave a site or application before they have found what they came to look for).  
• Incremental search allows users to find deeply buried content by suggesting related or similar search queries to what the user has already typed.  Such content is sometimes hardly findable at all using delimited search if the user doesn’t suspect its existence.
• Incremental search speeds up the search process by allowing an optimal query formulation to be submitted by users the first time around; thus eliminating “back-and-forthing” or other tedious incremental users search processes based on elimination of irrelevant search queries rather than on finding the right query from the start.

Benefits to the Content Service Operators

Content service operators (large web sites, directories, ecommerce companies, large enterprise applications, etc.) can leverage the benefits of using advanced incremental search for the following reasons:

• Reduced costs of hardware and operations of search infrastructure.  With incremental search users tend to use search only once and find their results right away.  When using a structured data search engine, this leads to dramatically decreased load on delimited search systems.  Strctured data search systems like Exorbyte’s MatchMaker are much cheaper to operate and maintain that a traditional or full-text search engine for instance.
• Dramatically improved control over search and navigation.  Search engines and content management systems are not always easy and flexible to configure.  Content service operators can use an advanced incremental search system to assist the users with fully controllable search and navigation suggestions before they become confused in searching and navigating the site with other tools.
• Business driven raking and biasing of search records allows to build interfaces that both optimize user satisfaction and business outcomes.
• Increased satisfaction generates user loyalty through improvements of users experiences in search and navigation of the content.

back to top ^

Example: Price Comparison Portal

In one of its first AJAX incremental search implementation on leading German price comparison portal Billiger.de, Exorbyte was able to collect some interesting data regarding the usage patterns of SearchNavigator and what changes occurred after its introduction.  Billiger was able to report exceptional results  given the small investments required by such an implementation.  Implementing SearchNavigator takes 3 to 5 days engineering and a monthly license fee to Exorbyte.

The FlexSearch Interface on L’Tur offering users an impressively simple start: one simple search field

In the case of Billiger.de, the 1st month of implementation saw a 5% increase in the conversion rates of the site.  That’s a significant revenue increase that easily offsets the costs of implementation.  Incremental search also proved a preferred method for digging deep in the multiple layers of the price comparison portal’s categorical structure for Billiger’s users.  The relative use of search versus the navigation of categories (directory style taxonomy) increased 20% thus showing that users were more satisfied with this method for product location.

back to top ^

B. Cost and Risk Analysis

As discussed previously, various types of incremental search implementation modes exist.  Typical classifications focus on their impact on the user experience but the table below (Figure 2) offers a classification that compares various incremental search systems based on user experience benefits as well as resources necessary to implement and maintain them.

As shown in the table above, it is easy to see why incremental search systems supported by a specialized structured data search engine such as MatchMaker are optimally suited to satisfy the most demanding business and financial constraints.

back to top ^

Optimizing the Cost vs. Feature Richness Dilemma of Incremental Search Interfaces

Incremental search interfaces require greater approximate search capabilities because the very premise of a search suggestion is to help users guess what alternative content may exist relative to what they have typed, or are about to type.  Such capabilities assume that the system should be able to correct user and content errors whenever possible.  This type of “did you mean” error tolerant search software must include facilities such as: algorithmic edit distance calculations, phonetic computations, aliases/synonym lookup tables, custom matching scripts, and many other refinements all wrapped in one.  Such logic can be developed or configured partially into the higher-end search engines but the hardware performance and maintenance cost is often daunting.  This is why error tolerant structured data search engines are so well suited to assist the deployment of such applications.

Figure 3 – Positioning map showing the relative cost/benefits of various incremental search approaches

back to top ^ 

An error tolerant structured data search engine such as Exorbyte MatchMaker is capable returning pertinent approximate matches over many millions of records and within the short time constraints of incremental search interfaces.  A specialized search engine like MatchMaker requires only a small fraction of the hardware resources required to upgrade traditional search systems to fit the demanding performance constraints of incremental search applications.  In many cases, it is not even possible to implement incremental search over a traditional search application because of sluggish response time and inability to handle approximate matching.

The use of an AJAX incremental search system coupled with MatchMaker offered the benefit of being capable of running in parallel or “on top of” an existing search application.  The index compiled by the data search engine (MatchMaker) can be directly extracted from the existing search index (catalog, directory records, etc.)  The actual AJAX interface is then implemented on the existing search web pages by simple addition of a few lines of JavaScript.  The back-end systems run completely independently:  should the main search engine fail, the AJAX incremental search system would still remain operational.

As expressed by this large body of evidence the costs and risks associated with incremental search are best mitigated by the implementation of a structured data search engine along with the incremental search interface.  In the case of Exorbyte, monthly fees for its custom incremental search solution based on the MatchMaker search engine start at around $2,000 per month plus approximately $6,000 of installation and configuration services.  For the smallest operators (below 1M queries per month and 100,000 records) this minimal fixed cost may be too large.  In such cases a minimal client side incremental search will offer some additional benefits for an affordable cost.  In all other cases, incremental search systems require a data matching server capable of handling high performance. 

back to top ^

IV. Other applications of AJAX Incremental Search Powered by Data Matching Servers

Although AJAX incremental search is an ideal fit for search interface destined for structured data (databases, directories, ecommerce, etc.), the use of approximate data matching technology such as Exorbyte MatchMaker opens possibilities for other types of search applications.  Most unstructured data search solutions involve searching web content such as web pages and other documents or searching through semi-structured data (price comparison XML feeds, EDI transactions, email messages, etc.)

It’s interesting to note that many full text search engines for instance have evolved to include a structured index accompanied with all sorts of dictionaries and lookup tables for spellchecking, taxonomies, and other search-related services.  Each of these data sources can be leveraged in some sort of incremental search interface if it fits with the search engine’s purposes.

The use of AJAX interfaces is only starting to take hold in web interface architectures.  Implementing fancy new search interfaces like AJAX incremental search is often a question of balancing quality of search experience with existing or future performance limitations.  Implementation of approximate high-performance data matching servers will become a necessity if such systems need to scale and remain optimal in search quality.

back to top ^

Dan Nicollet – Exorbyte Inc. 2009

All names and logos are trademarks and/or registered trademarks of their respective owners.

Notes: 

 back to top ^

1. Incremental search is sometimes called sometimes called “incremental find”, “typeahead search”, “autosuggest”, “autocomplete”, “combo box”, “search as you type”, “filter/find as you type” (FAYT), “inline search”, “instant search”, “word wheeling” or even “Google suggests”:
   http://en.wikipedia.org/wiki/Incremental_find
2. The Humane Interface, Jef Raskin (creator of the Macintosh Interface) - 2000 -  http://books.google.com/books?id=D39vjmLfO3kC&lpg=PA126&ots=COqFf33VS9&dq=incremental%20%22delimited%20search%22&pg=PA126
3. An Ajax framework is a framework that helps to develop web applications using Ajax, a collection of technologies used to build dynamic web pages on the client side. http://en.wikipedia.org/wiki/Ajax_framework
4. Most incremental search systems only generate a suggestion if the user pauses more than a few milliseconds.
5. http://en.wikipedia.org/wiki/Stemming
6. http://www.genialotel.com/index/en
7. Visit http://www.genialotel.com/index/en to see this system working.
8. Visit http://www.ltur.com/de/search.ltml?flexsearch=yes# for a live version of Exorbyte FlexSearch.
9. Billiger.de’s Managing Director, Lars Bauer discusses Billiger’s use of Exorbyte’s software in the article “Diskrete Gedächtnisstütze” in e-commerce MAGAZIN in May 2006.  See system live at http://www.billiger.de (in German Language).

back to top ^