Learning About Full-text Search

An anonymous reader writes "Tim Bray who's known for XML and has been /.'ed once or twice for that kind of stuff, actually seems to be a search geek and has been writing this endless series of essays on search technology since summer. He says he's finished now - it's like a textbook on searching."

Comments

Search this

[Anonymous Coward]

fp linux nerd

Salute

[grub]

..and has been /.'ed once or twice..

You mean two or three times now.

Re:Salute

[Anonymous Coward]

slashdotted++

Re:Salute

[antarctican]

..and has been /.'ed once or twice..

You mean two or three times now.

And it's my poor server that has to bare the burden.... but so far it's held up fairly well each time. Pretty good for a celeron 1.7GHz w/ 256M. :)

However this time was particularly bad because of it being a series of essays. I just increased the number of instances of Apache by 66% and doubled the number of requests before a child dies. That seems to have brought some responsiveness back.

Funny thing is I didn't even know he was /.'ed until he emailed me. I went to check my email (via pine) and the console was as responsive as usual.

For the geeks who enjoy technical detail... it's running on an Inspire cube PC, one of those little cubes with a mini-ATX in it. Shows you don't see a lot of horse power to serve static content. :)

web page irony

[Savatte]

He writes about seaching technology, but you can't easily search through his writings.

Re:web page irony

[Anonymous Coward]

How do I do a keyword search of the new textbook on searches?

Re:web page irony

[Dreadlord]

too bad his pages are valid XHTML documents, it would have made an excellent +5 funny comment :(

Re:web page irony

[Anonymous Coward]

>too bad his pages are valid XHTML documents, it would have made an excellent +5
>funny comment :(

Why does having xhtml documents automatically confer searchability? Do xhtml webpages come with built in search code? No, not they don't.

Re:web page irony

[Anonymous Coward]

they don't, but the parent post is about finding some conflict between the author's pages and aticles.
He's got an article about searching and his pages aren't searchable, and he's got articles about XML, so having non-valid XHTML pages would definitely have been ironic...

Re:web page irony

[arrogance]

Well, especially when it's been slashdotted. Here's a google cache hit to part of his writings.

I agree that it doesn't look to be easy to search around, at least when all you have is an URL to go on (http://www.tbray.org/ongoing/When/200x/2003/07/30 /OnSearchTOC) and Google to find reachable material. I'm also not too sure about using dates as folder names but that's just a personal thing: I think Tim Berners Lee recommended it at one point in an article "Cool URI's don't Change". He does recommend using "Latest" or some such instead of the creation date in a URI, though, if "there is no reason for the persistence of the URI to outlast the magazine." It might make things easier to search for though, at least if you know when it was created: if the URIs aren't changing then you won't have tons of broken links.

Re:web page irony

[Schwarzchild]

He writes about seaching technology, but you can't easily search through his writings.

Really? How about search site:tbray.org?

Re:web page irony

[Anonymous Coward]

Tee hee, I get it now. It reminds me of this time that something didn't happen, but if it had happened, it would have been funny. Ha ha, that still cracks me up. Yes, most amusing.

TOAST!!!

[Anonymous Coward]

toaster,toaster toaser, do you have toast in you yet i think
so!!!!!!!!!!!!!!!!!!!Im not a toaster!!!!!!!!!!And one more
thing........YOUR A TOASER!!!!!!!!!!!!!! AND A COOKIE WITH MILK SOAGE
MILK!!!!!!!!!!AND A BUTT WITH POOP IN IT!!!!!!!!!!!!!!!!

Hold on there

[arvindn]

...has been writing this endless series of essays on search technology since summer. He says he's finished now...

Finished an endless series?

Re:Hold on there

[MooCows]

The maximum number of results have been returned.

Re:Hold on there

[Dreadlord]

Maybe we have just hit +Infinity of time?
Time flies when we're sitting in front of our comps, reading /.

Re:Hold on there

[Lozzer]

In the first three months he wrote a page, in the next month and a half he wrote another page, in the next (scratching of head) three quarters of a month he wrote another page, and so on. Now after six months he has written an endless amount of stuff, simple (yet amazing) really.

Re:Hold on there

[haystor]

He wrote them in a circle.

books for losers

[Anonymous Coward]

how gay of a book to write

Tim Bray?

[Anonymous Coward]

Wasn't he the geek on Riptide?

Re:Tim Bray?

[Anonymous Coward]

>>Wasn't he the geek on Riptide?

Yes, Thom was his stage name IIRC

Osaka man arrested for spitting on schoolgirl

[Anonymous Coward]

OSAKA -- A man who spat on a high school student was arrested after being caught-red-handed at a station in Settsu, Osaka Prefecture, police said Tuesday.

The man, Kazuhiko Ukita, 31, was arrested for spitting on the back of the 17-year-old student at JR Senrioka Station in Settsu at about 7:25 a.m. on Tuesday.

Investigators said the student was using JR to get to Kyoto Station while she was on her way to school. She had noticed what appeared to be spit on her uniform about 10 times in the past, and had discussed the problem with the Kyoto Prefectural Police railway police unit.

A member of the unit accompanied the student as she was on her way to school on Tuesday, and caught Ukita, a resident of Suita, Osaka Prefecture, spitting at her.

Police said they suspected Ukita was involved in other similar crimes and they were continuing to question him.

wow this is exciting

[Anonymous Coward]

Although it looked like a decent set of articals, I'm sure it would only be useful to me as a sleep agent...

poor guy

[understyled]

i cringe at the bandwidth demands a slashdotting can bring with it. here's google's cache of the page.

Re:poor guy

[martingunnarsson]

If Google can cache pages and put them online, so should Slashdot. People say copyright issues would be a problem, but in that case, why is Google's online cache any better?

Re:poor guy

[Anonymous Coward]

The idea being people would visit the cache before the actual site. What if the site added an ammendum? Google Cache is a pain in the ass JUST ENOUGH that you will try the real link first.

Re:poor guy

[ihummel]

Google is a search engine used and respected by virtually everyone. Slashdot is, well, Slashdot.

Also, I believe that Google respects instructions in the robots.txt not to cache their page.

Re:poor guy

[martingunnarsson]

So could Slashdot do. Hehe, it's actually kind of funny! The webmaster's choises would be:
1) Allow Slashdot to cache the site
2) Get the site slashdotted back to the stoneage

Nothing wrong with some maffia methods every now and then!

Re:poor guy

[Arslan ibn Da'ud]

Slashdot has already considered this. RTFFAQ

Re:poor guy

[ihummel]

I think the main problem is that the guys who run slashdot would probably need to get permission beforehand to cache the linked page, and it would take too much time out of their day to email back and forth to every linked site. Sure, J Random Hacker wouldn't mind being cached, but CNN, News.com.com.com.com.com, and the New York Times just might. And they would have enough bandwidth to handle the Slashdotting.

Re:poor guy

[davew2040]

And they considered incorrectly.

Re:poor guy

[davew2040]

Too much out of their day? Out of the 15 sites they link every day, they can't be bothered with asking because of *time constraints*?!

Apparently it's more acceptable to them to knowingly blow sites out of the water (they even joked about it in this post) than to spend the time to fire off an email. The fact is, they don't even want to try.

Re:poor guy

[martingunnarsson]

Google isn't asking for permission. Again, Slashdot could obey to the rules in robots.txt.

Re:poor guy

[ihummel]

Google is Google and Slashdot is Slashdot.

But even if the issue of liability were taken off the table, they would still have to get off of their metaphorical butts and set up a caching system. I don't know if there is any usable open-source system currently in existence, but if not, they would either have to code it themselves or adapt something already out there that doesn't serve their needs. Disk space isn't really an issue, as the commenting system takes a lot more space than the cache would (assuming they didn't mirror isos or anything silly like that).

Re:poor guy

[johnteslade]

The site is still slashdotted. Each of his papers are on separate pages so here are the google caches of the individual papers:

• Table of Contents
• Chapter 1: Backgrounder
• Chapter 2: The Users
• Chapter 3: Basic Basics
• Chapter 4: Precision and Recall
• Chapter 5: Intelligence
• Chapter 6: Squirmy Words
• Chapter 7: UI Archeology (No Cache)
• Chapter 8: Stopwords
• Chapter 9: Metadata
• Chapter 10: I18n
• Chapter 11: Result Ranking
• Chapter 12: Interfaces
• Chapter 13: XML
• Chapter 14: Robots

I have to write some crap at the end here so i can get past the "Your comment has too few characters per line" error message.

Re:poor guy

[spectre_240sx]

I don't know about that. There seem to be too many problems associated with caching. One that comes to my mind is the extra bandwith that they would have to worry about. An Article about the design of the site mentions that just changing over to CSS made a grand savings of 3-14 GB a day equalling something like $3,600.00 in the end. Now that's just by cutting 2-9KB off every page request. Now, think about them serving (possibly) huge pages from other sites that may not optomize their code... That's a lot of money that slashdot would have to spend.

Re:poor guy

[davew2040]

Well then, I guess slashdot would learn firsthand about the slashdot effect!

Re:poor guy

[spectre_240sx]

Umm, I think they already do when you consider the amount of people who come here. Remember how often people say RTFA? If only those who view the articles cause "the slashdot effect" Imagine how much traffic slashdot already gets.

Re:poor guy

[The Unabageler]

I always called it a recursive wget.

Re:poor guy

[Nucleon500]

Their concern is that commercial sites will feel cheated out of ad revenue. But this problem is trivial to avoid: Don't cache pages initially, but have a system for caching them quickly if the webmaster asks. The stories wouldn't be delayed, but when they are accepted, a notification would be sent and a copy made. When the webmaster asks to be relieved, the links in the story would be changed to the cache.

Re:poor guy

[gangien]

So the quick answer is: "Sure, caching would be neat." It would make things a lot easier when servers go down, but it's a complicated issue that would need to be thought through in great detail before being implemented.

this is incorrect?? thinking about the implications of copying something and putting it on your server is incorrect?

Re:poor guy

[1iar_parad0x]

How much code does it take to mirror a simple site? I think I could copy the site and set up a link in Perl pretty easy. The hardware seems to be the tricky part.

On a related note... How does Slashdot avoid the Slashdot effect?

Re:poor guy

[Anonymous Coward]

How does Slashdot avoid the Slashdot effect?

The same way the ocean avoids getting flooded by the Nile. Distribution and lots of room.

Like...wow.

[gregarican]

it's like a textbook on searching. Like wow, dude. This sounds like it was submitted by Butthead.

Anderson in the Burger World drive thru: Did you get the order? Hello?

Butthead through the loudspeaker: We're like closed or something?

Re:Like...wow.

[no reason to be here]

Actually, this is one of the few times that someone used "like" correctly. The linked documents are not a textbook on searching; however, they are similar to a textbook on searching. It is, therefore, apropriate to use the preposition "like," since the linked essays are, in fact, like a textbook on searching.

Re:Like...wow.

[khamar]

From what I can see through the war-haze of ./ing these articles are more like a blog. Are we confusing "essay" and "like a textbook" with some random ideas?
I really like this guys comments, but would not confuse them with a textbook.

Favorite idea: 'Turn on Search' built-in to Apache. This should be a standard feature.

Of course, others have already started working on a flash version before this blog was written.

re-inventing the wheel

[peter303]

Try Knuth Vol 3.

Re:re-inventing the wheel

[Anonymous Coward]

Knuth is the most over rated, over read author, perhaps of all time.

And the crib sheets are even worse.

And surely you should be referring the very end of the 3rd volume.

Re:re-inventing the wheel

[Anonymous Coward]

> Try Knuth Vol 3.

Can't afford it. This is freely downloadable. Knuth loses.

Re:re-inventing the wheel

[Anonymous Coward]

Really? How much is there about Google in Knuth?

Re:re-inventing the wheel

[Anonymous Coward]

"Knuth is the most over rated, ..."

A common complaint from people who doesn't understand his books...

Re:re-inventing the wheel

[Anonymous Coward]

Try reading the articles/essays. Knuth's vol 3 is about comparison search, not full-text search.

Re:re-inventing the wheel

[getarun_vr]

Maybe search technology has changed a lot since Kuth days. If one cursorily glances through the last coupla journals on Information Search and Retrieval, one cannot help the heavy influence of PageRank (Google's own technology). Thankfully the algorithm is well known. On the flip side, Critics have often asked wheather such algorithms be published? The bloggers have demonstrated that even Google rankings can be rigged... Personally, I would choose the open architecture philosophy, due to parallels with the ideas of Bruce on cryptography. A peer reviewed system is always better than a closed proprietery system.

Re:re-inventing the wheel

[Anonymous Coward]

Managing Gigabytes by Ian Witten, Allistair Moffat, Timothy C. Bell is far more relevant to full-text searching.

Re:re-inventing the wheel

[Anonymous Coward]

You have that backwards. PageRank was heavily influenced by other systems, like Harvest. And full-text search has changed very little since Knuth. For instance, the basic extact string matching algorithms haven't advanced at all.

Re:re-inventing the wheel

[Anonymous Coward]

Thanks for the recommendation, that book's bound for my Amazon wishlist.

Re:re-inventing the wheel

[Anonymous Coward]

For a solid grounding in the subject, I would highly recommend (in addition to Knuth):
Pattern Matching Algorithms
by Alberto Apostolico and Zvi Galil
ISBN: 0195113675

Re:re-inventing the wheel

[Anonymous Coward]

Really? How much is there about Google in Knuth?
Very much. I seriously doubt that Google would consider hiring anyone who isn't at least familiar with Knuth either directly through his Art of Computer Programming, or indirectly through Sedgewick's works, Aho's works, Rivest's works, and perhaps every book on data structures, algorithms, and the running time of programs out there, because, eventually, they most all lead back to Knuth. Not to mention the fact that most mathematics texts as well as most technical texts in publication today use Knuth's TeX program or one of its derivatives in some form or another for their creation.
So, it's probably safe to say that Google probably would not exist if it weren't for Knuth.

Interesting stuff!

[clifgriffin]

Though, I'm unaware of how to apply this to my life. I think I'll take it and put it in the "Unaware of How to Apply This to My Life" Stack with The Simpsons and The Internet.

Re:Interesting stuff!

[KoolDude]

I'm unaware of how to apply this to my life. I think I'll take it and put it in the "Unaware of How to Apply This to My Life" Stack with The Simpsons and The Internet

But what if your stack grows big and you need to search through the stack ?

Re:Interesting stuff!

[Anonymous Coward]

If you're searching a stack, the best you can do is pop it until the thing you're looking for is on top.

Re:Interesting stuff!

[stoborrobots]

Actually no... one of the interesting things is that it is far more efficient to "scan" through a stack than to pop it if you're looking for something... (Assuming you have an in-memory stack, which is easily manipulated by memory operations as well as stack ops.)

It breaks the abstraction, but the improvement may actually be worth it sometimes...

Anti-XML

[MattRog]

Whether there's going to be a lot of XML around in repositories to search. XML these days is more used in interchange rather than archival applications.

Why the fascination with XML? Well, I certainly know the reason why *Tim* is fascinated, but I want to know why he's seriously contemplating reinventing the wheel - namely using XML as data storage when we already have gobs and gobs of systems (think SQL DBMS products) that do this in a much faster, more compact, safer, better way.

Also, most SQL DBMS (Oracle, Sybase ASE, MS SQL, etc.) come with full-text indexing built in, so all it would take would be to chop up HTML pages and stick them in the DBMS, then you can perform rich-text queries on them with minimal effort.

Re:Anti-XML

[SillySnake]

I thought Longhorn was going to use some sort of XML file system? Or at least there were thoughts about it?

Re:Anti-XML

[Havokmon]

namely using XML as data storage when we already have gobs and gobs of systems (think SQL DBMS products) that do this in a much faster, more compact, safer, better way.

I'm with ya there buddy.. If it wasn't for a corporate buyout, my OS/2 box with REXX scripts would still be ftp'ing files (I was really hoping for 10 years - but I've been gone for 3 now).

Now they'll do it in some xxx.Net, because it's all new and cool. Whatever, at least my stuff was readable with 'edit'.

Re:Anti-XML

[phurley]

I agree to a point, but if we are talking about a mixed environement where you are using Oracle, I am using DB2, our friend Bob has his data in a legacy ISAM setup and a customer wants to integrate a search system across the tree systems they are going to have to write a lot of custom glue.

If an XML aspect of the data is available (you can still keep it all in Oracle - just provide a "view" of it in XML) from each of us - common search tools and methods can be utilized.

Re:Anti-XML

[arrogance]

He even goes so far as to mention that Index Server will search your website: but fails to mention that it does full text searching on your entire file system.

Unfortunately his site (http://www.tbray.org/ongoing/) seems to be sufficiently disorganized that I have trouble finding out what his real points are, or whether he's addressed all of the issues: for example, I saw no mention of the Semantic Web if his concern is searchability on web documents.

As a side note, MS SQL is going more and more toward XML, as is the whole .NET framework. This results in richer (read: fatter) data but it does mean that you can store whatever metadata you want along with it.

Re:Anti-XML

[Hayzeus]

I don't really get the advantages of XML Data storage either, but when it comes to emitting data in a generic, interoperable, self-describing format, XML works quite nicely, even if it is a tad verbose.

Which (slightly OT) reminds me: has anyone here used an XML compression tool, that they'd like to share opinions on? I've looked at XMLPPM briefly but not worked with it yet. Any others?

Re:Anti-XML

[MattRog]

I don't think writing your own DBMS engine (with query, data management, concurrency, etc.) support is going to be 'less' work than simply either ensuring that your SQL works with different vendors or writing small data pieces to talk to a number of DBMS products.

You could, of course, bundle an existing DBMS product into the application which would remove the limitation of being forced to use the customer's DBMS product.

Re:Anti-XML

[anomalous cohort]

From the google cache...

searching for words isn't really what you want to do. You'd like to search for ideas, for concepts, for solutions, for answers.

That is why he is going in an XML direction. The relational approach is rectilinear and requires that the information be framed in a highly normalized fashion. Generalized semantic searching is highly non-normalized because, well, humans are highly non-normalized.

I think that he should look at some work by a different Tim, the Semantic Web.

Re:Anti-XML

[MattRog]

The relational approach is rectilinear and requires that the information be framed in a highly normalized fashion. Generalized semantic searching is highly non-normalized ...

That makes absolutely no sense.

Re:Anti-XML

[anomalous cohort]

Hmmm, perhaps a visit to a dictionary is in order. Once you read the definitions for rectilinear and normalized, I'll think you'll find the sense of the post.

This is a sound strategy any time you run into a message that makes no sense. Simply look up the definitions of the words that you don't know.

Re:Anti-XML

[MattRog]

It doesn't make any sense because it's meaningless. Try and provide reasoning why you think this sort of information can't be modeled relationally.

Re:Anti-XML

[cthrall]

SQL dbs might come with full-text indexing, but the power of information retrieval really comes into play when you can start clustering, using stemmers to find people/places, etc. Db full-text indexing feels more like a feature checkbox than a real information retrieval system.

XML can be useful because you can take data from disparate sources (an Exchange server, SQL db, etc.) and normalize the meta data (the document author, date the document was created, etc.).

I agree there's an overwhelming "silver-bullet" feel about XML sometimes, but it can definitely help in this case.

Re:Anti-XML

[I8TheWorm]

I tend to get on an XML soap (no pun intended) box when I see articles about it, so here goes...

XML is great for sharing data between non-congruous systems. It's horrible, however, for storing data in any large quantity, and even more horrible for treating as a searchable text file. It's inherintly large and full of ascii/ansi/utf characters that are completely unnecessary when performing byte by byte text searches. For large amounts of data, you're right... RDBMS is the current way to go... maybe OODBMS will be in the near future, but I still haven't tinkered with it myself and don't have any opinions developed yet.

XML is not the data end-all... same as __insert_your_own_programming_language_here__ is not the end-all of programming. It's a nice tool, but tends to be overused because it's still a buzz-word.

Re:Anti-XML

[DrVomact]

The reason why XML is widely used today for a multitude of purposes (e.g., data interchange between otherwise incompatible systems, configuration files, technical documents, command protocols that communicate with servers, etc. etc.) and why it will be used for even more stuff in the future is that it is centered on a very simple and powerful idea: self-documenting data. That is, the data is structured by internal markers that give information about the type of information contained in each logical element of the data stream (or file). Naturally, the XML geeks are doing everything they can to complicate this simple idea, but I digress...

Because XML files are structured, self-documenting text files that correspond to a formal definition (I know DTDs aren't technically required for "well-formed" XML, but you really don't want to do that), you can rely on your data being usable without making assumptions about the type of systems that will use it (OS is irrelevant, applications can have front and back ends that understand XML). Moreover, this compatibility isn't going to go away: it's just pure text--we will always be able to read it.

I have no idea whether the databases of the future will store their data in XML form or not. I'm not a database expert, but I suspect there are more efficient ways of storing and searching information than in huge chunks of tagged text. However, while a database that stores its data in a rigid table format may be quicker and more compact, it cannot preserve the richness of meta-information contained in an XML tagging system. If you put your XML into a traditional database, you won't be able to take advantage of being able to make searches based on information in the tags.

Be that as it may, the the fact remains that you will at least be able to feed your database XML, and get XML out of it. That means that the XML front end will parse the XML input data, and will be able to figure out how to organize your data in its innards based on the information provided by the XML tags in the data you give it. When you make a query (probably formatted as XML by the query software), the data will be returned as XML using the tag scheme specified in your DTD.

Another consideration is that you can store much more information about your data with an XML tagging scheme than you can with any database format--and you can communicate that information when you send your data to someone else, because the metadata is part of the data. I work with huge texts (technical manuals, actually) and I heartily welcome the flexibility and usefulness of being able to identify parts of that text based on any criteria that are meaningful to me or the consumer of the data.

Re:Anti-XML

[platypus]

Because you'd (for example) have to provide a relational model for the semantics of the english language. And even that wouldn't meet the criterium of "generalized", because, ehm, it's specialized for the english language.

Re:Anti-XML

[gorilla]

Call me stupid if you like, but I don't see how the representation of the data helps to search for ideas concepts etc. Regardless of how the text is stores, unless you have a human do a lot of markup on the text, then you're going to have a problem in extracting the ideas from the text. And by markup I don't mean Heading I mean some entering what the ideas, concepts etc are for each part of the text - which can be done equally easily in a traditional database as in a XML document.

Re:Anti-XML

[platypus]

Err, missed some context in this thread, clearly, XML as opposed to relational wouldn't help here either.

Re:Anti-XML

[radio4fan]

for example, I saw no mention of the Semantic Web

Try here on the page about metadata.

Re:Anti-XML

[cthrall]

The problem isn't that the information can't be modeled in a relational manner, you could easily use a relational database for your data store.

The problem is retrieving information to index. You pull information from existing data sources that have never heard of your data model and don't care. XML provides a simple way to map your existing content to some standard design that you come up with. That's the "normalization" step, and one of the harder parts of indexing.

Re:Anti-XML

[cthrall]

You can use stemmers, term frequencies and relative location in a document to provide some general gist of what a document is about. The whole point of creating advanced information retrieval tools is to make information processing a more automated task.

Re:Anti-XML

[gorilla]

Yep, but what difference does it make if the text is stored in XML or in a database?

Re:Anti-XML

[Anonymous Coward]

Sigh. Yeah, you're an idiot. I do (and have done for about 5 years) many IE/IR systems. "Generalized semantic searching" as you want to call it is actually a highly structured exercise. Most systems don't use databases to do the work because it is the opposite of that, so simply done that there is no reason for a database. It could be represented in a relational format, just like any large search engine, and tagger appropriately (word order information and such), but most systems work on small chuncks of text.

Sorry, please try again.

Re:Anti-XML

[Anonymous Coward]

I'd just like to point out that Tim specifically says that he is "going to use XML syntax, because it's reasonably readable... This is not to suggest that you'd actually store a search engine's document table in XML. You might (I wouldn't), but the point is the XML is being used here as an expository device.".

So he isn't suggesting "reinventing the wheel" at all.

Re:Anti-XML

[cthrall]

The XML part comes in when you are extracting content from an existing data store. You can use a relational database for a backend store, but when you're going through the step of mapping existing content to the info your indexing engine wants (the normalization step), XML is very handy.

Re:Anti-XML

[kirkjobsluder]

True, the problem is that HTML became such a beast mixing semantic markup with visual markup that it is really hard to find well-marked up documents.

Still, while it is possible to convert any form of data into a relational database, does that mean that the relational database is the best fit for all types of data?. One of the things that XML does well but relational databases don't do well (without a lot of violent shuffling around) is arbitrary parent-child relationships. So for example, a typical paper might have:

[frontmatter]
-[title]
-[author]
-[contact info]
-[abstract]
[section]
-[paragraph]
-[par agraph]
-[blockquote]
-[paragraph]
-[image]
-- [caption]

etc. etc..

Why go through the problem of chopping this up and normalizing the data if you don't have to? Especially if you give the people who are producing the content a template and schema that produces well-formed semantic XML or can process existing texts with some assumptions?

Re:Anti-XML

[kirkjobsluder]

I didn't get that impression from the article that he was considering XML as data storage. I saw the point as being that we don't know how much XML a search system will have to process. If your data consists of a large number of OpenOffice, DocBook, XHTML or Framemaker documents, then it might just be easier to keep things in XML rather than to split the data apart into a bunch of atomic chunks.

I love using RDBMS but for some applications, creating a normalized database is a pain in the rear. Bibliographic information for example requires three tables for author-article relationships. (And this is not getting into the fact that journal articles usually have a volume number while articles do not, inheritance of publisher's information from anthologies to individual book chapters, and the tricky difference between newspaper and academic citations.) I don't see RDBMS systems as a natural choice for structured documents that may have an arbitrary structure.

Re:Anti-XML

[Pseudonym]

XML is almost ideal for storing structured text in large quantities. Storing non-textual data, not so much. (This is one reason why XML gets a bad reputation for data representation; people are using it for tasks which are not textual markup-related.) For byte-by-byte searching... true enough, it sucks for that. But surely if you have text in large quantities, you're hardly going to search it using "grep". That would be insane whether it's stored in XML or plain text.

Re:Anti-XML

[Pseudonym]

Relational databases and full-text indexing are a poor fit once you have a lot of text to store. Yes, I know. Most SQL DBMS come with full-text indexing. That's not enough. Read on for the reason why.

Think about how a relational DBMS works. Internally, the major data structure is the "stream of tuples". A tuple is a virtual record which is made up of a number of fields, each of which has data in it.

When you search, you get back a stream of tuples, which is usually some projection of the record store. That is, you apply a function to each physical record which returns a tuple. This may be some subset of the physical fields, or may involve transforming them in some way.

Similarly, when you retrieve data back to the client, you get a stream of tuples. Everything conceptually works on these tuples.

Now think about how you work with a text database, such as Google. Google still has a record store. (See the "Google cache" for an example of what it might look like internally.) However, you don't see this. What you do is enter a search query and what is returned is the first ten results in summarised form. You hit "next" and you get the next ten. Typical searchers only look on one or two pages before they either go on to one of the results or refine their query.

What makes this feasable is that Google avoids hitting physical records unless the actual records are needed. To do this, its main internal data structure is a stream of record numbers, not a stream of tuples which contain data. (Z39.50, the successor to WAIS, calls this a "result set".) When you finally retrieve data, you can then go to the record store and retrieve the records associated with those record numbers.

This is why it's hard for relational databases to achieve the performance of native text databases: Text databases go to a lot of trouble to optimise the kinds of operations that text users want to do, which are very different from the kinds of operations that relational data users want to do. With text databases, searching, sorting, ranking and presenting data to the client are all conceptually different things, each with their own performance characteristics and access patterns. With relational databases, they are all intermingled, because relational database users tend not to need that kind of granularity.

Re:Anti-XML

[anomalous cohort]

Well, data structures and algorithms are related in that the choice of one affects the choice of the other. The classic example here is link lists are better for inserting than arrays but worse for searching.

IMHO, XML handles hierarchy better than relational databases but it is possible to use either. Of course, real human understanding is not strictly hierarchical so I guess that it's a wash. Neither XML nor RDB is all that good at capturing meaning.

You brought up a second point of who does the natural language processing, the human or the search algorithm? In Semantic Web, the publisher is doing the natural language processing and capturing meaning using XML.

Re:Anti-XML

[Anonymous Coward]

__insert_your_own_programming_language_here__? C'mon, eveyone knows you're talking about Python.

Re:Anti-XML

[gillbates]

I have no idea whether the databases of the future will store their data in XML form or not

Not likely. XML is designed to solve the data identification problem, not the data storage problem.

Due to the heirarchical nature of XML, a validating parser must read the entire document before returning any results. Given the way that most parsers are designed, the entire document will be read into memory and first parsed, then validated. Which, of course, limits the size of your database to the machine's memory.

The relational databases aren't going to go away. XML is more like a text-mode IMS for the PC. For those who have never heard of IMS, it was a heirarchical database built for IBM mainframes back in the 60's. When DB2 came out with it's relational model, IMS was largely abandoned. XML is no different, except it incurs a significant performance penalty - it isn't indexed, so binary searches are automatically precluded. Instead, searching a large XML "database" would require using a linear search after loading the document into memory.

But I think I've heard it best put by a manager, "XML forces your database to follow an arbitrary structure. It forces your database to be built around the presentation of the data, rather than the efficiency of retrieval." Until then, I hadn't thought about it in those terms, but I realized that he was exactly right. With a relational database, it's easy to represent many different views and relationships of the same data. But with XML, you're stuck with what the DTD designer believes necessary - the presentation in effect dictates the database structure.

I like XML as an exchange format. But it's the COBOL of the new millenium. The inherent inefficiencies involved (the entire document must be read to extract a single node?), and the inflexibility of relationships (it will always be heirarchical), make it a poor candidate for a database format.

Yes, I've used XML as a database format, with horrible results. A year or so ago, I used it for a financial application. I had written the frontend, and later decided to write an add-on piece which would compile statistics about the transaction data. Rather than being able to read a single record and do things like:

RunningTotal += CurrentRecord.AmountPayable;

I had to use syntax like:

RunningTotal = RunningTotal + Float.parseFloat(DocumentRoot().NextRecord().Item( "CurrentTransactions).Item("Transaction").Item("Am ountPayable"));

Now tell me that's an improvement!? And should I change my DTD, this code would useless. Yes, I could add fields, but I can't otherwise change the structure of the document without invalidating all of my code.

So XML isn't really as "universal" as the pundits would like to claim. In order to parse an XML document, you still need the DTD, and should the DTD change, your code will be broken. Here's a brief comparison of database formats:

• XML
• Memory Constrained
• No update in place (requires entire file rewrite)
• No fast search (1)
• Not architecture independent (2)
• Not self-documenting(3)

• Comma delimited:
• No update in place (requires entire file rewrite)
• No fast search (1)
• Not architecture independent (2)
• Not self-documenting(3)

• Fixed Width:
• Update in place
• Fast search (on indexed/sorted fields)
• Not architecture independent
• Not self-documenting.

Okay, flame away. Basically, XML doesn't offer any advantages to the old fixed-width mainframe formats, except possibly that it can be editted with a text editor. But it's not like any self-respecting DBA would let a programmer edit a production database with a text editor, so it's a moot point anyway.

Notes:

1. Since the record and field boundaries can be predicted in advance, a fixed width file doesn't need to pa

Re:Anti-XML

[2short]

"Which (slightly OT) reminds me: has anyone here used an XML compression tool"

I've looked at a few, but frankly, haven't seen the point. Several generic compression types (e.g. zip) are based on finding sequences in the data (e.g. "<SomeTagName") that are repeated, and hence they do very well with XML. I had some really big XML doc that whatever zip compression lib I was using for other stuff, with default options got down to ~15%, while some XML-specific compressor, after a bit of configuration bought me another 1 or 2%. Didn't seem worth it. Naturally, YMMV.

Anyway, I love XML. When I need to have my code send data to someone, I can say "It's in XML, here's a sample", and our format discussion is (almost) over. If it's really a lot of data, I'd rather say, "It's XML, zip compressed." than explain whatever less widely adopted XML specific compressor I'm using.

As far as XML for Data Storage as opposed to interchange: There's a variety of arguments for or against XML for storage, but the big pro for me is this: For the interchange side, I've written code to send XML to somewhere or receive XML from somewhere. Now I can do something different for storage, or I can just define "somewhere" to be a file.

Re:Anti-XML

[Hayzeus]

Actually, the tricky bit here is that the resulting data has to be text. The best solution I've seen so far involves generic compression and then base64 encoding, but I'm just wondering what other options might exist.

Re:Anti-XML

[Anonymous Coward]

EBCDIC is text. So is ASCII. So is Unicode.

mirrors ? anyone ?

[psycho_tinman]

Everything beyond the TOC (which I loaded onto my browser) is slashdotted. The problem with the links to the different articles is that its not part of a tree hierarchy, I cant just say "wget all pages beyond point X", nor can I make a guess and do a regex download of all URLs with "search" in them, because some articles do not conform to that pattern.

A tarball for offline browsing would be nice ? didnt see it on the page, though. Save you a part of a slashdotting, Tim.. how about it ? :)

Re:mirrors ? anyone ?

[Anonymous Coward]

Why doesn't slashdot just do a snapshot of a page if its just text?
Same thing google does right?
After a link to the page, just have a little "[cached]" that you can see if it gets slashdotted...

Re:mirrors ? anyone ?

[Anonymous Coward]

http://developers.slashdot.org/faq/suggestions.sht ml#su900

Thank you, drive through.

Bray's theorem

[KoolDude]

The essay series converges to text book when time tends to infinity. Proof is left as an exercise to the reader.

This technology still exists?

[Pathetic Coward]

Search technology. Hmmm. Wasn't that outsourced to India last month? Or was that last year? I just can't keep up with IT today.

Re:This technology still exists?

[smittyoneeach]

It will thrive until the Next Big Thing(tm) arrives, to "save us from the sad shortcomings of XML".

XML's only real fault is that's it's been oversold, not unlike Object Oriented Programming and Java before it.

Why isn't "someone" Tim Bray

[leoaugust]

I plan to conclude with a description of the next search engine, which doesn't exist yet but someone ought to start building.

"Someone" ought start building ... I wonder why this someone isn't Tim Bray. He is one of the most well known names in XML, has experience under his belt with another Search Engine Project Antartica .....

I just mean it in the sense that if he is having trouble getting his own ideas himself off the ground, what a challenge it will be for someone else to do so.

Mr. Bray should get the thing going like Linus did, and call in help from the Open Source Community. If he is waiting for someone with moneybags to catch the bait, and call him on the project as a highly paid consultant, maybe the approach needs to be modified.

Go Open Source Tim ... and get the ball rolling. You will be surprised how much help you will get ...

Re:Why isn't "someone" Tim Bray

[wizarddc]

Go Open Source Tim ... and get the ball rolling. You will be surprised how much help you will get ...

I thought that was just a myth?

Re:Why isn't "someone" Tim Bray

[veecee_veecee]

From the article (On Search: Backgrounder), on using Open Source tools:

Each of the ones I've looked at has a problem (lightly/poorly maintained, scalability problems, lack of internationalization, awkward API).

Good luck convincing him to go Open Source!

Re:Why isn't "someone" Tim Bray

[mbrinkm]

"This is the last in my series of On Search essays. I've written these pieces because I care about search and because the lessons of experience are worth writing down; but also because I'd like to change this part of the world. In short, I'd like to arrange for basically every serious computer in the world to come with fast, efficient, easy-to-manage search software that Just Works. This essay is about what that software should look like. Early next year I'll write something on how it might get built.

Naming the Baby An important piece of software needs to have a name, but that takes time and creativity and can wait; for now I'll just call this thing the Basic Resource Finder (BRF).

Requirements Then a couple of non-requirements and a conclusion.

BRF is Open-Source My heartfelt apologies to anyone still trying to make a go of it in server-side search; but that business is just so over. It always was a lousy business, nobody has ever made real money there on a sustained basis, and yet it's something that every Web deployment needs. For a substantial site you can easily drop six figures for a search engine, and all the bells and whistles that buys you are mostly not cost-effective.

So BRF is going to be open-source. That doesn't mean that you can't make money with search software; it just means you have to do it in services. There are always going to be search deployments loaded with tricky implementation and deployment work: figuring out where the data is, aggregating it, cleaning it up, building the workflows so these things keep happening, maintaining some application-specific synonyms, the list goes on and on, and none of these things are free. And they are much better things to spend money on than software licenses."

RTFA!

The original submission is about his last essay and that essay starts with the above quote.

And whoever moderated you up needs to RTFA also!

Re:Why isn't "someone" Tim Bray

[cutting]

Go Open Source Tim ... and get the ball rolling.

The ball is already rolling. Check out Lucene or Nutch. Either of these could be enhanced to support Tim's ideas. Volunteers? (I'm already working on it.)

Re:Why isn't "someone" Tim Bray

[gwhulbert]

Tim Bray was one of the founders of open text corporation ... they INVENTED the search engine.
Digital (with whom they were working) "stole" the idea and opened Altavista 3 months before their IPO.
I worked for Open Text for a year but after Tim left (just about the time the 1.0 draft of the XML spec appeared).

ObHutz

[sharkey]

Mr. Simpson, this is the most blatant case of fraudulent advertising since my suit against the film, ``The Never-Ending Story''.

-1 overrated

[Anonymous Coward]

non-metamodded overrated modifier is really killing /. , someone has just modded down 5 highly modded comments as overrated here.
Ideas?

google cache

[aarku]

here

Expert Advice

[Anonymous Coward]

Whether you are attending a private sex party or a public club, there are some good manners that should be followed. Obviously these rules will vary for different parties, but here are a few good rules to follow so that you don't become an unwanted guest and never get invited back again.

• Don't be a sling lizard - In other words, don't get into a sling unless you have a play partner. And if slings are limited, give other people a change to use the sling.
• Lay down paper towels on the floor before playing to collect any spilled lubrication. You may also want to place a paper towel under the bottoms butt. Wipe off the play area and the bottom completely before leaving the play area. It is the tops responsibility to make sure the lube is wiped off the bottoms butt and that the floor and sling or table is wiped off and clean for the next person.
• Ask your host what the house rules are This includes where you are allowed to play and what supplies you should bring (I always bring my own lube, beverage, paper towels and other party supplies to private parties). At THE SLING you can bring your own lube or we sell it there. Bring your own beer if desired, we provide sodas, paper towels, gloves, condoms and shower. For all parties it's polite to bring your own towel in case you want to shower
• Don't just walk up to a play session and join in It's best to try to get some eye contact to see if they want you to join in. It can be very distracting to be in a scene and have somebody just join in especially if you don't want them there.
• Keep unnecessary conversation and noises out of the play area Try not to have regular conversations where people playing can hear you. Also, if you are a screaming or make loud noises during play, this may disturb other guests. Some people enjoy the loud moans and groans but many find it disturbing.
• If you move any equipment around return it to the original spot when done For example, if you raise or lower the sling, return it to where it was when you got there. Or if you move a table or chair, return it.
• Do not share lube. This can lead to the transmission of HIV and other diseases. The cans can become contaminated while playing so it's good to write you name on the jar of crisco or lube.
• Wash off hands and arms and dick when done playing Preferrably with an antibacterial soap.
• Don't walk around the party in street clothes or be a gawkerAt most play parties the guys are usually in jocks or chaps so that their butts are exposed

Proper Fisting Technique Photograph

Slashdot search question

[Glass of Water]

But there is some good stuff out there; for example Slashdot's search engine seems to run smooth, clean, and fast, but some poking around failed to reveal what it is: I wouldn't be surprised if it's just the Mysql search facility.

Anybody know the answer to this one?

Re:Slashdot search question

[stoborrobots]

I don't know... see for yourself, then come and tell us...

The <a href="http://ask.slashcode.com/article.pl?sid=02/0 2/09/183217&mode=thread&tid=4" >comment on this page</a> suggests that you are right...

Re:Slashdot search question

[utopyr]

There are more suggestions here that you might be right.

Is this like Frequently-Asked-Magic-8-Ball?

Re:Slashdot search question

[ddilling]

Smooth, clean, fast... and kinda stupid.

Enter the precise title of this very article ("Learning about full text search" -- it will strip the hyphen anyway), and order by date: Your top hit will be "A.I. Helicopters" with this article hit #2.

Even better, order by score: your top hit will be "C++ Answers From Bjarne Stroustrup" -- this article doesn't even appear on the first page of 30 hits.

Okay, you say... maybe it's not searching the titles, but the article bodies only. Let's try "Tim bray XML search"... ordered by date, we get the same results (#2 to A.I. Helicopter's #1), ordered by score, this article again does not appear in the first 30 hits. By limiting the search to only the 'Developers' section, I finally got it to appear in the first page of results (at #5).

A rather hit-or-miss tool at best, for trying to find something older than the last couple days, in here.

Michael, you ignoramus.

[Seth Finklestein]

While you struggle with the use of opposable thumbs, I have implemented full-text search on my award-winning blog.

I'm sorry that it's taken you so long.

Sincerely,
Seth Finklestein
Michael Sims' worst nightmare

Or instead, talk to a librarian (the Register)

[JPMH]

An interesting counterpoint to this story in the Register today:

"A Quantum Theory of Internet Value" by Andrew Orlowski
-- why librarians are better at finding the book you want than Google.

Yeah, I know... Preview....

[stoborrobots]

I don't know... see for yourself, then come and tell us... The comment on this page suggests that you are right...

Mirror

[Door-opening Fascist]

Since the site looks bogged down from the /.'ing, I've made a few mirrors:

Mirror #1

Mirror #2

Mirror #3

Re:Mirror

[quartertone]

Excellent work. Not sure how you were able to circumnavigate the /. takedown.
One problem, however: It's just the front page. The meat of the information is still hiding on his server.

Re:Mirror

[Door-opening Fascist]

One problem, however: It's just the front page. The meat of the information is still hiding on his server.

It was originally just the front page. I decided to get that up fast to get the load off the original server. I've just updated the mirror with the important links, but those took a little longer to fetch.

page rank algorithm

[bcrowell]

Also, Google claims that links from pages that themselves have a lot of incoming links count for more, but I'm not actually sure they'd need to do that to get the results they do.
Is Google's page rank algorithm really that mysterious? I know they fiddle with it in secret ways now and then to discourage abuse, but I heard the fundamental algorithm was basically pretty simple: something like finding the eigenvectors and eigenvalues of the matrix of links. (Not sure exactly what they do with these -- associate each page with the eigenvector of which it's the biggest component?) Is this wrong? Wouldn't it be pretty easy to reverse engineer the algorithm anyway?

And when he says but I'm not actually sure they'd need to do that to get the results they do, can he be serious? If that wasn't the case, then it would really be encouraging link farms. If the eigenvalue/eigenvector approach is really how they do it, then it certainly does have this recursive property.

Re:page rank algorithm

[bcrowell]

(Replying to myself): Here is a site that claims to explain Google page rank completely. I found it by doing a Google search on 'google "page rank"', and I assume it's pretty authoritative, because it had the highest page rank :-)

"long departed Open Text index?" Not

[Anonymous Coward]

It just has a new name, and it's being developed by librarians.
http://www.dlxs.org/products/xpat.htm l

Searching and Sorting

[andy666]

It seems that both searching and sorting are very important topics. Someone should write a good thorough book on them.

Re:Searching and Sorting

[alw53]

And maybe discuss the actual algorithms
instead of the UI.

So, where can I find it?

[mod_parent_down]

I've been looking all over...

It's the FAKELSTEIN TROLL

[Anonymous Coward]

Trolling has been implemented.

RBTFL Re:Why isn't "someone" Tim Bray

[leoaugust]

Sure we did RTFA. Can you Read Between The F* Lines RBTFL ?

Here is what Tim says:

This essay is about what that software should look like. Early next year I'll write something on how it MIGHT get built.

So BRF is going to be open-source.

I plan to conclude with a description of the next search engine, which doesn't exist yet but someone ought to start building.

And if the following is not Consultant-Speak I don't know what is - Consultants are great at telling you why you should not be doing what you are doing. They might even tell you what you should be doing - but do they ever do anything except collect big fees. I have been on both sides and I know people who talk and people who walk. Stop talking and start walking.

always going to be search deployments loaded with tricky implementation and deployment work

figuring out where the data is,

aggregating it,

cleaning it up,

building the workflows so these things keep happening,

maintaining some application-specific synonyms,

the list goes on and on,

it's geared for public consumption

[Anonymous Coward]

it's geared for public consumption,
such is the nature of websites,
so as long as you don't pretend you wrote it,
it's abundantly clear where the original came from,
go ahead and mirror (by mirror i mean take a snapshot).

only if a copyright holder says don't do that should you remove it.

searching using php perl and mysql

[chrisranjana.com]

More search related functions should be available to php and perl and built in to them .. Even Mysql too...

Re:searching using php perl and mysql

[Pseudonym]

Both Perl and PHP already have Z39.50 support to connect to full-text search engines.

another pagerank discussion

[goon]

google broken? (www.google-watch.org)

"... unique ID for each page stored as ansi c, 4 bytes on Linux system (~4yo) gives theoretical limit of 4.2 billion pages. ..."

discusses the move to 5 bytes and suggests how this move may be the cause of weird search results on google searchs this year - of course the other reason my be google foiling search cue jumpers.

UI you say - check out www.geninterface.com

[wheatking]

in the post-google world, UIs like the General Interface will appear. check out their demo at Integrated Web Services and no i dont work there. i just like the direction they are going in.

General Interface?

[sean.peters]

If they're so general, how come I get this when I try to view the sample apps?

Sample Applications

General Interface Objects currently supports Internet Explorer 5.5 and later browsers running on Windows. For access to the sample applications please use another browser.

I guess "general" means "IE only".

Sean

Searchlores

[Anonymous Coward]

Fravia was once the biggest name in reverse engineering. His webpage was a reverse-engineering blog as far back as 1995, and he was instrumental in getting good reverse-engineers to talk together and teach each other their tricks.

The one remaining active mirror of his site is at http://www.woodmann.com/fravia. The messageboard at http://www.woodmann.com/upload is still the best place to go for reverse-engineering windows code; no crack requests, serial requests, or target-specific code are allowed, but you can address particular copy protections by name.

Fravia has since moved on to reverse-engineering search engines. If you want to find the stuff that doesn't turn up at the top of a google search, start here.

I think his searching technique needs some work

[cbreaker]

From the site: "It has fifteen instalments not including this table of contents."

Last I searched the dictionary, it was "installments."

I guess alphabetical searching is best after all.

Re:I think his searching technique needs some work

[tepples]

At least American Heritage Dictionary lists "instalment" as a recognized variant.

surviving a slashdotting

[Habbie]

Have you considered 'KeepAlive Off'? One busy site I admin for has been up 100% ever since I did that, used to go down (gigs of swap in use) every night..