Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Text, stream, spatial and temporal mining

Practical study notes on mining unstructured text, high-speed streams, spatial data and temporal (time-series) data: definitions, key algorithms, formulas, worked examples and exam guidance.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Text, stream, spatial and temporal mining extract patterns from different data types engineers meet in real systems: user reviews and documents (text), sensor/mobile logs and clickstreams (stream), maps and GPS traces (spatial), and measurements over time like CPU load or stock prices (temporal). Knowing models and single-pass or local methods are essential to build scalable analytics, real-time alerts, search and location-aware services.

Key ideas

Start with clear definitions (I bold each term the first time I introduce it).

  • Text mining: techniques to extract structured information (topics, important terms, classification) from unstructured text. Assumes text is tokenizable into words/tokens and that word occurrences carry signal about topics or labels.
  • Tokenization: splitting raw text into tokens (words, punctuation). Define stopwords and punctuation removal as preprocessing steps.
  • Stopword: a common word (e.g. 'the', 'is') removed because it carries little topical signal. Stemming and lemmatization reduce words to root forms; stemming is rule-based chopping, lemmatization uses vocabulary and morphological analysis.
  • Bag-of-words (BoW): represent a document by counts of tokens; order is ignored. Assumes a 'document-term' matrix is sufficient for downstream tasks.
  • TF-IDF: weighting scheme: term frequency (TF) shows importance within a document; inverse document frequency (IDF) downweights common words across documents. (See Formulas.)
  • Cosine similarity: measure between two document vectors; commonly used after TF-IDF.
  • Latent Semantic Analysis (LSA): apply SVD to the document-term matrix to get a low-rank approximation (topics). Assumes linear latent structure.
  • Latent Dirichlet Allocation (LDA): a generative probabilistic model where each document is a mixture of topics and each topic is a distribution over words. Key assumption: documents arise from Dirichlet-mixed multinomial word draws.

Stream mining (data that arrives continuously, potentially unbounded):

  • Stream: sequence of items x1, x2, x3, ... arriving over time. We usually require algorithms to be one-pass, use sublinear memory, and produce approximate answers with error bounds.
  • Sliding window model: only last W items are considered. Useful when only recent data matters.
  • Concept drift: the generating distribution changes over time; algorithms must adapt (retrain, weighted windows, detection).
  • Frequent items in streams: exact counting for all items is costly; algorithms like Misra–Gries (a.k.a. Frequent algorithm) and Lossy Counting keep small summaries. For Misra–Gries, an important guarantee is: with parameter k (k-1 counters), any item with true frequency f > N/k (N total items seen) will be reported; the estimated count f̂ satisfies f − N/k ≤ f̂ ≤ f. Lossy Counting uses an error parameter ε (and optional support s): it outputs all items with true frequency ≥ sN and no items with true frequency < (s−ε)N, with estimates underestimating by at most εN. See Worked Examples.
  • Bloom filter: a space-efficient probabilistic structure to test set membership with false positives but no false negatives; uses multiple hash functions and a bit array. Also commonly used in streams: Count-Min Sketch (approximate frequency counts with overestimation bounded by εN with probability ≥ 1−δ) and Reservoir Sampling (keeps a uniform random sample of fixed size m from an unbounded stream).

Spatial mining:

  • Spatial data: points, lines, polygons with coordinates in a metric space (usually 2D or 3D). Spatial data mining finds clusters, associations, outliers respecting spatial proximity and topology. For geographic coordinates (latitude/longitude), prefer great-circle distances (e.g., Haversine) over Euclidean; spatial autocorrelation measures (e.g., Moran's I) quantify clustering vs dispersion.
  • DBSCAN (Density-Based Spatial Clustering of Applications with Noise): an important spatial clustering algorithm. Formal definitions (exact university style):
    • Let dist(p,q) be a distance (usually Euclidean).
    • For ε > 0, define the ε-neighborhood Nε(p) = {q | dist(p,q) ≤ ε}.
    • For integer MinPts ≥ 1, a point p is a core point if |Nε(p)| ≥ MinPts (counting p itself).
    • Point q is directly density-reachable from p if q ∈ Nε(p) and p is a core point.
    • Point q is density-reachable from p if there exists a chain p = p0, p1, ..., pn = q where each pi+1 is directly density-reachable from pi.
    • Points p and q are density-connected if there exists o such that both p and q are density-reachable from o.
    • A cluster is a maximal set of density-connected points. Remaining points are noise. Assumptions: choice of ε and MinPts depends on data scale and density.
  • Variants: ST-DBSCAN extends DBSCAN to spatio-temporal data by requiring proximity in space and time and possibly different epsilons.

Temporal mining (time series):

  • Time series: sequence {x_t} indexed by time t. Stationary series have time-invariant mean and autocovariance.
  • Autocorrelation function (ACF) measures correlation between x_t and x_{t+τ}. Seasonality is repeating patterns at known periods. The partial autocorrelation function (PACF) helps identify AR order (for an AR(p), the PACF cuts off after lag p while the ACF tails off; for an MA(q), the ACF cuts off after lag q while the PACF tails off). For similarity/alignment of time series, Dynamic Time Warping (DTW) aligns sequences under time distortions; Euclidean distance is the special case with no warping.
  • Change point detection: detect time t where distribution changes. Methods include CUSUM and Bayesian online change detection.
  • ARIMA(p,d,q): autoregressive–integrated–moving-average model. Assumes after differencing d times the series is (weakly) stationary and modeled by AR(p) and MA(q) components.

Spatio-temporal mining combines spatial and temporal constraints: e.g., moving-object clustering, trajectory mining, hotspot detection (spatial clusters that are significant in a time interval).

Formulas

TF(t,d) = count of term t in document d — TF is dimensionless; applies to document-term counts. IDF(t) = ln(N / df(t)) — N is number of documents (dimensionless), df(t) is document frequency; applies in TF-IDF weighting (ln = natural log). Verify choice of log base with exam convention (some use log10). TF-IDF(t,d) = TF(t,d) * IDF(t) — weight for term t in document d. cosine(v,w) = (v · w) / (||v|| * ||w||) — v·w is dot product (sum of products), ||v|| is Euclidean norm; dimensionless. Applies to vector similarity. Misra–Gries guarantee: if parameter k, any item with true frequency f > N/k will appear in output; estimated f̂ satisfies f - N/k ≤ f̂ ≤ f — N is total items seen. ε-neighborhood: N_ε(p) = { q | dist(p,q) ≤ ε } — dist in same units as point coordinates (e.g., metres). Applies in DBSCAN. Autocorrelation at lag τ: ρ(τ) = Cov(x_t, x_{t+τ}) / Var(x_t) — dimensionless; applies when mean and variance exist.

Worked examples

  1. TF-IDF and cosine similarity (small corpus). Documents (tokens separated by spaces):

    • D1: 'cat sat mat'
    • D2: 'cat cat dog'
    • D3: 'dog sat log' Vocabulary: cat, sat, mat, dog, log. N = 3 documents. Document frequencies: df(cat)=2, df(sat)=2, df(mat)=1, df(dog)=2, df(log)=1. IDF values: IDF(cat)=ln(3/2)=0.405465, IDF(sat)=0.405465, IDF(mat)=ln3=1.098612, IDF(dog)=0.405465, IDF(log)=1.098612. TF (raw counts) and TF-IDF vectors:
    • D1: [cat:1, sat:1, mat:1, dog:0, log:0] => TF-IDF = [0.405, 0.405, 1.099, 0, 0]
    • D2: [2,0,0,1,0] => [0.811, 0, 0, 0.405, 0]
    • D3: [0,1,0,1,1] => [0, 0.405, 0, 0.405, 1.099] Cosine similarity between D1 and D3:
    • Dot = 0.4050 + 0.4050.405 + 1.0990 + 00.405 + 0*1.099 = 0.164025
    • Norms: ||D1|| = sqrt(0.164025+0.164025+1.2078)=1.2393 ; ||D3|| = same =1.2393
    • Cosine = 0.164025 / (1.2393*1.2393) = 0.1068 Final: D1 and D3 similarity ≈ 0.107.
  2. Misra–Gries trace (frequent items in a stream). Stream: a, b, a, c, a, b, a, d, a (N=9). Use parameter k=4 (keeps k-1=3 counters). Step-by-step (show counters after each item): 1: a -> {a:1} 2: b -> {a:1, b:1} 3: a -> {a:2, b:1} 4: c -> {a:2, b:1, c:1} 5: a -> {a:3, b:1, c:1} 6: b -> {a:3, b:2, c:1} 7: a -> {a:4, b:2, c:1} 8: d -> counters full -> decrement all by 1 -> {a:3, b:1, c:0} remove c -> add d -> {a:3, b:1, d:1} 9: a -> {a:4, b:1, d:1} Final estimated counts: a:4, b:1, d:1. True frequency of 'a' is 5. The guarantee: true f(=5) - N/k(=9/4=2.25) ≤ f̂(=4) ≤ f, i.e. 2.75 ≤ 4 ≤ 5, holds. So 'a' is reported as frequent (true f > N/k).

  3. DBSCAN example (2D points). Points: P1(0,0), P2(0,1), P3(1,0), P4(5,5), P5(5,6). Use ε=1.5 and MinPts=2 (counting the point itself). Compute ε-neighborhoods:

    • Nε(P1) includes P1,P2,P3 (distances 0,1,1)
    • Nε(P2) includes P2,P1,P3 (distances 0,1,~1.414)
    • Nε(P3) includes P3,P1,P2
    • Nε(P4) includes P4,P5 (distance 1)
    • Nε(P5) includes P5,P4 All five points satisfy |Nε(Pi)| ≥ 2 (the ε-neighborhood count includes the point itself) => all are core points. Two density-connected groups: cluster1 {P1,P2,P3}, cluster2 {P4,P5}. No noise.

Common mistakes

  • Confusing cosine similarity with a raw dot product: if you use cosine, the normalization is in the formula; if you use dot product as a proxy, you must L2-normalize vectors first, otherwise longer documents appear spuriously closer.
  • In stream problems, assuming exact counts are possible with small memory — must ask for approximation/error bounds and specify k or ε-window.
  • Mixing up DBSCAN parameters: MinPts is often counted including the point itself; if you use an alternative convention be explicit. Choosing ε without exploring data scale leads to wrong clusters.
  • For time series, treating non-stationary series as stationary (e.g., running AR model without differencing) leads to spurious results.

For your exam

Types of questions you will see here:

  • Definitions and short notes (e.g., define TF-IDF; explain concept drift).
  • Derivations and proofs (e.g., show Misra–Gries frequency guarantee; derive SVD-based LSA truncation error statement in words).
  • Numericals/trace (e.g., compute TF-IDF and cosine, or trace Misra–Gries on a small stream).
  • Algorithm description and step-by-step traces (DBSCAN clustering steps, sliding-window frequency count or Bloom filter insert/query steps).
  • Short programs or pseudo-code (implement TF-IDF, or pseudocode for Misra–Gries/Lossy Counting).

What a full-marks answer includes:

  • Precise definitions with assumptions (e.g., whether MinPts counts the point itself; definition of N in stream problems).
  • Correct formulas and units where relevant (distances in metres etc.).
  • For algorithms: clear pseudocode, complexity discussion (time per element and memory), and correctness/error bounds.
  • For numericals: show all steps, intermediate values, final numbers with correct rounding and units.

Quick check

  1. What does IDF measure and why do we use it?
  2. State the DBSCAN definition of a core point (be precise about ε and MinPts).
  3. In Misra–Gries with parameter k, what frequency threshold guarantees an item will be reported? Answers: 1) IDF measures how rare a term is across documents (downweights common words); used to reduce importance of ubiquitous words. 2) A point p is a core point if |N_ε(p)| ≥ MinPts where N_ε(p) = {q | dist(p,q) ≤ ε} (MinPts counts p itself under the usual convention). 3) Any item with true frequency f > N/k is guaranteed to be reported; estimated f̂ satisfies f - N/k ≤ f̂ ≤ f.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?