Changeset: 1792323f8eb0 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=1792323f8eb0
Modified Files:
sql/backends/monet5/LSST/Tests/All
sql/backends/monet5/LSST/Tests/htmxmatch.sql
sql/backends/monet5/LSST/lsst.c
sql/backends/monet5/LSST/lsst.h
sql/backends/monet5/LSST/lsst.mal
Branch: default
Log Message:
HTM xmatch by htm level
The cross match is performed using the number of levels as an
indicator of the distance. This crude, but fast approach may
lead to larger result sets then strictly needed when you perform
a more expensive geometric distance function.
diffs (117 lines):
diff --git a/sql/backends/monet5/LSST/Tests/All
b/sql/backends/monet5/LSST/Tests/All
new file mode 100644
--- /dev/null
+++ b/sql/backends/monet5/LSST/Tests/All
@@ -0,0 +1,1 @@
+htmxmatch
diff --git a/sql/backends/monet5/LSST/Tests/htmxmatch.sql
b/sql/backends/monet5/LSST/Tests/htmxmatch.sql
new file mode 100644
--- /dev/null
+++ b/sql/backends/monet5/LSST/Tests/htmxmatch.sql
@@ -0,0 +1,11 @@
+create table htm( id lng);
+insert into htm values (100), (101), (102), (103);
+insert into htm values (110), (111), (112), (113);
+insert into htm values (120), (121), (122), (123);
+insert into htm values (130), (131), (132), (133);
+
+-- select identical pairs
+select * from htm a, htm b where a.id xmatch(0) b.id;
+
+-- select pairs at distance one
+select * from htm a, htm b where a.id xmatch(1) b.id;
diff --git a/sql/backends/monet5/LSST/lsst.c b/sql/backends/monet5/LSST/lsst.c
--- a/sql/backends/monet5/LSST/lsst.c
+++ b/sql/backends/monet5/LSST/lsst.c
@@ -433,22 +433,34 @@
}
/*
* the remainder is an example of hooking up a fast cross match operation
- * using two HtmID columns bounded by the delta distance.
+ * using two HtmID columns bounded by the htm delta distance.
+ * The delta indicates the number of triangulat divisions should be ignored.
+ * For delta =0 the pairs match when their HtmID is equal
+ * for delta =1 the pairs match if their HtmID shifted 2 bits match and so on.
* Ideally the two columns are sorted upfront.
*/
str
-xmatch(int *ret, int *lid, int *rid, lng *delta)
+xmatch(int *ret, int *lid, int *rid, int *delta)
{
BAT *bn, *bl, *br;
lng *l, *r;
+ lng lhtm, rhtm;
lng *lend, *rend;
+ int shift;
+ oid lo = 0, ro=0;
+
+
+ if( *delta < 0 || *delta >31)
+ throw(MAL, "algebra.xmatch", "delta not in 0--31");
+ shift = 2 * *delta;
if( (bl= BATdescriptor(*lid)) == NULL )
throw(MAL, "algebra.xmatch", RUNTIME_OBJECT_MISSING);
if( (br= BATdescriptor(*rid)) == NULL )
throw(MAL, "algebra.xmatch", RUNTIME_OBJECT_MISSING);
+
l= (lng*) Tloc(bl, BUNfirst(bl));
lend= (lng*) Tloc(bl, BUNlast(bl));
r= (lng*) Tloc(br, BUNfirst(br));
@@ -464,12 +476,27 @@
BATaccessBegin(bl, USE_TAIL, MMAP_SEQUENTIAL);
BATaccessBegin(br, USE_TAIL, MMAP_SEQUENTIAL);
- for(; l < lend; l++) {
- for(; r < rend; r++)
- if ( *l != lng_nil && *r != lng_nil)
+ for(; l < lend; lo++, l++)
+ if ( *l != lng_nil) {
+ lhtm = *l >> shift;
+ for(; r < rend; ro++, r++)
+ if ( *r != lng_nil)
{
- /* here comes the HtmID distance test */
- (void) delta;
+ rhtm = *r >> shift;
+ if ( lhtm == rhtm){
+ /* match */
+ BUNins(bn,&lo,&ro, FALSE);
+ } else if ( lhtm < rhtm ) {
+ lhtm = lhtm << shift;
+ for ( ; *l < lhtm && l < lend; lo++,
l++)
+ ;
+ lhtm = lhtm >> shift;
+ } else{
+ rhtm = rhtm << shift;
+ for ( ; *r < rhtm && r < rend; ro++,
r++)
+ ;
+ rhtm = rhtm >> shift;
+ }
}
}
BATaccessEnd(bl, USE_TAIL, MMAP_SEQUENTIAL);
diff --git a/sql/backends/monet5/LSST/lsst.h b/sql/backends/monet5/LSST/lsst.h
--- a/sql/backends/monet5/LSST/lsst.h
+++ b/sql/backends/monet5/LSST/lsst.h
@@ -41,5 +41,5 @@
lsst_export str qserv_ptInSphCircle(int *ret, dbl *ra, dbl *dec, dbl *ra_cen,
dbl *dec_cen, dbl *radius);
lsst_export str qserv_ptInSphPoly(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci);
-lsst_export str xmatch(int *ret, int *lid, int *rid, lng *delta);
+lsst_export str xmatch(int *ret, int *lid, int *rid, int *delta);
#endif /* _SQL_UDF_H_ */
diff --git a/sql/backends/monet5/LSST/lsst.mal
b/sql/backends/monet5/LSST/lsst.mal
--- a/sql/backends/monet5/LSST/lsst.mal
+++ b/sql/backends/monet5/LSST/lsst.mal
@@ -39,6 +39,6 @@
address qserv_ptInSphPoly
comment "Returns 1 if the given spherical longitude/latitude polyline contains
the given position";
-command lsst.xmatch(l:bat[:oid,:lng], r:bat[:oid,:lng],
delta:lng):bat[:oid,:oid]
+command lsst.xmatch(l:bat[:oid,:lng], r:bat[:oid,:lng],
depth:int):bat[:oid,:oid]
address LSSTxmatch
-comment "Return the HtmID pairs whose distances is within a delta distance";
+comment "Return the HtmID pairs that lie within the same triangle at level
depth";
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
