doc/zvrank.txt

   1 This is an experimental addon (or patch) for the Zebra server
   2 to faciliate ranked searches with the Vector Space Model.
   3 To install the addon, copy the file 'rank1.c' in the index
   4 directory of the Zebra distribution to 'rank1.c.orig' and
   5 replace 'rank1.c' with 'zrank1.c'. Then recompile Zebra.
   6 (make sure you link with the math library, so add the linker option
   7 '-lm'  if necessary).
   8
   9
  10 Introduction:
  11 =============
  12 In the vector space model, queries and documents are
  13 represented as vectors of term weights. Positive weights
  14 characterise terms assigned to a document while a zero weight
  15 is used for terms that do not occur in the document.
  16 The most popular method to obtain term weights is the tf-idf
  17 weighting schema, where the weight of a term is calculated as
  18 the product of a term factor (tf) and an inverse document factor
  19 (idf). Combining the tf and idf factors (usually the product)
  20 and normalizing them yields a tf-idf vector (or term weight vector)
  21 modelling a document (or query).
  22 The similarity score between a query and a document (or the
  23 similarity between two documents) depends on the term weight vectors and is
  24 then computed by a similarity function combining these two
  25 weight vectors (most often the cosine between the vectors is computed).
  26
  27 Weighting functions:
  28 ====================
  29 1) term frequency functions:
  30    locc denotes the in document frequency of a term (local frequency)
  31
  32    none ('n'):      tf = locc
  33    binary ('b'):    tf = 1
  34    max_norm ('m'):  tf = locc/max_locc
  35    aug_norm ('a'):  tf = K + (1 - K) * (locc/max_locc)  ; K = 0.5
  36    square ('s'):    tf = locc * locc
  37    log ('l'):       tf = log(locc) + 1
  38
  39 2) inverse document functions:
  40    gocc is the database frequency of a term (global frequncy)
  41    num_docs is the number of documents in the database
  42
  43    none ('n'):      idf = 1
  44    tfidf ('t'):     idf = log (num_docs / gocc)
  45    prob ('p'):      idf = log ((num_docs - gocc) / gocc)
  46    freq ('f'):      idf = 1 / n
  47    squared ('s'):   idf = log (num_docs / gocc) ^ 2
  48
  49 3) weight normalisation functions:
  50    wt = tf * idf
  51
  52    none ('n'):      nwt = wt
  53    sum ('s'):       nwt = wt / sum ( wt_i )
  54    cosine ('c'):    nwt = wt / sqrt ( sum ( wt_i ^2 ))
  55    fourth ('f'):    nwt = wt / sum ( wt_i ^ 4 )
  56    max ('m'):       nwt = wt / max ( wt_i )
  57
  58
  59 For example, the string 'atc' indicates that the
  60 augmented normalized term frequency ('a'), the
  61 usual tfidf weight ('t') and cosine normalisation ('c') is to be
  62 used for term weight caomputation.
  63
  64 *) similarity function:
  65    - cosine ('c')
  66    others are (TODO, not yet implemented):
  67    - pivoted unqiue normalisation ('p')
  68    - jaccard ('j')
  69    - dice ('d')
  70    - minkwoski ('m')
  71
  72 (Note: at the moment, there are 6 * 5 * 5 * 6 * 5 * 5 (* 1)
  73 ranking schemes selectable, but not all of them work).
  74
  75
  76 Example query (for yaz-client):
  77 ===============================
  78   find @attr 1=4 @attr 2=102 @attr 4=105 "where do i find literature on medical databases"
  79 Relation attribute 102 indicates that the results should be ranked by relevance
  80 and the query should be treated as free text (or wordlist).
  81
  82
  83
  84 Pitfalls and problems:
  85 ======================
  86 - The name of the ranking schema should be read from the Zebra
  87   configuration file.
  88 - Some weighting schemas require values to be calculated
  89   that are assigned constant values in this addon.
  90   For example, the db_f_max is the maximum frequency of a term
  91   in the database.
  92 - Ranking (or weight computation) is done online, e. g. immediately before
  93   records are retrieved. A faster way to get term weights would be to store
  94   them within inverted files. Adding this feature to Zebra would require major
  95   changes for the indexing process (as far as I can tell).
  96 - Stopwords are frequent words considered not useful for indexing
  97   documents (for example, "and", "the", "above" are common stopwords).
  98   Often these words do not carry semantic information. A stopword
  99   list might considerably reduce the size of the index and will probably
 100   enhance precision for natural language queries. In Zebra, stopword removal
 101   is possible with input filters.
 102 - Stemming is often used to map various morphologic forms of a
 103   concept to a single representation (for example, "countries" and
 104   "country" should both be stemmed to "country"). Using stemming for indexing
 105   is used to increase recall. In Zebra, stemming should be part of input
 106   filtering.
 107
 108
 109 Literature:
 110 ===========
 111 * Sebastian Hammer and Adam Dickmeiss and Heikki Levanto and Mike Taylor,
 112   Zebra - user's guide and reference,
 113   IndexData, 1995-2003.
 114
 115 * Gerard Salton and Chris Buckley,
 116   "Term Weighting Approaches in Automatic Text Retrieval",
 117   Dept. of Computer Science, Cornell University,
 118   TR 87-881, November 1987.
 119   Also appeared in:
 120   Information Processing and Management, vol. 24, no. 5, pp. 513--523, 1988.
 121
 122 * Justin Zobel and Alistair Moffat,
 123   Exploring the Similarity Space,
 124   SIGIR Forum 32(1), p. 18-34, 1998.
 125   http://citeseer.nj.nec.com/zobel98exploring.html
 126
 127 * SMART related documents:
 128   http://www.dcs.gla.ac.uk/ftp/pub/Bruin/HTML/SMART.HTM
 129
 130
 131
 132 Nomenclature / glossary:
 133 ========================
 134 - Database and collection are used as synonyms
 135 - A Document is the indexed part of a record that is referred to in a query
 136   (for a title search, the title entry)
 137
 138 * Ranking schema
 139   A ranking schema is identified by a seven character string
 140   (note: this may change in the future).
 141   The first three characters indicate the function to be used
 142   for the documents term frequency factor, the documents
 143   inverse document frequency factor and the function to combine
 144   these factors to assign a term weight.
 145   The middle character is the delimiter '-'.
 146   The last three characters indicate the functions for query term weighting.
 147   Note that different functions may be used for query and document vectors.
 148
 149   The default similarity function calculates the cosine
 150   between a document term vector and the query term vector.
 151
 152 * Term:
 153   an atomic concept used for indexing (a string),
 154   for example a word, a phrase or a number
 155 * Document:
 156   In Zebra, any part of a record that has index terms assigned to
 157   it. As data can (sometimes) be structured, document also refers to the
 158   smallest substructure with index terms (for example, a newspaper
 159   article may be structured into its title, abstract and its body of
 160   text components, which can be considered as different documents).
 161 * Term weighting function:
 162   the function used to combine and normalize tf and idf
 163 * Term frequency factor (tf) / Local weight:
 164   It indicates how important a term is to a particular document
 165   and depends on how many times a term occurs in a document.
 166 * Inverse document factor (idf) / Global weight:
 167   The global weight indicates how important a term is to the entire
 168   database based on the number of documents in which the term occurs.
 169   The inverse document frequency is based on the observation that a less
 170   frequently occurring term has better properties discriminating
 171   documents than a term that in more documents.
 172 * Normalisation:
 173   the normalisation function tries to compensate for ranking discrepancies
 174   (for example different document lengths).
 175 * Score:
 176   The score of a document indicates its similarity to the query
 177   (0 <= score <=1000)
 178 * Rank:
 179   The rank of a document is the position in the ranked result set.
 180   (first document: rank 1, etc.)
 181
 182 TODO:
 183 =====
 184 - replace 'fprintf' with 'yaz_log'
 185 - produce small test database and test cases
 186 - extend naming schema to eight chars (include similarity functions)
 187 - warn if schema is not fully available (e.g. if 'num_docs' or 'tf_max'
 188   are used)
 189 - optimize implementation (!)
 190 - Some structure elements are declared as integers ('int').
 191   For larger databases, they might have to be declared as 'unsigned long int'
 192 - 'd_f_max_str' and 'f_max_str' are not really needed (in DS, RS)
 193 - 'db_num_docs' is the number of documents in the database.
 194   (probably the number of sysnos)
 195   This is computed for the DBs Explain record as 'recordCount'
 196   and should be avaialable as reg-> ... -> recordCount
 197 - 'db_terms' is the number of distinct terms used in the database.
 198   (probably the number of keys)
 199 - maybe maximum frequencies can be computed on-the-fly for result sets
 200   (in contrast to the whole set of records)
 201