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.

Crashes Konqeuror?

[Shaman]

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

Re:Cool! Just like form AutoComplete

[dustinbarbour]

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.

Browser Wars

[alva_edison]

Before more people complain that their browser doesn't work, here's [google.com][labs.google.com]what google specifies as the browser requirements.

Re:How is it so FAST!?

[mbyte]

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:Crashes Konqeuror?

[Espectr0]

Also, safari works fine

Re:Advertising potential

[luuc]

Type in:

a => amazon
b => best buy
c => cnn
e => ebay
f => firefox (!)
h => hotmail
i => ikea
m => mapquest
u => ups
v => verizon
x => xbox
y => yahoo

Great...

Hmm. Does interfere with FireFox autocomplete

[DollyTheSheep]

I have a list of queries, which I repeat every day or week or so. FireFox has now gathered them in its own form autocomplete. Now google interferes that with queries, I don't want to submit.

Re:Cool! Just like form AutoComplete

[eln]

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:What Google needs is Lexis-Nexis and Journal ta

[brokenwndw]

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:How is it so FAST!?

[nacturation]

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.

Re:The ABCs of Google Complete - The 123s

[highway40]

0 is for 02
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
9 is for 911

Implementation details

[JavaRob]

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).

Re:The ABCs of Google Complete

[witcomb]

That is based on alphabetics ordering, I think it would make more sense to sort based on rating. That has a little more significance when it comes to google.

A is amazon
B is for BBC
C is for cars
D is for Dell
E is for Ebay
G is for games
H is for http
I is for index
J is for jobs
K is for kelkoo
L is for love
M is for music
N is for news
O is for online games
P is for pubmed
Q is for quotes
R is for ringtones
S is for s (that is weird)
T is for target
U is for UPS
V is for virgin
W is for weather
X is for xbox
Y is for Yahoo
Z is for zdnet

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

[calibanDNS]

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

Re:Cool! Just like form AutoComplete

[Anonymous Coward]

n is the number of entries in the search database. In a search, n mostly refers to the sample space of the objects to search.

Re:Interesting Political Uses

[Skeezix]

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

Re:Obfuscated Javascript

[nacturation]

Why not grab a legal version [bitflux.ch] from the LiveSearch wiki page, which is given away under the Apache license?

Re:Cool! Just like form AutoComplete

[nacturation]

In your rush to point out you know more than the above poster, did you stop to consider that he might not be asking about the notation? I don't understand what n is supposed to be either. Do you? If you do, why don't you clue us in, instead of your smug arrogance. In case you are still missing it, I do know how O(n) notation works. So does the poster above.

Big O notation [wikipedia.org] refers to the efficiency of the algorithm. If you really understand the notation, you wouldn't be asking what 'n' means. The original post stated that the "Did you mean..." algorithm is O(n) efficient. If it stated that the algorithm is O(1) efficient, would you ask what the 1 represents?

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

[Deag]

It does go back to the server, load the page and kill your internet - it will no longer work.

Re:Try this:

[Underholdning]

Three words: Ads by goooooooooooooooogle

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

[Wiseleo]

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:The ABCs of Google Complete

[geekguy]

They seem to have linked it all under pr0n, that brings up lots of choices.

Re:The ABCs of Google Complete

[h4ter]

'porn' isn't there, but 'pr0n' is.

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

[samrolken]

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.

Re:Cool! Just like form AutoComplete

[Herbmaster]

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.

Furthermore, Big-Oh only means an upper limit on the worst case. Quicksort is O(n^4), and O(n^5), and O(n^6). It also happens to be O(n^2), which is a much more useful statement. For some reason people like to talk about Big-Oh even if they really mean Big-Theta.

Re:Privacy?

[tyler_larson]

I'm surprised no one has commented on privacy yet.

You wouldn't have been so surprised if you had done what the rest of use did and READ THE FAQ!

http://labs.google.com/suggest/faq.html [google.com]

You would have found it if you had clicked the "Learn More" link prominantly displayed on the page.

Your own previous searches are not used at all in determining results. The results you see are exactly the same results everyone else will see. You're sending the same information to Google that you send in a normal search (i.e. your query). Google is sending the same information back to you that they normally send (the results). The only things that's different is that they send each of the little pieces of it as you type them.

No one has commented on privacy yet because privacy is irrelevant. No one has commented on terrorism yet either, does that surprise you?

Re:Implementation details

[starrsoft]

No it doesn't support other languages... yet. Google Suggest FAQ [google.com]:

When will you support other languages?
We're not sure yet. But we're always interested in expanding our products into more languages, and hope to be able to offer you such services soon!

One more thing..

[Egorn]

Ohh! One more thing I just found, check it:

http://www.google.com/complete/search?hl=en&js=tru e&qu=natalie%20portman [google.com] - The results in a nice pretty array!