Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2004-09-30
2010-02-23
Breene, John E (Department: 2162)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
07668856
ABSTRACT:
The invention provides methods and systems for summarizing multiple continuous update streams such that an approximate answer to a query over one or more of the continuous update streams (such as a Query requiring a join operation followed by a duplicate elimination step) may be rapidly provided. The systems and methods use multiple (parallel) Join Distinct (JD) Sketch data structures corresponding to hash buckets of at least one initial attribute.
REFERENCES:
patent: 5857180 (1999-01-01), Hallmark et al.
patent: 5960434 (1999-09-01), Schimmel
patent: 6115705 (2000-09-01), Larson
patent: 6134546 (2000-10-01), Bestgen et al.
patent: 6339772 (2002-01-01), Klein et al.
patent: 6604102 (2003-08-01), Klein et al.
patent: 6694322 (2004-02-01), Warren et al.
patent: 6912524 (2005-06-01), Acharya et al.
patent: 7085911 (2006-08-01), Sachedina et al.
patent: 7110540 (2006-09-01), Rajagopal et al.
patent: 2002/0038313 (2002-03-01), Klein et al.
patent: 2004/0243563 (2004-12-01), Heiner et al.
patent: 2005/0091238 (2005-04-01), Zane et al.
S. Ganguly, M. Garofalakis, and R. Rastogi. “Processing Set Expressions over Continuous Update Streams”: In SIGMOD, Jun. 9-12, 2003.
“NetFlow Services and Applications”. Cisco Systems White Paper (http://www.cisco.com), 1999.
B. Babcock and C. Olston. “Distributed Top-K Monitoring”. InSIGMOD, 2003.
M. Charikar, K. Chen, and M. Farach-Colton. “Finding Frequent Items in Data Streams”. In ICALP, 2002.
C. Cranor, T. Johnson, O. Spatscheck, and V. Shkapenyuk. “Gigascope: A Stream Database for Network Applications”. InSIGMOD, 2003.
A. Das, S. Ganguly, M. Garofalakis, and R. Rastogi. “Distributed Set-Expression Cardinality Estimation”. Bell Labs Tech. Memorandum, 2003.
S. Ganguly, M. Garofalakis, and R. Rastogi. “Processing Set Expressions over Continuous Update Streams”: InSIGMOD, 2003.
P.B. Gibbons. “Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports”. InVLDB, 2001.
P.B. Gibbons and S. Tirthapura. “Distributed Streams Algorithms for Sliding Windows”. InSPAA, 2002.
A. C. Gilbert, Y. Kotidis, S. Muthukrishan, and M.J. Strauss. “How to Summarize the Universe: Dynamic Maintenance of Quantiles”. InVLDB, 2002.
S. Madden, M. J. Franklin, J. H. Hellerstein, and W. Hong. “The Design of an Acquisitional Query Processor for Sensor Networks”. InSIGMOD, 2003.
D. Moore, G.M. Voelker, and S. Savage. “Inferring Internet Denial-of-Service Activity”. InUSENIX Security Symposium, 2001.
C. Olston, J. Jiang, and J. Widom. “Adaptive Filters for Continuous Queries over Distributed Data Streams”. InSIGMOD, 2003.
G. Pottie and W. Kaiser. “Wireless Integrated Network Sensors”. Communications of the ACM, 43(5), 2000.
Ganguly Sumit
Garofalakis Minos N.
Kumar Amit
Rastogi Rajeev
Alcatel-Lucent USA Inc.
Breene John E
Bullock Joshua
Wall & Tong LLP
LandOfFree
Method for distinct count estimation over joins of... 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 for distinct count estimation over joins of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for distinct count estimation over joins of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4212432