2
$\begingroup$

I devised an algorithm / data structure and I would like to ask whether it already exists. The problem statement is: after having added some number of strings to the set, determine whether a given string is definitely not in the set. I have attempted searching it but discovered no similar algorithm.For reference, I'll name the set I devised Blake Set.

The set supports add and query operations however no removal operation. The query operation can either return 'value definitely not in set' or 'value possibly in set'. In this sense, the set is similar to a Bloom Filter in behaviour - though it operates entirely differently.

A Blake Set is represented as a singly linked list of size m where m is the number of characters in the longest inserted string. Each node stores a sequence of $k$ bytes, all initially zeroed, where $k$ is the number of different values for characters divided by four. For instance, if we were to store ASCII-strings $k$ would be 256/4 = 64. Additionally, every character must have a number associated with it that is at least 0 and at most $4k - 1$ hence every character has an unique number that can act as a valid index in an array of length $4k$

Adding a string s to the set works as follows:

for every character c in s
    let i be the index of c in s
    let v be the i-th node in the singly linked list
    let id be the number associated with c
    set the id-th high-order bit in v to 1
    if c is the last character in s
        set the id-th low-order bit to 1

So the first half of the number in any node stores whether a given character has been added and the second half stores whether it was the last character in the string. Subsequently, to query whether a given string $s$ is in the set, we perform the following operation:

for every character c in s
    let i be the index of c in s
    let v be the i-th node in the singly linked list
    let id be the number associated with c
    if the id-th high-order bit in v is not set
        return false
    if c is the last character in s and the id-th low-order bit in v is not set
        return false
return true

If a character's corresponding bit in any node is not set, its string was never added. The same is true for checking the last character. The second half of the byte sequence is not necessary but it decreases the probability for a false positive. It should be trivial that the time complexity is $\mathcal{O}(m)$ ($m$ being the size of the longest added string) as we perform a constant number of operations for every character. The space complexity is also $\mathcal{O}(m)$ as we always store $m$ nodes with constant size in the singly linked list.

The set described has some similarities with the bloom filter in terms of querying but the two structures are certainly different. Do any algorithms that you know match the description that I have given?

$\endgroup$
  • 1
    $\begingroup$ Eww.... Consider a Blake set containing $111\ldots 111$ and $000\ldots 000$. If understand correctly, it would say "yes" to any query for any binary string (of the same length). $\endgroup$ – Tom van der Zanden Mar 7 '16 at 9:41
  • $\begingroup$ @TomvanderZanden Yes, you are correct. The data structure is only capable of returning whether a given string is possibly in the set or definitely not. In the case of a your (well-picked) example, the data structure would yield false positives; though I would assert its amount of false positives decreases dramatically as the number of different character types increases. Though that has to be proofed, which I am planning to do. It is intended to be used with ASCII strings or strings that contain even more characters and with those it yield better results. $\endgroup$ – univise Mar 7 '16 at 10:35
  • $\begingroup$ @Raphael The uncertainty can occur: Suppose the two strings "aazz" and "bbyy". Add them to the set. Now check whether the string "aayy" is present. It will return true. Tom van der Zanden is correct: I would like to know whether my described set exists and has a name. However, I am not looking for a data structure as Tom's first sentence implies though Tom is right with stating that "might be" can be translated to "actually is with high probability". $\endgroup$ – univise Mar 7 '16 at 18:11
  • $\begingroup$ How this differs from Bloom filters? I mean, the operations are different, collision rate, space usage and so on, but the idea of testing and giving results with probability as you mentioned is similar, but operates differently - but the differences are not so big (sorry if I misunderstood the scheme, but without mentioning Bloom, it is quite obvious derivative). $\endgroup$ – Evil Mar 7 '16 at 19:05
  • 1
    $\begingroup$ If I understand correctly, this appears to be almost exactly a Bloom filter but with unusually weak hash functions (i.e.: the mapping of the $i^{th}$ character to the $c^{th}$ bit of the $i^{th}$ block). $\endgroup$ – mhum Mar 7 '16 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.