home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compress / 2809 < prev    next >
Encoding:
Internet Message Format  |  1992-07-26  |  3.1 KB
  1. Path: sparky!uunet!darwin.sura.net!mips!mips!public!rem
  2. From: rem@public.BTR.COM (Robert E. Maas  rem@btr.com)
  3. Newsgroups: comp.compression
  4. Subject: Re: digraph compression
  5. Message-ID: <7511@public.BTR.COM>
  6. Date: 26 Jul 92 20:51:21 GMT
  7. References: <1992Jul22.230017.1136@athena.mit.edu>
  8. Organization: BTR Public Access UNIX, MtnView CA. Contact: Customer Service cs@BTR.COM
  9. Lines: 43
  10.  
  11. <<I would like to compress a directed graph, but still be able to
  12. determine whether one node points to another directly from the
  13. compressed file. Any suggestions?>>
  14.  
  15. Before your question can be answered, a lot of ambiguities need to be
  16. clarified: Do you have ONLY a set of nodes and directional links, or
  17. are there labels on the nodes and/or the links? Are the labels strings
  18. of text or numbers (integers)? Is there any other information
  19. associated with the nodes or links? (I.e. is this a database with links
  20. between various records, or just a mathematical graph with no
  21. information content other than its structure?) If the nodes have no
  22. labels whatsoever, not even numbers, how do you ask questions about
  23. whether one node links to another or not? What sorts of questions about
  24. links do you specifically need to answer efficiently? (Given x and y,
  25. is there a link from x to y; Given x, what are all y such that there's
  26. a link from x to y; Given y, what are all x such that there's a link
  27. from x to y.) Depending on which kinds of questions you want to answer,
  28. and what the labels on nodes are, various different kinds of hash
  29. tables may be suitable for quickly looking up the answers to those
  30. questions. How many nodes and links are there altogether in your
  31. directed graph? What is the maximum number of characters in a label?
  32. What is the average and maximum amount of data associated with any
  33. node? Maybe if you have a mathematical graph with no labels and no
  34. information content, maybe you just want a way to abstract a given
  35. graph down to the minimum by which you can compare it to another, in
  36. which case hashing the whole graph down to a single 32-bit number would
  37. suffice. (But that doesn't sound like what you want here, right?)
  38.  
  39. If your graph has labels on nodes, and a large number of nodes, and
  40. only a small fraction of possible links exist, and you want to answer
  41. only YES/NO questions whether x->y is a link, a double-hashing on the
  42. two keys with a simple yes/no answer would suffice. The most efficient
  43. way storagewise to do this may be to have a bitmap which is by default
  44. all zeroes but where each x->y link causes several different
  45. pseudo-random bits to be turned to 1 based on the hash number that was
  46. computed. Then to find if a given link appears you check ALL the bits
  47. associated with that x->y link and if ALL are on then the link probably
  48. exists while if not all are on then the link definitely doesn't exist.
  49. If the graph is static, you can compile it once, then run a background
  50. process that generates all possible x->y pairs to see if there are any
  51. false matches, and collect a list of those exceptions. Then discard the
  52. original data (but keep a backup somewhere of course) and use the
  53. bitmap plus the exception list to answer all x->y YES/NO queries.
  54.