Yahoo to test desktop search

[LennonCook]

Original article

In a step to keep pace with chief rival Google, Yahoo plans to start testing a downloadable desktop search application in early January.

So, does Google officially control Yahoo! yet?
EDIT: And now MSN aswell...

[ 12-12-2004, 06:57 AM: Message edited by: LennonCook ]

[RoSs_bg2_rox]

I think no matter what Yahoo, or anyone else for that matter, does, there will be no competition for Google. It is only a click and a few letters away, and I for one never use anything else these days anyway. Google is all you need.

[philip]

Why would you want an online desktop search or HD search anyway. Every OS out there has its own tools to do that. Besides the m$ version was not secure at all IIRC.

[LennonCook]

Google's desktop search is reportedly alot faster than the Windows Search function... which realy makes me wonder about the programmer(s) who wrote the Windows search...

[aleph_null1]

Google's methods are no secret ...

If you've got enough storage space (i.e. Terabytes at the Mountain View facility) and a shared file structure, you can do anything.

Like make hashtables for EVERYTHING, ensuring a search in constant time of any arbitrary graph.

There really is no competition for constant time ...

[LennonCook]

But, wouldn't constructing those hashtables take linear time? And since a non-Google filesystem is almost guaranteed to change without Google's knowledge, wouldn't said hashtables need to be reconstructed with each and every search? Admittedly, it is more than possible for them to register only the changes to the filesystem in later indexing (effectively speeding it up to logarithmic time), but even the first search is reportedly alot faster than the Windows search. Wouldn't linear (or, if we give MS some credit in their abilities to organise a file system, logarithmic) time on a local system be faster than linear time across the internet to index the system, plus constant time to look it up, plus (probably) logarithmic time to send the data back to the user?
Something just doesn't add up for me, unless MS are truly more hopeless than I thought at designing simple things...

EDIT: Running colours that should have been no colours (typo in the start tag)...

[ 12-13-2004, 02:17 AM: Message edited by: LennonCook ]

[aleph_null1]

Disclaimer: My final in Complexity Theory is on Wednesday [img]graemlins/hehe.gif[/img]

http://www.desktop.google.com/about.html

Though, as usual, they don't come out & say anything straightforward, it sounds like Google Desktop Search builds a massive hashtable when it's first downloaded (the 400K app requires 500 Meg of HD space ), then indexes new documents in real time.

Admittedly, it is more than possible for them to register only the changes to the filesystem in later indexing (effectively speeding it up to logarithmic time), but even the first search is reportedly alot faster than the Windows search.

The "first search" can only be made after the initial hashtable is built (reported to take between 5 and 6 hours, as a background process). Subsequent changes are constant time -- with a 500 Meg contiguous buffer, it's hard to go wrong

So, no, Google goes with massive space waste in return for constant time searches, while MS (yes, I'll give them some filesystem credit) is stuck with O( log(n) ) at best, and possibly O( n log(n) ) if their initial index is retarted.

I've no idea how to factor in the across the internet part ... though I'd wager that, no matter how slow your connection, it'll still be asymptotically constant time.

[Luvian]

I think google products are very close to a legal spywares.

[LennonCook]

Originally posted by aleph_null1: Disclaimer: My final in Complexity Theory is on Wednesday [img]graemlins/hehe.gif[/img] http://www.desktop.google.com/about.html Though, as usual, they don't come out & say anything straightforward, it sounds like Google Desktop Search builds a massive hashtable when it's first downloaded (the 400K app requires 500 Meg of HD space ), then indexes new documents in real time. quote: Admittedly, it is more than possible for them to register only the changes to the filesystem in later indexing (effectively speeding it up to logarithmic time), but even the first search is reportedly alot faster than the Windows search.

The "first search" can only be made after the initial hashtable is built (reported to take between 5 and 6 hours, as a background process). Subsequent changes are constant time -- with a 500 Meg contiguous buffer, it's hard to go wrong

So, no, Google goes with massive space waste in return for constant time searches, while MS (yes, I'll give them some filesystem credit) is stuck with O( log(n) ) at best, and possibly O( n log(n) ) if their initial index is retarted.

I've no idea how to factor in the across the internet part ... though I'd wager that, no matter how slow your connection, it'll still be asymptotically constant time. [/QUOTE]Ok, now that makes sense. [img]smile.gif[/img] I've only come across bits and pieces in random threads on the Mozillazine forums, and not taken any detailed look into it myself (mainly because of the formats they search, I use precisely two: TXT and HTML, and I don't use them for storing detailed information). And since the only indexing these posts mentioned was mostly anti-Google, they implied that all of the indexing was done on the Google servers... Although I do wonder why they do it over the internet if they store the indexed data locally.
BTW, what is Complexity Theory?

Luvian, Google's products do some of the things spyware does, granted, but what they don't do is to make your information accesable. According to their privacy policy, not even Google employees can access to it, unless either a) The person who 'owns' the information asks them to, or b) They get a court order telling them to. And if they break that policy, they are misleading their customers, and I think that that would be illegal. [img]smile.gif[/img] Also, I don't think they store things like your name, age, mailing address... and their privacy policy also says that they don't data mine your documents (which alot of spywares do). To top it all off, they can only store what you give them. Spyware, especially browser helper objects and tracking cookies, will often sit their quietly behind the scenes, recording everything you type into other websites (which is how they can get things like your phone and credit card numbers). Google do admit to a small amount of data mining, though: they track the type of things you search for, and the type of ads you click on, to be able to better target ads at you (which generates them more clicks, and so more revenue).

[aleph_null1]

Time Complexity of a problem: The number of steps that it takes to solve an instance of the problem, as a function of the size of the input (usually measured in bits), using the most efficient algorithm.

http://en.wikipedia.org/wiki/Computa...plexity_theory

There's also space complexity, but Google just brute forces that one [img]tongue.gif[/img]

You've got a really good intuitive understanding of it, sounds like, from your post. All that business about logarithmic time (i.e. O( log(n) ), i.e. log base 2 eventually dominates the function, and is thus an upper bound), linear time, &tc. is from Complexity Theory.

Balanced trees (Red Black trees, for example) can be searched in O( log(n) ). Anything that can be solved by dividing it in half and searching each half (by dividing it in half) is an implicit tree, i.e. O( log(n) ).

Hashtables, if they're big enough that each key maps to a single entry (or at most a few), are constant time -- O( 1 ). So Google just wastes impossible amounts of space to ensure that this happens!