Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2007-09-18
2007-09-18
Wong, Don (Department: 2163)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
10114136
ABSTRACT:
A system and method are provided for summarizing dynamic data from distributed sources through the use of wavelets. The method comprises receiving a first data signal at a first location, where the first data signal is dynamic, determining a first array sketch of the first data signal and constructing a first wavelet representation by manipulating the first array sketch with a B-term wavelet expansion to produce a first representation. The method further comprises receiving a second data signal at a second location, where the second data signal is dynamic and where the second location is distinct from the first location, determining a second array sketch of the second data signal, and constructing a second wavelet representation by manipulating the second array sketch with a B-term wavelet expansion to produce a second representation. In one embodiment, the method further comprises obtaining first and second array sketches from first and second locations respectively, and constructing a wavelet representation of a linear combination of the first and second array sketches. In one embodiment, the expansion is done using a Haar wavelet.
REFERENCES:
patent: 6718346 (2004-04-01), Brown et al.
patent: 6760724 (2004-07-01), Chakrabarti et al.
patent: 6871165 (2005-03-01), Aggarwal
patent: 6882997 (2005-04-01), Zhang et al.
patent: 2003/0204499 (2003-10-01), Shahabi et al.
patent: 2006/0007858 (2006-01-01), Fingerhut et al.
“Self-tuning Histograms: Building Histograms Without Looking at Data,” by A. Aboulnaga et al,Proceedings of the ACM SIGMOD Conference, 1999, pp. 181-192.
“Tracking Join and Self-join Sizes in Limited Storage,” by N. Alon et al,ACM Symposium on Principles of Database Systems(PODS), 1999, pp. 10-20.
“The Space Complexity of Approximating the Frequency Moments,” by N. Alon et al,ACM Symp. on Theory of Computing(STOC), 1996, pp. 20-29.
“Evaluating Top-k Selection Queries,” by S. Chaudhuri et al,Proceedings of VLDB Conference, 1999, pp. 399-410.
“An Introduction to Wavelets,” by C. K. Chui, Wavelet Analysis and its Applications, vol. 1, Academic Press, 1992.
“Hancock: A Language for Extracting Signatures from Data Streams,” by Corinna Cortes et al,Proceedings of the Sixth International Conference on Knowledge Discovery and Data Mining, 2000, pp. 9-17.
“Mining High-Speed Data Streams,” by Pedro Domingos et al,Proceedings of the Sixth International Conference on Knowledge Discovery and Data Mining, 2000, pp. 71-80.
“Ideal Spatial Adaptation by Wavelet Shrinkage,” by David L. Donoho et al,Biometrika, 1994, pp. 425-455.
“Computing Iceberg Queries Efficiently,” by Min Fang et al,Proceedings of VLDB Conference, 1998, pp. 299-310.
“Multi-dimensional Selectivity Estimation Using Compressed Histogram Information,” by Ju-Hong Lee,Proceedings of the ACM SIGMOD Conference, 1999, pp. 205-214.
“An Approximate L sup 1 -Difference Algorithm for Massive Data Streams,” by J. Feigenbaum et al,Proceedings of IEEE Symposium on Foundations of Computer Science, 1999, pp. 501-511.
“Testing and Spot-Checking of Data Streams,” by J. Feigenbaum et al, SODA, 2000, pp. 165-174.
“Mining Very Large Databases,” by V. Ganti et al,IEEE Computer32(8), 1999, pp. 38-45.
“Space-Efficient Online Computation of Quantile Summaries,” by M. Greenwald et al,Proceedings of the ACM SIGMOD Conference, 2001, pp. 58-66.
“Synopsis Data Structures for Massive Data Sets,” by P. Gibbons et al,SODA, 1999, pp. 5909-5910.
“New Sampling-Based Summary Statistics for Improving Approximate Query Answers,” by P. B. Gibbons et al,Proceedings of the ACM SIGMOD Conference, 1998, pp. 331-342.
“Fast Incremental Maintenance of Approximate Histograms,” by P. B. Gibbons et al,Proceedings of VLDB, 1997, pp. 466-475.
“Clustering Data Streams,” by S. Guha et al, Proceedings of the Annual Symposium on Foundations of Computer Science, IEEE, 2000, pp. 359-366.
“Stable Distributions, Pseudorandom Generators, Embedding and Data Stream Computation,” by Piotr Indyk,41stSymposium on Foundations of Computer Science, 2000, pp. 189-197.
Computing on Data Streams, by Monika R. Henzinger et al,DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 50, 1999, pp. 107-118.
“Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets,” by G. Manku et al,Proceedings of ACM SIGMOD Conference, 1999, pp. 251-262.
“Histogram-Based Estimation Techniques in Database Systems,” by V. Poosala, Ph. D. dissertation, University of Wisconsin-Madison, 1997, pp i-xvii and pp. 1-238.
“Approximate Query Processing Using Wavelets,” by K. Chakrabarti et al,Proceedings of VLDB, 2000, pp. 111-122.
“Wavelet-Based Histograms for Selectivity Estimation,” by Y. Matias,Proceedings of the ACM SIGMOD Conference, 1998, pp. 448-459.
“Dynamic Maintenance of Wavelet-Based Histograms,” by Y. Matias,Proceedings of the 26thVLDB Conference, 2000, pp. 101-110.
“On Computing Correlated Aggregates Over Contunual Data Streams,” by J Gehrke et al,Proceedings of the ACM SIGMOD Conference, 2001, pp. 13-24.
“Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets,” by J. Vitter et al,Proceedings of ACM SIGMOD Conference, 1999, pp. 193-204.
“Data Cube Approximation and Histograms via Wavelets,”CIKM, 1998, pp. 96-104.
“Stanford Stream Data Manager,” http://www-db.stanford.edu/stream/, 5 pages, Jul. 16, 2002.
“Essential Wavelets for Statistical Applications and Data Analysis,” by R. T. Ogden, Birhauser, 1997.
“The Theory of Error-Correcting Codes,” by F. J. MacWilliams and N. J. A. Sloane, North Holland Mathematical Library, vol. 16, North Holland, New York, 1977.
Gilbert Anna C.
Kotidis Ioannis
Muthukrishnan Shanmugavelayutham
Strauss Martin J.
AT & T Corp.
Dang Thanh-Ha
Wong Don
LandOfFree
Method and apparatus for using wavelets to produce data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for using wavelets to produce data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for using wavelets to produce data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3764848