[FoRK] Non-speech, non-keyboard direct communications will create a new class of humans

J. Andrew Rogers andrew at jarbox.org
Tue Jun 25 19:30:32 PDT 2013

On Jun 25, 2013, at 5:28 PM, Stephen Williams <sdw at lig.net> wrote:
>> When using a curve as a computational structure there are some abstract types that are not tractable on curves that share their dimensionality. They can be mapped via a transform function onto a higher dimensionality curve in which
> I can see that.  But what types of intractableness have you run across?

Without using all the stuff I just talked about, polynomial space complexity trading off linear search complexity and/or lack of parallelism. It shows up all the time in spatial analysis, constraint processing, etc at non-trivial scales which is where I first ran across it. There are a bunch of scaling challenges in distributed systems that are equivalent to this problem.

> The obvious examples are non-linear, non-monotonic dimensions that are really a combination or function of multiple dimensions already.

No need to get that complicated. Simple interval types will suffice.

> What do you call this type of theory / topic?  What are the foundational papers here?

Most of the early work shows up in database indexing literature from the 80s and early 90s related to multidimensional indexing. Widmayer did some smart work in this area (and gave up on finding a solution). There isn't a term for it, it is just an extreme generalization and fusion of data representation/indexing theory and distributed/parallel computation. HPC world was using some of these concepts for a long time for parallel work without inventing a field around it. I've grasped several parts of this elephant at various times but almost none of the research into aspects of it is integrated with anything else and the equivalencies that tie specialist domains together has not been publicly explored much. It has become a very active area over the last five years but almost all of the R&D is happening at companies.

>> Brilliant for building distributed data structures, and more scalable than hash tables with about as much code. Much harder to understand though.
> How much more scalable?

No real limit. Efficiency improves with scale as you would expect. 

Hashing, in addition to not being very expressive due to only preserving equality relationships, becomes less efficient as the scales become large.

More information about the FoRK mailing list