Keywords: DataAccWG Hi Serge,
I'm moving this discussion to the mailing list, yes, it is interesting enough. This might work, however, I worry that it solves only the cross match problem. I am hoping that the solution to "the other problem" will automatically solve the cross-match problem (at no extra cost). This "other" problem is updating ~100K objects per visit. In practice we will be updating only part of the object: most values for a given band, so ~1/6 of all attributes, or ~300 bytes, but that is still too much to simply assume that we will be able to keep that in memory. Thanks, Jacek P.s. Why are you saying we have 5 min preparation time? I thought Tim mentioned we would have information about next observing field ~30 sec in advance. > -----Original Message----- > From: Serge Monkewitz [mailto:[EMAIL PROTECTED] > Sent: Wednesday, November 01, 2006 5:53 PM > To: [EMAIL PROTECTED]; Becla, Jacek; > [EMAIL PROTECTED]; [EMAIL PROTECTED] > Subject: An idea for the object catalog cross-match > > Hi all, > > I wasn't sure if this was of enough interest to post to > the LSST-DM list, but let me know if I should post it there. > > I've been thinking about cross-matching against the > object catalog problem, specifically in the context of the > base camp and I have fairly simple idea that I think could > work. The idea runs counter to the current "everything must > be massively parallel" line of thinking: what about storing a > compressed structure that represents the *entire* object > catalog (in a fashion similar to the WAX band/lane and > Maria's zone/ra approach) in the memory of a single machine? > This attempts to address the following > issues: > > - For a particular visit, we have a minimum of 5 min. preparation time > - [using zone approach] If I have understood correctly, zone > tables have to be created/indexed or brought into memory > during this time. If they aren't created dynamically, then > one must deal with various issues: the zone table(s) might > have to be updated along with the object catalog, > partitioning zone table(s) is complicated by the fact that a > single object may belong to more than 1 zone table or zone > table partition. > - [using WAX approach] The equivalent of the zone table has > to be read and created from the DBMS (basically it's the > "create zone tables dynamically" > approach with custom code for index creation and x-match). > > > Instead, consider the bare minimum we need to do a distance > based match - for objects and DIA sources: ID, ra, dec. > Additionally, an object type might be useful. > > First of all, quantize ra, dec into 32 bit integers (e.g. > write ra = 360*x degrees, store x as a 32 bit fraction: 0 <= > x <= (2^32 - 1)/2^32 and dec = 180*y degrees, y is a 32 bit > fraction 0 <= y <= (2^32 - 1)/2^32). This means we are > storing ra as multiples of ~0.0003 arc seconds, and dec as > multiples of ~0.00015 arc seconds. Finally, let the id be > some 64bit integer and reserve a small number of bits for the > object type (maybe just a single bit that says whether or not > the object is variable?). > > If we were to stop there, storing 20 billion objects at 16 > bytes per object would take ~320GB, which one might expect to > be within the memory capacity of a single machine by 2012 (I > can buy a 2 socket machine with 64GB of RAM today). However, > it's quite easy to further reduce the memory > requirements: > > - bin objects into (for example) 64k bands/zones. This means > the band/zone an object is in automatically gives you the > upper 16bits of that objects dec value. > - within a band/zone, store objects in ascending ra order. > Exploit this ordering to save space via delta-coding. > - Instead of storing some arbitrary id for an object, > stipulate that the first 40bits of the id are given by some > combination of the upper ~20 most significant bits of ra and > dec. The remaining ~24bits are dedicated towards guaranteeing > uniqueness of the ID. > > [Note: I expect data structure overhead to be quite small > compared to the object data, for the moment I am just ignoring it] > > So basically it seems quite feasible with only a very > lightweight compression scheme to store the necessary > information from the object catalog using roughly 8 bytes per > object, or ~160GB of memory. Of course, fancier compression > techniques could be applied on top of or instead of the above. > > Some further questions then arise: > > 1. How is this in-memory structure updated? > ------------------------------------------- > > It is never updated. We are not allowed to update IDs > anyway, and even if an object position is updated downstream, > I am assuming that the new position will never differ much > from the original one. The positions of the in-memory object > representations are therefore somewhat fuzzy and this must be > accounted for by increasing the search radius for finding matches. > > 2. What about new objects? > -------------------------- > > These must of course be inserted into the structure (and > such insertions must be logged to disk). Given the simple > indexing and compression scheme as well as the fact that the > number of inserts will in the common case be very small, this > doesn't seem to be a problem. In fact, we can use the > in-memory object index to generate the new object IDs: > since the IDs correlate to position extremely well, we just > have to do a cross match of the objects to insert against the > existing ones with appropriate search radius to make sure we > don't assign an ID already in use. Doing such a cross match > also naturally tells us where in the structure the new > objects must be inserted. > > 3. OK, but this is a (rough) distance match only - what next? > ------------------------------------------------------------- > > The (DIA Source ID, object ID) match pairs are sent to > the RDBMS. A 2-way join of the input DIA Source Collection > with the full object > table(s) then gives you the details necessary for further > decision making. > Hopefully the number of such pairs will be relatively small > (when compared to the total number of objects in the visited > region), otherwise the approach falls down. The speed of this > join determines the viability of the approach. > > It seems to me this has the following pros: > > - should drastically reduce database reads > - because everything stays in memory at all times, no advance > knowledge of the observation schedule is needed (at least not > for this step) > - the object catalog at the base camp needs just a single > B-tree index (on > ID) > - updates of the spatial index are eliminated > - inserts are not complicated by having to distribute parts > of the spatial index across machines > - cross-match performance for a single visit will likely be > extremely fast (consider that even a single machine will > likely have 2 or 4 sockets with each socket having 4 or more > cores) despite having to decompress data and compute (x,y,z) > for each object position. > > and cons: > > - memory is expensive > - for fault tolerance, we need at least 2 machines with > enough memory to support this approach, and they really > cannot be used for anything else > - what if the fuzzy positions inflate the number of matches > by a lot (especially early in the survey)? > - not clear that this is useful for the archive center > > So what do you all think? Am I barking up a tree? > > Serge > > _______________________________________________ LSST-data mailing list [email protected] http://www.lsstmail.org/mailman/listinfo/lsst-data
