Summary 08 — Documents & Queries: Languages & Properties

Source: 06_Doc-Query.pdf

1. Table of Contents (Topics Covered)

Part A — Documents: - Document syntax, structure, semantics, presentation; Metadata (descriptive, semantic, MARC, Dublin Core, RDF/OWL) - Document formats (text encodings, multimedia) - Markup languages: SGML, HTML/CSS, XML/XSL/XLL, HyTime, RDF, OWL - Text properties: information theory & entropy, modeling natural language (Zipf’s Law, Heaps’ Law, stopwords, bag-of-words) - Text similarity: Hamming, edit/Levenshtein, LCS, resemblance - Document preprocessing (5 text operations): lexical analysis, stopword removal, stemming (Porter), keyword selection, thesauri (WordNet, Roget’s), taxonomies/folksonomies - Semantic similarity metrics (Wu & Palmer, Leacock & Chodorow, Moldovan & Mihalcea, Rinaldi)

Part B — Queries: - Query languages: keyword/word queries, context (phrase/proximity), Boolean, pattern matching, natural language, structural (fixed/hypertext/hierarchical) - Query properties: characterizing web queries, lengths, Zipf distribution, user search behavior - Query intent (Broder’s taxonomy: navigational/informational/transactional), query topic, sessions vs. missions

Gist (2–3 paragraphs)

This double lecture covers how documents and queries are represented and analyzed. Documents have syntax, structure, semantics and presentation, often described by metadata (“data about data” — e.g., Dublin Core, MARC, RDF/OWL for the Semantic Web). Markup languages form a family: SGML is the meta-language (with DTDs); HTML is an SGML instance for the web (with CSS for styling); XML is a simpler SGML subset that lets anyone define tags and is both human- and machine-readable.

Text properties are governed by statistical regularities. Entropy (from information theory) measures information content and bounds compressibility. Zipf’s Law says word frequency is inversely proportional to rank (a few words dominate → stopwords), and Heaps’ Law says vocabulary grows sub-linearly (V = Kn^β) with text size. Documents are often reduced to a bag-of-words. Text similarity is measured via edit/Levenshtein distance, longest common subsequence, or set resemblance. Before indexing, documents go through five preprocessing operations: lexical analysis, stopword elimination, stemming (e.g., Porter’s suffix removal), index-term selection, and building thesauri (controlled vocabularies like WordNet with synonyms/hypernyms/hyponyms). Semantic similarity measures (Wu-Palmer, Leacock-Chodorow, etc.) compute meaning-distance over ontology hierarchies.

Queries range from simple word queries (ranked by TF-IDF) to conjunctive (all words required), context queries (phrase, proximity), Boolean (AND/OR/BUT/NOT, no native ranking), pattern matching (prefixes, suffixes, regex, errors), natural language, and structural queries over fixed/hypertext/hierarchical structures. Web query analysis (from logs) shows queries are short (~2.8 terms), follow a Zipf distribution, and that what people search differs from what they publish. Broder’s taxonomy classifies query intent as navigational, informational, or transactional. Queries are also grouped into time-based sessions and goal-based missions.

2. Key Terminologies — Meaning & Use Cases

Term Meaning Use Case
Metadata Data about data (author, date, subject) Cataloging, search filtering
SGML / DTD Meta-language for markup + structure definition Defining document types
HTML / CSS SGML instance for web pages / styling The web
XML Simple SGML subset; user-defined tags Data interchange, Semantic Web
RDF / OWL Resource description / ontology languages Semantic Web knowledge
Entropy Information content; compression bound Text compression, modeling
Zipf’s Law Word freq ∝ 1/rank^α Justifies stopwords, IDF
Heaps’ Law Vocabulary size V = Kn^β (sub-linear) Predicting index size
Stopwords Very frequent, low-meaning words Removed to shrink index
Bag-of-words Text as multiset of words (order ignored) Vector model, classification
Edit/Levenshtein distance Min edits to equate two strings Spell-check, fuzzy match
LCS Longest common subsequence diff, similarity
Stemming (Porter) Reduce words to their stem Match word variants
Thesaurus (WordNet) Controlled vocabulary with semantic relations Query expansion, concepts
Hypernym/Hyponym/Meronym is-a-broader / is-a-narrower / part-of relations Semantic hierarchies
Folksonomy Collaborative flat tag vocabulary User tagging
Boolean query AND/OR/BUT/NOT over keywords Precise filtering
Phrase / proximity query Adjacent / near words Higher-precision matching
Broder’s taxonomy Navigational / informational / transactional intent Understanding web queries
Session vs. mission Time-based group vs. goal-based query sequence Query log analysis

3. Process Workflow Diagram

flowchart TD
    A[Raw Document] --> B[Lexical Analysis
chars to words]
    B --> C[Remove Stopwords]
    C --> D[Stemming
Porter algorithm]
    D --> E[Select Index Terms / Keywords]
    E --> F[Build Thesaurus / Concepts]
    F --> G[Indexed Document Representation
bag-of-words]
    H[User Query] --> I{Query Type}
    I --> I1[Word / Conjunctive]
    I --> I2[Context: phrase / proximity]
    I --> I3[Boolean AND/OR/NOT]
    I --> I4[Pattern / Structural]
    I1 --> J[Match against index]
    I2 --> J
    I3 --> J
    I4 --> J
    G --> J
    J --> K[Ranked / filtered results]

4. ELI5 — Complex Terms Explained Simply