8 votes
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 ...
user avatar
  • 14.2k
4 votes

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 ...
user avatar
3 votes

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$,...
user avatar
2 votes

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 ...
user avatar
  • 141
2 votes
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/...
user avatar
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$...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
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 ...
user avatar

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