Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
chi's user avatar
  • 14.6k
5 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 ...
Jörg W Mittag's user avatar
4 votes

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: ...
Pseudonym's user avatar
  • 22.2k
4 votes

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 ...
Russel's user avatar
  • 2,745
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$,...
Yuval Filmus's 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$...
Ariel's user avatar
  • 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 ...
D.W.'s user avatar
  • 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. ...
D.W.'s user avatar
  • 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 ...
Lance's user avatar
  • 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 ...
Martin Thoma's user avatar
  • 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 ...
MSalters's user avatar
  • 895

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