Research On Microblog Information Search Algorithm Based On Bidirectional Dynamic Programming

In recent years,social platform like micro-blog,which represented by Twitter,FaceBook,Sina Microblog and Tencent,have gradually rised in domestic and foreign.This micro-blog platform become important information releasing and accessing platform of people's daily life.This type of social network platform provides people a convenient way to collect and publish information.And it also helps people finding like-minded friends efficient.According to the statistics,Sina microblog's registered users have exceeded 600 million since August 2009 which is the time it established.Its active users up to 282 million,and the average number of user's send microblog is more than 100 million.Microblog replace variety of user's information tools quickly,and infiltration to all aspects of user life.Microblog users will not only receive all kinds of official media information released,but also received from the media,large V release of information they focused in the daily use of microblog process.It has many information channels,and the number of information is very large.Users often struggle to deal with it.At present,the main contradiction faced by users is the contradiction between the great deal of microblog and the short reading time.How to reduce the redundancy of information on the basis of the information richness,and provide a rich and streamlined information flow to the users become the urgent problem to solve.The existing microblog information retrieval algorithms tend to pay more attention to how to present information for usersquickly,while ignoring the diversity of information,such as EarlyBird algorithm,TI algorithm and so on.In this paper,we pay more attention to the diversity of information.According to the characteristics of microblog data,we abstracts the demand for diversified microblog data into multi-query diversification.Among them,the user s needs to customize the information is represented by the multi-query.On the other hands,the user's demand for low information redundancy is represented by the diversity of microblog.At first,we defines the diversity threshold ?.And then define the cover? relationships between the microblog and microblog.Through the definition of coverA relationship between microblog,we only need to find a subset of the microblog that can cover the microblog subset complete under the diversity threshold ?.It can be said that the microblog subset has diversity under the diversity threshold ?.In this paper,the solution to the multi-query diversity problem is transformed into a solution to find the minimum microblog subset that can cover the microblog subset complete under the cover?relationship.Then,we introduces the microblog query algorithm based on dynamic programming.And we proved its validity.We alsocalculate the time complexity and the spatial complexity of the algorithm.Then,we put forward a microblog query algorithm based on bidirectional dynamic programming,which reduces the number of intermediate states and reduces the time of algorithm operation.In this paper,we use the inductive method to prove correctness' of the microblog query algorithm based on bidirectional dynamic programming.We can analyze its time complexity and spatial complexity.Finally,we design a experiments which realize the microblog query algorithm based on dynamic programming and the microblog query algorithm based on bidirectional dynamic programming.Experiments show that the microblog query algorithm based on bidirectional dynamic programming has better time efficiency.