Instant’s Auto complete Suggestions Review

Over the past couple of years, auto-complete has become famous over the web. Facebook, YouTube, Google, Bing, MSDN, LinkedIn,Apple and other websites try to complete text phrases as soon as we typing.

Auto-complete definitely makes for a nice user experience, but it can be a challenge to implement efficiently. In many cases, an efficient implementation requires the use of interesting algorithms and data structures. In this blog post, I will describe all about it.

Basic Idea

Basically Auto complete is combination of HTML,JS,CSS and data source. It could be JS string or a file or data fetching from db connection. we usually fetch data from source on the basis of JS events like onkeyup etc. 

Engineering Challenges

however we notice that Facebook or google's auto suggestions are working very fast or with good speed.  I encountered first time with speed issue when i worked for www.peerpower.com. Actually we had planed to use Auto suggester frequently to show master data in drop downs. see registration page http://www.peerpower.com/register.php. That time i implemented incremental caching feature at browser side but later i found that still i don't touch facebook and google standards.

However now some open sourse caching plugins are avalable by default. see http://docs.jquery.com/Plugins/Autocomplete and http://flexbox.codeplex.com.

Typically following are the key points which play game in efficient manner.

1.  Data structure to retrieve big data
2.  client side caching from memcache indexed javascript array (for example first letter as index, so friends['a'] = [andrey, albert] )
3. client side storage techniques (normally all modern browser support it )
4.  warm up caches as early as it can
5. build an index of names -> dom elements, do dom manipulation offline and attach the results with only people that match the searched term

Data structure to retrieve big data

Ternary search trees Trie is used to retrive data for auto-complete lookup but needs too much memory. Solution for it PATRICIA (Practical Algorithm to Retrieve Information Coded in Alphanumeric). http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/

Both are data structues so you can read them about in details separately. 

Other Challenges

Suggestions Can Vary By Region & Language

Not everyone sees the same suggestions. For example if i am in delhi then i will see delhi based results with high priority.

Previously Searched Suggestions

Big demand in suggestor product to track how are things going.

How Suggestions Are Ranked

Big question if you plan to put suggestor at home page.Popularity is a factor, but some less popular searches might be shown above more popular ones.

Deduplicating & Spelling Corrections

Its basic functionality that everyone dreams in auto suggestor :P

Freshness

If there are terms that suddenly spike in popularity in the short term, these can appear as suggestions, even if they haven’t gained long-term popularity.

Dev team with no QA resources

Right now in my organization, there are completely independent roles for QA and Dev. QA vs Development ratio is always an open issue, specially in crucial prod releases :P


In my office, we are thinking about DEV without QA i.e. push releases on prod without/partial help of QA. 


Overall idea is avoid QA using either TDD, peer programming or peer code review etc. 


Here are few key notes ( my worries :P however they are very subjective, but based on experience)

1. Can developers really be effective testers, with their intimate knowledge of the application?
2. Can developers could be a good "bug finders" rather than engineers.
3. People are often blind to their own shortcomings or mistakes, and developed code is best validated when tested by third parties. Of course, proper monitoring and management of this process could mitigate the process...but it's a concern.
4. Can developer think high visibility prospective. Sometimes a customer relationship can be impaired by simple usability flaws -- a somewhat common mistake for an immature developer.
5. Increases the chance for rework
6. Leads time involved more on testing application or module

However following are few parameters which helps.


How much unit testing the developers are doing. The more they do, the less QA dependency.


How much the developers are writing from scratch versus leveraging existing libraries. If there is a lot of pre-existing code in use then its disappointing call.


How dynamic the development is. If you are writing a UI where relatively small developer tweaks cause a large change to the testable surface then it would be pain.


How mission critical the feature is. It need a lot more testing because bugs are hard to fix in the field and very bad when they happen.

check before going to print a web page

Recently we launched online forms product where students can apply for courses in various institutes individually and can pay forms fees, submit documents etc. Here we encountered with  printing web page functionality. It behaves differently across browsers and sometimes forms layout is not same as form shown in web page. However team is working on that , i searched in google and  find out to know root causes.


1. Avoid printing web page, best is to provide pdf for same as earlier we did for sums invoices reports.


2. Lets look below points which generally we follow if we plan to print web page.


General print styles tips to use to get better print outs 



/* Print styles */
@media print 
{
    tr, td, th {page-break-inside:avoid}
    thead {display:table-header-group}
    .NoPrint {visibility:hidden; display:none}
    a {color:#000000}
}

1. The top one prevents page breaks inside of a table row
2. The thead style makes any rows in the thead tag repeat for each page that the table spans across.
3. NoPrint is a class I use to show something on the screen, but not in print.
4. And, I like to turn off link colors.

Use separate CSS for print.

<LINK rel="stylesheet" type"text/css" href="print.css" media="print">

There is another way also.

<STYLE type="text/css">

@media print {

   BODY {font-size: 10pt; line-height: 120%; background: white;}

}

@media screen {

   BODY {font-size: medium; line-height: 1em; background: silver;}

}

</STYLE>

So lets take an example of CSS where we shown two different versions for screen and media.

/* screen display styles */

BODY {color: silver; background: black;}

A:link {color: yellow; background: #333333; text-decoration: none;}

A:visited {color: white; background: #333333; text-decoration: none;}

A:active {color: black; background: white; text-decoration: none;}

H1, H2, H3 {color: #CCCCCC; background: black; padding-bottom: 1px;

    border-bottom: 1px solid gray;}

Here is page for same.

And for printing purpose.

/* print styles */
BODY {color: black; background: white;}
A:link, A:visited {background: white; color: black; text-decoration: underline;
   font-weight: bold;}
H1, H2, H3 {background: white; color: black; padding-bottom: 1px;
   border-bottom: 1px solid gray;}
DIV.adbanner {display: none;}

check page here.

There are some other points like margin, float, hyperlink etc causes printing effect. So here is common CSS for printing.

body {
   background: white;
   font-size: 12pt;
   }
#menu {
   display: none;
   }
#wrapper, #content {
   width: auto;
   margin: 0 5%;
   padding: 0;
   border: 0;
   float: none !important;
   color: black;
   background: transparent none;
   }
div#content {
   margin-left: 10%;
   padding-top: 1em;
   border-top: 1px solid #930;
   }
div#mast {
   margin-bottom: -8px;
   }
div#mast img {
   vertical-align: bottom;
   }
a:link, a:visited {
   color: #520;
   background: transparent;
   font-weight: bold;
   text-decoration: underline;
   }
#content a:link:after, #content a:visited:after {
   content: " (" attr(href) ") ";
   font-size: 90%;
   }
#content a[href^="/"]:after {
   content: " (http://www.shiksha.com" attr(href) ") ";
   }

Hope it will be helpful.