Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The hunt for the missing data type

hillelwayne.com

Post reply on HN
Print view View original

151–160 of 259 posts

Re: The hunt for the missing data type

#151

Post by js8 »

rhelz wrote: post #79

Ya, the central obstacle is that: 1. for simple and small graph problems, a simple vector-of-vectors adjacency list is easy enough to code up. 2. For complex and huge graph problems, the only way to get performant solutions is to tailor the graph implementation to the specific details of the problem to be solved. And its hard to see what kind of language support would help, other than just having a super-smart compil…

> we are really good at code sharing of small things like vectors, and of large things like operating systems. Its the middle-sized problems we are bad at.

Interesting. But I am not sure we are good at sharing small things - every programming language has its own implementation of vectors. Within one language ecosystem, the API of a vector is small, and that's probably what makes it easy to share.

For operating systems, the API is relatively small compared to the internal complexity of the OS. This is also true for libraries for numerical problems, which are also easily shared. But the more you want to customize things (e.g. share a complicated data structure), this complicates the API and inhibits sharing.

So it seems to this is determined by the surface area (relative size of the API) of the thing being shared.

Re: The hunt for the missing data type

#152

Post by jcgrillo »

michelpp wrote: post #39

I think one of the elements that author is missing here is that graphs are sparse matrices, and thus can be expressed with Linear Algebra. They mention adjacency matrices, but not sparse adjacency matrices, or incidence matrices (which can express muti and hypergraphs). Linear Algebra is how almost all academic graph theory is expressed, and large chunks of machine learning and AI research are expressed in this langu…

I was really excited about RedisGraph, and sad to see it was cancelled. In my (limited) experience with graph databases they proved very frustrating because it seemed like they tried to do too much. Ultimately the way I thought of a graph was an indexing strategy into some underlying data. So I needed the graph to be very quick, but I didn't have any requirement to store actual data in it--just references. This made triples based graph storage seem very heavy-handed.

The idea of composing sparse linear transformations to optimize queries is really cool. You can get a lot of work done in one shot that way, in a manner that's just quite a lot easier on the machine than chasing pointers around.

Re: The hunt for the missing data type

#153

Post by michelpp »

Chris_Newton wrote: post #122
tikhonj wrote: post #59

Earlier quoted context omitted.

FGL is a great example of how to make a "nice" high-level graph interface suited for functional programming. I'm a big fan. But it's orders of magnitude too slow and memory-inefficient for performance-sensitive graph computations—if you have even moderately sized graphs and graph algorithms are a bottleneck, you'll need to use something else, and probably something domain-specific. Given the way the interface works,…

But it's orders of magnitude too slow and memory-inefficient for performance-sensitive graph computations—if you have even moderately sized graphs and graph algorithms are a bottleneck, you'll need to use something else, and probably something domain-specific. This seems a little pessimistic to me. There are plenty of application domains that can be conveniently represented using graphs where you might have thousands…

> you probably want more specialised tools like BLAS/LAPACK

The GraphBLAS and LAGraph are sparse matrix optimized libraries for this exact purpose:

https://github.com/DrTimothyAldenDavis/GraphBLAS

https://github.com/GraphBLAS/LAGraph/

Re: The hunt for the missing data type

#154

Post by skybrian »

TachyonicBytes wrote: post #114
jjice wrote: post #14

Earlier quoted context omitted.

I used to think that since graphs are such a broad data structure that can be represented in different ways depending on requirements that it just made more sense to implement them at a domain-ish level (the article mentions this in the "There are too many implementation choices" section). Then I saw Petgraph [0] which is the first time I had really looked at a generic graph library. It's very interesting, but I stil…

Why wouldn't an abstract `Graph` type and specific implementations of that work? Like Java has for `Set` and various implementations?

For importing and exporting data, it often makes more sense to use something like a table or a tree rather than a graph. (Like a CSV file or a JSON file.)

So it's not clear what the interface would do. What methods should there be? Again, there are too many choices, and a Graph interface often isn't the best way to represent a view of some subset of a graph.

Re: The hunt for the missing data type

#155

Post by kragen »

gloftus wrote: post #142
ylow wrote: post #123

I think this is because a graph is not a data-structure nor a data-type. It is really an abstraction. Fundamentally, all I need to define a graph is a set of vertices v \in V and function Neighbors(v). And that really is all is needed for the most foundational set of graph algorithms. Everything else are case-by-case constraints. Does A->B imply B->A? is the node set partitionable with certain constraints? Are there…

Yes, graphs are ubiquitous because they are so abstract. They live on the same level of abstraction as pure numbers. There are useful "numerical" libraries that exist, and by analogy I think you could say there are also useful "graphical" libraries that exist. But we don't really have "number" libraries, and we don't really have "graph" libraries, because those concepts are a bit too abstract to write APIs against.

it's true that numbers are very abstract, which is what makes it so easy to design apis for them

the python runtime includes four built-in number types (small integer, arbitrary-precision integer, float, and complex) and the python standard library includes two more number types (decimal and fractions), and one of the most popular non-standard libraries for python is numpy, which provides some other kinds of numbers such as single-precision floats, vectors, and matrices. other systems like pari/gp have number libraries that provide other kinds of numbers, such as p-adic numbers and galois field elements

the only programming languages i've ever used that didn't have 'number' libraries were esoteric languages like brainfuck and the lambda calculus

Re: The hunt for the missing data type

#156

Post by bigbillheck »

ogogmad wrote: post #109
bigbillheck wrote: post #105

Earlier quoted context omitted.

You're a couple decades too late: https://graphblas.org

If you read what I wrote, you'd see I never claimed originality. Anyway, that's cool. I'll need to check how much abstract algebra stuff they use. Using semirings (uh, rigs) alone isn't impressive. Do they consider semirings with more algebraic structure attached to them?

> Using semirings (uh, rigs) alone isn't impressive. Do they consider semirings with more algebraic structure attached to them?

Wiki says they have R, the two tropical semirings, the 'max-min' semiring, and GF(2). The tropical and max-min have your idempotency requirement, all but the max-min have involution.

Re: The hunt for the missing data type

#157

Post by DylanSp »

rdtsc wrote: post #108

> There’s a gap between how often software engineers could use graphs and how little our programming ecosystems support them. Where are all the graph types? They've been there for quite a while :-) https://www.erlang.org/doc/man/digraph.html https://www.erlang.org/doc/man/digraph_utils And if you want to do some set theoretical stuff you're covered as well: https://www.erlang.org/doc/man/sofs.html

Erlang's briefly mentioned at the end of the article:

> There are two other languages I found with graph types: Erlang and SWI-Prolog. I don’t know either language and cannot tell when they were added; with Erlang, at least, it was before 2008. I reached out to a person on the Erlang core language committee but did not hear back.

Re: The hunt for the missing data type

#159

Post by Nevermark »

somat wrote: post #84
obi1kenobi wrote: post #3

As someone who did a lot of work with graphs, "why don't programming languages have a built-in graph data type?" is a question I’ve been asked a million times. I'm thrilled I'll be able to point folks to a much more in-depth analysis like the one here, instead of saying some variation of "it's really hard to do it well" and having them just take my word for it.

This is a super naive take. but I would consider the pointer the be the native graph type. What is wanted is not a graph type but the tooling to traverse graphs.

Generalized pointers (RAM addresses, disk storage locations, network locations, etc.) would be the general way to implement explicit literal graphs.

Other graphs, that are partly or wholly computed or recomputed as needed from other relationships, could be considered "implicit" graphs and can be implemented many other ways.

The fact that graphs can be any combinations of literally or dependently defined, static or dynamic defined, would add even more complexity to any truly general graph library.

Re: The hunt for the missing data type

#160

Post by ratmice »

gilleain wrote: post #8

> And then for each of those types we have hypergraphs, where an edge can connect three or more nodes, and ubergraphs, where edges can point to other edges. Huh, I've heard of hypergraphs (although never actually really used them) but never an 'ubergraph'. Sounds tricky! In practice, how often are there situations you definitely need hypergraphs? I had a particular situation where I needed graphs that were both verte…

ubergraphs are pretty weird, i've never actually seen them really used anywhere. Just a couple of papers pointing out their existence. They have some weird quirks like every hypergraph and thus graph has a dual, but ubergraphs with uberedges do not appear to have one.
Post reply on HN