Ranking method - Research Paper Example

The extensive growth of the internet has led to creation of many websites and this number is increasing at a very high rate. As a result, these websites, especially the social networking websites such as twitter with millions of tweets per second, have put huge amounts of data in the internet. Researchers have come up with ways of managing this pool of data to ensure fast access by the users to the websites and data of their interest. They have developed different algorithms that filter the tremendous data to give the users only the desired websites and data thus saving on their time.

The users don’t have to scan through every webpage to find the relevant ones or those with relevant tweets or news. Many ranking functions have been developed for the purpose of evaluating the websites and the web contents. Each of these functions is based on a different algorithm which uses a certain criteria to evaluate the relevance of web content and the data.This paper will consider three separate papers that make an illustration of the use different criteria to apply the ranking algorithm to solve ranking problems based on different aspects.

We will seek to find out the themes that are common in these papers, the non-overlapping concepts and any disagreements.We will also determine the various ranking algorithms and their use by researchers to improve ranking. The various aspects of the ranking algorithms will also be looked at to determine their importance to internet users.Categories and Subject DescriptorsH.3.3 [Information Systems]: Information Search and RetrievalGeneral TermsInformation, modelKeywordsUser engagement, time between visits, metrics, ranking evaluation, interleaving, search engine, click-through data.

Overview In the world today, there is an exponential increase in the demand for information which has been highly facilitated by the advancement of informational technology. This has resulted in the development of billions of online items and websites that try to satisfy the users’ needs. Most of these items and websites do not serve the interest of the users fully. Therefore there is the need to optimize these items by ranking them according to their usefulness and also gather information on the usefulness of various websites to users [2].

In this paper, we analyze three research papers which mainly revolve around improving the user experience in the online industry. The articles are Dupret etal [1], Feng etal [2] and Kumar etal [3]. Each one of them compliments the other in that they all propose how to optimize ranking of items in a website and how to evaluate the success by deriving the user engagement using a proposed metric. A summary of how to optimize the informational items found online will be provided which largely try to address the problems faced by users globally.

This is in regard to development of a suitable ranking method, ranking quantization and evaluating various ranking function to determine the usefulness of the content in a website. A scheme for tweet ranking on the individual level will be proposed which is an improvement to the previous works that addressed the problem on the global scale. The general organization of this paper will adopt five sections to tackle different aspects in the three research papers. In this regard, section two will tackle the common theme with the following section covering the discordant theme.

Section four will dwell on the overlapping themes which will involve the algorithms and concepts covered on each article. The last section will provide conclusion about the information provided in the three articles and how it can help improve the optimization of websites to efficiently serve the users needs.1. Common themesIn this section, we analyze the common themes between the three selected research papers. In all of them, it is clear that the main aim is to improve the significance of online items to ensure total customer satisfaction.

All the research papers propose different frameworks that can help improve the user experience and also determine his overall satisfaction from various sessions.Due to the exponential growth in the number of web pages, static scores used by search engines to give the quality of pages being browsed would require a significant number of bits. In research paper [3] the authors try to address this problem by proposing the use of rank quantization to reduce the number of bits required in the storage of an elements position in the case of full ranking.

In his way the page static rank of millions of search engines can be quantized with as few as eight bits. The authors in research paper [1] suggest the development of an efficient metric to assess user engagement with a website. The widely used metrics such as well time, page views and clickthrough rates can not be solely relied on to derive the overall user engagement. The authors propose the use of the absence time or the time between the two visits by an users to effectively measure their engagement.

In research paper [2], the authors’ suggest the development of personalized re-ranking to improve the efficiency of the current system. Its main focus is on the individual level. The goal of personalized tweet ranking (PTR) is to rank the tweets that are more likely to be re-tweeted at the front of the list of each session. Two ways that are used to determine if the predicted rating is well approximated include the point-wise approach and pair wise approach. The re-tweet behavior can be represented as a graph G=(V,E) where V involves three types of nodes (users, publisher and tweets) while E represent user trust on the publisher, content interestedness and publisher is the owner of the tweet.

The loss function used to determine the suitability of the approximation includes the point-wise loss and the pair-wise loss.It is worth noting that the search of information is on the increase each and every day. The three articles highlight the problems faced by users during their interaction with different websites. They possess a common theme which seems to revolve around the optimization of informational search. The same has been successfully conducted in tweeter by use of a tweet ranking system [2].

The successful optimization of informational search can however be achieved by improving the online items ranking. 2. Discordant themesThe algorithms used in the three research papers were different and different criteria were used for ranking. In research paper [2] the authors propose a general graph model to analyze re-tweet behavior. The sources of information are converted to the feature vectors of nodes and edges. Using this graph, they further propose a feature-aware factorization model which unifies the linear discriminative and the low-rank factorization models seamlessly.

Using real dataset from tweeter, this model is more effective than the existing models.The research paper [3] employed rank quantization and linearization to attain a better algorithm. Evaluation of the tweets in this case was also dependent on the users and the publishers. It is thus clear that the three articles are discordant in the way they treat a common problem.In research paper [1], the main focus is not the ranking functions themselves but a method to compare them. These functions include;Hand- a baseline function that is the result of very carefully human hand tuning over several yearsEmlr- a state-of-the-art machine learned ranking function trained on an extensive set of editorial labelsOther functions are based on the clicks model such as attr (attractiveness based model), util (utility based model), attrc (an attractiveness model with extra click features), satis (utility & attractiveness combination model with click features). 3. Non-overlapping themesThe main purpose of all the three papers is to come up with a ranking algorithm which will help achieve better outcome.

In each of the papers a different tool has been used to improve the ranking model and we seek to confirm this. We will be giving a detailed review of the papers in this section. Since the selected research papers tackle a similar problem in different ways while ensuring that the overall result is to improve the user experience. A detailed analysis on each one of them would provide a glimpse of how they manage to influence the user experience while using various websites.4.1 Absence Time and User Engagement: Evaluating Ranking FunctionsIn research paper [1], the authors propose the use of absence time is based o the assumption that if a website is deemed interesting by a given user, he will return to it sooner e.g. for questions and answers websites.

Dwell time and click through rates indicates that the user was interested in the content of the website but at time this may not be the case e.g. in direct displays. Direct display includes instances of contact information or weather data. Absence time adds significant insights to the interpretation of activity metrics such as page view and click. They address two potential issues that are faced by the use of absence time include; how to identify session boundaries. In addition, a user might decide to return sooner or later to a website due to reasons unrelated with the previous visits.

Some of the well known metrics such as clickthrough rate and abandonment rate which are arguably the corner stone of web search evaluation fail to address user behaviours in full. The authors propose the use of absence time to address these deficiencies. To study the absence time they make use of survival analysis. It mainly has three components namely; cox model, survival function and hazard rate. They argue that modelling the hazard rate rather than the survival function is more desirable and advantageous.

The cox model relies on the previous model where the hazard rates are constrained to be proportional which makes it possible to quantify their relations. They further apply the survival analysis to the functions mentioned in section 2 above. They authors conclude that Emlr is the best performing function followed by attrc and satis4.2 Rank QuantizationThey authors in this research paper [3] also suggest ways to discover elements at similar preference level. This is done in two steps: the first step involves finding a total order by linearizing the rankings induced by the multiple partial orders and the inconstant pair-wise preferences are removed.

Then after obtaining the total order, the authors the use of quadratic-time quantization and the 2/3-approximation algorithm to formalize the rank quantization problem while preserving the relationships that appear in the partial orders. In the rank quantization, problems are given in weighted graph G=(V,E). On the other hand the rank linearization problem strives to search for the minimum Feedback Arc-Set problem. To solve the minimum Feedback-Arc-Set various approaches are used such as sorting by out-degree, Eigenvector method, general quicksort algorithm and the local search.

Sorting out by degree – provides a way of computing a full order by sorting nodes by their weighted degree i.e. those with the highest degree come first.Eigenvector method – works by computing the stationary distribution of a random walk induced by the graph with a small teleportation probability to make sure the walk is ergodic.Generalised quicksort – this algorithm generates near optimal solutions for weighted tournament graph. The authors adapt it to general graphs thus lose the associated performance guarantee.

The authors propose the use of sorting by out-degree, the eigenvector heuristic and the generalized quicksort for the query sample. Their experiment uses two datasets, the random and the popular sample. In the random sample, each instance in the query log is chosen at random with a certain probability. In popular sample dataset, it is generated by taking a single instance of each of the million or so most frequently submitted queries.Of the three algorithms, general quicksort produce qualitatively worse results.

They further propose two algorithms for the rank quantization problem. The first algorithm (exact algorithm) shows how to solve the problem exactly while the second one (greedy approximation) can be implemented faster for sparse inputs which is familiar with their settings. The loss in performance after the use of greedy algorithm is however present on weighted edges though insignificant in practical terms.4.3 Re-tweet or not? Personalized Tweet Re-rankingIn this research paper [2], a model ‘Personalized Tweet Re-Ranking (PTR)’was developed by the researchers for the users to be able to re-rank the tweets to suit their interest.

On average, 340 million tweets are generated daily on Twitter. As such, researchers have to come up with a convenient way of reading them. The users don’t have to access all the tweets that they miss every day. Instead a ranking algorithm determines what appears on the home page of the user.The researcher in this paper has developed a Personalized Tweet Re-Ranking (PTR) model which uses a tweets probability to re-tweet to rank all the tweets in the user’s homepage. The users are therefore able to handle the huge volumes of tweets and find the tweets that are important or interesting to them quickly.

In the ranking method used in this paper, the researcher uses an evaluation that is very personalized. This is different from the ranking approach used by Twitter that is very general and ranks all the tweets in a social website according to their popularity.In this ranking method, a graph consisting of three nodes is used. These are the tweet quality, the users’ profile, and the publishers. The researchers then include the features for each node to strengthen the relation. Two factors affect the re-tweets;Node weights: This is an analysis of each of the three nodes.

For instance, is the publisher likely to re-tweet? Is the user likely to re-tweet? Is the quality of the tweet high? Edge weight: This determines how the user relates with the publisher or the tweet.These two factors create four relationships; user-location, user-publisher, user-hash-tag, and user-term.We first look at the features of each node in the graph and these are;1) Tweet node features: this involves an evaluation of each tweet depending on contents and features such as; the number of times it has been re-tweeted, whether it has multimedia content, URL, or the hash-tag.2) Publisher node features: determines the likelihood of a publisher’s tweet being re-tweeted using publisher profile information such as location, publisher ID, account, age, and popularity.3) User node features: examines a user’s profile and activity, for instance; account, age, time between re-tweet, user ID, and age.

We then look at the edge features and these are:1) User-publisher features: to determine the closeness of publisher and user by analyzing types of tweets from each side, reply count, re-tweet count, and each user’s self-description in Twitter.2) User-tweet features: to determine the kind of tweets a user has interest in.The researchers come up with Feature-Aware Factorization Model to ensure all the features are incorporated between the nodes and edges. Only five node features are taken into account for this model; user ID, location ID, term IDs, hash-tag IDs, and publisher IDs.

The Loss Function method is used to determine the parameter that is better. Many evaluation models such as Non-Personalized Re-tweet Prediction (RP), Feature-Based Model (Feat), and Recommendation with Social Regularization (SocRS) are used. User-publisher features are found to be more effective compared to user-tweet features. This is because determining the interestedness of a tweet to the user using the tweet content is difficult due to the tweet’s many characters. The new tweets ranking model is easy to use.

All a user is to specify the edge and node features to generate a Personalized Tweet Re-Ranking.4. ConclusionInformational web pages have increased over the decades which have been boosted by the advanced information technology. Due to the availability of large amount of information, most websites have the problem of ensuring that user’s obtain the most relevant and useful information in the least time possible. On tweeter, a system that suggests the most relevant tweets can be very useful due to the large numbers of tweets generated on a daily basis.

Personalized tweet re-ranking provides the best solution since it derive the experience ion the individual level. Due to the significant increase in the number of web pages, use of static scores by search engines would require a significant number of bits to store element position in full ranking. Rank quantization however provides the solution to this problem by ensuring a fewer number of bits are required for the same work.Lastly, to determine the usefulness of ranking functions, it is important to measure the user engagement.

Absence time as a way to measure user engagement has been found to be more efficient compared to dwell time and click through rates. It is easy to interpret and less ambiguous. Therefore, rank development, optimization and evaluation can ensures that the users are wholly satisfied after their interactions with their respective website.References[1] Dupret, G., & Lalmas, M., Absence Time and User Engagement: Evaluating Ranking Functions [2] Feng, W, & Wang, J. Retweet or not? Personalized Tweet Re-ranking Retweet or not?

Personalized Tweet Re-ranking, 2013.ACM. [3] Kumar, R., Lempel, R., Schwartz, R., & Vassilvitskii, S. Rank Quantization, 2013.ACM