Google Suggest

Cristiano writes "As you type into the search box, Google Suggest guesses what you're typing and offers suggestions in real time. This is similar to Google's 'Did you mean?' feature that offers alternative spellings for your query after you search, except that it works in real time." It crashes Konqueror, but works nicely on Mozilla. Update: 12/11 by J : The engineer who thought of it, then built it in his "20% time," blogs about the process.

/. Spelling

[Zorilla (791636)]

> loose

Google
------
Did you mean: lose?

Yeah, Slashdot needs this badly.

Re:/. Spelling

[MillionthMonkey (240664)]

When I type "loose" it doesn't suggest "lose".

It does suggest "loose women".

Re:/. Spelling

[RobertB-DC (622190)]

When I type "loose" it doesn't suggest "lose".

It does suggest "loose women".

It also suggests "loose weight". I can't believe how many web sites there are devoted to loosing weight. I guess that's the origin of the term, "to throw your weight around" -- so many people loosing it, and throwing weight will certainly loose it. What a bunch of loosers.

(and looking at that paragraph long enough makes me wonder if I've loosed it, myself)

Cool! Just like form AutoComplete

[GillBates0 (664202)]

but with a HUGE database/archive of possible candidates at it's disposal.

Wonder how it'll hold up when it gets out Beta though...it's bound to be pretty computationally intensive.

Re:Cool! Just like form AutoComplete

[mdf356 (774923)]

It's surviving a slashdotting. What more do you want?

Cheers,
Matt

Re:Cool! Just like form AutoComplete

[dustinbarbour (721795)]

Yes, it would be intensive for their server should everyone decide to use it in place of standrd Google search. However, the algorithm behind their "Did you mean" runs in O(n^2) worst case and O(n) best case. Not too shabby.. The algorithm is what makes it possible.

What is n?

[MasterVidBoi (267096)]

I'll try this myself: What does n represent in this case? The number of pages in google's database, the number of words or phrases in their database? The length of the search string?

I would really like to know where you came across this. Can point us to a discription of the algorithm?

Re:Cool! Just like form AutoComplete

[eln (21727)]

big-O notation

(definition)

Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".

Strangely enough, I got this definition from a Google search.

Re:Cool! Just like form AutoComplete

[Chris Mattern (191822)]

Nice, but not answering his question. He didn't ask what O(n) was, he asked what n is, and that's a legitimate question. What *is* n? What is the determining factor of problem size for this algorithm? The number of characters the user has typed? The size of the database of terms Google will search? What?

Chris Mattern

Re:Cool! Just like form AutoComplete

[JabberWokky (19442)]

If it makes you feel any better about Slashdot, there are plenty of people who knew exactly what you're asking and haven't responded because they know enough to know that they don't know the answer. Thus you're only getting responses from people who didn't understand the question.

I'd guess that n will vary between now and when they release as they grow their database.

Interestingly, they seem to clamp down on search phrases that are synonyms and start with the same beginning. For instance, the search for

Re:Cool! Just like form AutoComplete

[TheRaven64 (641858)]

Of course, if you're trying to decide between two search algorithms using the same dataset and one algorithm is O(n log n) and the other is O(n^2) then the Big-Oh comparison actually means something.

Not always. Big-Oh only means the worst case. Quicksort is O(n^2), but the worst case is so rare that it usually performs better than many O(n log n) algorithms.

Re:Cool! Just like form AutoComplete

[ciroknight (601098)]

This is why Google is such an awesome concept.

Instant access to any piece of human knowledge, and it now can guess what you are looking for right as you can type. The only next improvement I can think of is if it did related searches to the term you searched for, but I'm not sure how you would represent all of that data at once. Leave it to the Google geniuses ;)

Advertising potential?

[gavint (785035)]

Looks nice, but what happens when you type "the"?

"the incredibles"

Is anyone else seeing the advertising possibilities?

Re:I call foul: CENSORSHIP

[recursiv (324497)]

I agree with your conclusion, but I just had to stop and point out that you don't condone one-handed sex searching. Hilarious!

Careful though, some pervs our there might think you were talking about wanking, jagging, or otherwise masturbating. (Horrors!) They might not get your true message about amputees.

I keed, I keed. I was just very amused with puritanical way you approached the subject, and that you went the extra step not to condone it.

Re:URL is same, with ?complete=1?

[Wiseleo (15092)]

In the IE version, here is the function (for those curious how it all works, download www.google.com/ac.js)

function jb(){var A=null;
try{A=new ActiveXObject("Msxml2.XMLHTTP")}catch(e){try{A=new ActiveXObject("Microsoft.XMLHTTP")}catch(oc){A=nul l}}if(!A&&typeof XMLHttpRequest!="undefined"){A=new XMLHttpRequest()}return A}

This function is obviously copyright google, inc., but being presented here for educational purposes only.

Re:URL is same, with ?complete=1?

[samrolken (246301)]

This is the same mechanism by which the Gmail application receives its data. It seems like Google has become a big fan of this XMLHTTP object and its Mozilla cousin. It's a great way to give web applications access to live data without requiring a page refresh.

Try this:

[elid (672471)]

Type in g. Then type o. Then type o again. And again. Keep typing o's... Look what happens :-)

Try this:

[AEton (654737)]

Type in g. Then type o. Then type a. Then type t. Aiyeee! I just wanted goat feeding instructions!

Re:Try this:

[kzinti (9651)]

So why is it that goooooooooooooooogle, with 16 o's, has over 23000 hits, while strings with one more or one fewer o have only hundreds of hits?

gooooooooooooooogle 618
goooooooooooooooogle 23,300
gooooooooooooooooogle 198

I thought maybe it was a power-of-two thing, but other such disparities happen at non 2^n transitions. Interesting.

Crashes Konqeuror?

[Shaman (1148)]

Not mine. Worked like a charm. Version 3.3.2 on Gentoo Linux 64bit

Re:Crashes Konqeuror?

[Espectr0 (577637)]

Also, safari works fine

Is it any coincidence

[Moth7 (699815)]

That when you enter "P", the first suggestion is "Paris Hilton"? I guess this just proves that porn really does drive every new technology ;-)

Re:Is it any coincidence

[IdleTime (561841)]

No, it just means that you are a porn freak!

Their suggestions is ofcourse based on earlier interests shown from your ip. So when you type capital P, google knows that you are not intereste in Paris, France but Paris Hilton and no, it's not a hotel!

Re:Is it any coincidence

[Haydn Fenton (752330)]

Haha. What's also cool is 'f' gives 'Firefox' as the first suggestion, it must be making a big impact.

Re:Is it any coincidence

[kzinti (9651)]

There are some other interesting first-suggestions in the alphabet: h suggests "hotmail", and x suggests "x-box" (not, as I was expecting, a porn term). d suggests "dictionary", and o suggests "online dictionary". Most surprising: f suggests "firefox", where the top hit is mozilla.org.

Suggest failed

[SunPin (596554)]

I typed "tits" and it drew a blank.

Advertising potential

[by Anonymous Coward]

I wonder how long it will take before companies are able to pay for their 'suggestions' to show up at the top of the list.

How is it so FAST!?

[topham (32406)]

It is blazingly fast. I expected it to be slowwwww.
Can somebody outline how it works?

Re:How is it so FAST!?

[mbyte (65875)]

hmm, i think it loads the search results in the background. When i type in some text and look at my squid logs i see several of the following queries:

http://www.google.com/complete/search?

So, basicly they use some javascript to handle on keypress event, send the data to google and back, and display them .. but i'm also amazed how fast it is ! (one point can be that the search pages result about 500-1000 bytes ..)

Re:How is it so FAST!?

[loconet (415875)]

Everytime you type a letter, it requests a special modified version of the search tool which only returns the necessary javascript data.

check itout [google.com]

Impressive

Re:How is it so FAST!?

[nacturation (646836)]

Type livesearch into the box and hit I'm feeling lucky. You'll then find the details of what I'm positive inspired this. Essentially, as you type it passes data via an XMLHttpRequest control to the server which then returns a list of the top 10 elements and the page gets updated.

Implementation details

[JavaRob (28971)]

The source for the page is quite simple; most of the work happens in a condensed JavaScript library [google.com]. Not easy reading (note the word "condensed" above, meaning function and variable names are 1 or 2 chars, and all extra whitespace was removed...), but it's actually pretty straightforward.

It disables your browser's autocomplete on that textfield (for obvious reasons). Then it basically just defines a hidden div for that auto-complete dropdown (variations on this depending on browser... frickin' incompatibilities).

Each time you type a character, it populates that div body with the results of a quick, tiny query back to Google. It's NOT running the search for you; it's hitting (I assume) a simple, probably totally in-memory list of the most popular searches and number of results. That's how it can be so quick a response -- the lookup on their end is super-minimal, and the data to be transferred is probably less than 1k each time.

Cool. Nice concept, nice execution. And one of those nice "only obvious in hindsight" additions.

Even cooler -- it looks like (from the js file) they are supporting multiple languages here, not just English. Anyone using want to test this out for me? I think even Chinese is supported (or maybe that's the one that isn't.. I don't want to take the time to parse this properly).

google whacks

[manganese4 (726568)]

Well it definitely makes it easier to look for google whacks

Privacy?

[Frisky070802 (591229)]

I'm surprised no one has commented on privacy yet. It looks to me like it uses past queries to suggest future ones, because as soon as I zoomed in on an unusual name, it offered a couple of bizarre queries that could only have been typos (one was a two-word query, so it wasn't simply every word indexed -- unless they know every pair of words that quickly?).

I don't mind Google knowing what I ask, but I'm not sure I want the world to see them.

I can see it now

[Timesprout (579035)]

"It looks like you are searching for lesbian porn, would you like some help with that?"

"It looks like you are searching for lesbian porn again, do you remember what I showed you last time?"

"I know, I know, Lesbian porn,and can you rate these pages so I can update my page index?"

"Hello freak, try these"

The ABCs of Google Complete

[Hatta (162192)]

A is for Amazon
B is for Best Buy
C is for CNN
D is for Dictionary
E is for Ebay
F is for Firefox (yay!)
G is for Games
H is for Hotmail
I is for Ikea
J is for Jokes
K is for Kazaa
L is for Lyrics
M is for Mapquest
N is for News
O is for Online dictionary
P is for Paris Hilton (wtf?!)
Q is for Quotes
R is for Recipes
S is for Spybot
T is for Tara Reid
U is for Ups
V is for Verizon
W is for Weather
X is for Xbox
Y is for Yahoo
Z is for Zip Codes

Re:The ABCs of Google Complete

[dwvanstone (581420)]

Just to add to the list:

1 is for 1
2 is for 2004 election
3 is for 3m
4 is for 411
5 is for 50 cent
6 is for 60 minutes
7 is for 7th heaven
8 is for 89.com (as bad as Paris Hilton!!)
9 is for 911

Re:The ABCs of Google Complete

[by Anonymous Coward]

Explain THIS though:
x : xbox
xx: xxl
xxx:

p: paris hilton
po: poems
por: porsche
porn:

s: spybot
se: sears
sex:

Somehow, I don't think these are based purely on search requests :)

Re:The ABCs of Google Complete

[kzinti (9651)]

That is based on alphabetics ordering, I think it would make more sense to sort based on rating.

Google is ranking these suggestions so that the ones you're most likely to search for are higher. So even though 's' has more hits than 'spybot', Google thinks you're more likely to search for 'spybot'. That makes sense - the terms people search for most often are not necessarily the pages with the most search results (or the highest Pagerank).

I wonder...

[Lizard_King (149713)]

... how they prioritize the suggestions in the list. It's definitely not by the number of results per suggestion. Are there any revenue opportunities here for GOOG?

What Google needs is Lexis-Nexis and Journal tabs

[F34nor (321515)]

What Google really needs is a for pay LexisNexis tab so you can find real information from real sources in real time. That and a tab that indexes full text medical and science journals. Those damn journals! I love em but I don't have hundreds of dollars a year for each Psych. journal I want to read and hate going to libraries if I just want to see what's shaking in the world of science. With full text periodicals and full test journal search Google would become a singularity of information.

Re:What Google needs is Lexis-Nexis and Journal ta

[brokenwndw (471112)]

You mean like scholar.google.com [google.com]? Or something more where you could pay to get the full text? I definitely wish I could click on Google Scholar's results and get the full text right there with a uniform interface and without having to log in or pay other people.

Re:What Google needs is Lexis-Nexis and Journal ta

[calibanDNS (32250)]

See Google Scholar [google.com] for a service that might do just that one day. It was previously covered on Slashdot here [slashdot.org].

Interesting Political Uses

[ravenspear (756059)]

This was mentioned in another story last night but I thought it was funny.

If you go to the page [google.com] and type "George Bush is a" you get some interesting suggestions. ;)

Re:Interesting Political Uses

[Skeezix (14602)]

Also works for "Kerry is a" and "michael moore is a"

Obfuscated Javascript

[jdludlow (316515)]

http://www.google.com/ac.js [google.com]

The Javascript is ripped to shreds as far as readability goes, but buried in there somewhere is the key to making your own app based on this. If you were so inclined to piggy-back on top of this technology. Not that I'd advocate such things.

// Copyright 2004 and onwards Google Inc.

var w="";var pa=false;var ta="";var da=false;var g="";var G="";var m="";var j=-1;var h=null;var Z=-1;var za=null;var Ca=5;var q="";var Lb="div";var Bb="span";var la=null;var a=null;var b=null;var Xa=null;var mb=null;var X=null;var ha=null;var ra=false;var kc=null;var hc=null;var Ua=new Object();var ca=1;var Aa=1;var Y=false;var na=-1;var Va=(new Date()).getTime();var Q=false;var k=null;var sa=null;var E=null;var B=null;var aa=null;var Ba=false;var Ka=false;var p=60;var ia=null;var ya=null;var W=0;InstallAC=function(frm,fld,sb,pn,rl,hd,sm,ufn) {la=frm;a=fld;Xa=sb;if(!pn)pn="search";ia=pn;var Kb="en|";var Jb="zh-CN|zh-TW|ja|ko|vi|";if(!rl||Kb.indexOf(rl+" |")==-1)rl="en";ha=nb(rl);if(Jb.indexOf(ha+"|")==- 1){X=true;Y=false;Ba=false}else{X=false;if(ha.inde xOf("zh")==0)Y=false;else Y=true;Ba=true}if(!hd)hd=false;ya=hd;if(!sm)sm="qu ery";w=sm;mb=ufn;ac()}
;function Yb(){ra=true;a.blur();setTimeout("sfi();",10);retu rn}
function Fb(){if(document.createEventObject){var y=document.createEventObject();y.ctrlKey=true;y.ke yCode=70;document.fireEvent("onkeydown",y)}}
func tion nc(vb){var y=document.createEventObject();y.ctrlKey=true;y.ke yCode=vb;document.fireEvent("onkeydown",y)}
funct ion gc(event){}
function ic(event){}
function Pb(event){if(!event&&window.event)event=window.eve nt;if(event)na=event.keyCode;if(event&&event.keyCo de==8){if(X&&(a.createTextRange&&(event.srcElement ==a&&(bb(a)==0&&lb(a)==0)))){cc(a);event.cancelBub ble=true;event.returnValue=false;return false}}}
function mc(){}
function Db(){if(w=="url"){Ha()}ba()}
function ba(){if(b){b.style.left=ob(a)+"px";b.style.top=Qb( a)+a.offsetHeight-1+"px";b.style.width=Ja()+"px"}}
function Ja(){if(navigator&&navigator.userAgent.toLowerCase ().indexOf("msie")==-1){return a.offsetWidth-ca*2}else{return a.offsetWidth}}
function ac(){if(jb()){Q=true}else{Q=false}if(pa)E="complet e";else E="/complete/"+ia;sa=E+"?hl="+ha;if(!Q){qa("qu","" ,0,E,null,null)}la.onsubmit=Fa;a.autocomplete="off ";a.onblur=Ob;if(a.createTextRange)a.onkeyup=new Function("return okuh(event); ");else a.onkeyup=okuh;a.onsubmit=Fa;g=a.value;ta=g;b=docu ment.createElement("DIV");b.id="completeDiv";ca=1; Aa=1;b.style.borderRight="black "+ca+"px solid";b.style.borderLeft="black "+ca+"px solid";b.style.borderTop="black "+Aa+"px solid";b.style.borderBottom="black "+Aa+"px solid";b.style.zIndex="1";b.style.paddingRight="0" ;b.style.paddingLeft="0";b.style.paddingTop="0";b. style.paddingBottom="0";ba();b.style.visibility="h idden";b.style.position="absolute";b.style.backgro undColor="white";document.body.appendChild(b);Ma(" ",new Array(),new Array());Gb(b);var s=document.createElement("DIV");s.style.visibility ="hidden";s.style.position="absolute";s.style.left ="-10000";s.style.top="-10000";s.style.width="0";s .style.height="0";var M=document.createElement("IFRAME");M.completeDiv=b ;M.name="completionFrame";M.id="complet

Yippee! A new source of amusement!

[slcdb (317433)]

I got a real kick out of some of the suggestions.

my cat: ... hates you ... breath smells like cat food ... hates me ... is an alien

my girlfried:
(No suggestions, obviously Google is run by a pack of lonely nerds).

my boyfriend: ... is gay ... sucks ... cheated on me ... hates me ... dumped me
(Okay, make that an apparently gay pack of lonely nerds).

darth vader is: ... gay
(A delusional pack of gay nerds?)

Oh, the fun I'll have with this new toy when I'm bored at work.

Re:Great..

[APDent (81994)]

Except, if you actually watch the drop-down list as you're typing, once you've typed "nia", it's already suggesting "niagara falls" with the correct spelling and 3,090,000 results. True, "niagra falls" (incorrectly spelled) is also in the list, but since it only has 129,000 results, it's probably clear which one you're actually looking for if you're not trying to make a joke about Viagra.

This is pretty amazing, really.

Re:Wow

[Freexe (717562)]

Its javascript, using the XMLHTTP object to communicate with the server directly

You can see it http://www.google.com/ac.js cant say i understand it, Gmail using the same thing but way more advanced.

Re:Google starts to suck

[diamondsw (685967)]

So they screwed up Groups. What does that have to do with Suggest, which looks like a classic "awesome! why didn't anyone else do it that way?" Google feature?