12

Going with Patrick87's hash idea, here's a practical construction that almost meets your requirements — the probability of falsely mistaking a new value for an old one is not quite zero, but can be easily made negligibly small. Choose the parameters $n$ and $k$; practical values might be, say, $n = 128$ and $k = 16$. Let $H$ be a secure cryptographic ...


10

I don't think that degree of a tree is a standard term in either graph theory nor data structures. A degree is usually a property of a node/vertex of a graph, which denotes the number of its incident edges. For trees you sometimes consider only the edges to the children. I suppose "B-tree with minimum degree of 2" means that every node has at least two ...


10

To quote from the answer to “Traversals from the root in AVL trees and Red Black Trees” question For some kinds of binary search trees, including red-black trees but not AVL trees, the "fixes" to the tree can fairly easily be predicted on the way down and performed during a single top-down pass, making the second pass unnecessary. Such insertion ...


9

A B-Tree node can contain more than one key values whereas a BST node contains only one. There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer t>=2 called the minimum degree of the B-tree. Every node other than the root must have at least t-1 keys. Every internal node other ...


9

I've been researching this topic recently as well, so here are my findings, but keep in mind that I am not an expert in data structures! There are some cases where you can't use B-trees at all. One prominent case is std::map from C++ STL. The standard requires that insert does not invalidate existing iterators No iterators or references are invalidated....


8

Joe's answer is extremely good, and gives you all the important keywords. You should be aware that succinct data structure research is still in an early stage, and many of the results are largely theoretical. Many of the proposed data structures are quite complex to implement, but most of the complexity is due to the fact that you need to maintain ...


8

No, it is not possible to have an efficient data structure with these properties, if you want to have a guarantee that the data structure will say "new" if it is really new (it'll never, ever say "not new" if it is in fact new; no false negatives allowed). Any such data structure will need to keep all of the data to ever respond "not new". See pents90's ...


8

It is impossible to build a data structure that supports insert, maximum, and delete all in constant time. Such a data structure is a priority queue, and a priority queue with all constant-time operations can do heapsort in linear time. Since there is a superlinear lower bound on sorting, this is impossible. One of insert, maximum, or delete must be ...


8

Take any dictionary data structure and link its entries in whichever order suits you. In essence, you retain the $\Theta$-costs from the basic structure. In search trees, this is called threading. It gives you constant-time access to the first and last element, respectively, and maintaining the threading takes only constant-time overhead for each dictionary ...


7

I think your reasoning is in principle correct. Perfect hashing is an alternative to Bloom filters. However, classical dynamic perfect hashing is rather a theoretical result than a practical solution. Cuckoo hashing is probably the more "reasonable" alternative. Note that both dynamic perfect hashing and standard cuckoo hashing performance is only expected ...


7

I couldn't find the source, but the idea is simple: Use additional bloom filter to represent the set of the deletions. As this is a very simple solution, it might be considered as a folklore. Anyway, I found a short reference to this solution in the following paper (Theory and Practice of Bloom Filters for Distributed Systems): http://www.dca.fee.unicamp....


6

Given that you want to insert $n$ words into the Bloom filter, and you want a false positive probability of $p$, the wikipedia page on Bloom filters gives the following formulas for choosing $m$, the number of bits in your table and $k$, the number of hash functions that you are going to use. They give $ m = - \frac{n \ln p}{(\ln 2)^2} $ and $$ k = \frac{m}{...


6

What about just a hash table? When you see a new item, check the hash table. If the item's spot is empty, return "new" and add the item. Otherwise, check to see if the item's spot is occupied by the item. If so, return "not new". If the spot is occupied by some other item, return "new" and overwrite the spot with the new item. You'll definitely always ...


6

To summarize, this is what you require: a dictionary that offers find, add and delete in $O(\log n)$ time and also GetByIndex, KeyByIndex and IndexByKey in $O(\log n)$ time, where the index is determined by insertion order. The first part is easy: use any balanced search tree. Say we use AVL trees. For the second, we can use a second tree but use an ...


6

Here's a way to think about the feature-based approach: you select a set of candidate features, then look for the smallest decision tree that assigns each of the $N$ keys a different index in $[0,N)$ using only those features. This is effectively a way of building a perfect hash, where the hash function is expressed as a decision tree applied to the feature ...


5

It sounds like you want a succinct data structure for the dynamic membership problem. Recall that a succinct data structure is one for which the space requirement is "close" to the information-theoretic lower bound, but unlike a compressed data structure, still allows for efficient queries. The membership problem is exactly what you describe in your ...


5

I have seen three ways to characterize B-tree so far: With degree of the B-tree $t$ (either minimum, as in CLRS Algorithms book, or maximum as in B-tree Visualizer). The simplest B-tree occurs when $t=2$. Every internal node then has either 2, 3, or 4 children, and we have a 2-3-4 tree. The text referenced in Nasir’s answer closely follows B-tree ...


5

I am not a data structures expert, but the usual theoretical approach to hashing is that one defines a family of functions (e.g., $h_{a,b}(x) = ax + b \mod p$) and then considers the behavior on a worst case input on a randomly chosen member of the family, where the adversary doesn't know the random choice in advance. This is similar to how randomized ...


5

Hash table lookup can always be $O(1)$ for static sets, see the 2002 paper by Arne Andersson and Mikkel Thorup: Dynamic ordered sets with exponential search trees Firstly, we give the first deterministic polynomial-time (in n) algorithm for constructing a linear space static dictionary with $O(1)$ worst-case access cost (cf. perfect hashing). As ...


5

As far as I can tell, associative array is a newer term, maybe emerging from popular use in dynamic programming languages. In algorithms as an academic field, it seems to denote a generalisation of the dictionary but one usually works with dictionaries (probably because most resource characteristics carry over so one does not need to complicate notation). ...


5

There are probably better examples, but here is one, off the top of my head: Let's say you want to check whether the edit distance between two strings $S,T$ is $\le d$, and if it is, compute the edit distance. You can use the standard dynamic programming algorithm to compute the edit distance, but "prune" the computation (stop the recursion) at any place ...


4

There are several techniques that guarantee that lookups will always require O(1) operations, even in the worst case. How can I determine whether a hash table has a chance of having O(1) operations, and possibly which techniques to use on my hash function? The worst case happens when some malicious attacker (Mallory) deliberately gives you data that ...


4

Order(m) of B-tree defines (max and min) no. of children for a particular node. Degree(t) of B-tree defines (max and min) no. of keys for a particular node. Degree is defined as minimum degree of B-tree. A B-tree of order m : All internal nodes except the root have at most m nonempty children and at least ⌈m/2⌉ nonempty children. A B-tree of (minimum) ...


4

In the case where the universe of items is finite, then yes: just use a bloom filter that records which elements are out of the set, rather than in the set. (I.e., use a bloom filter that represents the complement of the set of interest.) A place where this is useful is to allow a limited form of deletion. You keep two bloom filters. They start out empty....


4

Suppose that you have a very large number of sufficiently uniform elements, $n$, that you want to hash. We want to minimize lookup time, obviously. If we use separate chaining with $m$ linked lists, our lookup time will be, on average, $O(n/m)$ since we have $n$ elements and $m$ buckets. The actual lookup time depends on whether our input set is ...


4

In addition to what everyone else has said, you can get some of the locality back in a separate chaining scenario by unrolling the linked list. Assuming a C-esque language, separate chaining might naively be implemented with a structure like this: struct hash_node { unsigned hash_value; void* data; struct hash_node* next; }; There are plenty ...


3

This is how I use Bloom filter: suppose that full dictionary check is 10x slower than checking a bit in the Bloom filter. Then if you make a Bloom filter having $N$ bits per dictionary word, then average time required for one check would be $1+10/N$. For example, with $N=8$ (i.e., use one byte in Bloom filter per dictionary word), the avg.time will be 2.25 ...


3

Let's analyze how many hash bits you need in your new scheme versus a Bloom filter. First of all, we need to agree about terminology. I will use $q$ to represent the probability of a false positive. For a Bloom filter the design problem of choosing $m$ and $k$ given that you want to hold $n$ elements with false positive rate $q$ is solved by $k = -\lg_2 q$...


3

To answer the explicitly asked question: There probably is no specific name for this data structure since noone has bothered to use or study it. Regarding the underlying question: Even using a "good" hash function, you can not expect as well a degree of balanced as you think: Looking at the node with key $foo$, we see that all keys (in the subtree below $...


3

Let's start with a simpler question. Consider what is perhaps the simplest data structure in existence, an array. For concreteness, let us imagine an array of integers. How much time does the operation $A[i] = A[j]$ take? The answer depends on the computation model. Two models are relevant here: the RAM model (which is more common) and the bit model (which ...


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