On Nov 16, 2006, at 9:31 PM, Hugh Perkins wrote: > The way this works is that you register your newest creations > centrally. The sim server then checks objects regularly - or on > demand - for similarity with your registered creations. > > Any object found to be too similar to your registered creation is > wiped / quarantined / signalled to an administrator / or similar. I won't go as far as to say this is not possible; I will say that this is extremely difficult, and an unsolved problem in computer science.
How do you tell if objects are identical? Well, that's not too bad -- you could take every attribute of object A, and compare each attribute with the matching attribute in object B -- and if they're the same, you have a match / infringement. Okay, that works, but how do you do that checking on the scale of Second Life, with hundreds of thousands of objects to sift through? That's probably solvable with a hash function -- but that's not really the problem we're trying to solve, because the moment you change some small part of one parameter of object B, it's no longer identical. Okay. So how do you tell if objects are similar? On the surface, this doesn't seem too bad -- you could take each attribute and add up the deltas. But what if you add one tiny little prim to object B? This is the graph isomorphism problem: http://en.wikipedia.org/wiki/ Graph_isomorphism_problem. Note that the phrase "Also, a generalization of the problem, the subgraph isomorphism problem, is known to be NP-complete" effectively means "this is impossible to do efficiently", with a complexity of O(m^2 * n^2), with m being the size (well, complexity -- number of prims?) and n being the number of objects in your database (hundreds of thousands). To put it in more accessible terms: The problem is similar to a few other problems which people *have* tried to solve, with varying degrees of success. For example, it's a lot like trying to detect plagiarism -- are Essay A and Essay B similar? A physics professor at UVA wrote some software (http:// plagiarism.phys.virginia.edu) and used it to successfully to detect cheating a few years back -- http://archives.cnn.com/2002/EDUCATION/ 11/26/uva.plagiarism.ap . Note that this involved a fair bit of manual effort, and involved a set of maybe a thousand papers. It is also similar to the problem of trying to determine if two MP3s are of the same song -- usually more to try to associate good metadata with them, rather than trying to find infringement. MusicBrainz does this http://en.wikipedia.org/wiki/MusicBrainz -- but they've had a lot of trouble, and had to throw out their initial attempt at acoustic fingerprinting because it generated an obscene number of false positives; their new scheme is too young to be judged. I'd be interested in hearing any counterexamples, where something like this has been done successfully. I know of none. Ben _______________________________________________ Libsecondlife-dev mailing list [email protected] https://lists.berlios.de/mailman/listinfo/libsecondlife-dev
