Share Your Experience: Take the 2024 Developer Survey

# 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.6k

### 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 ...
• 6,160

### How do XFast and Y Fast Tries compare to B trees in performance?

On top of the other answer, the reason why any data structure tends to be preferred by databases over any other data structure (e.g. B+-trees over anything else) usually boils down to two factors: ...
• 22.2k

### How do XFast and Y Fast Tries compare to B trees in performance?

Apart from their more complex structure, Y-fast and X-fast trie assumes that data to be stored are integers, while balanced BSTs only assumes that data be from some ordered universe, not necessarily ...
• 2,745

### 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$,...
• 277k
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.4k
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 ...
• 161k
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. ...
• 161k
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 ...
• 2,243
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,360
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 ...
• 895

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