[go: up one dir, main page]

Datar et al., 2002 - Google Patents

Estimating rarity and similarity over data stream windows

Datar et al., 2002

View PS
Document ID
14030903088620347227
Author
Datar M
Muthukrishnan S
Publication year
Publication venue
European Symposium on Algorithms

External Links

Snippet

In the windowed data stream model, we observe items coming in over time. At any time t, we consider the window of the last N observations a t-(N-1), a t-(N-2),..., at, each ai ε 1,..., u; we are required to support queries about the data in the window. A crucial restriction is that we …
Continue reading at wwwdimacs.dimacs.rutgers.edu (PS) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30386—Retrieval requests
    • G06F17/30424—Query processing
    • G06F17/30477—Query execution
    • G06F17/30483—Query execution of query operations
    • G06F17/30486—Unary operations; data partitioning operations
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30386—Retrieval requests
    • G06F17/30424—Query processing
    • G06F17/30533—Other types of queries
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/14—Network architectures or network communication protocols for network security for detecting or protecting against malicious traffic
    • H04L63/1408—Network architectures or network communication protocols for network security for detecting or protecting against malicious traffic by monitoring network traffic
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/02—Details
    • H04L12/26—Monitoring arrangements; Testing arrangements
    • H04L12/2602—Monitoring arrangements
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L43/00—Arrangements for monitoring or testing packet switching networks
    • H04L43/02—Arrangements for monitoring or testing packet switching networks involving a reduction of monitoring data
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99933—Query processing, i.e. searching
    • Y10S707/99936—Pattern matching access

Similar Documents

Publication Publication Date Title
Datar et al. Estimating rarity and similarity over data stream windows
Gibbons et al. Distributed streams algorithms for sliding windows
Datar et al. Maintaining stream statistics over sliding windows
Dimitropoulos et al. Probabilistic lossy counting: An efficient algorithm for finding heavy hitters
US20070226188A1 (en) Method and apparatus for data stream sampling
US7669241B2 (en) Streaming algorithms for robust, real-time detection of DDoS attacks
CN101459560B (en) Long stream recognition method, data flow measuring method and device thereof
Rottenstreich et al. Optimal rule caching and lossy compression for longest prefix matching
Shi et al. Cuckoo counter: Adaptive structure of counters for accurate frequency and top-k estimation
Suri et al. Range counting over multidimensional data streams
Rottenstreich et al. Lossy compression of packet classifiers
Jia et al. Loglog filter: Filtering cold items within a large range over high speed data streams
Woodruff New algorithms for heavy hitters in data streams
Zhao et al. Minmax sampling: A near-optimal global summary for aggregation in the wide area
Aceto et al. Efficient storage and processing of high-volume network monitoring data
US8195710B2 (en) Method for summarizing data in unaggregated data streams
Li et al. Ladderfilter: Filtering infrequent items with small memory and time overhead
Ben Basat et al. Fast flow volume estimation
Huang et al. Optimal sampling algorithms for frequency estimation in distributed data
Homem et al. Finding top-k elements in a time-sliding window
Cormode et al. Time-decaying sketches for sensor data aggregation
Flajolet Counting by coin tossings
Zhou et al. Per-flow cardinality estimation based on virtual loglog sketching
Guo et al. Hourglasssketch: An efficient and scalable framework for graph stream summarization
Li et al. Online Mining Changes of Items over Continuous Append-only and Dynamic Data Streams.