System, method and computer-readable medium for providing...

Details System, method and computer-readable medium for providing... System, method and computer-readable medium for providing...

2005-07-20

2008-08-19

LeRoux, Etienne (Department: 2161)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

07415464

ABSTRACT:
A system, method and computer-readable medium are disclosed for identifying representative data using sketches. The method embodiment comprises generating a plurality of vectors from a data set, modifying each of the vectors of the plurality of vectors and selecting one of the plurality of generated vectors according to a comparison of a summed distance between a modified vector associated with the selected generated vector and remaining modified vectors. Modifying the generated vectors may involve reduced each generated vector to a lower dimensional vector. The summed distance then represents a summed distance between the lower dimensional vector and remaining lower dimensional vectors.

REFERENCES:
patent: 5904727 (1999-05-01), Prabhakaran
patent: 5933806 (1999-08-01), Beyerlein et al.
patent: 6023673 (2000-02-01), Bakis et al.
patent: 6567709 (2003-05-01), Malm et al.
patent: 6665790 (2003-12-01), Glossner et al.
patent: 6931400 (2005-08-01), Indyk et al.
R. Agrawal, et al., “Efficient Similarity Search in Sequence Databases.” Proc. Of the 4thInt. Conference on Foundations of Data Organization and Algorithms, pp. 69-84, Oct. 1993.
D. Barbara, et al., “The New Jersey Data Reduction Report.” Data Engineering Bulletin, Dec. 1997.
T. H. Cormen, et al., “Introduction to Algorithms.” McGraw Hill and MIT Press, pp. 780-781, 1990.
C. Faloutsos and D. Lin, “Fast Map: A Fast Algorithm for Indexing, Data Mining and Visualization of Traditional and Multimedia Data Sets.” Proceedings of ACM Sigmond, San Jose, California, pp. 163-174, Jun. 1995.
C. Faloutose, et al., “Fast Subsequence Matching in Time Series Databases.” Proceedings of ACM Sigmond, pp. 419-429, May 1994.
A. Glonis, et al., “Similarity Search in High Dimensions via Hashing.” Proceedings of VLDB, pp. 518-529, Sep. 1999.
J. Han et al, “Efficient Mining of Partial Periodic Patterns in Time Series Databases.” Proceedings of ICDE, pp. 106-115, Mar. 1999.
J. Hellerstein, “Automated Tuning Systems: Beyond Decision Support.” Computer Measurement Group, pp. 263-270, Dec. 1997.
J. Han, et al., “Mining Segment-Wise Periodic Patterns In Time Series Databases.” KDD, pp. 214-218, Aug. 1998.
J. Hellerstein, et al., “An Approach to Predictive Detection for Service Management.” Symposium on Integrated Network Management, pp. 309-322, May 1999.
J. Hellerstein, et al., “Characterizing Normal Operation of a Web Server: Application to Workload Forecasting and Capacity Planning.” Computer Measurement Group, pp. 150-160, Dec. 1998.
W.B. Johnson and J. Lindenstrauss, “Extensions of Lipshitz Mapping into Hilbert Space.” Contemporary Mathematics, vol. 26, pp. 189-206, May 1984.
K. V. Ravi Kanth, et al., “Dimentionality Reduction for Similarity in Dynamic Databases.” Proceedings of ACM Sigmod, pp. 166-176, Jun. 1998.
J. Lee, et al., “Multi-dimensional Selectivity Estimation Using Compressed Histogram Information.” Proceedings of the 1999 ACM Sigmod Int. Conf. On Management of Data, pp. 205-214, Jun. 1999.
Y. Matias, et al., “Wavelet-Based Histograms for Selectivity Estimation.” Proceedings of the 1998 ACM Sigmod Int. Conf. On Management of Data, pp. 448-459, Jun. 1998.
A. Oppenheim and A. Willsky, “Signals and Systems.” Prentice Hall, Signal Processing Series, pp. 359-373, 1stEd., 1983; 2ndEd. 1997.
V. Poosala and Y. Ioannidis, “Selectivity Estimation Without the Attribute Value Independence Assumption.” Proceedings of VLDB, Athens, Greece, pp. 486-495, Aug. 1997.
D. Sankoff and J. Kruskal, “Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison.” Addison-Wesley, Reading, Massachusetts, pp. 1-39 (1983).
J. Vitter and M. Wang, “Approximate Computation of Multidimensional Aggregates on Sparse Data Using Wavelets.” Proceedings of SIGMOD, pp. 193-204, Jun. 1999.
J.S. Vitter, et al., “Data Cube Approximation and Histograms via Wavelets.” Proceedings of the 1998 ACM CIKM Int. Conf. On Information and Knowledge Management, pp. 96-104, Nov. 1998.
R. Durbin, et al., “Biological Sequence Analysis: Probabillstic Models of Proteins and Nucleic Acids.” Cambridge University Press, pp. 1-10, 1998.
P. Indyk and R. Motwani, “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.” 30thSymposium on the Theory of Computing, pp. 604-613, Sep. 1998.

Affiliated with

Also associated with

Rating

System, method and computer-readable medium for providing... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System, method and computer-readable medium for providing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method and computer-readable medium for providing... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3996360