1
$\begingroup$

I have theorised a indexing algorithm (like a B-tree).

However, there's a mental block stopping me actually implementing it.

The algorithm comes in to forms:

form 1:

A look up time of O(1) to O(log2(n))

Each value in the index will have metadata associated to it that is of the size log2(n)*memory address size

form 2:

A look up time of O(1) to O(log2(n)/2)

Each value in the index will have metadata associated to it that is of the size log2(n)*2*memory address size

Unlike B-tree/other index algorithms, there's no time penalty for a add/deletion.

You can for example do a add, then do a search straight after (with no waiting in between).

You get a faster search at the expense of more metadata (memory) along with being able to insert/delete in real time.

You can also do sequential access/search sequential data values fast.

I can't find any other algorithm that has that attributes and time complexity.

If I can get it to work, I plan to sell it.

My question is; would this actually worth anything to anyone/or useful in any particular application?

Or is the amount of memory it uses too much of a deal breaker?

$\endgroup$
  • $\begingroup$ I think that your question is opinion-based. There is no objective question. Even if the data structure was presented, it seems out of the scope here. $\endgroup$ – Evil Jan 8 '17 at 19:15
  • $\begingroup$ What kind of items are you indexing? If we are talking about integers, then this scheme achieves $O(1)$ worst-case lookup and $O(1)$ amortized expected insertion/deletion: arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/… $\endgroup$ – akappa Jan 8 '17 at 19:40
  • $\begingroup$ It's generic, it can be any type of data, integers strings etc. $\endgroup$ – eric Spam Jan 8 '17 at 19:45
  • $\begingroup$ Well, if you think about it you get the same bound by hashing your input data so yeah, that wouldn't be a state-of-the-art result in algorithms and data structure (besides the substantial space occupancy per item). $\endgroup$ – akappa Jan 8 '17 at 19:49
  • $\begingroup$ @akappa Make an answer? $\endgroup$ – Yuval Filmus Jan 8 '17 at 20:09
4
$\begingroup$

If I understand correctly, you have designed a data structure for what is known in the scientific literature as dynamic dictionary problem: keep an index I that can dynamically maintain a set S supporting queries like "is $x \in S$?" under a stream of insertions/deletions.

There are many solutions to this problem. The classical solution is to use a dynamic perfect hash function, which takes $O(1)$ worst case lookup time and $O(1)$ expected amortized update time (it's randomized) and $O(n)$ bits of space.

An arguably more practical solution to your problem is given by Cuckoo hashing, that has the same theoretical bounds of the previous solution but is much easier to understand and implement, and has reportedly better experimental performances.

These solution take much less space than your solution and have favorable time bounds (even if the bound on the update time hold only in expectation).

Moreover, your claim that "add/deletion have no penalty" is unclear to me. If your claim is that an insertion/deletion takes $O(1)$ time, then that's obviously impossible because you cannot build a data structure of size $\Omega(n \log n)$ with time complexity $O(n)$, and if you mean that they take as much time as a look-up, then your solution is no better than any self-adjusting binary tree, like AVLs or Splay trees.

Provided that this problem is well-studied and that there are quite a few high-quality implementations around, I think it is quite hard to design a new competitor that might enjoy commercial success.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.