ONE OF THE MOST IMPORTANT STEPS IN OBTAINING A RELATIONAL MODEL FROM LEGACY SYSTEMS IS THE EXTRACTION OF FUNCTIONAL DEPENDENCIES (FDS) THROUGH DATA MINING TECHNIQUES. SEVERAL METHODS HAVE BEEN PROPOSED FOR THIS PURPOSE AND MOST USE DIRECT SEARCH METHODS THAT TRAVERSE THE SEARCH SPACE IN EXPONENTIAL TIME IN THE NUMBER OF ATTRIBUTES OF THE RELATION. AS IT IS NOT UNCOMMON TO FIND IN PRACTICE RELATIONS WITH TENS OF ATTRIBUTES, A NEED EXISTS TO FURTHER DEVELOP MORE EFFICIENT TECHNIQUES TO FIND FDS. THE METHOD STUDIED HERE FINDS THE MINIMAL SET OF MINIMAL FDS USING ALGORITHMS THAT SOLVE THE HYPERGRAPH DUALITY PROBLEM APPLIED ON THE COMPLEMENT OF THE REFUTATION HYPERGRAPH OF THE RELATION WITHOUT GOING THROUGH THE EXPONENTIAL SEARCH SPACE. AFTER SHOWING THAT THE EXTRACTION OF FDS CAN BE REDUCED TO THE HYPERGRAPH DUALITY PROBLEM, EXPERIMENTAL RESULTS ARE GIVEN AS VERIFICATION AND CHARACTERIZATION OF THE CORRECTNESS AND TIME COMPLEXITY OF THE PROPOSED TOOL.

THE HAUSDORFF DISTANCE BETWEEN TWO SETS OF POINTS A AND B CORRESPONDS TO THE LARGEST OF THE DISTANCES BETWEEN EACH OBJECT X ? A AND ITS NEAREST NEIGHBOR IN B. THE HAUSDORFF DISTANCE HAS SEVERAL APPLICATIONS, SUCH AS COMPARING MEDICAL IMAGES OR COMPARING TWO TRANSPORT ROUTES. THERE ARE DIFFERENT ALGORITHMS TO COMPUTE THE HAUSDORFF DISTANCE, SOME OPERATE WITH THE SETS OF POINTS IN MAIN MEMORY AND OTHERS IN SECONDARY MEMORY. ON THE OTHER HAND, TO FACE THE CHALLENGE OF INDEXING LARGE SETS OF POINTS IN MAIN MEMORY, THERE ARE COMPACT DATA STRUCTURES SUCH AS K 2 -TREE WHICH, BY MINIMIZING STORAGE, CAN BE EFFICIENTLY CONSULTED. AN EFFICIENT ALGORITHM (HDK2) THAT ALLOWS THE CALCULATION OF THE HAUSDORFF DISTANCE IN THE COMPACT STRUCTURE K 2 -TREE IS PRESENTED IN THIS ARTICLE. THIS ALGORITHM ACHIEVES AN EFFICIENT SOLUTION IN BOTH TIME AND SPACE. THROUGH A SERIES OF EXPERIMENTS, THE PERFORMANCE OF OUR ALGORITHM WAS EVALUATED TOGETHER WITH OTHERS PROPOSED IN LITERATURE UNDER SIMILAR CONDITIONS. THE RESULTS ALLOW TO CONCLUDE THAT HDK2 HAS A BETTER PERFORMANCE IN RUNTIME THAN SUCH ALGORITHMS

TWO SETS A AND B , WHOSE ELEMENTS FULFILL A TOTAL ORDER ON OPERATOR ? , CAN HAVE A BINARY RELATION R?A×B REPRESENTED BY THE K 2 -TREE COMPACT DATA STRUCTURE, WHICH GREATLY IMPROVES STORAGE SPACE. CURRENTLY, COUNT QUERY IS MANAGED BY EITHER USING RANGE QUERY OR TO MODIFY THE STRUCTURE TO HAVE AGGREGATE INFORMATION, IMPLYING ADDITIONAL TIME OR SPACE IN ORDER TO PERFORM THE QUERY. THIS ARTICLE PRESENTS COMPACT COUNT , WHICH EXPLOITS THE K 2 -TREE PROPERTIES TO REDUCE THE PATHS TO BE SCANNED TO COUNT THE NUMBERS IN A RANGE R , THUS ENSURING AN EXPECTED RUNTIME OF O(LOGKRLOGKN) AND STORAGE OF O(LOGKR) WITH THE K 2 -TREE PARAMETERS N AND K . OUR ALGORITHM WAS COMPARED THROUGH A SERIES OF EXPERIMENTS THAT CONSIDER BOTH SYNTHETIC DATA WITH DIFFERENT DISTRIBUTIONS AND REAL DATA, WITH A SOLUTION BASED ON THE RANGE ALGORITHM. EXPERIMENTAL RESULTS SHOW THAT COMPACT COUNT IS 250 TO 1,000 TIMES FASTER THAN RANGE ON SYNTHETIC AND REAL DATA, RESPECTIVELY, WITH A SMALL ADDITIONAL STORAGE COST, AS EXPECTED BY THE THEORETICAL ANALYSIS.

A VAST AMOUNT OF GEO-REFERENCED DATA IS BEING GENERATED BY MOBILE DEVICES AND OTHER SENSORS INCREASING THE IMPORTANCE OF SPATIO-TEXTUAL ANALYSES ON SUCH DATA. DUE TO THE LARGE VOLUME OF DATA, THE USE OF INDEXES TO SPEED UP THE QUERIES THAT FACILITATE SUCH ANALYSES IS IMPERATIVE. MANY DISK RESIDENT INDEXES HAVE BEEN PROPOSED FOR DIFFERENT TYPES OF SPATIAL KEYWORD QUERIES, BUT THEIR EFFICIENCY IS HARMED BY THEIR HIGH I/O COSTS. IN THIS WORK, WE PROPOSE CBIK, THE FIRST SPATIO-TEXTUAL INDEX THAT USES COMPACT DATA STRUCTURES TO REDUCE THE SIZE OF THE STRUCTURE, HENCE FACILITATING ITS USAGE IN MAIN MEMORY. OUR EXPERIMENTAL EVALUATION, SHOWS THAT THIS APPROACH NEEDS HALF THE SPACE AND IS MORE THAN ONE ORDER OF MAGNITUDE FASTER THAN A DISK RESIDENT STATE-OF-THE-ART INDEX. ALSO, WE SHOW THAT OUR APPROACH IS COMPETITIVE EVEN IN A SCENARIO WHERE THE DISK RESIDENT DATA STRUCTURE IS WARMED-UP TO FIT IN MAIN MEMORY.

IN THE CONTEXT OF BIG DATA SCENARIOS, THE PRESENCE OF EXTENSIVE STATIC DATASETS IS NOT UNCOMMON. TO FACILITATE EFFICIENT QUERIES ON SUCH DATASETS, THE UTILIZATION OF MULTIPLE INDEXES, SUCH AS THE KD-TREE, BECOMES IMPERATIVE. THE CURRENT SCALE OF MANAGED POINTS MAY, HOWEVER, EXCEED THE CAPACITY OF PRIMARY MEMORY, POSING A SIGNIFICANT CHALLENGE. IN THIS ARTICLE WE INTRODUCE CKD-TREE, A COMPACT DATA STRUCTURE DESIGNED TO REPRESENT A KD-TREE EFFICIENTLY. THE STRUCTURE CKD-TREE IS ESSENTIALLY AN ENCODING OF THE SPIRAL CODE SEQUENCE OF POINTS WITHIN AN IMPLICIT KD-TREE (IKD-TREE) USING DIRECTLY ADDRESSABLE CODES (DACS). THE UNIQUE FEATURE OF CKD-TREE LIES IN ITS ABILITY TO PERFORM SPIRAL ENCODING AND DECODING OF POINTS BY RELYING SOLELY ON KNOWLEDGE OF THEIR PARENT POINTS WITHIN THE IKD-TREE. THIS INHERENT PROPERTY, COMBINED WITH DACS? DIRECT ACCESS CAPABILITY TO SEQUENCE ELEMENTS, ENABLES CKD-TREE TO TRAVERSE AND EXPLORE THE TREE WHILE DECODING ONLY THE NODES RELEVANT TO QUERIES. THE ARTICLE DETAILS THE ALGORITHMS NECESSARY FOR CREATING AND MANIPULATING A CKD-TREE, AS WELL AS ALGORITHMS FOR EVALUATING TWO FUNDAMENTAL QUERIES OVER POINTS: THE POINT QUERY AND THE RANGE QUERY . TO ASSESS THE PERFORMANCE OF CKD-TREE, A SERIES OF EXPERIMENTS ARE CONDUCTED, COMPARING IT WITH IKD-TREE AND K 2 -TREE DATA STRUCTURES. THE EVALUATION METRICS INCLUDE COMPRESSION EFFICIENCY AND EXECUTION TIME OF QUERIES. CKD-TREE ACHIEVES A COMPRESSION RATIO COMPARABLE TO THAT OF K 2 -TREE, APPROXIMATELY 70%, DEMONSTRATING HEIGHTENED EFFICIENCY, PARTICULARLY IN SCENARIOS CHARACTERIZED BY SPARSE DATA. ADDITIONALLY, CONSISTENT WITH EXPECTATIONS, K 2 -TREE EXHIBITS SUPERIOR PERFORMANCE IN QUERYING INDIVIDUAL POINTS, WHEREAS CKD-TREE OUTPERFORMS IN THE CONTEXT OF AGGREGATE DATA QUERIES, SUCH AS RANGE QUERIES.

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).

IN THIS WORK, WE PROPOSE A FRAMEWORK TO STORE AND MANAGE SPATIAL DATA, WHICH INCLUDES NEW EFFICIENT ALGORITHMS TO PERFORM OPERATIONS ACCEPTING AS INPUT A RASTER DATASET AND A VECTOR DATASET. MORE CONCRETELY, WE PRESENT ALGORITHMS FOR SOLVING A SPATIAL JOIN BETWEEN A RASTER AND A VECTOR DATASET IMPOSING A RESTRICTION ON THE VALUES OF THE CELLS OF THE RASTER; AND AN ALGORITHM FOR RETRIEVING K OBJECTS OF A VECTOR DATASET THAT OVERLAP CELLS OF A RASTER DATASET, SUCH THAT THE K OBJECTS ARE THOSE OVERLAPPING THE HIGHEST (OR LOWEST) CELL VALUES AMONG ALL OBJECTS. THE RASTER DATA IS STORED USING A COMPACT DATA STRUCTURE, WHICH CAN DIRECTLY MANIPULATE COMPRESSED DATA WITHOUT THE NEED FOR PRIOR DECOMPRESSION. THIS LEADS TO BETTER RUNNING TIMES AND LOWER MEMORY CONSUMPTION. IN OUR EXPERIMENTAL EVALUATION COMPARING OUR SOLUTION TO OTHER BASELINES, WE OBTAIN THE BEST SPACE/TIME TRADE-OFFS.

EVEN THOUGH THE FIELD OF SPATIAL DATABASES IS MORE THAN 40 YEARS OLD, MOST EXISTING LOGICAL DATA MODELS ARE HIGHLY FOCUSED EITHER ON SPATIAL OBJECTS (VECTOR DATA MODELS) OR SPATIAL FIELDS (RASTER DATA MODELS). FURTHERMORE, SPATIAL INDEX STRUCTURES AND QUERY ALGORITHMS ARE STILL PROPOSED FOR ONE OF THE APPROACHES AND LITTLE RESEARCH WORK HAS BEEN DEDICATED TO INDEX STRUCTURES AND QUERY ALGORITHMS WHERE BOTH TYPES OF INFORMATION ARE NEEDED. HOWEVER, DUE TO THE CURRENT HIGH AVAILABILITY OF DIFFERENT TYPES OF DATA, IT IS MUCH MORE COMMON NOWADAYS THAT APPLICATIONS REQUIRE QUERYING VECTOR AND RASTER DATA AT THE SAME TIME. THIS PAPER PRESENTS A METHOD TO PERFORM A SPATIAL QUERY BETWEEN A VECTOR DATA SET REPRESENTED USING AN R-TREE AND A RASTER DATA SET REPRESENTED USING A COMPACT AND SPACE-EFFICIENT DATA STRUCTURE CALLED K2-TREE THAT SAVES MAIN MEMORY SPACE. THEREFORE, THE METHOD DESCRIBED IN THIS PAPER SOLVES TWO PROBLEMS: FIRST, IT CAN BE USED TO EVALUATE QUERIES BETWEEN VECTOR AND RASTER DATA WITHOUT HAVING TO CONVERT ONE OF THE DATA SETS TO THE OTHER DATA MODEL; AND SECOND, IT SAVES MAIN MEMORY SPACE, THUS OBTAINING A MORE SCALABLE SYSTEM.

IN THIS PAPER WE PROPOSE THE USE OF THE COMPACT DATA STRUCTURE K 2 -TREAP TO PROCESS DATA CUBES OF DATA WAREHOUSES (DWS) INTO MAIN MEMORY. COMPACT DATA STRUCTURES ARE DATA STRUCTURES THAT ALLOW COMPACTING THE DATA WITHOUT LOSING THE CAPACITY OF QUERYING THEM IN THEIR COMPACT FORM. A DW IS A DATA REPOSITORY TO STORE HISTORICAL DATA FOR DECISION SUPPORT, AND CONSISTS OF DIMENSIONS AND FACTS. THE FORMER ARE AN ABSTRACT CONCEPT THAT GROUPS DATA WITH A SIMILAR MEANING, THEY ARE MODELLED AS HIERARCHIES OF LEVELS, WHICH CONTAIN ELEMENTS. THE LATTER ARE QUANTITATIVE DATA ASSOCIATED TO DIMENSIONS. A DATA CUBE IS A TYPICAL WAY TO RETRIEVE FACTS AT DIFFERENT LEVELS OF GRANULARITY (THROUGH NAVIGATION ON DIMENSIONS HIERARCHIES). A DW CAN STORE TERABYTES OF DATA, THUS THE EFFICIENT PROCESSING OF DATA CUBES IS KEY IN OLAP (ON-LINE ANALYTICAL PROCESSING). WE SHOW THAT BY USING A COMPACT REPRESENTATION OF DATA CUBES AND BITMAPS TO REPRESENT DIMENSIONS WE ARE ABLE TO IMPROVE THE USE OF SPACE IN MAIN MEMORY, AND ACHIEVE BETTER PERFORMANCE FOR QUERY PROCESSING.

GIVEN TWO SPATIAL POINT SETS R AND B IN THE PLANE, WITH CARDINALITIES M AND N, RESPECTIVELY, AND STORED IN TWO SEPARATE R-TREES, WE PROPOSE AN EFFICIENT ALGORITHM TO VERIFY WHETHER R AND B ARE LINEARLY SEPARABLE. THE SETS R AND B ARE LINEARLY SEPARABLE IF THERE EXISTS A LINE THAT SPLITS THE PLANE INTO TO HALFPLANES, ONE CONTAINING ALL R AND THE OTHER ONE CONTAINING ALL B. THIS IS THE FIRST ALGORITHM THAT ANSWERS THE SEPARABILITY QUESTION IN THE CONTEXT OF THE SPATIAL DATA BASES. THAT IS, IT CONSIDERS AS INPUT BIG SPATIAL DATA STORED IN SECONDARY STORAGE DATA STRUCTURES (E.G., THE R-TREE) WHICH ARE NOT ALLOWED TO BE COMPLETELY STORED IN THE MAIN MEMORY OF THE COMPUTER TO RUN A CLASSIC ALGORITHM. THE ALGORITHMS DESIGNED IN THIS CONTEXT AIM TO MINIMIZE AS MUCH AS POSSIBLE THE NUMBER OF BLOCKS READ FROM THE SECONDARY STORAGE DATA STRUCTURES TO THE MAIN MEMORY. STUDIED PROBLEMS IN THIS SETTING ARE THE K-NEAREST NEIGHBOR PROBLEM AND THE SPATIAL RANGE QUERY PROBLEM. OUR ALGORITHM EXPLICITLY EXPLOITS THE GEOMETRIC AND SPATIAL PROPERTIES OF THE R-TREES TO ACCESS ONLY THE NODES RELEVANT TO DECIDE THE LINEAR SEPARABILITY OF THE GIVEN SETS. OUR EXPERIMENTAL RESULTS SHOW THE EFFICIENCY OF THE ALGORITHM, SINCE IT ACCESSES BETWEEN THE 0.34 AND 2.79% OF THE NODES OF THE R-TREES. WE ALSO ANALYZE THE ASYMPTOTIC RUNNING TIME OF THE ALGORITHM, SHOWING THAT IT RUNS IN O(MLOGM+NLOGN) TIME IN THE WORST CASE.

LET BE A SET OF POINTS LOCATED IN A RECTANGLE AND IS A POINT THAT IS NOT IN . THIS ARTICLE DESCRIBES THE DESIGN, IMPLEMENTATION, AND EXPERIMENTATION OF DIFFERENT ALGORITHMS TO SOLVE THE FOLLOWING TWO PROBLEMS: (I) MAXIMUM EMPTY RECTANGLE (MER), WHICH CONSISTS IN FINDING AN EMPTY RECTANGLE WITH A MAXIMUM AREA CONTAINED IN R AND DOES NOT CONTAIN ANY POINT FROM AND (II) QUERY MAXIMUM EMPTY RECTANGLE (QMER), WHICH CONSISTS IN FINDING THE RECTANGLE WITH THE SAME RESTRICTIONS GIVEN FOR THE MER PROBLEM BUT MUST ALSO CONTAIN . IT IS ASSUMED THAT BOTH PROBLEMS HAVE INSUFFICIENT MAIN MEMORY TO STORE ALL THE OBJECTS IN SET . ACCORDING TO THE LITERATURE, BOTH PROBLEMS ARE VERY PRACTICAL IN FIELDS SUCH AS DATA MINING AND GEOGRAPHIC INFORMATION SYSTEMS (GIS). SPECIFICALLY, THE PRESENT STUDY PROPOSES TWO ALGORITHMS THAT ASSUME THAT IS STORED IN SECONDARY MEMORY (MAINLY DISK) AND THAT IT IS IMPOSSIBLE TO STORE IT COMPLETELY IN MAIN MEMORY. THE FIRST ALGORITHM SOLVES THE QMER PROBLEM AND CONSISTS OF DECREASING THE SIZE OF S BY USING DOMINANCE AREAS AND THEN PROCESSING THE POINTS THAT ARE NOT ELIMINATED USING AN ALGORITHM PROPOSED BY ORLOWSKI (1990). THE SECOND ALGORITHM SOLVES THE MER PROBLEM AND CONSISTS OF DIVIDING R INTO FOUR SUBRECTANGLES THAT GENERATE FOUR SUBSETS OF SIMILAR SIZE; THESE ARE PROCESSED USING AN ALGORITHM PROPOSED IN EDMONS ET AL. (2003), AND FINALLY THE PARTIAL SOLUTIONS ARE COMBINED TO OBTAIN A GLOBAL SOLUTION. FOR THE PURPOSE OF VERIFYING ALGORITHM EFFICIENCY, RESULTS ARE SHOWN FOR A SERIES OF EXPERIMENTS THAT CONSIDER SYNTHETIC AND REAL DATA.

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.

WE PROVIDE IN THIS ARTICLE A BRANCH-AND-BOUND ALGORITHM THAT SOLVES THE PROBLEM OF FINDING THE K CLOSEST PAIRS OF POINTS (P,Q), P???P,Q???Q, CONSIDERING TWO SETS OF POINTS IN THE EUCLIDEAN PLANE P,Q STORED IN EXTERNAL MEMORY ASSUMING THAT ONLY ONE OF THE SETS HAS A SPATIAL INDEX. THIS PROBLEM ARISES NATURALLY IN MANY SCENARIOS, FOR INSTANCE WHEN THE SET WITHOUT AN INDEX IS THE ANSWER TO A SPATIAL QUERY. THE MAIN IDEA OF OUR ALGORITHM IS TO PARTITION THE SPACE OCCUPIED BY THE SET WITHOUT AN INDEX INTO SEVERAL CELLS OR SUBSPACES AND TO MAKE USE OF THE PROPERTIES OF A SET OF METRICS DEFINED ON TWO MINIMUM BOUNDING RECTANGLES (MBRS). WE EVALUATED OUR ALGORITHM FOR DIFFERENT VALUES OF K BY MEANS OF A SERIES OF EXPERIMENTS THAT CONSIDERED BOTH SYNTHETICAL AND REAL WORLD DATASETS. WE COMPARED THE PERFORMANCE OF OUR ALGORITHM WITH THAT OF TECHNIQUES THAT EITHER ASSUME THAT BOTH DATASETS HAVE A SPATIAL INDEX OR THAT NONE HAS AN INDEX. THE RESULTS SHOW THAT OUR ALGORITHM NEEDS ONLY BETWEEN A 0.3 AND A 35 % OF THE DISK ACCESSES REQUIRED BY SUCH TECHNIQUES. OUR ALGORITHM ALSO SHOWS A GOOD SCALABILITY, BOTH IN TERMS OF K AND OF THE SIZE OF THE DATA SET.

GIVEN A SET S OF POINTS IN THE TWO-DIMENSIONAL SPACE, WHICH ARE STORED IN A SPATIAL DATABASE, THIS PAPER PRESENTS AN EFFICIENT ALGORITHM TO FIND, IN THE AREA DELIMITED BY THOSE POINTS, THE EMPTY CIRCLE WITH THE LARGEST AREA THAT CONTAINS ONLY A QUERY POINT Q. OUR ALGORITHM ADAPTS PREVIOUS WORK IN THE FIELD OF COMPUTATIONAL GEOMETRY TO BE USED IN SPATIAL DATABASES, WHICH REQUIRES TO MANAGE LARGE AMOUNTS OF DATA. TO ACHIEVE THIS OBJECTIVE, THE BASIC IDEA IS TO DISCARD A LARGE PART OF THE POINTS OF S, IN SUCH A WAY THAT THE PROBLEM CAN BE SOLVED PROVIDING ONLY THE REMAINING POINTS TO A CLASSICAL COMPUTATIONAL GEOMETRY ALGORITHM THAT, BY PROCESSING A SMALLER COLLECTION OF POINTS, SAVES MAIN MEMORY RESOURCES AND COMPUTATION TIME. THE CORRECTNESS OF OUR ALGORITHM IS FORMALLY PROVEN. IN ADDITION, WE EMPIRICALLY SHOW ITS EFFICIENCY AND SCALABILITY BY RUNNING A SET OF EXPERIMENTS USING BOTH SYNTHETIC AND REAL DATA.

LET S BE A SET OF N POINTS IN A FIXED AXIS-PARALLEL RECTANGLE R?R2, I.E. IN THE TWO-DIMENSIONAL SPACE (2D). ASSUMING THAT THOSE POINTS ARE STORED IN AN R-TREE, THIS PAPER PRESENTS SEVERAL ALGORITHMS FOR FINDING THE EMPTY RECTANGLE IN R WITH THE LARGEST AREA, SIDES PARALLEL TO THE AXES OF THE SPACE, AND CONTAINING ONLY A QUERY POINT Q. THIS POINT CAN NOT BE PART OF S, THAT IS, IT IS NOT STORED IN THE R-TREE. ALL ALGORITHMS FOLLOW THE BASIC IDEA OF DISCARDING PART OF THE POINTS OF S, IN SUCH A WAY THAT THE PROBLEM CAN BE SOLVED ONLY CONSIDERING THE REMAINING POINTS. AS A CONSEQUENCE, THE ALGORITHMS ONLY HAVE TO ACCESS A VERY SMALL PORTION OF THE NODES (DISK BLOCKS) OF THE R-TREE, SAVING MAIN MEMORY RESOURCES AND COMPUTATION TIME. WE PROVIDE FORMAL PROOFS OF THE CORRECTNESS OF OUR ALGORITHMS AND, IN ORDER TO EVALUATE THE PERFORMANCE OF THE ALGORITHMS, WE RUN AN EXTENSIVE SET OF EXPERIMENTS USING SYNTHETIC AND REAL DATA. THE RESULTS HAVE DEMONSTRATED THE EFFICIENCY AND SCALABILITY OF OUR ALGORITHMS FOR DIFFERENT DATASET CONFIGURATIONS.