1CMU SCS15-826: Multimedia Databases and Data MiningMulti-key and Spatial Access Methods - IIC. Faloutsos15-826 Copyright: C. Faloutsos (2005) 2CMU SCSOutlineGoal: ‘Find similar / interesting things’• Intro to DB• Indexing - similarity search• Data Mining15-826 Copyright: C. Faloutsos (2005) 3CMU SCSIndexing - Detailed outline• primary key indexing• secondary key / multi-key indexing• spatial access methods– problem dfn– z-ordering– R-trees– ...• text• ...15-826 Copyright: C. Faloutsos (2005) 4CMU SCSSpatial Access Methods -problem• Given a collection of geometric objects(points, lines, polygons, ...)• organize them on disk, to answer spatialqueries (like??)15-826 Copyright: C. Faloutsos (2005) 5CMU SCSSpatial Access Methods -problem• Given a collection of geometric objects(points, lines, polygons, ...)• organize them on disk, to answer– point queries– range queries– k-nn queries– spatial joins (‘all pairs’ queries)15-826 Copyright: C. Faloutsos (2005) 6CMU SCSSpatial Access Methods -problem• Given a collection of geometric objects(points, lines, polygons, ...)• organize them on disk, to answer– point queries– range queries– k-nn queries– spatial joins (‘all pairs’ queries)215-826 Copyright: C. Faloutsos (2005) 7CMU SCSSpatial Access Methods -problem• Given a collection of geometric objects(points, lines, polygons, ...)• organize them on disk, to answer– point queries– range queries– k-nn queries– spatial joins (‘all pairs’ queries)15-826 Copyright: C. Faloutsos (2005) 8CMU SCSSpatial Access Methods -problem• Given a collection of geometric objects(points, lines, polygons, ...)• organize them on disk, to answer– point queries– range queries– k-nn queries– spatial joins (‘all pairs’ queries)15-826 Copyright: C. Faloutsos (2005) 9CMU SCSSpatial Access Methods -problem• Given a collection of geometric objects(points, lines, polygons, ...)• organize them on disk, to answer– point queries– range queries– k-nn queries– spatial joins (‘all pairs’ within )15-826 Copyright: C. Faloutsos (2005) 10CMU SCSSAMs - motivation• Q: applications?15-826 Copyright: C. Faloutsos (2005) 11CMU SCSSAMs - motivationsalaryagetraditional DBGIS15-826 Copyright: C. Faloutsos (2005) 12CMU SCSSAMs - motivationsalaryagetraditional DBGIS315-826 Copyright: C. Faloutsos (2005) 13CMU SCSSAMs - motivationCAD/CAMfind elementstoo closeto each other15-826 Copyright: C. Faloutsos (2005) 14CMU SCSSAMs - motivationCAD/CAM15-826 Copyright: C. Faloutsos (2005) 15CMU SCSday1 365day1 365S1SnF(S1)F(Sn)SAMs - motivationeg, avgeg,. std15-826 Copyright: C. Faloutsos (2005) 16CMU SCSIndexing - Detailed outline• primary key indexing• secondary key / multi-key indexing• spatial access methods– problem dfn– z-ordering– R-trees– ...• text• ...15-826 Copyright: C. Faloutsos (2005) 17CMU SCSSAMs: solutions• z-ordering• R-trees• (grid files)Q: how would you organize, e.g., n-dimpoints, on disk? (C points per disk page)15-826 Copyright: C. Faloutsos (2005) 18CMU SCSz-orderingQ: how would you organize, e.g., n-dimpoints, on disk? (C points per disk page)Hint: reduce the problem to 1-d points(!!)Q1: why?A:Q2: how?415-826 Copyright: C. Faloutsos (2005) 19CMU SCSz-orderingQ: how would you organize, e.g., n-dimpoints, on disk? (C points per disk page)Hint: reduce the problem to 1-d points (!!)Q1: why?A: B-trees!Q2: how?15-826 Copyright: C. Faloutsos (2005) 20CMU SCSz-orderingQ2: how?A: assume finite granularity; z-ordering = bit-shuffling = N-trees = Morton keys = geo-coding = ...15-826 Copyright: C. Faloutsos (2005) 21CMU SCSz-orderingQ2: how?A: assume finite granularity (e.g., 232x232 ;4x4 here)Q2.1: how to map n-d cells to 1-d cells?15-826 Copyright: C. Faloutsos (2005) 22CMU SCSz-orderingQ2.1: how to map n-d cells to 1-d cells?15-826 Copyright: C. Faloutsos (2005) 23CMU SCSz-orderingQ2.1: how to map n-d cells to 1-d cells?A: row-wiseQ: is it good?15-826 Copyright: C. Faloutsos (2005) 24CMU SCSz-orderingQ: is it good?A: great for ‘x’ axis; bad for ‘y’ axis515-826 Copyright: C. Faloutsos (2005) 25CMU SCSz-orderingQ: How about the ‘snake’ curve?15-826 Copyright: C. Faloutsos (2005) 26CMU SCSz-orderingQ: How about the ‘snake’ curve?A: still problems:2^322^3215-826 Copyright: C. Faloutsos (2005) 27CMU SCSz-orderingQ: Why are those curves ‘bad’ ?A: no distance preservation (~ clustering)Q: solution?2^322^3215-826 Copyright: C. Faloutsos (2005) 28CMU SCSz-orderingQ: solution? (w/ good clustering, and easy tocompute, for 2-d and n-d?)15-826 Copyright: C. Faloutsos (2005) 29CMU SCSz-orderingQ: solution? (w/ good clustering, and easy tocompute, for 2-d and n-d?)A: z-ordering/bit-shuffling/linear-quadtrees‘looks’ better:• few long jumps;• scoops out the whole quadrantbefore leaving it• a.k.a. space filling curves15-826 Copyright: C. Faloutsos (2005) 30CMU SCSz-orderingz-ordering/bit-shuffling/linear-quadtreesQ: How to generate this curve (z = f(x,y) )?A: 3 (equivalent) answers!615-826 Copyright: C. Faloutsos (2005) 31CMU SCSz-orderingz-ordering/bit-shuffling/linear-quadtreesQ: How to generate this curve (z = f(x,y))?A1: ‘z’ (or ‘N’ ) shapes, RECURSIVELYorder-1order-2...order (n+1)15-826 Copyright: C. Faloutsos (2005) 32CMU SCSz-orderingNotice:• self similar (we’ ll see about fractals, soon)• method is hard to use: z =? f(x,y)order-1order-2...order (n+1)15-826 Copyright: C. Faloutsos (2005) 33CMU SCSz-orderingz-ordering/bit-shuffling/linear-quadtreesQ: How to generate this curve (z = f(x,y) )?A: 3 (equivalent) answers!Method #2?15-826 Copyright: C. Faloutsos (2005) 34CMU SCSz-orderingbit-shuffling0001101111100100xyx0 0y1 1z =( 0 1 0 1 )2 = 515-826 Copyright: C. Faloutsos (2005) 35CMU SCSz-orderingbit-shuffling0001101111100100xyx0 0y1 1z =( 0 1 0 1 )2 = 5How about the reverse: (x,y) = g(z) ?15-826 Copyright: C. Faloutsos (2005) 36CMU SCSz-orderingbit-shuffling0001101111100100xyx0 0y1 1z =( 0 1 0 1 )2 = 5How about n-d spaces?715-826 Copyright: C. Faloutsos (2005) 37CMU SCSz-orderingz-ordering/bit-shuffling/linear-quadtreesQ: How to generate this curve (z = f(x,y) )?A: 3 (equivalent) answers!Method #3?15-826 Copyright: C. Faloutsos (2005) 38CMU SCSz-orderinglinear-quadtrees : assign N->1, S->0 e.t.c.010100...01...10...11...W ENS15-826 Copyright: C. Faloutsos (2005) 39CMU SCSz-ordering... and repeat recursively. Eg.: zblue-cell = WN;WN = (0101)2 =