Friday, June 19, 2009
Thursday, June 18, 2009
Real time search (what about Ranking?)
The number of real time search engines is increasing. Yesterday, two new engines joined the race. CrowdEye is from Ken Moss, who ran search engineering at Microsoft and built the new engine himself. Collecta is from Gerry Campbell, who was a search executive at AOL and Reuters, as well as an adviser to Summize (now Twitter Search). OneRiot who is run by Kimbal Musk and my old friend Alessio Signorini. Other engines are Topsy, Tweetmeme and Scoopler, not to mention Twitter Search itself.
This reminds me the old times when Excite, Lycos, Altavista and a lot of new-comers joined the search race -- back in 1997. Search is alive and kicking with new exciting stuffs to play with.
I would expect more and more academic publication on real time search problems, such as real time ranking.
This reminds me the old times when Excite, Lycos, Altavista and a lot of new-comers joined the search race -- back in 1997. Search is alive and kicking with new exciting stuffs to play with.
I would expect more and more academic publication on real time search problems, such as real time ranking.
The Tradeoffs Between Open and Traditional Relation Extraction
The Tradeoffs Between Open and Traditional Relation Extraction is a paper about extraction of relations between entities on a massive scale. The system is based on a self-training unsupervised approach derived by the Conditional Random Fields (CRF) theory. A set of training examples are extracted by a training corpus by means of hand-crafted defined parsing rules. The training examples are then used to train a linear chain of CRF.
.
Results are pretty impressive both in term of precision and recall.
.Results are pretty impressive both in term of precision and recall.
Wednesday, June 17, 2009
Tuesday, June 16, 2009
Monday, June 15, 2009
Fresh Correlations: Valentino Rossi and Jorge Lorenzo
Valentino is correlated to Jorge, algorithm says. Here is the motivation:
"The world champion's win at the Catalan Grand Prix came on the final corner of a last lap prize-fight with Jorge Lorenzo, his Fiat Yamaha team-mate, and means the pair are tied at the top of the MotoGP standings with Casey Stoner on 106 points. "
"The world champion's win at the Catalan Grand Prix came on the final corner of a last lap prize-fight with Jorge Lorenzo, his Fiat Yamaha team-mate, and means the pair are tied at the top of the MotoGP standings with Casey Stoner on 106 points. "
Sunday, June 14, 2009
Go Lakers Go!
Multimedia clustering algorithm captured the fresh correlations between news articles, blogs, images, video, faces and names. All in real time.
Twitter, OneRiot, Google
Interesting article from NYT on Real time search
"TECHNOLOGY blogs have wondered whether Google is a lumbering giant in this Twitter moment, unable to handle streams of tweets that were broadcast just seconds earlier."
"A number of search start-ups have appeared recently that differentiate their offerings from older search engines’ by playing up their specialized focus on the real-time Web. For example, OneRiot, based in Boulder, Colo., covers Twitter among other social media, but it has an intriguing means of reducing Twitter spam: it does not index the text in tweets — it plucks only the links, reasoning that the videos, news stories and blog posts that are being shared are what others will be most interested in."
"Google’s almost-real-time search provides much higher-quality results than does literal real-time search. When speaking about the need to index the Web “every second,” Mr. Page acknowledged the usefulness of taking a wee bit of time to analyze the gathered information. “If you really want up-to-the-second information, it’s not going to be as good as if you’re willing to wait a couple of minutes,” he said. “I’m not sure everybody needs to be seeing this stuff every second.”
"TECHNOLOGY blogs have wondered whether Google is a lumbering giant in this Twitter moment, unable to handle streams of tweets that were broadcast just seconds earlier."
"A number of search start-ups have appeared recently that differentiate their offerings from older search engines’ by playing up their specialized focus on the real-time Web. For example, OneRiot, based in Boulder, Colo., covers Twitter among other social media, but it has an intriguing means of reducing Twitter spam: it does not index the text in tweets — it plucks only the links, reasoning that the videos, news stories and blog posts that are being shared are what others will be most interested in."
"Google’s almost-real-time search provides much higher-quality results than does literal real-time search. When speaking about the need to index the Web “every second,” Mr. Page acknowledged the usefulness of taking a wee bit of time to analyze the gathered information. “If you really want up-to-the-second information, it’s not going to be as good as if you’re willing to wait a couple of minutes,” he said. “I’m not sure everybody needs to be seeing this stuff every second.”
Saturday, June 13, 2009
Friday, June 12, 2009
Efficient Interactive Fuzzy Keyword Search
Efficient Interactive Fuzzy Keyword Search is a pretty nice paper about a new information-access paradigm, called“interactive, fuzzy search,” in which the system searches the underlying data “on the fly” as the user types in query keywords. This is useful for search suggestion services provided while users are typing search queries.
The underlying data structure is a combination of tries, inverted lists, and smart caching techniques used for achiveving good performance. The basic data-structures are then expanded for supporting ranking and synonims.
I enjoyed the paper, but the index dimensions are so small that all the data-structures can fit in memory (even without compression)
The underlying data structure is a combination of tries, inverted lists, and smart caching techniques used for achiveving good performance. The basic data-structures are then expanded for supporting ranking and synonims.
I enjoyed the paper, but the index dimensions are so small that all the data-structures can fit in memory (even without compression)
Inverted Index Compression and Query Processing with Optimized Document Ordering
Inverted Index Compression and Query Processing with Optimized Document Ordering is a paper describing the state-of-the-art compression techniques for inverted list data structure, after document re-ordering. A reference reading paper.
I wonder if this work can be extended by taking into account the modern search engines are storing all the index in memory. This is also including inverted lists. Therefore, one can explore the benefits of having different hierarchies of memory.
I wonder if this work can be extended by taking into account the modern search engines are storing all the index in memory. This is also including inverted lists. Therefore, one can explore the benefits of having different hierarchies of memory.
Thursday, June 11, 2009
Yahoo Distribution of Hadoop
Yahoo announced the availability of the Yahoo Distribution of Hadoop, a source-only version of Apache Hadoop that Yahoo uses within its own search engine.
Congratulation to Doug Cutting, a very friendly man who is behind cool things such as Nutch, Lucene and Hadoop.
When will you return in Italy to visit us? This is an official invitation!
Congratulation to Doug Cutting, a very friendly man who is behind cool things such as Nutch, Lucene and Hadoop.
When will you return in Italy to visit us? This is an official invitation!
Fiat , Chrysler deal done: news, video, blog and images
When you see a fresh topic, you may want to have all different ingredients covered: news articles, blogs, fresh images, faces and videos. Here it is an example of our multimedia clustering technology working in real time on thousands of sources. This is coming from Italy:
Wednesday, June 10, 2009
Tuesday, June 9, 2009
Bing is growing
A nice article from techcrunch "According to comScore, Microsoft Sites increased its average daily penetration among searchers in the United Stated from 13.8% during the period of May 26-30 to 15.5% during the period of June 2-6, 2009, an indication that the search engine is reaching more people than before. Microsoft’s share of search engine results pages (SERPs) in the U.S., increased from 9.1% to 11.1% during the same time frame."
Here the original Comscore article
Here the original Comscore article
| Microsoft Sites Search Performance 6/2/09-6/6/09 vs. 5/26/09-5/30/09 Total U.S. – Home/Work/University Locations Source: comScore qSearch | |||
| | 5/26/09-5/30/09 | 6/2/09-6/6/09 | Point Change |
| Searcher Penetration (Avg. Daily) | 13.8% | 15.5% | 1.7 |
| Share of Search Results Pages | 9.1% | 11.1% | 2.0 |
Monday, June 8, 2009
Oneriot is growing steadly
Oneriot, the real-time search engine is growing steadly. They closed a very good deal with Microsoft.
Congratulation to my old friend Alessio and to Kimbal, who likes to mix the passion for technology and new business ideas with some great food experience.
Alessio, ganzo deh!
Congratulation to my old friend Alessio and to Kimbal, who likes to mix the passion for technology and new business ideas with some great food experience.
Alessio, ganzo deh!
Exploiting Web Search Engines to Search Structured Databases
Exploiting Web Search Engines to Search Structured Databases is a Microsoft paper about the integration of verticals in Web search results. The key idea is that each vertical is a-priori associated with a list of relevant entitites. When a user submit a query, those entities are extracted by the search results snippets. In this way, the query itself is implicitely expanded with vertical related entities found in search results (note that similar idea, has been investigated by Yahoo in a paper for adversiting).
The paper discusses many off-line pre-processing techniques for extracting entities before query time. A mixed approach based on trie pattern-matching and svm classification is proposed. Extracted entities are then ranked by taking into account proximity, frequency count and relevance of documents. For a given query, a vertical result is then triggered when 'good enough' entities are retrieved. A case study based on product search vertical and Microsoft Live search is discussed. Entities are extracted from Wikipedia, Trec QA, and IMDB.
The approach is quite effective and the performances are pretty good. Anyway, it can show some limits of real time verticals (such as Twitter or News) where entities are not known a priori.
The paper discusses many off-line pre-processing techniques for extracting entities before query time. A mixed approach based on trie pattern-matching and svm classification is proposed. Extracted entities are then ranked by taking into account proximity, frequency count and relevance of documents. For a given query, a vertical result is then triggered when 'good enough' entities are retrieved. A case study based on product search vertical and Microsoft Live search is discussed. Entities are extracted from Wikipedia, Trec QA, and IMDB.
The approach is quite effective and the performances are pretty good. Anyway, it can show some limits of real time verticals (such as Twitter or News) where entities are not known a priori.
Sunday, June 7, 2009
Herb Sutter on Cache False Sharing
A nice article by Herb Sutter on Cache False Sharing. It is worth reading in these multicore days.
Saturday, June 6, 2009
Is Bing growing?
Source: StatCounter Global Stats - Search Engine Market Share
The company's analysis for Thursday finds that in the U.S. Bing overtook Yahoo to take second place on 16.28%, with Yahoo Search currently at 10.22%. For the sake of comparison: Google's U.S. market share is pegged at 71.47%, and its worldwide share at a whopping 87.62% (vs. 5.62% for Bing and 5.13% for Yahoo).
Friday, June 5, 2009
Goodbye Rajeev Motwani
Although I don't have a direct connection with Rajeev Motwani, he has become a source of inspiration for me to start studying computer science many years ago. Thanks for your books, your papers, and the amazing contribution you gave to silicon valley community. Keep us creative from above.
Thursday, June 4, 2009
Personalized Recommendation on Dynamic Content Using Predictive Bilinear Models
Dynamic Content Using Predictive Bilinear Models is a Yahoo! paper about suggesting relevant news stories for Yahoo's "Today" module The paper describes a bi-linear model leveraging both instantaneous dynamic click-through information and static content based features. The objective function adopted is concave and minimized with a gradient descent approach.
The authors collected about 40 million click/view events by about 5 million users from the random bucket before a certain time stamp for training. One evaluation metric adopted is the number of clicks in each rank position. The intuition is that a good predictive model should have more clicks on the top-ranked positions and lesser clicks on the lower ranked position. Results are quite interesting: the model shows the benefits of adopting dynamic click-through data.
Unluckly, no information is given about the time needed to process the data. A rather important point when you process (near) real time data.
The authors collected about 40 million click/view events by about 5 million users from the random bucket before a certain time stamp for training. One evaluation metric adopted is the number of clicks in each rank position. The intuition is that a good predictive model should have more clicks on the top-ranked positions and lesser clicks on the lower ranked position. Results are quite interesting: the model shows the benefits of adopting dynamic click-through data.
Unluckly, no information is given about the time needed to process the data. A rather important point when you process (near) real time data.
Wednesday, June 3, 2009
Visual Diversification of Image Search Results
Visual Diversification of Image Search Results is a Yahoo paper about image clustering that I liked very much. The paper deploys lightweight clustering techniques, to best capture the discriminative aspects of the resulting set of images that is retrieved.
For earch image, a set of representative features are extracted such as Color histogram, Color layout, Scalable color, CEDD, Edge histogram, Tamura. Strangely enough the authors are not considering SIFT and wavelet signatures, which are quite popular these days.
Authors evaluated three different algorithms:
Evaluation measures are the Folwkes-Mallow index and the Variation of Information Criterion. Folding is the best algorithm under the FM index evaluation, and Reciprocal is the best one according to the Variation of Information Criterion.
I reccomend reading the paper if you are interested in Image search and in Clustering. Just one observation to the authors. Since the target of this work is an use in production, I would have appreciated a comparison of the time needed to extract the features and to cluster the results with the three different algorithms.
For earch image, a set of representative features are extracted such as Color histogram, Color layout, Scalable color, CEDD, Edge histogram, Tamura. Strangely enough the authors are not considering SIFT and wavelet signatures, which are quite popular these days.
Authors evaluated three different algorithms:
- The folding algorithm appreciates the original ranking of the search results as returned by the textual retrieval model. Images higher in the ranking have a larger probability as being selected as a cluster representative. In one linear pass the representatives are selected, the clusters are then formed around them.
- The maxmin approach also performs representative selection prior to cluster formation,but discards the original ranking and finds representatives that are visually different from each other.
- Reciprocal election lets all the images cast votes for other images that they are best represented by. Strong voters are then assigned to their corresponding representatives, and taken off the list of candidates. This process is repeated as long as there exist
unclustered images.
Evaluation measures are the Folwkes-Mallow index and the Variation of Information Criterion. Folding is the best algorithm under the FM index evaluation, and Reciprocal is the best one according to the Variation of Information Criterion.
I reccomend reading the paper if you are interested in Image search and in Clustering. Just one observation to the authors. Since the target of this work is an use in production, I would have appreciated a comparison of the time needed to extract the features and to cluster the results with the three different algorithms.
Binging Google, Yahoo and Ask
Why Bing is exposing a search box which uses Google, or Yahoo or Ask.com?
Are they suggesting a comparison?
Are they suggesting a comparison?
Tuesday, June 2, 2009
Academic works on News and Freshness
Steven Skiena is quite famous among the Algorithmic comunity for his beatiful books. His research studies for freshness and, in general, on stream data analysis, are less known.
- TextMap identifies trends in the temporal and geographic interest in entities such as people, places, and things by analyzing roughly 1000 daily English language newspapers.
- TextMed identifies the relationships between medical or biological entities through an analysis of PubMed/Medline abstracts.
- TextBiz uses random-walk models to generate a probability distribution on the future prices for all NASDAQ, NYSE, and AMEX stocks.
- Lydia: A System for Large-Scale News Analysis by L. Lloyd, D. Kechagias, and S. Skiena, 12th Symp. of String Processing and Information Retrieval, (SPIRE '05), Lecture Notes in Computer Science, 3772 (2005) 161-166 provides an overview of the architecture of the Lydia system as of May 2005.
- Question Answering with Lydia by J. Kil, L. Lloyd, and S. Skiena, 14th Text REtrieval Conference (TREC 2005), NIST Gaithersburg MD, November 15-18, 2005 describes an extension to Lydia for answering factoid, list, and open-ended English-language questions.
- Newspapers vs. Blogs: Who Gets the Scoop? by L. Lloyd, P. Kaulgud, and S. Skiena, AAAI Symp. Computational Approaches to Analysing Weblogs (AAAI-CAAW 2006), Stanford University, March 27-29, 2006 provides an comparison of entity frequencies between blogs and more formal news sources.
- Identifying co-referential Names Across Large Corpora by L. Lloyd, A. Mehler, and S. Skiena, Proc. Combinatorial Pattern Matching (CPM 2006) discusses our method for identifying synonym sets of entities.
- Spatial Analysis of News Sources, by A. Mehler, Y. Bao, X. Li, Y. Wang, and S. Skiena, IEEE Trans. Visualization and Computer Graphics 12 (2006) 765-772 discusses our ``heatmap'' analysis.
- Large-Scale Sentiment Analysis for News and Blogs (with N. Godbole and M. Srinivasaiah). Int. Conf. on Weblogs and Social Media (ICWSM 2007), Denver CO, March 26-28, 2007. Also see our system demonstration description.
- Concordance-Based Entity-Oriented Search (with M. Bautin) IEEE/ACM Web Intelligence (WI-07), Silicon Valley CA, November 2-5, 2007.
Monday, June 1, 2009
Query log search suggestions and News search suggestions
Sometime query log based search suggestions show problems. Sergio Marchionne is the CEO of Fiat Spa, he was discussing with Angela Merkel about buying Opel, the General Motors german assets.
Saturday, May 30, 2009
Fresh answers and old ones
Sometime the answer to a question is changing according to time. In this case, Cerberus bougth Crysler for 7.4 Billions in 2007. Anyway, the company is currently evaluating a Chapter 11 and it sold a large part of his assets to Fiat, an Italian company.
Business is a circle. Fiat was in deep deep troubles 5 years ago. Then, everything changed when Sergio Marchione, the new manager accepted to run the company as CEO.
Ask is nailing the fresh answer, Google and Live give the old one, Yahoo is not nailing the story.
Business is a circle. Fiat was in deep deep troubles 5 years ago. Then, everything changed when Sergio Marchione, the new manager accepted to run the company as CEO.
Ask is nailing the fresh answer, Google and Live give the old one, Yahoo is not nailing the story.
Estimating the ImpressionRank of Web Pages
ImpressionRank is the number of times users viewed the page, while browsing search results returned by the search engine. In turn, ImpressionRank has an intuitive correlation with power law search query distribution.
Estimating the ImpressionRank of Web Pages proposes a number of methodologies for estimating ImpressionRank. It is based on sampling of search suggestion services provided by search engines and on extraction of popular keywords extracted by web pages. The paper achieves quite interesting results in terms of recall and convergence speed.
I am pretty sure that the work is quite interesting for all the SEO companies.
Estimating the ImpressionRank of Web Pages proposes a number of methodologies for estimating ImpressionRank. It is based on sampling of search suggestion services provided by search engines and on extraction of popular keywords extracted by web pages. The paper achieves quite interesting results in terms of recall and convergence speed.
I am pretty sure that the work is quite interesting for all the SEO companies.
Friday, May 29, 2009
Search is alive and kicking
In the last couple of months we have seen many completely new initiatives.
Are we now out of the crisis? I say, YES we are!
Are we now out of the crisis? I say, YES we are!
- Microsoft Bing, a serious new competitor in the arena. In my opinion Bing is moving in a direction of more focused search. There are some ideas inspired by Vivisimo, Seachme , and my old Snaket for the categories. Some other ideas taken from the Ask3D interface. A much better ranking, and more important a new way of accessing and organizing search results. It seems that Microsoft wants to invest more money in search and is a very good news for the whole sector. I will follow their performance in the next months.
- Wolfram Alpha, is something very different and also very difficult to evaluate. They aims at having all systematic knowledge immediately computable by anyone. A very ambitious goal. For this reason they have my full respect. They provide amazing results for some queries and very poor results for other queries. Precision is very high, recall is low. I will observe their performance more and more in the next months.
- Many proposals for RealTime Search with players such as Twitter Search, OneRiot, FriendFeed, and the many others. This is where freshness is important.
Thursday, May 28, 2009
Wednesday, May 27, 2009
Real Time Semantic Correlations
Algorithm is the key. Always. Here I am talking about fresh correlations among automatically extracted fresh semantic entities. This is a funny story, but I just wanted to explain a technology we had since many years.
Noemi Letizia is the new supposed italian Monica Lewinsky. Someone is saying that she has an affair with Silvio Berlusconi, this is not proved. But there are rumors. Veronica Lario is Berlusconi's wife. She asked for a divorce due to this story. Gino Flaminio is the ex-boyfriend of Noemi Letizia. He had an important interview with the main italian newspaper. I guess you know why Clinton is there.
Algorithm nailed the true essence of the story
Noemi Letizia is the new supposed italian Monica Lewinsky. Someone is saying that she has an affair with Silvio Berlusconi, this is not proved. But there are rumors. Veronica Lario is Berlusconi's wife. She asked for a divorce due to this story. Gino Flaminio is the ex-boyfriend of Noemi Letizia. He had an important interview with the main italian newspaper. I guess you know why Clinton is there.
Algorithm nailed the true essence of the story
Tuesday, May 26, 2009
Real time Semantic Search
Well everyone is talking about Semantic Search ( have you seen Wolfram Alpha ?). You know, I live in this place so far away from all the rest ;-) But here in this little and wasted land we keep asking a question ;-) !!
Now do you know the answer? Did you ever hear about it?
I think that Semantic Search needs Freshness and realtime data as well
Now do you know the answer? Did you ever hear about it?
I think that Semantic Search needs Freshness and realtime data as well
Monday, May 25, 2009
Sunday, May 24, 2009
Google vs. the Real-Time Web
Google vs. the Real-Time Web is a nice article by the way of Gigaom.
- "By contrast, real-time discovery engines like Twitter and Facebok use a more dynamic kind of democracy, linking to content that users finds worthwhile. As a result, content on the web is splitting into two basic models, and understanding this distinction makes clear why Google’s centralized role is being threatened"
- "There is no time available to develop meta data that separates the wheat from the chaff, or in recent terms, the stupid bacon jokes from real news about Swine Flu"
- "It has to have a past to give people’s reactions time to develop. But yes, right now if you say realtime, you certainly can get funded. In the Valley, at least."
- I partially agree with Adam. We already saw some working Real time web search. Namely News blending into Web search. Now, Real time is not just news blending. It’s much more, but the news blending experience may be leveraged there.
Using Graphics Processors for High Performance IR Query Processing
Using Graphics Processors for High Performance IR Query Processing is a paper exploring the use of CUDA GPU as co-processor for serving search queries. The idea is quite intriguiging since GPUs may potentially offer amazing performances at very low cost.
The authors propose a parallel sum prefix based Rice encoding and a PForDelta encoding.
Rice coding encodes an integer (the gap between two consecutive docIDs) by choosing a number of bits b such that 2^b is close to the average of all the gaps, and then representing each integer
as q · 2^b + r for some r < 2b. Then the integer is encoded in a unary part, consisting of q 1s followed by a 0, and a binary part of b bits representing r. PForDelta first selects a value b such that most gaps are less than 2^b, and then uses an array of b-bit values to store all gaps less then 2^b while all other gaps are stored in a special format as exceptions.
The paper describes gap encoding, decoding, and merge operations. In addition, it discusses how to process ranked query, skip lists, dijunctive and conjiuntive queries.
Performances are good, a single server with a GPU and a CPU we can sustain a query arrival rate beyond 300 q/s, versus less than 100 for CPU only. The index size was ~25M documents.
Quite an interesting paper, indeed.
The authors propose a parallel sum prefix based Rice encoding and a PForDelta encoding.
Rice coding encodes an integer (the gap between two consecutive docIDs) by choosing a number of bits b such that 2^b is close to the average of all the gaps, and then representing each integer
as q · 2^b + r for some r < 2b. Then the integer is encoded in a unary part, consisting of q 1s followed by a 0, and a binary part of b bits representing r. PForDelta first selects a value b such that most gaps are less than 2^b, and then uses an array of b-bit values to store all gaps less then 2^b while all other gaps are stored in a special format as exceptions.
The paper describes gap encoding, decoding, and merge operations. In addition, it discusses how to process ranked query, skip lists, dijunctive and conjiuntive queries.
Performances are good, a single server with a GPU and a CPU we can sustain a query arrival rate beyond 300 q/s, versus less than 100 for CPU only. The index size was ~25M documents.
Quite an interesting paper, indeed.
Saturday, May 23, 2009
Learning to Tag
Learning to Tag is a Microsoft paper about suggesting tags associated to Flicker images. The authors use traditional textual co-occurences and visual features (such as colour histogram, and moment). These features are combined by using a RankBoost learning process.
The results are compared with a naive linear combination of ranking signals, and with simple tag co-occurences. It seems that Microsoft likes to combine different ranking signals with RankBoost, since I saw many papers describing variations of this idea and the performance they achieve seems quite good.
The results are compared with a naive linear combination of ranking signals, and with simple tag co-occurences. It seems that Microsoft likes to combine different ranking signals with RankBoost, since I saw many papers describing variations of this idea and the performance they achieve seems quite good.
Friday, May 22, 2009
American Idol: Freshness, Variety and UI
Who is the winner of american idol? Let's see what is the performance of various search engines. I cannot vote since I am involved in the contest. Anyway, these are the criteria:
1) Freshness, how fast do they broke the news
2) Accurateness, how much accurate are the results
3) Variety, do they provide a sense of variety in them (not just 10 blue links?)
4) UI, is the user experience good?
What is your opinion?
Ask.com has the winner on the top with News, Video and Audio
Google has the official site, wikipedia, and youtube videos
Yahoo has the news with images
Live has the news with images
Searchme has the best UI all around (IMO)
Twitter has all the rumors, and they broke the story
Hmm ... actually OneRiot broke the story !!
1) Freshness, how fast do they broke the news
2) Accurateness, how much accurate are the results
3) Variety, do they provide a sense of variety in them (not just 10 blue links?)
4) UI, is the user experience good?
What is your opinion?
Ask.com has the winner on the top with News, Video and Audio
Google has the official site, wikipedia, and youtube videos
Yahoo has the news with images
Live has the news with images
Searchme has the best UI all around (IMO)
Twitter has all the rumors, and they broke the story
Hmm ... actually OneRiot broke the story !!
Mapping the World's Photos
Mapping the World's Photos is a fascinating paper from Jon Kleimberg et al. They used textual features and SIFT image signatures to geo-localize a large sample of Flicker images. It seems that the two different class of features show a mutual benefit.
It's fascinating to discover what are the most photographed world landmarks.. Applestore in 5th avenue, NYC is the 5th most photograped place in the world, while Rome's colosseum is just 41th...
It's fascinating to discover what are the most photographed world landmarks.. Applestore in 5th avenue, NYC is the 5th most photograped place in the world, while Rome's colosseum is just 41th...
Thursday, May 21, 2009
Mining Interesting Locations and Travel Sequences From GPS Trajectories
Mining Interesting Locations and Travel Sequences From GPS Trajectories . Hmm ... when I read this paper from Microsoft, I though "...we will follow you ". The key idea is to rank users and places using a HITS-based approach since there is an evident mutual reinforcement propriety among them. 107 people were tracked for one year.
Wednesday, May 20, 2009
Network Analysis of Collaboration Structure in Wikipedia
Network Analysis of Collaboration Structure in Wikipedia is a study about topic polarization and edit activities on Wikipedia. It seems that there are topics where people starts neverending revert wars. I wonder why the authors are not talking about spam and bots here....
Tuesday, May 19, 2009
Understanding User's Query Intent with Wikipedia
"Understanding User's Query Intent with Wikipedia" is a nice paper from Microsoft. It explains how to classify Web queries in order to trigger results from different verticals (such as news, images, video, travel, shopping).
Each category is bootstrapped with few keywords chosen by editors. These descriptions are then automatically expanded using a random walk on wikipedia's categories and concepts. The semantic concepts are then extracted by using Gabrilovich's esa. Results are provided on Live search query log for July 2007 (which has just ~2.6M frequent queries). Precision, Recall and F1 measures are quite impressive and this generic solution can compete with the best ad-hoc KDD2005 classification competition result.
Query classification is a very important topic for Search Engines, and leveraging Wikipedia is definitevely a good idea. (see also my previous posting for Yahoo's query classification)
Each category is bootstrapped with few keywords chosen by editors. These descriptions are then automatically expanded using a random walk on wikipedia's categories and concepts. The semantic concepts are then extracted by using Gabrilovich's esa. Results are provided on Live search query log for July 2007 (which has just ~2.6M frequent queries). Precision, Recall and F1 measures are quite impressive and this generic solution can compete with the best ad-hoc KDD2005 classification competition result.
Query classification is a very important topic for Search Engines, and leveraging Wikipedia is definitevely a good idea. (see also my previous posting for Yahoo's query classification)
Multidimension Scaling
Multidimension Scaling is a technique for projecting multi-dimensional points in a 2-d plan, so that the distances as preserved as much as possible.
Here you have a C++ code skeleton with STL and boost.
Here you have a C++ code skeleton with STL and boost.
Monday, May 18, 2009
Range minimum queries and LCA
Range Minimum Query (RMQ) is used on arrays to find the position of an element with the minimum value between two specified indices. There is a trivial quadratic solution based on dynamic programming. I found this tutorial complete and useful. Many other solutions exist. In particular, I appreciated the one based on Segment Trees. A bookmark, and I plan to revisit it soon.
Sunday, May 17, 2009
Unsupervised Query Categorization using Automatically-Built Concept Graphs
Unsupervised Query Categorization using Automatically-Built Concept Graphs is a paper from Yahoo! for automatic query classification without any training phase. The key idea is to build a network of cross-referencing terms extracted from a search engine's snippets. Categories are then hooked in this graph, by using few seed terms. The categorization algorithm is a variation of a truncated random walk. The results are compared with a basic SVM classifier and with KDD2005. Yahoo! UK is using this system in production.
Saturday, May 16, 2009
Level statistics of words: Finding keywords in literary texts and symbolic sequences
Francesco pointed out this paper "Level statistics of words: Finding keywords in literary texts and symbolic sequences" where they extract relevant word from a single text document by leveraging word positions and frequency, without the need of a training corpus. This are the kind of papers I like since they create a bridge between different research fields.
Friday, May 15, 2009
45 watches and a table
There are 45 watches randomly ordered on a table. Prove that the sum of the distances among the center of the table and the ends of the minutes hands can be greater than the sum of the distances among the center of the table and the centers of the watches.
Thursday, May 14, 2009
The new frontier: Real-Time Search-Off
A wonderfult article from TechCrunch about Real Time Web search. The new frontier.
Wednesday, May 13, 2009
Y/N questions and T/F Men
Another variant, this time a bit harder. Men can say the Truth or the False, to any type of Yes or No question. They decide artbitrarly. Identify the type of man with just one question.
Tuesday, May 12, 2009
A bag of white and black balls
You have a bag with n balls, with colours either white or black. What is the probability to extract a sequence of two white balls.
Monday, May 11, 2009
Y/N questions and T/F Men
In a country there are men who always says the truth (T), men we always lie (F) and men who will alternatively lie or say the truth (ToF). Men can only answer Yes or No, if this kind of answer make sense. With only one question can you determine the type of man you are facing?
Sunday, May 10, 2009
Cut a 3D cube in slices
You have a 3x3x3 3D cube, like the rubik cube. Cut it into 27 pieces with the minum number of cuts.
Saturday, May 9, 2009
5 weights, how to identify them
You have 5 different weights of 1, 2, 3, 4, 5 grams. They are indentical when you observe them. Can you state how many different weighting you need by using a balance which can compare two weights.
Friday, May 8, 2009
Logic puzzle: the yes/no world
There is world where the people answers just "Yes" or "No". People are divided in two groups: the ones who always says the truth and the ones who always says the false. Can you formulate a question which cannot be answered by any of the two groups but is a yes/no question?
Thursday, May 7, 2009
Train to heaven or hell
You can go to heaven or to hell. Trains arrive with the same interval, namely 10 minutes. Heaven is on the south platform, hell is on the north platform. You take the first one which will arrive. How it comes that you have 9/10 probabilities to go to the hell?
Wednesday, May 6, 2009
Alice, Bob and the extraction of 3 numbers
Alice and Bob extract 3 numbers between 1..9 with no replacement. Can you suggest a winning strategy to Alice? The goal is to extract 3 numbers whose sum is 15.
Tuesday, May 5, 2009
Online Expansion of Rare Queries for Sponsored Search
Online Expansion of Rare Queries for Sponsored Search is a Yahoo paper which discusses how to expand rare queries for serving matching ads. The emphasis is on efficience. The key intuition is to find related "sentences" by hitting the search engine for the rare queries. The related sentences are extracted from search results snippets. High efficience is achieved by using an offline pre-processing step which aims at creating an offline index of related sentences.
The improvement in precision-recall is relevant, but i wonder why the authors are using human evaluators instead of a direct evaluation based on ads click rate for the expanded query set.
Another relevant result is distribution of rare queries
I wonder where the fresh queries are located here. I assume that "swine flu" was not so popular on the web until few months ago. Examples like "swine flu" are more common than one can imagine at first glance.
The improvement in precision-recall is relevant, but i wonder why the authors are using human evaluators instead of a direct evaluation based on ads click rate for the expanded query set.
Another relevant result is distribution of rare queries
I wonder where the fresh queries are located here. I assume that "swine flu" was not so popular on the web until few months ago. Examples like "swine flu" are more common than one can imagine at first glance.
Monday, May 4, 2009
Tag Ranking
Tag Ranking is a paper from Microsoft which discusses how to rank the flat collections of tags associated to Flicker images. The key idea is to weight tags according to (a) their probabilistic relevance (a slightly sophisticated variation of well-known TF*IDF, where the probability density function is estimated with a KDE approach) and to (b) a random walk on a tag similarity graph.
The results obtained on a limited testbed are encorauging, but I want to see how this scales on a large database of tagged images. In addition, I would have leveraged the taggers and not just the tags... Maybe an idea for a future work paper.
The results obtained on a limited testbed are encorauging, but I want to see how this scales on a large database of tagged images. In addition, I would have leveraged the taggers and not just the tags... Maybe an idea for a future work paper.
Sunday, May 3, 2009
A Search-based Method for Forecasting Ad Impression in Contextual Advertising
A Search-based Method for Forecasting Ad Impression in Contextual Advertising is a paper from Yahoo to forecast ads monetization based on previous exposition of the similar ads. The estimation is precise when there is a large amout of previous data available.
This is a seminal paper, but there is a lot of room for improvement. I assume that there are three types of ads:
This is a seminal paper, but there is a lot of room for improvement. I assume that there are three types of ads:
- Those always shown such as "real estate"
- Those with periodic peak and a slow growth like "u2 concert"
- Those with instananeous and fast growth like "swine flu vaccine"
Saturday, May 2, 2009
Quicklink Selection for Navigational Query Results
Quicklink Selection for Navigational Query Results is a Yahoo paper about selecting QuickLinks by using toolbar click data. An interesting application of traffic rank, indeed.
Anyway, I wonder wether one can improve a lot the performance by taking into account some linguistic analysis on the suggested tags and titles.
Anyway, I wonder wether one can improve a lot the performance by taking into account some linguistic analysis on the suggested tags and titles.
Friday, May 1, 2009
An axiomatic approach for result diversification
Search engines have different goals, when they return 10 blue links. One goal is relevance. Another one is variety. Yet another one is freshness. The list if very long.
An axiomatic approach for result diversification is a Microsoft paper providing an axiomatic framework for addressing both relevance and variety. Very interesting paper, indeed.
An axiomatic approach for result diversification is a Microsoft paper providing an axiomatic framework for addressing both relevance and variety. Very interesting paper, indeed.
Thursday, April 30, 2009
A ten digit number
Write a ten digits number, such that position i indicates the number of i units in the number (e.g. position 3 indicates the number of 3 in the number, and so on).
Wednesday, April 29, 2009
Two missiles
Two missiles are directed one against the other. The first one has a speed of 9,000 Km/h. The secon one has a speed of 21,000 Km/h. They start 1234 Km apart. What is their distance one minute before they collide?
Tuesday, April 28, 2009
Fastest runner is not the winner
In a 100 meters race, the fastest runner is not the winner. His run is a valid one. How is this possible?
Monday, April 27, 2009
Fast Dynamic Reranking in Large Graphs
Fast Dynamic Reranking in Large Graphs is a google paper for learning a ranking function of a graph based on positive and negative votes given to a subset of nodes. A node is ranked high if in
a truncate random walk starting from it the probability of hitting a relevant node before an irrelevant one is large. Here below an example.
.
a truncate random walk starting from it the probability of hitting a relevant node before an irrelevant one is large. Here below an example.
.
Sunday, April 26, 2009
Efficient Overlap and Content Reuse Detection in Blogs and Online News Articles
Efficient Overlap and Content Reuse Detection in Blogs and Online News Articles describes a word based signature duplicate detection for news and blogs. good paper, but lacks of comparison with previous state-of-the-art.
Saturday, April 25, 2009
FPGA Acceleration of RankBoost in Web Search Engines
FPGA Acceleration of RankBoost in Web Search Engines is a Microsoft paper about accellerating RankBoost learning algorithm. RankBoost is a variant of AdaBoost, where the weak learners are based on features extracted from the web documents. Microsoft claims of using more that 646 features. Each feature acts as a binary selector and gives a positive vote, if its value is above a threshold. Two techiques are used for speeding up the learning computation:
- a binning and histogram based approximation, for the sequential version of the algorithm.
- a FGPA-based implementation, for the parallel version of the algorithm.
Friday, April 24, 2009
Thursday, April 23, 2009
Find a perfect square, cube and fifth power
Find a number that is a perfect square, cube and fifth power and is less than 2*10^14
Wednesday, April 22, 2009
100 random digits
100 digits are chosen at random. What is the probability to find two numbers, a and b, such that a^2=b and each digit is used just one time in forming the two numbers?
Tuesday, April 21, 2009
Two search engines recently launched ( I like them )
SearchMe just expanded its index to anything related to entertainment/media, song, artists, news, video, images, web, whatever. I like the quality offered by the search ranking, the freshness, and the variety or results. The interface is very innovative. My suggestion is to experiment a little more by adopting the different layouts seen in FoxTab.
DuckDuckGo is a simple combination of Yahoo's Boss and Wikipedia. Anyway, I like the clean interface and the concepts extracted from Wikipedia.
DuckDuckGo is a simple combination of Yahoo's Boss and Wikipedia. Anyway, I like the clean interface and the concepts extracted from Wikipedia.
Friday, April 17, 2009
A great review on our freshness job
Off-topic, but just want to say thank you to anyone who worked hard on it. These are nice words.
http://www.seobythesea.com/?p=1333
For example, a search for Bruce Springsteen is presently showing a rich mix of images, scheduled events, web pages, and news results for the performer, and if you hover your mouse over the image next to the news results for Bruce Springsteen at Ask.com, the news video starts playing.
http://www.seobythesea.com/?p=1333
For example, a search for Bruce Springsteen is presently showing a rich mix of images, scheduled events, web pages, and news results for the performer, and if you hover your mouse over the image next to the news results for Bruce Springsteen at Ask.com, the news video starts playing.
They sound interesting to me, too. I do like their focus on providing timely information.
I looked at search results for “Bruce Springsteen” in Google, Yahoo, and Ask, to see how current the information was from each. All three had fairly up-to-date news information. Ask actually had a richer results than the other two in terms of the images that they displayed, and their listing of future “events” or concerts for Springsteen.
Wednesday, April 15, 2009
Bayesan Classifiers
Bayesan Classifiers are one of the most powerful data mining tool. I use them everyday with very good results. I found out that having an accurate and rich training dataset is much more important than having a ultra-sophisticate classifier (such as SVM). Bayesan classifiers have a very simple math, are easy to implement, and provide very good results in almost all the situations.
Here you have a Naive implementation of Naive Bayesan Classifier.
Here you have a Naive implementation of Naive Bayesan Classifier.
Friday, April 10, 2009
Wednesday, April 8, 2009
Two dice
Can you design two dice so that their sum behave just like a pair of ordinary dice?
E.g. 2 ways of getting 3 (2+1, 1+2). 1 way of getting 12 (6+6), etc
PS: this puzzle is quite interesting. You need a way to encode dice. It turns out this can leverage the representation of polynomial
E.g. 2 ways of getting 3 (2+1, 1+2). 1 way of getting 12 (6+6), etc
PS: this puzzle is quite interesting. You need a way to encode dice. It turns out this can leverage the representation of polynomial
Tuesday, April 7, 2009
Dropping K Swarovsky balls
Someone asked for a variant of the Dropping Swarovski Crystals problem where you have m balls available and n floors. In this case, what is the number of drops needed?
Let's see: we can formulate the problem with 2 balls as a recursion problem. Let f(k) the maximum number of floors we can test with k drops and using 2 balls. If a ball breaks at a floor k, we need to start from the very ground up to the k floor and test all the k floors. If the ball is not breaking we need to test f(k-1). Therefore, the recursion is f(k) = f(k-1) + k. In other words f(k) = sum_i=1,..k i = k (k+1) / 2. We need to find the minimum k such that k(k+1)/2 > 100. This can be solved by direct test and we find that 14 (15/2) = 105. The number of test we obtain is 14. If we want to know what are the floor to test we can "unroll" the recursion and find the actual floors.
Now suppose you have 3 balls, can you see the problem as a recursion one? And what about m balls?
Let's see: we can formulate the problem with 2 balls as a recursion problem. Let f(k) the maximum number of floors we can test with k drops and using 2 balls. If a ball breaks at a floor k, we need to start from the very ground up to the k floor and test all the k floors. If the ball is not breaking we need to test f(k-1). Therefore, the recursion is f(k) = f(k-1) + k. In other words f(k) = sum_i=1,..k i = k (k+1) / 2. We need to find the minimum k such that k(k+1)/2 > 100. This can be solved by direct test and we find that 14 (15/2) = 105. The number of test we obtain is 14. If we want to know what are the floor to test we can "unroll" the recursion and find the actual floors.
Now suppose you have 3 balls, can you see the problem as a recursion one? And what about m balls?
Monday, April 6, 2009
Sorted Matrix for rows and columns
Given a random matrix, prove that if you sort by rows and then by columns the matrix is still sorted by rows
Sunday, April 5, 2009
15 bags
You have 15 bags. How many crystal balls do you need to have a different number of balls in each bag?
PS: try to solve with less than 30 balls
PS: try to solve with less than 30 balls
Saturday, April 4, 2009
Linear Solvers (Successive Over Relaxation)
Successive over-relaxation (SOR) is a linear solver which speed up convergence of the Gauss–Seidel method. Implementation of the method is quite easy and convergence is fast.
SOR has been frequently used for computing PageRank (see Adaptive Methods for the Computation of PageRank , A Survey on PageRank Computing , Comparison of Krylov subspace methods on the PageRank problem ).
Here you have the code for SOR solver in C++
PS: if you are interested in Linear Solvers with C++, I suggest using Dolfin, which provides high-performance linear algebra through uBLAS, PETSc, Trilinos and MTL4 (experimental) with simple C++ and Python wrappers.
SOR has been frequently used for computing PageRank (see Adaptive Methods for the Computation of PageRank , A Survey on PageRank Computing , Comparison of Krylov subspace methods on the PageRank problem ).
Here you have the code for SOR solver in C++
PS: if you are interested in Linear Solvers with C++, I suggest using Dolfin, which provides high-performance linear algebra through uBLAS, PETSc, Trilinos and MTL4 (experimental) with simple C++ and Python wrappers.
Friday, April 3, 2009
Decision Tree (part II)
Added the classification code to the Decision Tree implementation. Classification is a visit of the tree. If the new observation matches the value contained in the internal node, then the true branch if followed. Otherwise, the false branch is followed. Nothing can simpler than this.
Please note that a complete Decision Tree implementation should also incorporate some pruning strategy, but I will leave this to the interested reader ;-)
Please note that a complete Decision Tree implementation should also incorporate some pruning strategy, but I will leave this to the interested reader ;-)
Thursday, April 2, 2009
Splay Trees in C++
I was looking for a generic implementation of Splay Tree in C++. Splay Tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. This is useful for competitive analysis and online algorithms. Splay Trees operations such as insertion, look-up and removal are performed in O(log(n)) amortized time.
I found no generic implementation, but the original C implementation of Daniel Sleator and Robert Tarjan. Therefore, I decided to transform this implementation into generic C++ with templates.
Here you have the C++ code for Splay Trees (adapted by the original C version)
I found no generic implementation, but the original C implementation of Daniel Sleator and Robert Tarjan. Therefore, I decided to transform this implementation into generic C++ with templates.
Here you have the C++ code for Splay Trees (adapted by the original C version)
CGAL : Computational Geometry Algorithms Library in C++
I was looking for a library implementing Range Trees and Interval Trees, two less known but very useful data structures for retrieving overlapping segments and points. Those data structures are used in databases and in many other contexts.
Well, what I found is a larger golden mine. The Computational Geometry Algorithms Library (CGAL) is a software library that aims to provide easy access to efficient and reliable algorithms in computational geometry. While primarily written in C++, Python bindings are also available.
The table of content shows an impressive amount of already cooked algorithms and data structures, ranging from basic 2D and 3D Geometry Kernel, to Convex Hulls and Delaunay Triangulations, to Voronoi Diagrams.
I found the Search Structures part quite interesting with implementations of 2D Range and Neighbor Search , Interval Skip List, Spatial Searching ( Neighbor Searching , Range Searching , - tree ), Range and Segment Trees, Intersecting Sequences of dD Boxes.
The library has additional tools for Linear and Quadratic Programming Solver and Spatial Sorting and support for third party software such as the GUI libraries Qt, Geomview, and the Boost Graph Library. (Gosh all these are together?)
A huge amount of software all using Template C++ with an approach similar to Boost.
I take what I need for my coding task, but this is bookmarked and I will discuss about it more intensively in the future.
Well, what I found is a larger golden mine. The Computational Geometry Algorithms Library (CGAL) is a software library that aims to provide easy access to efficient and reliable algorithms in computational geometry. While primarily written in C++, Python bindings are also available.
The table of content shows an impressive amount of already cooked algorithms and data structures, ranging from basic 2D and 3D Geometry Kernel, to Convex Hulls and Delaunay Triangulations, to Voronoi Diagrams.
I found the Search Structures part quite interesting with implementations of 2D Range and Neighbor Search , Interval Skip List, Spatial Searching ( Neighbor Searching , Range Searching , - tree ), Range and Segment Trees, Intersecting Sequences of dD Boxes.
The library has additional tools for Linear and Quadratic Programming Solver and Spatial Sorting and support for third party software such as the GUI libraries Qt, Geomview, and the Boost Graph Library. (Gosh all these are together?)
A huge amount of software all using Template C++ with an approach similar to Boost.
I take what I need for my coding task, but this is bookmarked and I will discuss about it more intensively in the future.
Wednesday, April 1, 2009
Fuzzy Clustering
Fuzzy clustering is an interesting data mining process where every item belongs to multiple clusters with different membership values in [0, 1]. As a consequence clusters are not crips but fuzzy (guess what? this is a typical situation in fuzzy logic). Fuzzy c-means clustering is the most famous fuzzy clustering algorithm and can be seen as a variant of the well-known k-means.
Here you have the C++ for Fuzzy Clustering (it uses Boost::uBlas for matrix operations)
Here you have the C++ for Fuzzy Clustering (it uses Boost::uBlas for matrix operations)
Subscribe to:
Posts (Atom)