1

I have been practicing some algorithm questions for interviews and have stumbled upon various questions that relate to sorting data that comes from an infinite stream and designing a data structure to search billions of records

  1. Describe how to sort integers read one at a time from an infinite stream

  2. Search through a tremendous number of elements is a search space. I.E. You're asked to design a storage structure and search algorithm to search through 100 billion data records. You can have multiple servers and multiple threads.

Here is what I think, please correct me if I am wrong or if there is a better solution

  1. For sorting integers read one at a time from infinite stream, could we use insertion sort? Worst case of insertion sort is O(n2) to sort an unsorted list but in this case the run time could be lowered down to O(logn). When the new element is to be inserted into the already sorted stream, we could just perform a binary search for the new element and insert it in logn time. But we would need to shift all the items to the right by 1 which would result in O(N). I am still not sure if this is right though

  2. We would use a Balanced BST which would have the worst case for insertion and searching to be logN or we could just use a HashMap which would ideally perform lookup in O(1) and insertion in O(1). However as we are dealing with 100 billion records, our worst case lookup for HashMap would be O(N) with a linked list implementation.

I still don't have a clear answer for these questions. If someone could provide some more insight, it would be great!

thanks!

Improve this question
1
  • 1
    You can evenly distribute the search space into m, and store m subsets in m servers respectively. For each n/m data on a server, use a hash table. Make sure you keep the load factor constant, i.e., table should grow with the size of the input, so that you get O(1) average search time. As to the worse case, yes, but you can always try find a good hash function. Commented Feb 23, 2015 at 3:22

1 Answer 1

Reset to default
5

For sorting a very large amount of data, you typically do it in two steps:

  1. Buffer data as it comes in until you've received some (typically very large) number of data items. You then sort those and write the sorted block to disk. You continue to do this until you've received and sorted all of the data.
  2. After you've sorted all the blocks, you do a k-way merge of the sorted blocks to create a single sorted file.

The buffering and sorting can be done in parallel if you have enough horsepower. As each block is received, you spin up a thread to sort it while the main thread continues to receive data in a new block. This isn't infinitely scalable, of course, because it's going to take much longer to sort a large buffer than it does to receive. So you might have to write each block to disk as it's received, and have a fixed number of background threads that sort those blocks. The basic algorithm is the same, though ... just a little time delayed.

If you can use multiple machines for searching, you'd typically spread the data among the many machines. So if you have 4 machines, each machine gets 1/4 of the data. When you want to do a search, you have each machine search its data set for matching records, and communicate those results to some central place, which sorts and removes duplicates.

Now, if you want to maintain a sorted data structure from a potentially infinite stream (i.e. be able to search at any time while the data is being received), then you need something more dynamic. One simple way is to have your main sorted structure, and also your "not yet sorted" buffer. So, for example, say you have already received a billion items that you've already sorted and stored, and you have a buffer size of 1 million items. As data is received, you store a million items in memory before you merge them with the primary data structure.

When you receive a search query, you search the main structure, which would be O(log N) if you used a binary search, and then you search your receive buffer sequentially. Granted the sequential search is a little slow because it's sequential, but all of the data is in memory so you don't have to pay the cost of I/O.

When your buffer fills, you use an efficient algorithm to merge it with the stored structure.

That's the basic idea. There are many ways to improve efficiency with multiple levels of merging, or by using a better data structure than a binary tree or similar.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I have a question on searching through multiple machines. I assume as you mentioned there would be a central machine which would route the data as it comes and search the data in a specific machine. Say there are 4 machines, then each machine would store specific type of data to be searched based on some criteria. So the central machine would have a hash table and when searching is performed, it performs a lookup based on the data, gets the right machine no and then performs search in that machine which then sends the result back to the central machine?
Also in the second part for sorting infinite stream of data, where you mention doing a sequential search on the buffer. What exactly does it mean when you say you don't pay the cost of I/O as data is in the memory?
@Htlcs: For distributed search, it depends largely on the type of data you have. If you have a sorted structure and you're searching by key, then a central server could determine which machine might contain the data, and route the request there. But if you're looking for the phrase "sequential search" among many documents that are stored on many machines, then you just send the request to all of the machines.
@Htics: Regarding my comment about the I/O, I meant that if you have a very large data set it's probably stored on disk. So searching it requires reading at least some data (the index, at least) from disk. That takes time. When searching the buffer, which is in memory because it hasn't yet been written to disk, you don't have to read it. That saves a little time because disk I/O is pretty expensive.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.