# Tag Info

Accepted

### Why splitted text files is bigger than a large one with the same content?

Filesystem overhead. Every time you create a file, the filesystem reserves space on disk to store the file name, and other metadata like its permissions, creation date, etc. It also has to maintain a ...
• 14.2k

### What is the difference between FLOPS and OPS?

What is the difference between FLOPS and OPS? FLOPS is floating-point operations per second OPS is operations per second The difference should be obvious from the name: one is the number of ...
• 5,151

### Semi-streaming algorithm for $s$-$t$ connectivity

You cannot do it in a single pass. Consider the set of all graphs of the following form: the vertices are $\{s,t\} \cup A \cup B$, where $|A|=|B|=n/2-1$. The only allowed edges are between $s$ and $A$,...
• 270k

### High Dimensional Data Structures

You can compress sparse multi-dimensional array by using a hash table. Calculate hash key for the required coordinates and use that as O(1) look-up to the cells in the array. If the cell is empty it ...
• 141
Accepted

### High Dimensional Data Structures

I would suggest you to use a hierarchical K-means, or a hierarchical vocabulary tree approach. For example: http://gecco.org.chemie.uni-frankfurt.de/hkmeans/H-k-means.pdf http://www.vlfeat.org/...
• 527
1 vote
Accepted

### Solving number of distinct elements in $O(\frac{n\ell}{p})$ space complexity with $2p$ passes over data

Try something along the following lines. Preform $p$ iterations where each iteration consists of two passes over the stream. The $i$'th iteration first pass remembers all elements whose index $\bmod p$...
• 13.2k
1 vote

### Applying algorithms on large data

Probably what you are looking for in one neat book:Algorithms and Data Structures for External Memory by Jeffrey Scott Vitter.
• 9,325
1 vote
Accepted

### Learning a perceptron from stream data

I think you're confusing yourself by worrying about a worst case that likely won't happen. Assuming each element of the stream comes randomly and independently from some distribution, then it is ...
• 143k
1 vote

### Large-scale string clustering

There are many possible approaches. One approach that I would suggest investigating is finding all pairs of similar strings, and then applying a standard algorithm for clustering of sparse graphs. ...
• 143k
1 vote

### Where do you exactly use data structures?

This is a broad question but will attempt to answer. From my understanding of your question, you have billions of strings which you want to use for autocomplete. The way most typical autocomplete ...
• 1,911
1 vote
Accepted

### Bias or not when finding patterns using data mining techniques?

In data mining, is it okay to start from expectations (bias) as to which patterns could be present and actually do statistics to see if this is actually the case Sure. This is called hypothesis ...
• 2,310
1 vote
Accepted

### Number of seeks in an I/O efficent algroithm

You're missing the trivial point that the input is on disk, and needs P seeks to be read, while the output needs to go to disk and needs Q seeks to be written. (Or 1+1 in the cases they're contiguous ...
• 809
1 vote

### (a,b)-tree vs B-tree

It seems you are right. The author probably takes as a standard definition the B+-tree where internal nodes are used as separators. You should always be prepared for authors that deviate from ...
• 27.7k
1 vote

### Hashing by doing modulo $m$ for $m=p^2$ for a prime $p$ instead of using a prime $m$ - is it that bad?

There are some reason why people would like to use modulo prime hashing. Assume we need a hash from $\{1,\ldots,n\}$ to $\{1,\ldots,m\}$, one popular choice is $h(n) = (an+b)\mod p\mod m$, where $p$ ...
• 362
1 vote

### Hashing by doing modulo $m$ for $m=p^2$ for a prime $p$ instead of using a prime $m$ - is it that bad?

There are a lot of things which could have gone wrong, but it is really hard to say, especially since you don't tell us the bad values of $n_l$ and $p^2$. So for now, here are some comments: SHA1 is ...
• 270k

Only top scored, non community-wiki answers of a minimum length are eligible