Approximate/Fuzzy Search for strings keys

#1

Dear all,

I have read the literature on fuzzy/approximate search for strings
keys in large databases, but I could not find a clear answer on what
is the best that has been achieved thus far in terms of the cost of
search (regardless of cost of building any index).

I understand this depends on the application/domain/type of data, but,
to keep things simple, supoose the target data is some string (names,
addresses, or any sequence of characters), and assume any distance
function. I am simply asking this: what is the best that has been
achieved? Is there a logarithmic solution (i.e., that can retrieve a
set of "similar" objects in some logarithmic order), or are they all,
in the worst case, linear?

I thank you in advance...

#2

On Jun 19, 9:36*am, walid.s... (AT) gmail (DOT) com wrote:

Quote:

Dear all,

I have read the literature on fuzzy/approximate search for strings
keys in large databases, but I could not find a clear answer on what
is the best that has been achieved thus far in terms of the cost of
search (regardless of cost of building any index).

I understand this depends on the application/domain/type of data, but,
to keep things simple, supoose the target data is some string (names,
addresses, or any sequence of characters), and assume any distance
function. I am simply asking this: what is the best that has been
achieved? Is there a logarithmic solution (i.e., that can retrieve a
set of "similar" objects in some logarithmic order), or are they all,
in the worst case, linear?

Without a clear definition of exactly what you are trying to
accomplish, your question cannot be answered.

If I have a hash table of strings, with no duplicates allowed, and my
hash table is large enough, then insert, update, and delete are all
O(1) for exact strings.

Are the strings short or long?
What are the rules for similarity?
Are you looking at soundex sort of similarity or Levenstein edit
distance or something else?
Can we have exact duplicate strings stored in our repository?
What is the domain data? Personal names? DNA sequences?
Do you expect to return the entire class in the case of a fuzzy match?
I do not think you can expect an exact answer with a fuzzy question
(even when the topic of the question is fuzzy).
I guess if you specify the problem exactly you will get a better
answer.

#3

On Jun 19, 9:36*am, walid.s... (AT) gmail (DOT) com wrote:

Quote:

Dear all,

I have read the literature on fuzzy/approximate search for strings
keys in large databases, but I could not find a clear answer on what
is the best that has been achieved thus far in terms of the cost of
search (regardless of cost of building any index).

I understand this depends on the application/domain/type of data, but,
to keep things simple, supoose the target data is some string (names,
addresses, or any sequence of characters), and assume any distance
function. I am simply asking this: what is the best that has been
achieved? Is there a logarithmic solution (i.e., that can retrieve a
set of "similar" objects in some logarithmic order), or are they all,
in the worst case, linear?

Without a clear definition of exactly what you are trying to
accomplish, your question cannot be answered.

If I have a hash table of strings, with no duplicates allowed, and my
hash table is large enough, then insert, update, and delete are all
O(1) for exact strings.

Are the strings short or long?
What are the rules for similarity?
Are you looking at soundex sort of similarity or Levenstein edit
distance or something else?
Can we have exact duplicate strings stored in our repository?
What is the domain data? Personal names? DNA sequences?
Do you expect to return the entire class in the case of a fuzzy match?
I do not think you can expect an exact answer with a fuzzy question
(even when the topic of the question is fuzzy).
I guess if you specify the problem exactly you will get a better
answer.

#4

On Jun 19, 9:36*am, walid.s... (AT) gmail (DOT) com wrote:

Quote:

Dear all,

I have read the literature on fuzzy/approximate search for strings
keys in large databases, but I could not find a clear answer on what
is the best that has been achieved thus far in terms of the cost of
search (regardless of cost of building any index).

I understand this depends on the application/domain/type of data, but,
to keep things simple, supoose the target data is some string (names,
addresses, or any sequence of characters), and assume any distance
function. I am simply asking this: what is the best that has been
achieved? Is there a logarithmic solution (i.e., that can retrieve a
set of "similar" objects in some logarithmic order), or are they all,
in the worst case, linear?

Without a clear definition of exactly what you are trying to
accomplish, your question cannot be answered.

If I have a hash table of strings, with no duplicates allowed, and my
hash table is large enough, then insert, update, and delete are all
O(1) for exact strings.

Are the strings short or long?
What are the rules for similarity?
Are you looking at soundex sort of similarity or Levenstein edit
distance or something else?
Can we have exact duplicate strings stored in our repository?
What is the domain data? Personal names? DNA sequences?
Do you expect to return the entire class in the case of a fuzzy match?
I do not think you can expect an exact answer with a fuzzy question
(even when the topic of the question is fuzzy).
I guess if you specify the problem exactly you will get a better
answer.

#5

On Jun 19, 9:36*am, walid.s... (AT) gmail (DOT) com wrote:

Quote:

Dear all,

I have read the literature on fuzzy/approximate search for strings
keys in large databases, but I could not find a clear answer on what
is the best that has been achieved thus far in terms of the cost of
search (regardless of cost of building any index).

I understand this depends on the application/domain/type of data, but,
to keep things simple, supoose the target data is some string (names,
addresses, or any sequence of characters), and assume any distance
function. I am simply asking this: what is the best that has been
achieved? Is there a logarithmic solution (i.e., that can retrieve a
set of "similar" objects in some logarithmic order), or are they all,
in the worst case, linear?

Without a clear definition of exactly what you are trying to
accomplish, your question cannot be answered.

If I have a hash table of strings, with no duplicates allowed, and my
hash table is large enough, then insert, update, and delete are all
O(1) for exact strings.

Are the strings short or long?
What are the rules for similarity?
Are you looking at soundex sort of similarity or Levenstein edit
distance or something else?
Can we have exact duplicate strings stored in our repository?
What is the domain data? Personal names? DNA sequences?
Do you expect to return the entire class in the case of a fuzzy match?
I do not think you can expect an exact answer with a fuzzy question
(even when the topic of the question is fuzzy).
I guess if you specify the problem exactly you will get a better
answer.

#6

On Jun 19, 9:36*am, walid.s... (AT) gmail (DOT) com wrote:

Quote:

Dear all,

I have read the literature on fuzzy/approximate search for strings
keys in large databases, but I could not find a clear answer on what
is the best that has been achieved thus far in terms of the cost of
search (regardless of cost of building any index).

I understand this depends on the application/domain/type of data, but,
to keep things simple, supoose the target data is some string (names,
addresses, or any sequence of characters), and assume any distance
function. I am simply asking this: what is the best that has been
achieved? Is there a logarithmic solution (i.e., that can retrieve a
set of "similar" objects in some logarithmic order), or are they all,
in the worst case, linear?

Without a clear definition of exactly what you are trying to
accomplish, your question cannot be answered.

If I have a hash table of strings, with no duplicates allowed, and my
hash table is large enough, then insert, update, and delete are all
O(1) for exact strings.

Are the strings short or long?
What are the rules for similarity?
Are you looking at soundex sort of similarity or Levenstein edit
distance or something else?
Can we have exact duplicate strings stored in our repository?
What is the domain data? Personal names? DNA sequences?
Do you expect to return the entire class in the case of a fuzzy match?
I do not think you can expect an exact answer with a fuzzy question
(even when the topic of the question is fuzzy).
I guess if you specify the problem exactly you will get a better
answer.

#7

On Jun 19, 9:36*am, walid.s... (AT) gmail (DOT) com wrote:

Quote:

Dear all,

I have read the literature on fuzzy/approximate search for strings
keys in large databases, but I could not find a clear answer on what
is the best that has been achieved thus far in terms of the cost of
search (regardless of cost of building any index).

I understand this depends on the application/domain/type of data, but,
to keep things simple, supoose the target data is some string (names,
addresses, or any sequence of characters), and assume any distance
function. I am simply asking this: what is the best that has been
achieved? Is there a logarithmic solution (i.e., that can retrieve a
set of "similar" objects in some logarithmic order), or are they all,
in the worst case, linear?

Without a clear definition of exactly what you are trying to
accomplish, your question cannot be answered.

If I have a hash table of strings, with no duplicates allowed, and my
hash table is large enough, then insert, update, and delete are all
O(1) for exact strings.

Are the strings short or long?
What are the rules for similarity?
Are you looking at soundex sort of similarity or Levenstein edit
distance or something else?
Can we have exact duplicate strings stored in our repository?
What is the domain data? Personal names? DNA sequences?
Do you expect to return the entire class in the case of a fuzzy match?
I do not think you can expect an exact answer with a fuzzy question
(even when the topic of the question is fuzzy).
I guess if you specify the problem exactly you will get a better
answer.

#8

On Jun 19, 9:36*am, walid.s... (AT) gmail (DOT) com wrote:

Quote:

Dear all,

I have read the literature on fuzzy/approximate search for strings
keys in large databases, but I could not find a clear answer on what
is the best that has been achieved thus far in terms of the cost of
search (regardless of cost of building any index).

I understand this depends on the application/domain/type of data, but,
to keep things simple, supoose the target data is some string (names,
addresses, or any sequence of characters), and assume any distance
function. I am simply asking this: what is the best that has been
achieved? Is there a logarithmic solution (i.e., that can retrieve a
set of "similar" objects in some logarithmic order), or are they all,
in the worst case, linear?

Without a clear definition of exactly what you are trying to
accomplish, your question cannot be answered.

If I have a hash table of strings, with no duplicates allowed, and my
hash table is large enough, then insert, update, and delete are all
O(1) for exact strings.

Are the strings short or long?
What are the rules for similarity?
Are you looking at soundex sort of similarity or Levenstein edit
distance or something else?
Can we have exact duplicate strings stored in our repository?
What is the domain data? Personal names? DNA sequences?
Do you expect to return the entire class in the case of a fuzzy match?
I do not think you can expect an exact answer with a fuzzy question
(even when the topic of the question is fuzzy).
I guess if you specify the problem exactly you will get a better
answer.

#9

On Jun 19, 9:36*am, walid.s... (AT) gmail (DOT) com wrote:

Quote:

Dear all,

I have read the literature on fuzzy/approximate search for strings
keys in large databases, but I could not find a clear answer on what
is the best that has been achieved thus far in terms of the cost of
search (regardless of cost of building any index).

I understand this depends on the application/domain/type of data, but,
to keep things simple, supoose the target data is some string (names,
addresses, or any sequence of characters), and assume any distance
function. I am simply asking this: what is the best that has been
achieved? Is there a logarithmic solution (i.e., that can retrieve a
set of "similar" objects in some logarithmic order), or are they all,
in the worst case, linear?

Without a clear definition of exactly what you are trying to
accomplish, your question cannot be answered.

If I have a hash table of strings, with no duplicates allowed, and my
hash table is large enough, then insert, update, and delete are all
O(1) for exact strings.

Are the strings short or long?
What are the rules for similarity?
Are you looking at soundex sort of similarity or Levenstein edit
distance or something else?
Can we have exact duplicate strings stored in our repository?
What is the domain data? Personal names? DNA sequences?
Do you expect to return the entire class in the case of a fuzzy match?
I do not think you can expect an exact answer with a fuzzy question
(even when the topic of the question is fuzzy).
I guess if you specify the problem exactly you will get a better
answer.

#10

On Jun 19, 9:36*am, walid.s... (AT) gmail (DOT) com wrote:

Quote:

Dear all,

I have read the literature on fuzzy/approximate search for strings
keys in large databases, but I could not find a clear answer on what
is the best that has been achieved thus far in terms of the cost of
search (regardless of cost of building any index).

I understand this depends on the application/domain/type of data, but,
to keep things simple, supoose the target data is some string (names,
addresses, or any sequence of characters), and assume any distance
function. I am simply asking this: what is the best that has been
achieved? Is there a logarithmic solution (i.e., that can retrieve a
set of "similar" objects in some logarithmic order), or are they all,
in the worst case, linear?

Without a clear definition of exactly what you are trying to
accomplish, your question cannot be answered.

If I have a hash table of strings, with no duplicates allowed, and my
hash table is large enough, then insert, update, and delete are all
O(1) for exact strings.

Are the strings short or long?
What are the rules for similarity?
Are you looking at soundex sort of similarity or Levenstein edit
distance or something else?
Can we have exact duplicate strings stored in our repository?
What is the domain data? Personal names? DNA sequences?
Do you expect to return the entire class in the case of a fuzzy match?
I do not think you can expect an exact answer with a fuzzy question
(even when the topic of the question is fuzzy).
I guess if you specify the problem exactly you will get a better
answer.