Advanced Topics in Data ManagementBinYaoSpring 2014(Slides were made available by Feifei Li)
Bin Yao Spring 2014 (Slides were made available by Feifei Li) Advanced Topics in Data Management
Massive DataMassive datasets are being collected everywhereStorage management software is billion-$ industryExamples (2002):MoreNewInformation OverNext2Years Than in All Previous History200324B· Phone: AT&T 20TB phone calldatabase, wireless tracking5.7· Consumer: WalMart 70TBdatabase, buying patterns200212B40.000BCBILLION WEB: Web crawl of 200M pagesbonttoolGIGABYTES20016BPaper 10sand 2000M links, Akamai storespnnting20003Btlectncity,telephom93%7 billion clicks per daytransetor194ofnewinformationconpuang1950Late1960borndigital199· Geography: NASA satellites(DARPA)Theweh1999Source:UC Berkeleygenerate 1.2TB per dayEMC Copyright 2001
Massive Data • Massive datasets are being collected everywhere • Storage management software is billion-$ industry Examples (2002): • Phone: AT&T 20TB phone call database, wireless tracking • Consumer: WalMart 70TB database, buying patterns • WEB: Web crawl of 200M pages and 2000M links, Akamai stores 7 billion clicks per day • Geography: NASA satellites generate 1.2TB per day
Example: LIDAR Terrain DataMassive (irregular) point sets (1-10Om resolution)- Becoming relatively cheap and easy to collect Appalachian Mountains between 50GB and 5TBExceeds memory limit and needs to be stored on disk
Example: LIDAR Terrain Data • Massive (irregular) point sets (1-10m resolution) − Becoming relatively cheap and easy to collect • Appalachian Mountains between 50GB and 5TB • Exceeds memory limit and needs to be stored on disk
Example:Network Flow Data·AT&T IP backbone generates 500 GB per day? Gigascope: A data stream management system- Compute certain statistics. Can we do computation without storing the data?
Example: Network Flow Data • AT&T IP backbone generates 500 GB per day • Gigascope: A data stream management system − Compute certain statistics • Can we do computation without storing the data?
Random Access Machine ModelRAMStandard theoretical modelofcomputation-Infinite memory-Uniform access cost? Simple model crucial for success of computer industry
Random Access Machine Model • Standard theoretical model of computation: − Infinite memory − Uniform access cost • Simple model crucial for success of computer industry R A M