Linked Questions

97
votes
3answers
31k views

How does one know which notation of time complexity analysis to use?

In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ...
26
votes
2answers
4k views

Efficient map data structure supporting approximate lookup

I'm looking for a data structure that supports efficient approximate lookups of keys (e.g., Levenshtein distance for strings), returning the closest possible match for the input key. The best suited ...
6
votes
1answer
4k views

Find all pairs of strings in a set with Levenshtein distance < d

I have a set of $n = $ 100 million strings of length $l = 20$, and for each string in the set, I would like to find all the other strings in the set with Levenshtein distance $\le d = 4$ from that ...
0
votes
1answer
2k views

Large-scale string clustering

I've more than 10 million strings of length 1-100 characters. This number will be even bigger in the future. I'm interested in clustering this data, but I'm not quite sure what would be effective at ...
4
votes
1answer
669 views

Find the closest string to a fixed set of strings

I want to find the closest string to a fixed set of strings. The strings are all equal in length, and the number of strings in the set is relatively small (compared to all the possible strings of the ...
2
votes
0answers
561 views

Matching strings in one set to strings in another based on Levenshtein distance

Suppose I have two sets, A and B, which each have one or more strings. I'm looking for an algorithm that'll go through each ...
2
votes
1answer
111 views

Approximate Similarity Search

I am implementing an approximate similarity search using multi-index hashing. I have a set (T) of millions of strings (of same length) and I have a query string(P) (or set of strings) that needs to ...
1
vote
0answers
81 views

How to find close match of levenshtein distance [duplicate]

Let's say we have some function, float distance(String a, String b) { /*...*/ } to find the Levenshtein distance between two strings, and we have a large array ...
1
vote
1answer
81 views

Algorithm to Check for Upper Bound of Levenshtein Distance

I am looking for an algorithm that checks if the Levenshtein distance between two strings $s_1$ and $s_2$ is less than a certain upper bound $B$. I know, there are plenty of algorithms for calculating ...
0
votes
0answers
47 views

Fast text comparison algorithm for long texts

I want to calculate a similarity ratio between two long texts (by "long", I imply something around 1000 characters or higher). For example, two texts with only one word changing should have ...
0
votes
1answer
46 views

How to check rapidly if an element is present in a large set of data

I am trying to harvest scientific publications data from different online sources like Core, PMC, arXiv etc. From these sources I keep the metadata of the articles (title, authors, abstract etc.) and ...