News for hackers. Stuff that matters.
Re:Hitchhiker trees: functional, persistent, off-heap sorted... by rdtsc on Friday August 05, 2016 @01:39AM (#12230280)
Those 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... by dgrnbrg on Friday August 05, 2016 @08:44AM (#12231808)
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.

Re:Hitchhiker trees: functional, persistent, off-heap sorted... by rdtsc on Friday August 05, 2016 @12:14PM (#12233456)
Thanks for explaining. That makes sense.

Great work by the way! Really like the description of the code structure on the README page.

If patent is indeed not an issue, I might play with translating that to Erlang. You already did the hard work and also made it functional. I'd have to learn to read Clojure.

Speaking of functional, I was surprised to find the other day, Erlang's queue module implements an Okasaki API, complete with funny function names like deah, liat, and snoc.

http://erlang.org/doc/man/queue.html

Re:Hitchhiker trees: functional, persistent, off-heap sorted... by xytop on Friday August 05, 2016 @02:17AM (#12230387)
> 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... by rdtsc on Friday August 05, 2016 @02:25AM (#12230415)
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... by beagle3 on Friday August 05, 2016 @04:10AM (#12230738)
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... by sitkack on Friday August 05, 2016 @08:03AM (#12231577)
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... by rrobukef on Friday August 05, 2016 @04:18AM (#12230767)
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).