IRC log of dig on 2011-07-25
Timestamps are in UTC.
- 01:17:56 [melvster]
- melvster has quit (Ping timeout: 260 seconds)
- 01:52:42 [manu`]
- timbl, don't know if you've seen this yet: JSON for Linked Data Playground - http://json-ld.org/playground/
- 01:52:58 [manu`]
- brief bit about it here: http://json-ld.org/
- 01:53:44 [manu`]
- Most important thing: We think we have a good algorithm for normalization of graphs and digital signatures that could apply to N-Triples - implementation is in JSON-LD for the time being.
- 01:54:27 [manu`]
- (click on an example in the playground, like "Person" and then click on the "normalized" tab)
- 01:54:48 [manu`]
- algorithm works with all of the nasty cases in Jeremy Caroll's paper on graph normalization.
- 02:05:05 [tlr]
- tlr (~tlr@130.129.69.163) has joined #dig
- 02:05:43 [tlr_]
- tlr_ (~tlr@130.129.69.163) has joined #dig
- 02:05:43 [tlr]
- tlr has quit (Read error: Connection reset by peer)
- 02:05:43 [tlr_]
- tlr_ is now known as tlr
- 02:20:06 [timbl]
- Algorithm for normalization of graphs for signature?
- 02:20:20 [timbl]
- Did yoiu see Carlos' paper on hashing graphs?
- 02:20:47 [manu`]
- I don't think so, got a link?
- 02:20:51 [manu`]
- (or a full name)
- 02:21:37 [timbl]
- http://portal.acm.org/citation.cfm?id=1809692
- 02:21:45 [timbl]
- Hashing and canonicalizing Notation 3 graphs
- 02:22:11 [timbl]
- Should be on the DIG site as a DIG paper as he did work on it at DIG
- 02:22:17 [manu`]
- "Algorithm for normalization of graphs for signature" == a mechanism to deterministically hash a graph consisting of seemingly identical bnodes.
- 02:23:19 [manu`]
- we needed this for the Web Payments Community Group starting at W3C this coming week - the ability to digitally sign assets and listings for sale - assets/listings are expressed as RDF graphs in the Web Payments work (PaySwarm)
- 02:23:46 [manu`]
- we had supported hashing graphs containing named nodes (nodes w/ IRI identifiers)
- 02:24:19 [manu`]
- but we extended the hashing algorithm to support graphs w/ arbitrary bnodes and improved on Jeremy Carrol's algorithm, which required modifying the graph in order to digitally sign it
- 02:27:08 [manu`]
- timbl, do you know if there is an implementation of Carlos' algorithm anywhere?
- 02:29:16 [manu`]
- that is, has it gone through the wringer? Does it solve the case where there are multiple graph isomophisms as a sub-graph?
- 02:29:26 [manu`]
- and is the implementation performant?
- 02:29:52 [timbl]
- Well, I have sent you a cc on a copy o fte paper
- 02:30:50 [manu`]
- great, thanks - I'll follow up w/ Carlos.
- 02:31:17 [manu`]
- We're trying to get an algorithm standardized for the graph normalization problem.
- 02:35:44 [timbl]
- The original reason I suggested Carlo's student Jesus work on it was that the reasoner needed to sped up its unification of nested graphs, and labelling each iwth a hash would have done that.
- 02:36:35 [timbl]
- There is BTW a graph canonicalization algo in python in the cwm release, and I think Jeremy's and matbve also Carlos's are basically the same way of going about things.
- 02:36:54 [timbl]
- The cwm on onlt does NT not N3 now I think about it
- 02:37:07 [timbl]
- that's why it was called cant.py
- 02:37:36 [timbl]
- http://www.w3.org/2000/10/swap/cant.py
- 02:37:40 [manu`]
- ah, yes - it would certainly speed that sort of operation up. We've needed to normalize graphs for equality testing, graph diff-ing, and digital signatures.
- 02:38:09 [manu`]
- We didn't want to use Jeremy's solution because it modified the output graph.
- 02:38:22 [timbl]
- ?
- 02:38:26 [timbl]
- How do you mean?
- 02:38:44 [manu`]
- it added _:cn14xxx nodes to the output graph.
- 02:38:53 [manu`]
- sorry, properties.
- 02:39:11 [timbl]
- Of.
- 02:39:14 [timbl]
- oh
- 02:39:17 [timbl]
- weird.
- 02:39:27 [manu`]
- so, in order to differentiate nodes, it would add properties to each node until the similarity between two bnodes were broken.
- 02:39:34 [timbl]
- vaguely rings a bell
- 02:39:42 [manu`]
- and you must do something like that if you don't want to go into NP territoriy.
- 02:40:39 [manu`]
- our approach generates a series of path strings (which can be sped up quite a bit on modern CPUs)... and doesn't require anything to be added to the graph... and has some nice performance characteristics on very large graphs containing very large isomorphic subsets.
- 02:40:55 [timbl]
- WhatI found is that with a real graph, in fact the environment around bnodes are typically very different, so establishing an ordering of the bnodes is easy.
- 02:41:06 [timbl]
- You don't have to do any work at all in a lot of cases.
- 02:41:13 [manu`]
- yes, exactly
- 02:41:16 [manu`]
- we found the same thing.
- 02:41:26 [manu`]
- most of the NP cases are useless graphs.
- 02:41:48 [manu`]
- (in fact, we haven't found an NP case that is a useful graph)
- 02:42:03 [timbl]
- In some cases, you have so much symmetry that seatrching for miles doesn't find a difference -- then you exit wiht error
- 02:42:27 [timbl]
- and say sorry can't sign that graph - try a less weird one
- 02:42:32 [manu`]
- yes, we have a "processing depth" flag that is set if you go off into NP territory.
- 02:43:02 [timbl]
- I've never had it happen using cant.py for comparing graphs output vs expected in the cwm regeressiontesting for example.
- 02:43:44 [manu`]
- we're busy attempting to generate some really nasty graph isomorphisms during the next couple of weeks to test out the algorithm.
- 02:44:13 [manu`]
- where is your regression testing source repo, btw? We'll include those in the JSON-LD normalization tests.
- 02:44:26 [timbl]
- One way to make it work in engineering practcie is to specify a set of graphs which will always work.
- 02:44:29 [manu`]
- (We have implementations for JSON-LD in Python, PHP, JavaScript and C++ at the moment, btw)
- 02:44:32 [timbl]
- for useers.
- 02:45:19 [manu`]
- yes, but we still need to catch "poison" messages in our system... to prevent DDoS attacks - sending the payment network highly isomorphic graphs
- 02:45:30 [manu`]
- np - thanks for the pointers... will follow up w/ Carlos
- 02:45:33 [timbl]
- yes, you need a limit
- 02:45:39 [timbl]
- y w
- 02:45:42 [timbl]
- kutgw
- 02:45:50 [manu`]
- thx - and you :)
- 02:47:16 [timbl]
- (What intruiged me was whether you could hash a graph much faster than canonicalize it)
- 02:48:05 [manu`]
- hmm interesting... i'd think you couldn't hash it w/o canonicalizing it first.
- 02:58:25 [tlr]
- tlr has quit (Quit: tlr)
- 03:58:13 [tlr]
- tlr (~tlr@modemcable053.6-176-173.mc.videotron.ca) has joined #dig
- 04:56:12 [nunnun]
- nunnun has quit (Ping timeout: 258 seconds)
- 05:00:27 [nunnun]
- nunnun (~nunnun@p2.nunnun.jp) has joined #dig
- 05:05:03 [melvster]
- melvster (~melvin@p4FF96E12.dip.t-dialin.net) has joined #dig
- 05:35:32 [melvster1]
- melvster1 (~melvin@p5797FEF1.dip.t-dialin.net) has joined #dig
- 05:37:30 [melvster]
- melvster has quit (Ping timeout: 276 seconds)
- 06:03:12 [melvster1]
- melvster1 has quit (Ping timeout: 252 seconds)
- 10:01:10 [danbri]
- danbri has quit (Ping timeout: 252 seconds)
- 10:03:22 [danbri]
- danbri (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 10:35:08 [danbri_]
- danbri_ (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 10:36:31 [danbri]
- danbri has quit (Ping timeout: 240 seconds)
- 10:37:12 [Yudai__]
- Yudai__ has quit (Quit: Tiarra 0.1+svn-36726: SIGTERM received; exit)
- 10:40:21 [danbri]
- danbri (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 10:41:54 [danbri_]
- danbri_ has quit (Ping timeout: 276 seconds)
- 10:52:41 [AlexZ]
- AlexZ (~quassel@host220-77-dynamic.16-87-r.retail.telecomitalia.it) has joined #dig
- 10:53:39 [danbri_]
- danbri_ (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 10:54:58 [danbri]
- danbri has quit (Ping timeout: 258 seconds)
- 11:03:10 [Yudai]
- Yudai (~Yudai@pa3592a.hkidnt01.ap.so-net.ne.jp) has joined #dig
- 11:28:27 [RalphS]
- RalphS (Ralph@30-7-118.wireless.csail.mit.edu) has joined #dig
- 11:31:16 [DIGlogger]
- DIGlogger (~dig-logge@groups.csail.mit.edu) has joined #dig
- 11:31:16 [niven.freenode.net]
- topic is: Decentralized Information Group @ MIT http://dig.csail.mit.edu/
- 11:31:16 [niven.freenode.net]
- Users on #dig: DIGlogger RalphS Yudai danbri_ AlexZ nunnun tlr timbl manu` presbrey manu-db mattl ericP sandro
- 11:33:59 [melvster]
- melvster (~melvin@p5797EAF2.dip.t-dialin.net) has joined #dig
- 11:36:49 [RalphS]
- RalphS has quit (*.net *.split)
- 11:36:49 [danbri_]
- danbri_ has quit (*.net *.split)
- 11:37:39 [RalphS]
- RalphS (Ralph@30-7-118.wireless.csail.mit.edu) has joined #dig
- 11:39:07 [danbri_]
- danbri_ (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 12:01:32 [timbl]
- timbl has quit (Quit: timbl)
- 12:06:45 [AlexZ]
- AlexZ has left #dig
- 12:14:23 [danbri_]
- danbri_ has quit (*.net *.split)
- 12:14:46 [danbri]
- danbri (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 12:42:41 [danbri_]
- danbri_ (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 12:43:03 [danbri]
- danbri has quit (Ping timeout: 258 seconds)
- 12:55:28 [tlr]
- tlr has quit (Quit: tlr)
- 13:05:11 [danbri]
- danbri (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 13:05:58 [danbri_]
- danbri_ has quit (Ping timeout: 252 seconds)
- 13:10:37 [timbl]
- timbl (~timbl@31-35-173.wireless.csail.mit.edu) has joined #dig
- 13:15:51 [tlr]
- tlr (~tlr@130.129.21.39) has joined #dig
- 13:17:14 [timbl]
- timbl has quit (Read error: Connection reset by peer)
- 13:54:02 [timbl]
- timbl (~timbl@31-35-173.wireless.csail.mit.edu) has joined #dig
- 14:00:17 [scor]
- scor (~scor@drupal.org/user/52142/view) has joined #dig
- 14:01:09 [amy]
- amy (~amy@30-5-15.wireless.csail.mit.edu) has joined #dig
- 14:30:38 [betehess]
- betehess (~betehess@betehess.w3.org) has joined #dig
- 14:45:49 [timbl]
- timbl has quit (Quit: timbl)
- 14:46:09 [tlr]
- tlr has quit (Quit: tlr)
- 14:51:10 [timbl]
- timbl (~timbl@31-35-173.wireless.csail.mit.edu) has joined #dig
- 14:51:20 [tlr]
- tlr (~tlr@dhcp-1527.meeting.ietf.org) has joined #dig
- 14:52:32 [danbri_]
- danbri_ (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 14:53:34 [danbri]
- danbri has quit (Ping timeout: 264 seconds)
- 15:01:48 [danbri_]
- danbri_ has quit (Ping timeout: 258 seconds)
- 15:04:08 [danbri]
- danbri (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 15:17:32 [timbl]
- timbl has quit (Quit: timbl)
- 15:22:11 [danbri_]
- danbri_ (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 15:22:23 [danbri]
- danbri has quit (Ping timeout: 240 seconds)
- 15:31:28 [tlr]
- tlr has quit (Quit: tlr)
- 15:34:26 [danbri_]
- danbri_ has quit (Ping timeout: 240 seconds)
- 15:37:11 [danbri]
- danbri (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 15:49:26 [timbl]
- timbl (~timbl@31-35-173.wireless.csail.mit.edu) has joined #dig
- 15:59:15 [timbl]
- timbl has quit (Quit: timbl)
- 15:59:37 [timbl]
- timbl (~timbl@31-35-173.wireless.csail.mit.edu) has joined #dig
- 16:19:51 [timbl]
- timbl has quit (Quit: timbl)
- 16:26:12 [danbri]
- danbri has quit (Ping timeout: 276 seconds)
- 16:27:42 [danbri]
- danbri (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 16:28:19 [timbl]
- timbl (~timbl@31-35-173.wireless.csail.mit.edu) has joined #dig
- 16:37:50 [timbl]
- timbl has quit (Quit: timbl)
- 16:44:13 [danbri_]
- danbri_ (~danbri@ip176-48-210-87.adsl2.static.versatel.nl) has joined #dig
- 16:44:47 [danbri]
- danbri has quit (Ping timeout: 246 seconds)
- 17:29:45 [tlr]
- tlr (~tlr@dhcp-1527.meeting.ietf.org) has joined #dig
- 17:39:35 [timbl]
- timbl (~timbl@31-35-173.wireless.csail.mit.edu) has joined #dig
- 18:59:37 [tlr]
- tlr has quit (Quit: tlr)
- 19:09:57 [tlr]
- tlr (~tlr@dhcp-1527.meeting.ietf.org) has joined #dig
- 19:14:35 [tlr]
- tlr has quit (Client Quit)
- 19:59:45 [timbl]
- timbl has quit (Quit: timbl)
- 20:17:25 [RalphS]
- RalphS has quit ()
- 20:33:50 [timbl]
- timbl (~timbl@31-35-173.wireless.csail.mit.edu) has joined #dig
- 21:13:01 [timbl]
- timbl has quit (Quit: timbl)
- 22:21:28 [scor]
- scor has quit (Quit: scor)
- 23:05:44 [tlr]
- tlr (~tlr@207.164.135.98) has joined #dig
- 23:28:04 [tlr]
- tlr has quit (Quit: tlr)