2

How to index a massive, randomly selected, uncontrollable, constantantly changing dataset?

Imagine you want to index all of the snow particles in a giant snowglobe that is constantly being shaken. Each snow particle represents a piece of lengthy text (say a book) that needs to be indexed, however, the particles are constantly moving and cannot be grouped into categories of indexed and not indexed. On top of this, snow particles disappear from the globe (either through disintegration or removal) and new particles are added. It is also possible for the text of the book to be changed or updated. There is a desire to keep the database as up to date as possible, so older index data may need to be updated periodically.

a. Is there an algorithm that can prevent having to look up a particle each time to see if it has already been indexed? On a large enough dataset, this will become very burdensome. I imagine there may be more overhead associated with such an algorithm and may be cumbersome for smaller datasets, but would prove faster with larger datasets as the index grows.

b. How to handle the updating of the index in terms of making sure the text is still the same and still exists? I don't really want to check if the data is the same in the case I randomly pick up an already indexed item to prevent unecessary loops (i.e. picking indexed items multiple times instead of spending less time indexing new data). As long as the first problem is solved, i.e. each examined item is a new item, then I suppose an update scheme which goes through after a certain period of time checking for consistency will work. Any other thoughts?


UPDATE:

Please see my comments below which might help clarify my question and its motivation.

I will also add another example in case the snowglobe bs isn't clear:

Imagine you are tasked with independently cataloging and indexing the entire Library of Congress, but without the help of the library staff, so you must personally go to each book rack and begin indexing them individually on your own. Also, they will not help you by holding checked out books at the counter for your approval before reshelving. There is no clear place to start, so you begin with authors last names beginning with 'A'. By the time you get to section 'B', it is likely that someone has returned a book into the 'A' section after you completed indexing it and have no way of knowing which one it was, if there was one put back up at all. Now, let's imagine that the LOC is extremely busy, and so not going back to check the 'A' section would result in your index missing 10-20% of the dataset. In addition to that, not only are checked out books being returned by patrons, but new books are being published and stocked, as well as the release of updated editions to existing indexed items.

This is obviously not an ideal situation for actually indexing the LOC, but given the problem I'm certain there are better solutions than others. How to solve while minimizing time and cycles wasted?

  • Don't see how anything has an identity here. Would help if we knew why we would ever look something up again or care if it had changed or moved. – candied_orange Jul 29 '16 at 6:07
  • Well, each particle (or the text to be indexed) would be the identity. It's not that we would look something up again or care if it moved, it's that if and when it moves we may accidently waste time looking it up again. Ideally, when indexing a dataset we would have two piles: "indexed" and "non-indexed". This would make it easy to ensure that each time we examine an item it will be in need of indexing and no time will be wasted putting it down and picking up another item in hopes it will be non-indexed. This is what I meant by a lack of control over the dataset... – user58446 Jul 30 '16 at 1:12
  • ...since I am having to put the already indexed items back into the pile with the non-index data. This is also what I meant by the selection being "random" in a sense. – user58446 Jul 30 '16 at 1:13
  • How big is the text in each "particle"? You can compute a hash checksum on the "content" of each "particle", and for each checksum remember whether it is currently in the index or not. You will have to benchmark to see whether the hashing actually performs faster than your indexing. If indexing refers to a histogram of words, it is possible for indexing (if simple enough) to be faster than hashing. – rwong Jul 30 '16 at 1:53
  • The snow glob is fundamentally different than the Library of Congress example. Books have an identity: ISBN. When people are done with a book it is returned to the same shelf. When people update a book it remains unchanged. Instead a new volume comes out. This is not uncontrollable. When indexing a book first check that the ISBN is new to you. Index everything in place. Then index everything that moves. Unlike the snow globe the LoC is a very solvable problem. – candied_orange Jul 30 '16 at 5:45
1

Note: see update farther down.

This sounds a lot like an Information Retrieval system, AKA a search engine. The problem is best attacked by dividing it into separate, loosely connected pieces.

  1. The spider (or scout or whatever) that keeps looking for things that need to be indexed. These are identified, possibly caching a copy for a moment-in-time, and added to a work queue. Then its work is done.

  2. The parser that breaks the object into searchable chunks (I'm being deliberately vague here because this is a swamp unto itself).

  3. The index updater. This can get tricky. In the late 80's we were building indices that had in excess of 5,000,000 separate keys, each of which could have from 1 to 1,000,000 instances in the collection. This approach is generally called a fully inverted index.

  4. A search engine that takes a query and applies it to the index. We were doing a hybrid of similarity searching (specifically Cosine Coefficient), quorum, and Boolean searching.

All parts are easily done in parallel except for the index update itself, which has many problems in common with multiple-writer RDBMS updating. How you build this is at least a Master's Capstone project, maybe more.

As far as avoiding dupes, that is a function of document (object) management so you recognize it as it is happening. If the address is a dupe, check for it and you're done. If the contents are a dupe, the parser can generate a key/hash/tuple that is checked before any heavy updating occurs.

Near-dupes are more difficult, but possible depending on your underlying index and the way you represent objects.

Update for comments:

OK, so I went a bit off the rails. You seem to be focused on the problem of tracking the changing nature of the the document population in as close to real-time as possible. Note: I'll call them documents, but I've seen/used variants of this approach on images and on DNA samples. As long as the 1's and 0's are talking about the same thing, what they are doesn't really matter.

Things that can make a difference:

  1. What do you mean by "massive"? Nowadays a few million or 10's of millions of documents is a toy collection. You could hold all of the names in the memory of 1 decent-sized server.

  2. What is your cost of acquisition of the names of the documents? If it's local to the machine, it's trivial. If it's across the global Interwebs, anything tricky you do will be swamped by the communications cost, and probably by the relative performance of the various servers you are talking to.

  3. Detecting name-dupes is trivial. I would suggest generating a MD5 hash (or the hash of your choice) and using that as an indexed column in your table. Lookup cost is trivial on a decent-sized server. Although it's possible to write your own index-lookup-algorithm, I recommend against it. Find a good library / RDBMS and use it. Life is too short to reinvent this wheel.

  4. Detecting full-content-dupes is only slightly more expensive. Again, you hash and index the hash. Note: Since this is content based it works well with dupes across a wide document-namespace.

  5. Detecting partial-content-dupes is much more interesting. The general approach is to have some 'chunking algorithm' to break up the docs (e.g. paragraph or section sized chunks), then hash each chunk. The rest is as above. Note: variations on what a "chunk" is makes this useful for plagiarism detection, matching DNA fragments, etc. If you are dealing with long text documents, early work done by Professor Marti Hearst may be of interest. Also work by Salton and Buckley at Cornell on paragraph-level similarity, although a bit old, may still offer some insights.

  6. Do you need to detect changes/deletions of already-indexed docs? This makes the problem substantially more expensive since you are constantly having to go back and look at stuff you've already looked at. It helps massively if you have cooperation from the individual servers.

  7. How close to real-time do you need to correctly detect the changes? As soon you move away from local-machine or local-network, then "eventually correct" is this best you can hope for. It also matters whether each server is actively cooperating in detecting/communicating changes. If you are having to do it from the outside, then "eventually correct sometime this year, maybe never" may be the best you can do.

Scale and access-speed are the overriding concerns here. The bigger the population, the more you have to think parallel. If you have 10^6 docs that's one problem. If you have 10^12 docs, then whatever the solution was for 10^6 will collapse.

In the late 80's, when doing similarity searching on collections of 10^8 documents, we were using clusters of machines (big DEC Alphas). We used something like sharding to break the data in to machine-sized chunks, and then searched with an algorithm we called scatter-gather-merge; it predates MapReduce, but is conceptually related. Our problem was the search, document tracking and indexing were relatively straightforward.

Hopefully this update addresses your problem more directly.

  • Thank you for taking the time to write the first part, but it is outside the scope of the question. The last two paragraphs are. Yes, this is similar to a search engine, however they have a much "simpler" algorithm of indexing pages that are linked in other pages; true you may end up on a duplicate page but at least you have a place to start and a place to go. The library example could be similar if you were to take a book and then index the the books in the bibliography, spidering out from there... but no, forget there is an index and the notion that books are linked to other books. – user58446 Jul 30 '16 at 7:48
  • ...using the search engine example, how would you index the web if not using the hyperlink / page reference algorithm. Would you start at www.a.com, then www.ab.com, then www.abc.com? What happens when you get to www.abcde.com and then someone registers www.abc.com? Do you wait until you reach www.zzzzzzzzzzzz.com before you return to www.abc.com? Do you mark www.abc.com as unindexed/unregistered, place it in an unregistered pile, and then specifically check for those later on at a more convenient time?... – user58446 Jul 30 '16 at 7:56
  • ... This could become very unwieldly considering how long a URL can be. But at least this way, you know you do not have to check for a duplicate and can use it as a "target" right away. – user58446 Jul 30 '16 at 7:56
  • ... or how about indexing some data scraped off of youtube videos. Suppose you want to scrape ALL of youtube. You may decide to take a single uploader, index all of their videos and then move on to the next uploader channel based alphabetically. BUT new uploaders are joining all the time, and indexed channels have new videos uploaded all of the time. In this case, it may make sense to construct a list of videos uploaded by date/time, with new videos being appended to the end of the list. Then begin with the oldest working towards the newest. This way there would be some type of 'organization'. – user58446 Jul 30 '16 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.