10

R-Precision R-Precision is defined as $\frac{r}{R}$, which is the ratio between all the relevant documents retrieved until the rank that equals the number of relevant documents you have in your collection in total ($r$), to the total number of relevant documents in your collection $R$. Suppose in your collection there are 100 documents in total, 30 of ...


6

I'm not from this field, but I believe the following advice holds in any field. First of all, I will suggest reading related literature; always a good idea. What do people in the field say about this topic? Is there an active community working on it? If not, you may find it hard to publish this work. In my discipline it is quite acceptable to publish ...


5

The above sequence it read as a concatination of 5 numbers: You start from the left side, read the first unary code. It let's you know what is the length of the first number. The 2nd number starts right after the 1st, and you interpet it the same way. First, read the first unary code, it is 1110 - so the first number is "1110:001", which is 9 The next ...


5

There is a formula for the PageRank which involves inverting an $n\times n$ matrix. When $n = 3$ this is not too hard. For inverting the matrix, use the formula given on Wikipedia, which is just a special case of the general formula involving the adjugate matrix. That said, I see absolutely no reason why you would ever have to calculate PageRank by hand. ...


4

It is a bit confusing. Suppose the alphabet has size $\Sigma$. Basically the idea is that instead of allocating each state an entire block of $\Sigma$ elements in next[] to hold the target states for each possible input character, most of which would just hold a special "this transition is invalid" sentinel value since there are typically only a few valid ...


3

In this paper they differentiate between these two terms as follows: While CLIR is concerned with retrieval for given language pairs (i.e. all the documents are given in a specific language and need to be retrieved to queries in another language), MLIR is concerned with retrieval from a document collection where documents in multiple languages co-...


3

Assuming that your data comes from a Markovian source, you can estimate the entropy of the source using an optimal compression algorithm such as Lempel–Ziv, whose theoretical version (without limiting the table size) is known to asymptotically converge to the entropy. That is, if the entropy of the source (suitable defined) is $H$, then the expected ...


3

The Chomsky hierarchy is a hierarchy of grammars described by a given formalism. The other grammar descriptions that you are giving (attribute grammars, ...) are not part of that formalism so they are outside the Chomsky hierarchy (and if I'm not mistaken are able to recognize some languages of higher level in the hierarchy while being unable to recognize ...


3

Like most things of this nature the best method is best found by empirical evaluation. One thing worth noting is that most smoothing schemes can be thought of as the incorporation of a prior into your likelihood estimate. For example if you are trying to estimate the parameter $\theta$ of a binary random variable $X$ and you have data $\mathcal{D} = \{x_1, \...


3

For a formal definition of document in the Information Retrieval context, you can look at IR glossaries. A common definition is: Document: Specific unit of retrieval (usually text). It can be a web page, an article, a book, a section or chapter. (see for example the Glossary of the book Modern Information Retrieval by Ricardo Baeza-Yates and Berthier ...


3

If the size of the alphabet is constant and $n$ denotes the length of the document (i.e. the total number of characters), you can indeed use Tries to get $O(n)$ running time - regardless of the length of the words. In a Trie, you can search for (or insert) a word in time linear in the length of the word. You can use a Trie to keep track of the words as you ...


2

When encoding several numbers in sequence, we simply concatenate the encodings of the individual numbers. The gamma code is an example of a prefix-free code: no codeword is a prefix of another codeword. Due to this property, the encoding of every string has a unique prefix which is a codeword; this prefix encodes the first number. After removing it, you ...


2

You have a dataset with at least billions of entries, whose size is that of a medium-sized hard disk. This is large. If something takes only “many hours” and not many months, that's as good as you can expect. Sorting the file is a viable strategy to get rid of the duplicates. You'll also need to canonicalize the pairs. If you stick with a flat file, the ...


2

There is a lower bound of $\Omega(n\log n)$ in the comparison model for ELEMENT DISTINCTNESS, which is the following problem: given $n$ elements, decide whether they are all different. Your task can be used to solve ELEMENT DISTINCTNESS, so in the comparison model (if you are only allowed to compare elements) there is no $O(n)$ algorithm. Using a hash table,...


2

I'm assuming that you're referring to the Elias gamma code. This code is a prefix code, also known as a self-terminating code. This means that you can encode a sequence of numbers by simply concatenating the encodings of the individual numbers. Since the code is self-terminating, the concatenated encoding can be decoded into the encodings of the individual ...


2

In addition to what @simonst told, I'm gonna add these: Disadvantage of Precision@K: Precision at K has this disadvantage that the total number of relevant documents in the collection has a strong influence on this metric. For example, a perfect system, could only achieve a precision@20 of 0.4, if there were only 8 documents relevant to an information need. ...


2

We could have a field separator, but we don't, because of historical reasons. Most of the characters are brought from the era of typewriters. So we have line-separator ^M and page-separator ^L, and we actually have record separator \037 and unit separator \038 which can be used as field separator. But in reality no one uses that. First if you have a text ...


2

In an $n-$word text you have exactly $n-1$ ordered word pairs (not distinct of course). If you use a Trie, you don't need to represent all $n-1$ pairs separately. Take for a example the following text: A new puppy in New York is happy with it's New York life. You first start looking at the words in the text as pairs where the first pair is (a,new), the ...


2

Information gives semantics e.g. the meaning to data. Consider pulling out of the tweets from the last hour as a raw data. If you carry out sentiment analyses form this data you get something meaningful out of raw data: information about the mood of tweeters at the moment. Data can be sourced by other means other than extracting. For example apps can ...


1

At it's core a trie is a tree-shaped deterministic finite state machine (no loops, no merges). They work best when you have a preset number of keywords to search for. The root is the start state and the leaves are all final states but each with its own action. However for parsing the http optimally one wouldn't use a pure trie. BEcause the input is mostly ...


1

The question gives you enough information to deduce $N$ and $s$. You are given $f(1,s,N)$ and $f(2,s,N)$. Note that $$ \frac{f(1,s,N)}{f(2,s,N)} = \frac{1/1^s}{1/2^s} = 2^s. $$ Hence you can find $s$. In order to calculate $f(3,s,N),f(4,s,N)$ you don't really need to find $N$, since, $$ \frac{f(1,s,N)}{f(3,s,N)} = 3^s, \quad \frac{f(1,s,N)}{f(4,s,N)} = 4^s, $...


1

I assume that your question is being put in the context of boolean retrieval. It seems that there is not a single metric that takes into account both efficiency and effectiveness and provide a theoretical framework for IR evaluation. This is mainly because these two issues can sometimes be quite independent between each other. We use certain methods to ...


1

This is a document clusterization problem. A general solution is to define some sort of distance between documents and apply a standard clusterization algorithm, such as k-means or expectation maximization. There are different approaches to picking distance measure $L$: Build a common vocabulary and convert each document into a bag of words, i.e. a long ...


1

Let $p(r)$ be the best precision which can be achieved at recall $r$. The average precision is $$ p_{avg} = \int_0^1 p(r) \, dr. $$ Let $r(p)$ be the best recall which can be achieved at precision $p$. The average recall is $$ r_{avg} = \int_0^1 r(p) \, dp. $$ Notice that the functions $p(r)$ and $r(p)$ are inverses of one another. We can express these ...


1

You could consider that a form of information retrieval, if you want. It sounds like keyword matching, so not one of the more sophisticated forms of information retrieval, but sometimes the simplest solutions are the best. I wouldn't worry too much about the name. There's no strict, hard-and-fast definition of exactly what counts and what doesn't. The ...


1

Don't know any fresh references. Off the top of my head: Signature files require candidate verification via forward files. This requires lots of random accesses, basically one per potential match. One random memory access is 100+ CPU cycles. You can do a lot of work in 100 CPU cycles (e.g., you can decompress more than 100 IDs single core http://boytsov....


1

I don't know what search engines actually do, but one approach would be sort by decreasing pagerank, resolving ties using the document ID. (In other words, the primary sorting key is the page rank, and the secondary sorting key is the document ID.) This still allows the merge operation. It also ensures that results are generated in decreasing pagerank ...


1

If I understand what you're trying to achieve correctly, you can use this technique discounted cumulative gain. $$DCG_p=\sum_{i=1}^{p}{\frac{2^{rel_i}-1}{\log_2{(i+1)}}}$$ $i$ is the rank, and $p$ is the number of results that you want to evaluate. For example, if you evaluate DCG for the first 10 results, then $p=10$. NDCG is a form of DCG that involves ...


1

A less formal answer, but nice step by step strategy is described in this video


1

As you state in your comment, you could use a variety of different approaches. Your question isn't limited to the vector space model. Various language models rely on these concepts as well. Here are two approaches: N-Grams One popular approach is the use of n-grams. This approach involves treating adjacent words as one word. For instance, "big house" would ...


Only top voted, non community-wiki answers of a minimum length are eligible