Follow Slashdot blog updates by subscribing to our blog RSS feed

 



Forgot your password?
typodupeerror
Software

Faster P2P By Matching Similiar Files? 222

Posted by CmdrTaco
from the something-doesn't-jive-here dept.
Andreaskem writes "A Carnegie Mellon University computer scientist says transferring large data files, such as movies and music, over the Internet could be sped up significantly if peer-to-peer (P2P) file-sharing services were configured to share not only identical files, but also similar files. "SET speeds up data transfers by simultaneously downloading different chunks of a desired data file from multiple sources, rather than downloading an entire file from one slow source. Even then, downloads can be slow because these networks can't find enough sources to use all of a receiver's download bandwidth. That's why SET takes the additional step of identifying files that are similar to the desired file... No one knows the degree of similarity between data files stored in computers around the world, but analyses suggest the types of files most commonly shared are likely to contain a number of similar elements. Many music files, for instance, may differ only in the artist-and-title headers, but are otherwise 99 percent similar.""
This discussion has been archived. No new comments can be posted.

Faster P2P By Matching Similiar Files?

Comments Filter:
  • Nickelback? (Score:5, Funny)

    by onemorehour (162028) * on Wednesday April 11, 2007 @10:46AM (#18690017)

    Many music files, for instance, may differ only in the artist-and-title headers, but are otherwise 99 percent similar.


    Well, sure, if you're only looking at Nickelback [thewebshite.net] songs.
    • Re:Nickelback? (Score:5, Informative)

      by beckerist (985855) on Wednesday April 11, 2007 @10:54AM (#18690193) Homepage
      The idea is that the song "Girl Talk - Once Again" might be represented as "girltalk-onceagain" "girl talk - once again" "GirlTalk - Once Again" "01-once again.mp3" "OnceAgain.mp3"

      Being that the only difference is just the text (ID3, ID3-2) tags, the rest of the song is exactly the same, so why can't you use that as a download source too? I personally organize all of my music, and because of this P2P programs believe that it's an entirely new file, when really it was just renamed and the header information was changed (generally to be grammatically correct.)</summary>
      • Re:Nickelback? (Score:5, Interesting)

        by thepotoo (829391) <thepotoospam@yah[ ]com ['oo.' in gap]> on Wednesday April 11, 2007 @11:17AM (#18690599)
        If you use bittorrent, the DHT protocol (supported by Azureus, BitComet, and uTorrent, among others) does the exact thing you're describing. It checks MD5 hashes for files (the whole file, not the pieces, I think), and connects you to peers which have the same file.
        DHT even supports partially corrupted files, your client just discards the corrupt data.

        My question is, why would I want to use SET over DHT? Does SET not need a ceneralized server, or does it have any other advantage at all?
        TFA is really short on technical details, but it sounds to me as though SET is just a re-design of DHT. Still, I imagine SET support will be in the next builds of all the major bittorrent clients if it ends up being worth something.

        • by beckerist (985855)
          I read this as being less effective for bittorrent (as your assumption is correct, DHT basically does this on its own already) and more effective for Gnutella. While the gnutella network is maturing to a level past the Bearshare/Limewire days, there are still inherent problems with download speeds simply because a mechanism like DHT (or as the article calls it SET) doesn't currently exist. Are there problems with DHT? Absolutely, I get node errors all the time in Bittyrant. I think this is just the next nat
          • by beckerist (985855)
            errrrr...sorry. I need to proofread better. Instead of saying "I think this is just the next natural extension for Bittorrent..." I meant to say "next natural extension for Gnutella."

            --beckerist
        • Re:Nickelback? (Score:4, Informative)

          by Robotech_Master (14247) * on Wednesday April 11, 2007 @11:46AM (#18691075) Homepage Journal
          If I understand the article right, SET looks at individual files within a particular download. DHT just looks at the whole download.

          For instance, if I'm uploading my "Songs I Like to Dance To" mp3 mix, and someone else is uploading an "All-Time Greatest Dance Hits" CD rip, and there are a couple of songs both uploads have in common, SET would enable someone downloading my MP3 mix to treat the CD rip as a partial seed (and vice versa), and pull down the songs held in common from either one.

          Whereas DHT would simply enable people to pull down my mix from other people uploading the mix, or the CD rip from other people uploading the CD rip, even if the tracker was down. (If I understand what DHT does correctly. Which it is possible I don't.)
        • Re:Nickelback? (Score:5, Interesting)

          by Andy Dodd (701) <atd7&cornell,edu> on Wednesday April 11, 2007 @11:46AM (#18691089) Homepage
          If I recall correctly, DHT takes the file name into account when calculating the hash. Thus identical files with different names are treated differently.

          Some P2P protocols allow looking up a file by a hash which does not take filename into account, but this will not handle the case where the files differ in only one small section. The best example is the following:
          Person downloads an MP3.
          Person finds that the MP3 is not properly tagged (for example, has a comment field saying who ripped it/released the rip, and has no track number.)
          Person changes the MP3's ID3 tag
          Now, nearly all existing P2P protocols will treat the new file as a completely different file, when in reality the most important contents (the audio itself) have not changed, only the file's metadata.
          Other users will go for the "full-file" match with the largest number of sources, thus causing the mistagged MP3 to propagate more than a "fixed" one.

          So a P2P system that ignores the ID3 tag when hashing would have significant advantages, in which the user could download the file from many sources and then choose which source to get their metadata from.
          • by beckerist (985855)
            The problem might be inherent to MP3's though. Header information is still stored as binary information in the file, changing the amount of bits in the file, therefore the hash (as read by any hashing system I'm aware of.) If there were a way to store the header text such that it doesn't affect the filesize, current P2P protocols/software might already be able to do this...
            • by dreamlax (981973)
              I guess the idea would be to truncate the file on either end (depending on where the meta data is stored) to have the raw MP3 data. Hashing just that would mean that people such as myself who not only rename but re-tag all my MP3s (because I hate seeing things like "santana - baila mi hermana " . . . Capitalise!) would still be able to share our MP3s the same way we got it from someone else, and that next person can tag it however they please.
          • Re: (Score:3, Informative)

            by thepotoo (829391)
            Actually, DHT doesn't care about file names. You can test this yourself if you have a LAN. Grab a torrent, start downloading it on one computer (save as a different filename), get a little of the file downloaded, and start the same torrent on a different computer. Use your firewall to block the second computer's access to the tracker. DHT will kick in, your computers will log in, get each other's IPs, and computer 2 will get an insanely fast download speed until it catches up with computer 1.
            Tested on u
          • Re: (Score:3, Informative)

            by evilviper (135110)

            Some P2P protocols allow looking up a file by a hash which does not take filename into account,

            By "Some", you mean "Every Single Frickin' One Of Them", right?

            nearly all existing P2P protocols will treat the new file as a completely different file,

            No. Only the most brain-dead P2P protocols will. "tree" hashes are in use by several P2P protocols. Some are just old or primitive, and have a large number of old servants around that don't understand newer hashes.

        • Re: (Score:2, Interesting)

          by Anonymous Coward
          No, it's a different kind of identifying which blocks are interesting in a swarm download.

          Basically - and this isn't the first time this idea has been tabled, I have an unpublished paper and a reference implementation - chuck BT's idea in the bin, as it uses lists of SHA1 hashes and that's not suitable for this. Shareaza's better placed to do this technically, but you could of course adapt torrent.

          What you actually want to use is a TTH - Tiger Tree Hash (THEX standard). That's a Merkle hash tree based on TI
        • TFA is really short on technical details, but it sounds to me as though SET is just a re-design of DHT. Still, I imagine SET support will be in the next builds of all the major bittorrent clients if it ends up being worth something.

          As TFA current describes things, I'm really struggling to find a use for this feature that does not involve copyright infringement. The rightsholders for "legitimate" p2p traffic already have a strong incentive to act as a central authority for low-bandwidth meta-data.

          I think th
        • SET seems to be an incremental update of DHT or MD5 hashes.
          Most recent p2p use hashes to recognize files instead of just filename, BUT this makes that music files that are different in their header will come out as different.
          This method allows just to distinguish between data and meta-data for the file and allo the meta data to be different.
          Anyway, just my understanding of it.
          Otherwise, i'm sure they could just do md5 hashes of all your 16k/32k/64k parts of all your shared files and download parts with the
      • Re:Nickelback? (Score:4, Interesting)

        by hey! (33014) on Wednesday April 11, 2007 @11:41AM (#18690987) Homepage Journal
        I don't think this is just about inconsistent metadata.

        I think what he's talking about may be more like the document fingerprinting algorithms used to pare search engine results, or to detect plagiarism in student papers.

        In some cases you will be downloading components of a file from two sources, neither of which have the others' component. The example in TFA was downloading the video portion of a movie from a foreign language site and the audio from a site with the language you speak but less bandwidth.

        I suppose another example would be that if you were downloading an anthology of stories, you could take a particular story from a server that hosted a different anthology including that story. Or maybe you are downloading the new distro; you could take some of your files from sites offering the distro version you are looking for, some from sites only offering the files you need to upgrade to that version, and some from entirely different distros or much older versions if they happened to be the same.

        I guess it could be thought of as a kind of "fuzzy akamai".

        It's an interesting idea, but I don't see any commercial support for it. In fact I see commercial opposition under the current regime of copyright laws and royalty based business models.

        • "It's an interesting idea, but I don't see any commercial support for it. In fact I see commercial opposition under the current regime of copyright laws and royalty based business models."

          Who needs commecial suport for P2P?


    • Well, sure, if you're only looking at Nickelback songs.


      Or "theory of a deadman" or "default"

      I think they should merge and call themselves Theory of a Nickelfault

      =D
  • grea tide a (Score:5, Funny)

    by underwhelm (53409) <underwhelm&gmail,com> on Wednesday April 11, 2007 @10:51AM (#18690103) Homepage Journal
    I'm hoping this CATCHES ON and wet ransfer a11 sorts of information like this. It'11 be 1ike getting every thing in the form of a ransom n0te.
  • by Vollernurd (232458) on Wednesday April 11, 2007 @10:51AM (#18690111)
    So it's not me then? All new tunes DO sound the same?
  • porn.

    No wait, hear me out. Most porn is going to be largely white or black skin colour (particularly with Friesian Cows if you're into that sort of thing), so the P2P can just find a chunk with a similar amount of that colour and download that!
  • Summary: (Score:5, Informative)

    by PhrostyMcByte (589271) <phrosty@gmail.com> on Wednesday April 11, 2007 @10:53AM (#18690153) Homepage
    instead of sharing files, divide them into 16KB chunks and share those, to help work around files that get renamed or trivially altered (eg a website tagging their url to all the files you upload).
    • If the file length was affected, the 16KB chunks would absolutely differ starting at the point where the length was affected.
    • by EllisDees (268037)
      Even better, just ignore the metadata and search on a hash of the actual content. I'm not sure where the ID3 tags are placed (and I'm too lazy to look it up right now) in an mp3, but if you strip them off and ignore the file name, you should have the raw mp3 data left over.
  • LOTS of overhead just to find the chunks.
    The article talks about 16kb chunks, which for a dvd image would take more than the torrent protocol currently allows.

    The client would spend more time communicating its chunk lists around than actually getting data.

    (If I remember rightly, torrents can have a max of 65535 chunks and some servers prevent huge .torrent files which contain the chunk breakpoints anyway)
    • by burris (122191)
      Sorry, the limit on the number of pieces in a torrent is 2^32. The message length prefix (i.e. the max length of the have-bitfield) as well as the piece indicies are 4-byte unsigned ints.
  • by brunascle (994197)
    not particularly new. many P2Ps have been grouping identical files together. i know one of the early ones did it (was it Napster, Audiogalaxy?), but i think only if the files were 100% identical other than the filename.

    there's definitely potential for problem here. what if those files really arent supposed to be the same? a swapped byte here and there could have huge effects on the end result.
  • Wouldn't this generate a lot more overhead traffic?
    I'm sure smarter people than I have already thought this out,
    but that seems to be the most immediate downside.

    "SET divides a one-gigabyte file into 64,000 16-kilobyte chunks"

    In other words: instead of seeking out the one master-hash for the file,
    your P2P is looking up the thousands of chunk hashes.

  • I have no idea what the overheads might be for their "handprinting" algorithms, or how effective they are. But I've wondered in the past whether something vaguely similar could be achieved by for example hashing each stream and headers separately in audio and video files, or each file within an archive. The same could apply to any container format. That would certainly deal with e.g. the same mp3 with different ID3 tags, and the overheads might be lower. Could get messy though, I guess.
  • by Anonymous Coward
    I think everyone posting above saying "it won't work" should RTFA.

    This works by breaking files down into clusters and hashing the clusters (like Bittorrent already does). Then it searches for other shares that have clusters with the same hash value, and requests them.

    Assuming that the hashing scheme being used it "good" in that there are no collisions, two clusters with the same hash will contain the *exact same* information.

    Should work just fine.
  • Of COURSE all files are "basically" the same, after all its just a set of 1s and 0s, and given that you already have lots of 1s and 0s on your machine this means that you already have the file even before you download it. It reminds me of Eric Morcambe and Andre Previn Previn: You were playing all the wrong notes Morcambe: No I was playing all the right notes just not necessarily in the right order
  • This is just an illustration of the fact that P2P is an incredibly inefficient way of transferring files around. Most of the material is not only pirated, but a big fraction of the pirated material is the same stuff. P2P "peers" aren't necessarily nearby, either in a physical or bandwidth sense. So huge amounts of bandwidth are being spent shipping the same stuff around.

    If it weren't for the piracy issue, the daily output of the RIAA, which is a few gigabytes, could be distributed efficiently by putti

    • by abscissa (136568)
      I used to disagree with what you said... but after seeing how P2P affects networks first hand, I am now inclined to agree.

      P2P is very inefficient.. but the problem is that means that are maximally efficient (e.g. proxies, usenet, etc.) are inaccessible to the masses.
      • by Animats (122034)

        Yes, if we had "alt.binaries.music.riaa.top40" we could probably cut the world's P2P load in half. At least.

        It might be a good move for the RIAA members to do that. They pay radio stations to play the stuff. Why not cut out the middleman and ship direct to consumers?

        We may be headed for an era where top-40 music is free, but ad-supported.

  • a new P2P app call BET promises faster downloads, utilizing the tried-and-true method of giving a file a set time limit to download then filling in random bytes after that.
  • The RIAA is going to absolutely hate any research in this area that can improve P2P performance in any manner. And especially by a university, no less. Those hot beds of piracy don't deserve public money at all, when they spend it like this!!
  • by dduardo (592868) on Wednesday April 11, 2007 @11:14AM (#18690557)
    So let say person A wants to download copyrighted material. They would connect to a tracker who would when tell person A where to get chunk 1 from. This chunk could come from copyrighted data or public domain data. What the tracker stores isn't the actual copyrighted data, but offsets, lengths, and ip addresses of where to find particular chunks.

    In essence, if you were downloading a music CD, the data chunks could be coming from someone who has an Ubuntu ISO image, or some type of copyrighted material.

    With this system it essential becomes impossible to tell who is uploading what.
    • Re: (Score:3, Interesting)

      The chances of two 16kB chunks from a Ubuntu ISO and a music CD being identical are extremely unlikely, or for that matter, the chances of any two 16kbit chunks from any two non-similar (meaning, in this case, files that are not of/from the same source [the same movie, album, program, whatever]) files being the same are incredibly slim.

      That being said, about 90% of the commenters missed the point completly, though it is somewhat understandable given how vague and nontechnical the linked article and summa
    • As the other reply said, the chances of two chunks, even ones that are relatively small (like 16kb) being identical are very, very small, unless the source data was similar in the first place. So you're not going to be able to download your top 40 CD from all-free sources using that method.

      You could do something like reducing the chunk size to 10 bytes or something else really small, and probably be able to find chunks from non-copyrighted sources. (Disregard for the moment the fact that the overhead wou

  • I thought of this a few years ago. The idea seemed an obvious one. There'll always be blocks of repeating data(e.g. FF00FF00), and exe, zip, rar, mp3, etc. headers with many similarities. If one can make the algo vary the size of the chunks it uses then you can derive your data from lots of different sources including getting data from image files that are to be applied to an .exe. The key would be to be able to recreate as much as possible from the similar data and the checksum/CRC using some of today's er
  • Storage is cheap, bandwidth more expensive. Why not chunk up each file into many different permutations of its compressed data, with the variants recorded in the local index by fingerprint? Those fingerprints of unique chunks and the list of chunks to files can be maintained in the distributed index of many sites to each fingerprinted chunk. That would make more chances for a given content site to have a chunk that's identical to the one looked for, even if the chunk originated in a different file.

    At some p
  • by diakka (2281)
    This could be a great tool for distributing updates. Say, if you already downloaded one DVD iso image for your favorite Linux distro, it could save a lot of time over downloading a whole new DVD iso. Even for smaller files or individual packages it could be really handy. I know there are already tools for generating rpm deltas and such, but if it could be transparant, it could really save a lot of hassle as well as bandwidth.
  • ... that hashes collide, all the time. It probably won't collide over a large data chunk, but if you split the data chunks into $number chunks and send around MD5's (or other hashes) for that, you'll multiply the possible collisions by $number.

    The only solution therefore is to create a one-to-one hash for each chunk, but then you could just as well transfer the data, because the hash size = chunk size.

    Therefore, this approach won't work. Because, say you are transferring an OGG file (of your favorite indie
  • by Junior J. Junior III (192702) on Wednesday April 11, 2007 @12:10PM (#18691415) Homepage
    At their fundamental level, all files are essentially similar. They're encoded as 1's and 0's. So, wherever a file happens to call for a 1, you should be able to just pull that 1 from ANYWHERE. Even some random file on your local hard drive. And likewise for zeroes. All you need is a smart download algorithm to re-assemble the 1s and 0s in the correct order, and you're set.
  • by J0nne (924579) on Wednesday April 11, 2007 @12:13PM (#18691459)
    Shareaza has been doing this for years. When hashing MP3 files, it disregards what(s in the id3 tags, and just computes a hash for the audio information. This means that files with different id3 tags will still be added to the swarm, whicj is great.
    Unfortunately, there are some issues with it:
    -Only Shareaza supports it, other clients didn't want to play along.
    -Shareaza has/d a bug where it would fail to reconstruct the id3 tag after downloading, giving you files with empty tags
    -Only mp3 is supported, so no ogg, aac or wma

    So this paper isn't as revolutionary (if that's what they mean).

    This will only work with identical files that have metadata that is frequently changed by end-users, because there's no way you're going to be able to get a good file if you try to mix a cam with a dvdrip, or an ogg with an mp3, or an xvid file with a divx file. It just doesn't work that way.
  • ID3v1 tags won't pose a problem for this, they occur at the end of the file, i.e. the last chunk.

    But ID3v2 files occur at the start of the file and have variable size. AVI files might have similar video streams but different language audio tracks, or be interleaved slightly differently, and so forth.

    So although similar information might exist in these files, the chances of that information laying exactly on the same chunk boundaries, and thus the chunks having matching MD5s, is pretty low I bet. Even a 1ms
  • by DigitAl56K (805623) on Wednesday April 11, 2007 @12:39PM (#18691913)
    If a client recreates a file from "similar" pieces, is it a derivative work?
  • I tried it (Score:3, Funny)

    by Intron (870560) on Wednesday April 11, 2007 @01:36PM (#18692799)
    I tried downloading "My Sweet Lord" by George Harrison, but I got "He's So Fine" by the Chiffons instead.
  • by Bluesman (104513) on Wednesday April 11, 2007 @02:21PM (#18693521) Homepage
    This seems to be an intractable problem.

    How do you know a file is similar? By hashing? There's no guarantee that a particular chunk of a file with an md5 hash (for example) contains the same bytes as that of another file.

    There are 2^256 possible chunks of 256 bits of data. There are 2^16 possible hashes with (using a 16 bit binary key) for that same data. That means that for every hash match, the data has a 1 in 16 chance of actually matching.

    You can extend the key length to reduce this ratio, but you'll end up with a key length equal to your data size before you're sure the data is not a collision.

    The problem gets worse if the chunks of data aren't equal in size.

    This can only work if you have a centralized database of every possible file combination on your network. It's workable for a small amount of files, but will grow exponentially in a real environment. Not to mention, the centralized database would have to handle a significant amount of traffic, reducing the speed gains possible.

    Count me as skeptical.
  • perhaps 100% similar (Score:3, Interesting)

    by Frisky070802 (591229) * on Wednesday April 11, 2007 @02:46PM (#18693821) Journal
    I recall hearing a story on NPR Music a few weeks ago about someone who plugged a CD into itunes and had it come up with the right piece but the wrong performer. Then it happened again, with the same ostensible pianist but yet another "wrong" performer. Detailed analysis showed the pianist had apparently published CDs claiming to perform pieces but actually substituting the work of others! Itunes must have used a signature over the content to index the piece by the earlier CD.

    Similarity detection rules.

A computer lets you make more mistakes faster than any other invention, with the possible exceptions of handguns and Tequilla. -- Mitch Ratcliffe

Working...