BINARY RELATIONS ARE COMMONLY USED IN COMPUTER SCIENCE FOR MODELING DATA. IN ADDITION TO CLASSICAL REPRESENTATIONS USING MATRICES OR LISTS, SOME COMPRESSED DATA STRUCTURES HAVE RECENTLY BEEN PROPOSED TO REPRESENT BINARY RELATIONS IN COMPACT SPACE, SUCH AS THE K 2 -TREE AND THE BINARY RELATION WAVELET TREE (BRWT). KNOWING THEIR STORAGE NEEDS, SUPPORTED OPERATIONS AND TIME PERFORMANCE IS KEY FOR ENABLING AN APPROPRIATE CHOICE OF DATA REPRESENTATION GIVEN A DOMAIN OR APPLICATION, ITS DATA DISTRIBUTION AND TYPICAL OPERATIONS THAT ARE COMPUTED OVER THE DATA. IN THIS WORK, WE PRESENT AN EMPIRICAL COMPARISON AMONG SEVERAL COMPRESSED REPRESENTATIONS FOR BINARY RELATIONS. WE ANALYZE THEIR SPACE USAGE AND THE SPEED OF THEIR OPERATIONS USING DIFFERENT (SYNTHETIC AND REAL) DATA DISTRIBUTIONS. WE INCLUDE BOTH NEIGHBORHOOD AND SET OPERATIONS, ALSO PROPOSING ALGORITHMS FOR SET OPERATIONS FOR THE BRWT, WHICH WERE NOT PRESENTED BEFORE IN THE LITERATURE. WE CONCLUDE THAT THERE IS NOT A CLEAR CHOICE THAT OUTPERFORMS THE REST, BUT WE GIVE SOME RECOMMENDATIONS OF USAGE OF EACH COMPACT REPRESENTATION DEPENDING ON THE DATA DISTRIBUTION AND TYPES OF OPERATIONS PERFORMED OVER THE DATA. WE ALSO INCLUDE A SCALABILITY STUDY OF THE DATA REPRESENTATIONS.

IN THIS PAPER, WE PRESENT TWO ALGORITHMS TO OBTAIN THE CONVEX HULL OF A SET OF POINTS THAT ARE STORED IN THE COMPACT DATA STRUCTURE CALLED K2-TREE. THIS PROBLEM CONSISTS IN GIVEN A SET OF POINTS P IN THE EUCLIDEAN SPACE OBTAINING THE SMALLEST CONVEX REGION (POLYGON) CONTAINING P. TRADITIONAL ALGORITHMS TO COMPUTE THE CONVEX HULL DO NOT SCALE WELL FOR LARGE DATABASES, SUCH AS SPATIAL DATABASES, SINCE THE DATA DOES NOT RESIDE IN MAIN MEMORY. WE USE THE K2-TREE COMPACT DATA STRUCTURE TO REPRESENT, IN MAIN MEMORY, EFFICIENTLY A BINARY ADJACENCY MATRIX REPRESENTING POINTS OVER A 2D SPACE. THIS STRUCTURE ALLOWS AN EFFICIENT NAVIGATION IN A COMPRESSED FORM. THE EXPERIMENTATIONS PERFORMED OVER SYNTHETICAL AND REAL DATA SHOW THAT OUR PROPOSED ALGORITHMS ARE MORE EFFICIENT. IN FACT THEY PERFORM OVER FOUR ORDER OF MAGNITUDE COMPARED WITH ALGORITHMS WITH TIME COMPLEXITY OF O(NLOGN).

BINARY RELATIONS ARE COMMONLY USED TO REPRESENT RELATIONSHIPS BETWEEN REAL-WORLD OBJECTS. CLASSICAL REPRESENTATIONS FOR BINARY RELATIONS CAN BE VERY SPACE-CONSUMING WHEN THE SET OF ELEMENTS IS LARGE. IN THESE CASES, COMPRESSED REPRESENTATIONS, SUCH AS THE -TREE, HAVE PROVEN TO BE A COMPETITIVE SOLUTION, AS THEY ARE EFFICIENT IN TIME WHILE CONSUMING VERY LITTLE SPACE. MOREOVER, -TREES CAN SUCCESSFULLY REPRESENT BOTH SPARSE AND DENSE BINARY RELATIONS, USING DIFFERENT VARIANTS OF THE TECHNIQUE. IN THIS PAPER, WE PROPOSE AND EVALUATE ALGORITHMS TO EFFICIENTLY PERFORM SET OPERATIONS OVER BINARY RELATIONS REPRESENTED USING -TREES. MORE SPECIFICALLY, WE PRESENT ALGORITHMS FOR COMPUTING THE UNION, INTERSECTION, DIFFERENCE, SYMMETRIC DIFFERENCE, AND COMPLEMENT OF BINARY RELATIONS. THUS, THIS WORK EXTENDS THE FUNCTIONALITY OF THE DIFFERENT VARIANTS OF THE -TREE REPRESENTATION FOR BINARY RELATIONS. OUR ALGORITHMS ARE COMPUTED DIRECTLY OVER THE COMPRESSED REPRESENTATION, WITHOUT REQUIRING PREVIOUS DECOMPRESSION, AND GENERATE THE RESULT IN COMPRESSED FORM. THE EXPERIMENTAL EVALUATION SHOWS THAT THEY ARE EFFICIENT IN TERMS OF SPACE AND TIME, COMPARED WITH DIFFERENT BASELINES WHERE THE BINARY RELATIONS ARE REPRESENTED IN PLAIN FORM OR REQUIRE A PREVIOUS DECOMPRESSION TO PERFORM THE SET OPERATION.