Estimating rank on graph streams

Details Estimating rank on graph streams Estimating rank on graph streams

2009-05-04

2011-12-06

Leroux, Etienne (Department: 2161)

Data processing: database and file management or data structures

Database and file access

Search engines

Reexamination Certificate

active

08073832

ABSTRACT:
The rank of nodes in a graph may be inferred from a calculated probability that each node in the graph appears in a single random walk of the graph. Short random walks may be generated for each node in the graph. The generated random walks may be combined to form a longer single random walk. Multiple single random walks may be generated in this fashion. The probability of each node appearing in a single random may be calculated from the generated single random walks. The rank of each node may then be inferred from the calculated probabilities.

REFERENCES:
patent: 5680608 (1997-10-01), Chang et al.
patent: 7363300 (2008-04-01), Davis et al.
patent: 2005/0027685 (2005-02-01), Kamvar et al.
patent: 2005/0028080 (2005-02-01), Challenger et al.
patent: 2005/0120311 (2005-06-01), Thrall
patent: 2007/0203789 (2007-08-01), Jain et al.
patent: 2007/0208730 (2007-09-01), Agichtein et al.
patent: 2009/0037410 (2009-02-01), Jones et al.
patent: 2009/0083222 (2009-03-01), Craswell et al.
Chen, et al., “Local Methods for Estimating Pagerank Values”, Proceedings of the 13th ACM Conference on Information and Knowledge Management, Retrieved at <<http://delivery.acm.org/10.1145/1040000/1031248/p381-chen.pdf?key1=1031248&key2=9448516321&coll=GUIDE&dl=GUIDE&CFID=24546217&CFTOKEN=26970120>>, Nov. 8-13, 2004, pp. 381-389.
Guo, et al., “Efficient Multiple-Click Models in Web Search”, Proceedings of the second ACM international conference on web search and data mining, Retrieved at <<http://research.microsoft.com/pubs/73115/Multiple-Click-Model-wsdm09.pdf>>, Feb. 9-12, 2009, pp. 8.
Rungsawang, et al., “Un-Biasing the Link Farm Effect in PageRank Computation”, 21st International Conference on Advanced Networking and Applications, Retrieved at <<http://ieeexplore.ieee.org/ielx5/4220856/4220857/04220990.pdf?temp=x>>, May 21-23, 2007, pp. 8.
Agichtein, et al., “Identifying “Best Bet” Web Search Results by Mining Past User Behavior”, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, Retrieved at <<http://www.mathcs.emory.edu/˜eugene/papers/kdd2006.pdf>>, Aug. 20-23, 2006, pp. 7.
Radlinski, et al., “Query Chains: Learning to Rank from Implicit Feedback”, Proceedings of the 11th ACM SIGKDD international conference on Knowledge discovery and data mining, Retrieved at <<http://www.cs.cornell.edu/people/tj/publications/radlinski—joachims—05a.pdf>>, Aug. 21-24, 2005, pp. 10.
White, et al., “Comparing Query Logs and Pseudo-Relevance Feedback for Web-Search Query Refinement”, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, Retrieved at <<http://research.microsoft.com/en-us/people/silviu/sigir07-3.pdf.>>, Jul. 23-27, 2007, pp. 2.
Chakrabarti, Soumen, “Web Search result' ranking: PageRank, HITS and related work”, Retrieved at <<http://www.it.iitb.ac.in/˜tejaswi/seminar/seminar.ps>>, Nov. 30, 2004, pp. 10.
Agichtein, et al., “Learning User Interaction Models for Predicting Web Search Result Preferences”, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, Retrieved at 21 <http://www.mathcs.emory.edu/˜eugene/papers/sigir2006preferences.pdf>>, Aug. 6-11, 2006, pp. 8.
Brin, et al., “The Anatomy of a Large-Scale Hypertextual Web Search Engine”, Retrieved at <<http://citeseerx.ist.psu.edu/viewdocs/summary?doi=10.1.1.42.3243>>, Apr. 1998, pp. 18.
Broder, Andrei, “A Taxonomy of Web Search”, ACM SIGIR Forum, Retrieved at <<http://www.sigir.org/forum/F2002/broder.pdf>>, vol. 36, No. 2, 2002, pp. 8.
Craswell, et al., “An Experimental Comparison of Click Position-Bias Models”, Proceedings of the international conference on Web search and web data mining, Retrieved at <<http://delivery.acm.org/10.1145/1350000/1341545/p87-craswell.pdf?key1=1341545&key2=5514426321&coll=GUIDE&dl=GUIDE&CFID=24703637&CFTOKEN=69444284>>, Feb. 11-12, 2008, pp. 87-94.
Claypool, et al., “Inferring User Interest”, Retrieved at <<http://web.cs.wpi.edu/˜claypool/papers/iui/iui.pdf>>, Aug. 31, 2001, pp. 17.
Dupret, et al., “Web Search Engine Evaluation Using Click-Through Data and a User Model”, Proceedings of the Sixteenth International World Wide Web Conference, Retrieved at <<http://www2007.org/workshops/paper—28.pdf>>, May 8-12, 2007, pp. 4.
Fox, et al., “Evaluating Implicit Measures to Improve the Search Experience”, ACM Transactions on Information Systems, Retrieved at <<http://delivery.acm.org/10.1145/1060000/1059982/p147-fox.pdf?key1=1059982&key2=7034426321&coll=GUIDE&dl=GUIDE&CFID=25371401&CFTOKEN=65758704>>, vol. 23, No. 2, Apr. 2005, pp. 147-168.
Joachims, Thorsten, “Optimizing Search Engines using Click through Data”, The Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Retrieved at <<http://www.cs.cornell.edu/people/tj/publications/joachims—02c.pdf>>, Jul. 23-26, 2002, pp. 10.
Joachims, et al., “Accurately Interpreting Clickthrough Data as Implicit Feedback”, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, Retrieved at <<http://www.cs.cornell.edu/People/tj/publications/joachims—etal—05a.pdf>>, Aug. 15-19, 2005, pp. 10.
Kelly, et al., “Implicit Feedback for Inferring User Preference: A bibliography”, ACM SIGIR Forum, Retrieved at <<http://www.sigir.org/forum/2003F/teevan.pdf>>, vol. 37, No. 2, 2003, pp. 11.
Pandey, et al., “Shuffling a Stacked Deck: The Case for Partially Randomized Ranking of Search Engine Results”, In Proceedings of the 31st International Conference on Very Large Databases, Retrieved at <<http://www.cs.cmu.edu/˜spandey/publications/randomRanking.pdf>>, 2005, pp. 13.
Radlinski, et al., “Minimally Invasive Randomization for Collecting Unbiased Preferences from Clickthrough Logs”, Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, Retrieved at <<http://www.cs.cornell.edu/People/tj/publications/radlinski—joachims—06a.pdf>>, 2006, pp. 7.
Richardson, et al., “Predicting Clicks: Estimating the Click-Through Rate for New Ads”, Proceedings of the Sixteenth International World Wide Web Conference, Retrieved at <<http://delivery.acm.org/10.1145/1250000/1242643/p521-richardson.pdf?key1=1242643&key2-32 4534426321&coll=GUIDE&dl=GUIDE&CFID=24703957&CFTOKEN=38118872>>, May 8-12, 2007, pp. 521-529.
Zaragoza, et al., “Microsoft Cambridge at TREC-13: Web and Hard Tracks”, In Proceedings of TREC 2004, Retrieved at <<http://trec.nist.gov/pubs/trec13/papers/microsoft-cambridge.web.hard.pdf>>, 2004, pp. 7.

Affiliated with

Also associated with

Rating

Estimating rank on graph streams does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Estimating rank on graph streams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Estimating rank on graph streams will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4255063