/*PyramidApp.java
* Using Pyramid Technique to process multidimensional queries
* Fay Pan 2007
* Computer Science, University of Otago
*/
import java.lang.Math;
import java.util.*;
import java.io.*;
public class PyramidApp{
private static BPlusTree b;
private static int d;
private static int tot;
private static int node_hit;
public static void main(String[] args){
int leaf=0, inner=42;
d = Integer.parseInt(args[0]);
leaf = 1012/(16*d+16);
b = new BPlusTree(leaf, inner, d);
double[] point = new double[d];
double[] range = new double[2*d];
boolean p_query, con=true;
ResultList result1 = new ResultList();
setupTree(args[1]);
tot = b.getTotal();
System.out.println("Total number of nodes is : "+tot);
do{
System.out.println("Enter p followed by point query or r followed by range query
q to quit");
Scanner inString = new Scanner(System.in);
char nex = inString.next().charAt(0);
switch(nex){
case 'p':
for(int i = 0; i < d; i++){
point[i] = inString.nextDouble();
}
p_query = pointQuery(point);
System.out.println("Access Time is: "+b.getTime()+" " +p_query);
break;
case 'r':
//range query test to get average result
//first parameter is the percentage, second is the number of test
double per = inString.nextDouble();
int num = inString.nextInt();
int total=0;
double average=0;
for(int i = 0; i < num; i++){
rangeT(per);
total += node_hit;
}
average = (double) total/num;
System.out.println("Average Number of Disk Hit of query size "+per+"% with "+num+" times of tests is "+average+" "+average/tot+"%\n");
/* single range query
for(int i = 0; i < 2*d; i++){
range[i] = inString.nextDouble();
}
result1 = rangeQuery(range);
System.out.println("Access time is: "+ node_hit);
*/
/* print out the results within range
if(result!=null) {
ResultNode temp = new ResultNode();
temp = result.header;
for(int i=0; i<result.length();i++){
for(int j=0; j<d;j++){
System.out.print(temp.p[j]+" ");
}
temp = temp.next;
System.out.println();
}
} else
System.out.println("No Match in the range");*/
break;
case 'q':
//b.print();
con = false;
break;
default:
System.out.println("invalid input!");
}
} while(con != false);
}
public static void rangeT(double percentage){
//Random r = new Random();
double width = Math.pow(percentage,1.0/d);
double[] range = new double[2*d];
for(int i = 0; i < d; i++){
range[i] = Math.random()*(1-width);
range[i+d] = range[i] + width;
}
rangeQuery(range);
}
public static boolean pointQuery(double[] po){
double key = generateKey(po);
return b.find(key, po);
}
public static ResultList rangeQuery(double[] ra){
node_hit = 0;
ResultList result = new ResultList();
result.header = null;
ResultList res = new ResultList();
ResultNode temp, pos = new ResultNode();
double[] h = new double[2];
int flag = 0;
for(int i = 0; i < 2*d; i++){
if(intersect(i, ra)){
h = determine_range(i, ra);//h[0] = h_low, h[1] = h_high
//System.out.println(i+" " + h[0] + " " + i+" "+h[1]);
//double[][] cs = b.findRange(0,5);
res = b.findRange(i + h[0], i + h[1]);
// get list of points from B+ tree
int v = 0;
if(res != null){
if(res.header.p != null){
temp = res.header;
//System.out.println(temp.k+" "+temp.p);
for(int c = 0; c < res.length(); c++){
flag=0;
for (int z = 0; z < d; z++){
//System.out.println(flag);
if(temp.p[z] >= ra[z] && temp.p[z] <= ra[z+d]) flag++;//check if each dimension within the query
//System.out.println(flag);
}
if (flag == d){ // if all match
//System.out.println("Adding "+result);
if(result.header==null) {
//System.out.println("header "+result.header);
result = new ResultList(temp); //add the point to the point list
pos = result.header;
result.inc();
}
else {
//System.out.println("body "+result.header);
pos.next=temp;
pos = pos.next;
result.inc();
}
v++;
}
temp = temp.next;
}
//System.out.println(b.getTime());
node_hit += b.getTime();
}// else System.out.println("null point");
}//else {
//System.out.println("null return list");
//}
}
}
return result;
}
public static double[] determine_range(int pr, double[] q){
double[] q_min = new double[d];
double[] q_max = new double[d];
double[] h = new double[2];//h[low], h[high]
double[] min = new double[d];
double m = 1;
int pi = pr%d;
for(int i = 0; i < d; i++){//get the range query with Origin shifted to the middle of space
q_min[i] = q[i] - 0.5;
q_max[i] = q[i+d] - 0.5;
}
int flag = 0;
for(int i = 0; i < d; i++){
if(q_min[i] <= 0 && 0 <= q_max[i]) flag++;
}
if (flag == d){// center of space is in the query
h[0] = 0;
h[1] = max_r(min_hat(pr, q_min[pi]), max_hat(pr, q_max[pi]));
}
else {//center of space is out of query
h[1] = max_r(min_hat(pr, q_min[pi]), max_hat(pr, q_max[pi]));
for(int j = 0; j < d; j++){
if(j != pi){
if(max_d(q_min[j], q_max[j]) > min_d(min_hat(pr, q_min[pi]), max_hat(pr, q_max[pi]))) {
//System.out.println("1");
min[j] = Math.min(max_d(min_hat(pr, q_min[pi]), max_hat(pr, q_max[pi])), min_d(q_min[j], q_max[j]));
} else {
//System.out.println("2");
min[j] = min_d(min_hat(pr, q_min[pi]), max_hat(pr, q_max[pi]));
}
} else min[j] = 1;
}
for(int i = 0; i < min.length; i++) m = Math.min(m, min[i]);
h[0] = m;
}
return h;
}
public static double max_hat(int pr, double h){
if(pr < d) return Math.min(h, 0);
else return h;
}
public static double min_hat(int pr, double l){
if(pr >= d) return Math.max(l, 0);
else return l;
}
public static double max_d(double l, double h){
if(l < 0 && 0 <= h) return 0;
return
Math.max(Math.abs(l), Math.abs(h));
}
public static double max_r(double l, double h){
return Math.max(Math.abs(l), Math.abs(h));
}
public static double min_d(double l, double h){
if(l < 0 && 0 <= h) return 0; //l <= 0 <= h
else return Math.min(Math.abs(l), Math.abs(h));
}
public static double min_r(double l, double h){
return Math.min(Math.abs(l), Math.abs(h));
}
public static boolean intersect(int pr, double[] q){//range query is like this: (0 0 0), (0.2 0.4 0.6)
double[] q_min = new double[d];
double[] q_max = new double[d];
double min;
int pi = pr%d;
for(int i = 0; i < d; i++){
q_min[i] = q[i] - 0.5;
q_max[i] = q[i+d] - 0.5;
}
if(pr < d){
int flag=0;
for(int j = 0; j < d; j++){
if(pi != j){
min = min_d(q_min[j], q_max[j]);
if(q_min[pi] <= -min) flag++;;
}
}
//System.out.println(flag);System.out.println(flag);
if(flag == d-1) return true;
else return false;
} else if (pr < 2*d){
int flag=0;
for(int j = 0; j < d; j++){
if(pi !=j){
min = min_d(q_min[j], q_max[j]);
if(q_max[pi] >= min) flag++;
}
}
// System.out.println(flag);
if(flag == d-1) return true;
else return false;
} else {
System.out.println("Error!");
return false;
}
}
public static void setupTree(String filename){
double[] point = new double[d];
try{
File file = new File(filename);
Scanner scanner = new Scanner(file);
while(scanner.hasNext()){
for(int i =0; i < d; i++){
point[i] = Double.parseDouble(scanner.next());
//System.out.print(point[i]+ " ");
}
//System.out.println();
double key = generateKey(point);
b.insert(key, point);
}
scanner.close();
} catch(FileNotFoundException e){
e.printStackTrace();
}
}
public static double generateKey(double[] po){
//there will be 2*d pyramids
int i, j, k, j_max=0;
double h, key;
for (k=0; k<d; k++){
for(j=0; j<d; j++){
if(j!=k){
if (Math.abs(0.5-po[j]) >= Math.abs(0.5-po[k]))
j_max = j;
}
}
}
if(po[j_max] < 0.5)
i = j_max;
else i = j_max + d;
h = Math.abs(0.5 - po[i%d]);
//System.out.println("The point is in the "+ i+"th pyramid, and the height is "+h);
key = i+h;
return key;
}
}
posted on 2007-10-17 15:15
Fay 閱讀(177)
評論(2) 編輯 收藏