Hitchhiker trees: functional, persistent, off-heap sorted maps
1–10 of 33 posts
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#2Those are very cool, and functional too!
> As it turns out, after I implemented the fractal tree, I spoke with a former employee of Tokutek, a company that commercialized fractal tree indices. That person told me that we’d actually implemented fractal reads identically!
That's not necessarily a good thing. Last I heard Tokutek patented that. Not a laywer, from what I understand patents specifically pertain to "implementation".
Not sure what happened after they were acquired by Percona, but, as I am in US I would personally stay away from it. Even if current owner doesn't want to enforce the patent, the next one might.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#3Those are very cool, and functional too! > As it turns out, after I implemented the fractal tree, I spoke with a former employee of Tokutek, a company that commercialized fractal tree indices. That person told me that we’d actually implemented fractal reads identically! That's not necessarily a good thing. Last I heard Tokutek patented that. Not a laywer, from what I understand patents specifically pertain to "implem…
> Not a laywer, from what I understand patents specifically pertain to "implementation".
There should be identical blocks of code which I doubt they have. I think by "identically" they mean the same thought/method.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#4Those are very cool, and functional too! > As it turns out, after I implemented the fractal tree, I spoke with a former employee of Tokutek, a company that commercialized fractal tree indices. That person told me that we’d actually implemented fractal reads identically! That's not necessarily a good thing. Last I heard Tokutek patented that. Not a laywer, from what I understand patents specifically pertain to "implem…
> Not a laywer, from what I understand patents specifically pertain to "implementation". There should be identical blocks of code which I doubt they have. I think by "identically" they mean the same thought/method.
Identical blocks of code, I think make sense for copyright cases -- "they copied our code, look here it is lines 12 through 25". Instead I believe patents are about a particular implementation of an idea.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#5Funny: I implemented the exact same thing, with a focus on AWS and pagination (albeit less well-documented):
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#6Earlier quoted context omitted.
> Not a laywer, from what I understand patents specifically pertain to "implementation". There should be identical blocks of code which I doubt they have. I think by "identically" they mean the same thought/method.
Identical blocks of code, I think make sense for copyright cases -- "they copied our code, look here it is lines 12 through 25". Instead I believe patents are about a particular implementation of an idea.
They are supposed to be about a particular implementation, but the USPTO awards then for ideas (stuff like "treat years less than 50 as 19xx and above 50 as 20xx" and LZW, which are each implementable in many ways).
Courts assume the USPTO is competent, so overturning a patent is extremely costly. The bottom line is: practically speaking, ideas are patentable but without complete certainty of prevailing in court.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#7Earlier quoted context omitted.
> Not a laywer, from what I understand patents specifically pertain to "implementation". There should be identical blocks of code which I doubt they have. I think by "identically" they mean the same thought/method.
Identical blocks of code, I think make sense for copyright cases -- "they copied our code, look here it is lines 12 through 25". Instead I believe patents are about a particular implementation of an idea.
Isn't one of the prerequisites of a patent also a 'new and novel idea'? Since the author did not base his work on the patent it is by definition not novel anymore. This is exacerbated by other implementations like libbruce (see other comments).
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#8Earlier quoted context omitted.
Identical blocks of code, I think make sense for copyright cases -- "they copied our code, look here it is lines 12 through 25". Instead I believe patents are about a particular implementation of an idea.
They are supposed to be about a particular implementation, but the USPTO awards then for ideas (stuff like "treat years less than 50 as 19xx and above 50 as 20xx" and LZW, which are each implementable in many ways). Courts assume the USPTO is competent, so overturning a patent is extremely costly. The bottom line is: practically speaking, ideas are patentable but without complete certainty of prevailing in court.
Not only are ideas patentable, just recognizing a need or problem is patentable. One doesn't even need a solution.
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#9Does someone know of an existing visualization of this algorithm, for better understanding?
Re: Hitchhiker trees: functional, persistent, off-heap sorted maps
#10Those are very cool, and functional too! > As it turns out, after I implemented the fractal tree, I spoke with a former employee of Tokutek, a company that commercialized fractal tree indices. That person told me that we’d actually implemented fractal reads identically! That's not necessarily a good thing. Last I heard Tokutek patented that. Not a laywer, from what I understand patents specifically pertain to "implem…
Creator here. I would absolutely agree with this, but let me shed a bit more light to clarify: the underlying idea of B+ trees with inline caches is not patented (or maybe it was, but a long time ago?). Tokutek's patents are all focused on the methods they use to achieve concurrent operations on a single tree--they have a very interesting & novel locking protocol.
The Hitchhiker tree completely avoids their patents, since it makes very different decisions in order to become purely functional.