Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Friday, December 31, 2010
Divide in two equal parts
Thursday, December 30, 2010
Longest increasing sub-sequence
Wednesday, December 29, 2010
Subsequences
Tuesday, December 28, 2010
DP bracket problem
Monday, December 27, 2010
Count the number of inversions in an array
Sunday, December 26, 2010
Reverse a string with O(1) additional space
Saturday, December 25, 2010
Friday, December 24, 2010
Nesting envelopes
strictly smaller than the dimensions of B. how many possible combination you can have?
Thursday, December 23, 2010
Modify a stack to implement min/max in O(1)
Wednesday, December 22, 2010
Maximize the number of items you collect
What is the complexity and the space needed?
Tuesday, December 21, 2010
Launched News in UK, and FR
Another year, another news product. Optimized local rankers, classifiers and clustering. Oh yes, clustering my dear.
Monday, December 20, 2010
Are you the average of your friend actions?
Sunday, December 19, 2010
Related Searches shipped in 8 countries
What an amazing ride. We shipped 8 countries in less than one year with localized filtering, aggregation, and ranking. Italy is part of the list (yeah!!!)
More pictures here
Saturday, December 18, 2010
Maximize and expression with no parenthesis
Friday, December 17, 2010
Autosuggest shipped in 5 countries
What an amazing ride. We shipped 5 countries in less than one year with localized filtering, aggregation, and ranking.
More pictures here
Thursday, December 16, 2010
Encode and Decode a document
Write the code to serialize and de-serialize a collection of 'Documents'
Wednesday, December 15, 2010
Hive, SQL like, Facebook and the map join optimization
This is the optimization: "Hive-1641 solves this scaling problem. The basic idea of optimization is to create a new MapReduce local task just before the original join MapReduce task. This new task reads the small table data from HDFS to an in-memory hash table. After reading, it serializes the in-memory hash table into a hashtable file. In the next stage, when the MapReduce task is launching, it uploads this hashtable file to the Hadoop distributed cache, which populates these files to each mapper's local disk. So all the mappers can load this persistent hashtable file back into memory and do the join work as before."
So they are doing some pre-computation before the join operation itself for computing an hash table which is then pre-loaded in the memory of the local mapper. The performance gains are amazing since optimized map join is 12 to 26 times faster than the previous one.
I wonder how a fast compression scheme could help here. Paolo?
Tuesday, December 14, 2010
K-th sum for two sorted arrays
Hint: i like this problem, a possible solution is by induction and the complexity is O(n+m).
Monday, December 13, 2010
Interesting google talk
Sunday, December 12, 2010
Out of band: Red power led on dg834g
It turns out that the problem was with power supply unit. I just replaced it with an equivalent one.
Saturday, December 11, 2010
Out of band: vnc connection to server behind a dg834g nat
The solution was to use dynamic dns (supported natively by the router), and ultravnc with security encryption. The dynamic ip allows to have a unique name, regardless of the dynamic ip assigned to the router. Then, I needed a way to reach the vnc severs. My solution was to a assign static ip to each server in my lan (instead of relaying on dhcp), and to have different range of vnc ports for each server (from server property page). Finally, i setup a static port forwarding set of rules for those ports (for each service configure a "service" in router's content filtering, and then open the "service" in the router's firewall and send to a specific lan server).
And voila, now my servers are accessible with 2048-bit RSA keys and 256-bit AES keys security encryption.
Friday, December 10, 2010
Out of band: vpn with a dg834g router
Facebook data store
Thursday, December 9, 2010
Google's Dremel
Greg pointed out this interesting G paper "Dremel: Interactive Analysis of Web-Scale Datasets" (PDF)"
"By combining multi-level execution trees and columnar data layout, it is capable of running aggregation queries over trillion-row tables in seconds. The system scales to thousands of CPUs and petabytes of data, and has thousands of users at Google. In this paper, we describe the architecture and implementation of Dremel, and explain how it complements MapReduce-based computing."
The key idea is very simple, but the implementation is complex: "our goal is to store all values of a given field consecutively to improve retrieval efficiency". This is the so called columnar vs. record-oriented storage.
Then, SQL relational operations are implemented by using the following intuition: "Think of a nested record as a labeled tree, where each label corresponds to a field name. The selection operator prunes away the branches of the tree that do not satisfy the specified conditions." .. "Dremel uses a multi-level serving tree to execute queries (see Figure 7). A root server receives incoming queries, reads metadata from the tables, and routes the queries to
the next level in the serving tree."
Dremel scans quadrillions of records per month.
Wednesday, December 8, 2010
Segments with points
Tuesday, December 7, 2010
RTTI
Monday, December 6, 2010
Subarray sorted
Sunday, December 5, 2010
Saturday, December 4, 2010
Facebook friend suggestions
Friday, December 3, 2010
Queries and time
. Define a data-structure for efficiently identify the top k most frequent queries in the time interval [t0, t0 + \tau]
Thursday, December 2, 2010
Celebrity twitters
Hint: how many information can you infer with one question?
Wednesday, December 1, 2010
Ants in a row
(thanks giuseppe, muthu)
Tuesday, November 30, 2010
A classical one: find the element which appears 5/8 of times
(this is a classical must solve// know problem)
Monday, November 29, 2010
Out of Band but interestingç "Microsoft Gives the Cloud to Scientists"
http://bits.blogs.nytimes.com/2010/11/17/microsoft-gives-the-cloud-to-scientists/?src=tptw
"Microsoft has hit on a direct path to university researchers’ hearts and minds: give them free tools and easy access to huge data sets.
The software maker has started grafting popular scientific databases and analysis tools onto its Windows Azure cloud computing service. This basically means that researchers in various fields can get access to a fast supercomputer of their very own and pose queries to enormous data sets that Microsoft keeps up to date. For the time being, Microsoft will allow some research groups to perform their work free, while others will have to rent calculation time on Azure via a credit card."
Disclaimer: I work for Microsoft
Sunday, November 28, 2010
A classical one: a triangle and a point
PS: sometime you forgot old geometry, but this problem is simply a generalization of a point P and a segment S. Is the point above or below S?
Thursday, November 25, 2010
Friendship and Polymorphism
Wednesday, November 24, 2010
Monday, November 22, 2010
Exchange coins
Sunday, November 21, 2010
Serialization and deserialization
Saturday, November 20, 2010
Can you implement a queue using a stack?
Friday, November 19, 2010
Everyone is allied to someone
Thursday, November 18, 2010
Wednesday, November 17, 2010
Arrays comparison. don't always sort them.
Tuesday, November 16, 2010
Facebook is opening read-only the Message service
Interestingly enough, Message works on the top of HBase
Monday, November 15, 2010
Looking for a new ads major paradigm shift (part I, where we are)
We have hundreds of millions of users producing zillions of web pages, blogs, real time updates, and so on and so forth. Then, search engines index this content and serve search results, when users submit relevant queries. In addition, search engines serve commercial ads together with the indexed content. Now, why the content producers receive no money for their content? After all, if there no content then there will be no index, no search results and no commercial ads.
You may say ... well your analysis is partial since commercial ads are not the only way to monetize the content. Another element to consider is the traffic sent to the content producer by the search. Fair enough. This observation is certainly pertinent. However, receiving traffic is very much important for commercial sites, but is not necessarily the same of getting direct money.
For instance, say that I love the music of the 80s. This is my hobby, and so I write about it. I would be interested in receiving some traffic for content produced for this hobby. Anyway, I would be more happy to get some direct money anytime that my content is accessed by using a search engine. After all, the search engine has probably served some commercial ads together with the index built on the top of my content (and on the top of the content written by other similar content producers).
Nowadays, A similar mechanism is missing .. and I am not sure why? Would you consider it a new ads major paradigm shift? And could it be a pair with a new search major paradigm ?
Sunday, November 14, 2010
Another good summary about Google infrastructure
Saturday, November 13, 2010
Print all the strings made up of balanced parethesis and with lenght n
Is Facebook starting to become a true search engine?
Friday, November 12, 2010
Personalized Facebook Autosuggest. I like it.
Update: they also have Web pages where users expressed a "Like it". So they are effectively crawling them (or at least leveraging the "Like" anchor). Is Facebook starting to become a true search engine?
Thursday, November 11, 2010
Bing, if you want to play a role in algorithmic search
There are just two players with algoritmic search out of there. Search follows fractal geometries. You can take advantage of your experiences and, by learning and generalizing, you can anticipate and recognize problems with similarities :)
Wednesday, November 10, 2010
Stock had a 40% increase last year, IAC's Barry Diller Surrenders to Google, Ends Ask.com's Search Effort
Tuesday, November 9, 2010
Repeating numbers
Monday, November 8, 2010
Find the min difference among two numbers in an Array
Sunday, November 7, 2010
Store the file and save space
(PS: this was an old interview coding question, which I am not going to use anymore)
Saturday, November 6, 2010
Database of queries and similarity
Friday, November 5, 2010
sharing lists.
Thursday, November 4, 2010
Find two numbers in an unsorted array
Wednesday, November 3, 2010
Alice and Bob play with an array
Tuesday, November 2, 2010
News Personalization
I am really interested in your opinion
http://www.projectemporia.com/
Monday, November 1, 2010
Break through technology for next phone generation
Sunday, October 31, 2010
Looking for a new search major paradigm (part I, where we are)
First, what i called the run for the biggest index with relevant search results, with champions such as Fast, Google, Teoma. Crystal Clear Winner: Google
Second, what Google called Universal search and Ask.com called Ask3d and Bing called Decision engine. Search is no more just about ten web blue links, but is an integrated experience with blended multimedia, fresh news, social stuffs, and so on and so forth. Winner: Bing & Google; Special Mention: Ask.com and Yahoo. Surprisingly, enough Ask.com gave up on this field where they were truly innovators.
Third, the adoption of large scale machine learning methodologies for ranking based on query logs and other signals, with champions like Yahoo and large scale adopters such as Bing. Google claims that they are not adopting machine learning for learning to rank, but I frankly doubt it. Winner: Bing.
So you can ask why are you saying the those are minor changes in search? Well, the business is still the same: mapping keywords to urls. I don't see any major switch from that paradigm. Do you ?
Probably it's all a matter of defining what's a major switch. So, let's avoid theories and go on the practical side. Let's learn by examples and analogies. The adoption of mp3 format was a major switch for the music industry. GUIs such as X-Windows, Windows, and MacOS were a major switch for the interaction with computers. The adoption of the Apps model was a major switch for the phone industry. Investment funds were a major switch for the finance industry. Kinetics is a major switch for the game industry (still to be proven, but in my personal opinion it will be huge. Yes, I work for Microsoft but I would be impressed by this technology even if working for Google). Electrical cars will not be a major switch for the automobile industry (still to be proven, but in my personal opinion they will not be).
So, have you seen any major switch for the search industry in the past fifteen years? Surely, you have not.
You may argue: search is a mature business there is no need to innovate there and switch the paradigm. Hmm, I gently but firmly disagree with that point of view. Actually, my argument is the opposite: since search is a mature business there is now an immense need of innovation in the field. Again let's learn by the examples. Computation was a mature business (do you remember about Digital, IBM?) when the visual UI on PCs appeared. Music industry was one of the most established one, when mp3 came and changed that world. Mobile Phones business was a very consolidated one when the App model broke all the already written rules. Game business was all based on devices you can hold with your hands when kinetics came and said: why do you need to hold something just use your hands you have already them with yourself.
Also, if you study the past examples you will notice that it took at least fifteen years to innovate an already established business with new break through ideas. Beside, if you consider the acceleration we had in technologies you would probably agree with me that we are already accumulating a delay in addressing this immense need of innovation for search business.
My question to you: do you have ideas for innovating in the search business and moving away from the mapping keywords to urls paradigm? Be naive, be simple, be stupid, but be creative.
I have a couple of them and will post in the next days.
DISCLAIMER: Like everywhere else in this blog site, I am expressing my personal opinions, aspirations and ideas and not expressing any consideration related to my work with Microsoft.
Saturday, October 30, 2010
Sum of twos sorted arrays
Friday, October 29, 2010
Go and study: trie, patricia tree, succint tree and come back
Thursday, October 28, 2010
Compete's Top 50 Sites: Bing Grows 108%
My forecast? next year Facebook would be at 1st.
Wednesday, October 27, 2010
Tuesday, October 26, 2010
Write a C program to sort a stack in ascending order
Monday, October 25, 2010
Given a string S find all the distinct substrings
Sunday, October 24, 2010
Find substrings or words
Saturday, October 23, 2010
Center of a tree
Friday, October 22, 2010
Matrix again
Thursday, October 21, 2010
estimate the questions
Wednesday, October 20, 2010
Given a sorted array find two elements with sum = c
Tuesday, October 19, 2010
too many names in common
Monday, October 18, 2010
Search for space
Sunday, October 17, 2010
subarray sum k
Saturday, October 16, 2010
External memory : how to get the top elements in an array
Friday, October 15, 2010
Thursday, October 14, 2010
Google beats the expectation
Wednesday, October 13, 2010
Concepts in modern C++
Interesting article from DrDobs
enable_if is quite simple in and of itself -- if the first template parameter (which must be a boolean constant expression) evaluates to true then the nested "type" member is a typedef to the second template parameter. If the the first parameter evaluates to False then there is no nested "type" member.
The SFINAE rules mean that if enable_if
Tuesday, October 12, 2010
Another maximum length subsequence variant
Monday, October 11, 2010
Stock Markets: Human and Algorithms failures
On 2001, a trader of UBS Warburg meant to sell 16 shares of a company at 600,000 yen. Instead, he submitted an order for selling 610,000 shares at 6 causing a catastrophic failure with an estimated cost of 100 million of dollars. This is just the start, since things become more and more interesting when machine learning algorithms and artificial intelligence are used. ML and AI can turn a catastrophic failure into an epochal failure.
On 1987, October 17 a new algorithmic mechanism for automatic selling shares below a certain ground price has been put in production. October 17 was Monday and the new system introduced an un-expected latency which left some un-processed orders from the past week in the back-log queue. Guess what happened when all of them were processed all together? The price dropped instantaneously and the automatic mechanism for selling had an huge amplification effect. October 17, 1987 become a Black Monday with a 22% of loss in one single day, the worst day since 1929.
Today, we live in the Flash trade epoch. Humans are buying stocks aiming at keeping them for days, weeks, month or years. Flash trading algorithms have a different approach. The idea is to buy a stock and selling it after few micro-seconds. Talking about fast processing and investing on a long term basis. You don't care about what happens in two hours, you just try to predict what happens in a couple of micro-second away. Note that those algorithms can sometime see orders before they are processed, and this can probably make the prediction easier. Flash trading is taking about 25% of London Stock Exchange transactions.
A couple of weeks ago, US authorities published a report saying that on May 6 2010 the market suddenly dropped of 10% generating 1 trillion $ of loss (that is 1000 billions, wow!). Why? a single mistake! One order of selling 4.1 billion dollars linked to a future contract and submitted by a Kansans medium-size firm was accepted with no lower bound selling price limit, by mistake.
No one bought the contract and all the flash trading algorithms started to sell all the stocks all together in an amazing amplifying effect.
Did i say that I love Machine learning and Artificial intelligence?
Sunday, October 10, 2010
Saturday, October 9, 2010
Serialize a tree
Friday, October 8, 2010
Re-org: Live Labs absorbed in Bing
Thursday, October 7, 2010
Array sorted by frequency
Wednesday, October 6, 2010
Tuesday, October 5, 2010
Some days are containing months and months within. Thanks
Monday, October 4, 2010
Blood donors
Sunday, October 3, 2010
The Surprising Truth About What Motivates Us
Autonomy
Back in 1945, 3M pioneered the idea of giving free time to engineers. As a consequence, 3M obtained a bunch of innovative products including the "Post-It" stickers. 3M credo is "hire good people and leave them alone". They introduced the idea of giving free 15% time per week to each employeer but maintain the IP of the resulting inventions. Then, this approach has been championed by Google.
ROWE
Companies such as BestBuy adopted a Result Oriented Working Enviroment (ROWE), where suprisingly enough there is no Office Time at all. Everyone can self-schedule his time and can work from home when she decides that this is appropriate.
My opinion: Self-Organizing or Hierarchical?
In my opinion, there are several key advantages for self-organization:
- "Self-correcting and localizing what is wrong": mistakes or bad decisions(™), either technical or management related, are self-corrected by peers via intense discussions. In this sense, anything inherently "wrong" is confined into a local state and the system is agile.
- "Selft-Organizing means Dynamic Evolution of the Hierarchy (Deh!), not Chaotic": Let's change a classical wrong assumption. A self-organizing system is not chaotic. A self-organizing system is one where a hierarchy is naturally emergining due to merits and competencies. In other words, the hierarchy is dynamically changing according to different needs that will change over the time. "If I am you boos, this is not meaning that I am more expert than you" (™)
Saturday, October 2, 2010
Large Scale Tree Data Structures: Reading a fascinating paper on succinct data structure
We are all familiar with Trees, and we assume that pointers are an required evil needed for encoding the structure of a tree. Anyway, why do you need to spend 64bit pointers, when you can represent the structure with just few bits? Those ideas are not just theory, they are used in real implementation of Large Scale Tree data Structures that needs to fit in memory.
Let's start from this example taken from the paper Representing Trees of Higher Degree (E. Demain is one of the authors and his studies about Khipu are fascinating, but this is another story...)
An ordinal tree T can be represented as a bit array. The degree of each tree (number of sons) is encoded with a sequence of 1 terminated by a 0. All the nodes are represented with a level degree visit of T (commas are used just for helping the reader but we don't need to represent them). This representation is known as Level Ordered Unary Degree Sequence (LOUDS). Using auxiliary data structures for Rank and Select operations, LOUDS supports in constant time, finding the parent, the ith child, and the degree of a node.
- The number of 0 in the binary array is the number of node in the three.
- Each node is son of another node and therefore has a 1 representing it (we need to find which 1 is the correct one)
- As a consequence, we need at least a space of 2n, plus something for navigation
Now, we need to introduce two operations which can be computed in constant time with additional 0(n) space (see the paper).
- Rank1(j) returns the # of 1 up and including position j. Rank0(j) is a similar operation for 0
- Select1(j) returns the position of of the j-th 1. Select0(j) is a similar operation for 0
- Compute the degree of a node in position p. This is the number of 1 up to the next 0 and can be computed as Select0(rank0(p)+1) - p
- Compute the parent of a three as in Select1(rank0(p)+1)
- Compute the ith children of a tree;
Another magic representation is based on balanced parenthesis and it is due to Munro and Raman. Suppose you visit the three depth first and open a parenthesis on the way down, and close the parenthesis on the way up. The ordinal tree is encoded again ad a bitvector but now we have the additional benefit that the nodes of a subtree are very close in the bitvector. This is a consequence of the depth first visit. It is possible to navigate the three with Rank & Select operations.
Benoit, Demain, Munro, Raman proposed a variant of LOUDS based on depth first named Depth First Unary Degree Sequence (DFUDS), which preserves locality and still allows tree navigation in terms of Rank & Select. In addition, they proposed further optimization for finding the ith children of a node, if the tree is a trie with k outdegree.
More information about this fascinating word is available in Succinct Trees in Practice, 2010
Friday, October 1, 2010
More Fired UP then ever
Source: KARA
Yahoos,
Carol from the foxhole here. No, actually I’m in Atlanta to give a speech later tonight, and doing some client meetings.
But I’m sure you’ve seen the rumors about Hilary Schneider, David Ko, and Jimmy Pitaro leaving. Yes, they’re leaving, but each for different reasons that suit their life–and Hilary will send a separate note to her team with more about the Americas org. later today.
After nearly four years with Yahoo!, Hilary has decided to move on to the next phase in her career. Hilary has played a major role at Yahoo! in driving our strategies for content, online advertising and more. I want to thank her for her contributions over the years, and wish her the best as she moves on.
We expect to announce the new head of the Americas region before the end of the year. There is a lot of interest in joining our team for such a key position and, in the meantime, Hilary will stay on to help with the transition.
Now, you all know we’ve been intensely focused on improving our operations and top line growth. And we’ve seen good progress. But there’s a lot more to do, and as we transition to a new leader for the Americas we’re taking this opportunity to double down on these efforts. Hilary’s successor will clearly be maniacally focused on growing our top line in the region.
So everyone stay calm–we have a good plan in place. In fact, I’m more fired up than ever and can roll with the punches. Yahoo! is a great place.
Carol
I forecasted an acquisition, Apparently is partnership for Facebook & Skype
Thursday, September 30, 2010
Louis Mounier is back with Qwiki
Now I want to see Fuzzy Mauldin, back in action
Facebook 2nd Video site in U.S. and they do not host videos?
Tuesday, September 28, 2010
TechCrunch editor is tired and he sold to AOL
"The truth is I was tired. But I wasn’t tired of writing, or speaking at events. I was tired of our endless tech problems, our inability to find enough talented engineers who wanted to work, ultimately, on blog and CrunchBase software. And when we did find those engineers, as we so often did, how to keep them happy. Unlike most startups in Silicon Valley, the center of attention at TechCrunch is squarely on the writers. It’s certainly not an engineering driven company.
AOL of course fixes that problem perfectly. They run the largest blogging network in the world and if we sold to them we’d never have to worry about tech issues again. We could focus our engineering resources on higher end things and I, for one, could spend more of my day writing and a lot less time dealing with other stuff."
So they sold to AOL
Got a(nother) patent for Video Hover Preview
This is time is about Video Search. Back in 2005, we patented the idea of Video Hover preview. These days, Video Hover is a quite popular features among many video sites.
Abstract: A method and system to preview video content. The system comprises an access component to receive a search request and a loader to simultaneously stream a plurality of videos associated with the search request. The system may further comprise a trigger to detect a pointer positioned over a first video and a mode selector to provide the first video in a preview mode.
Inventors:
Gulli; Antonino (Pisa, IT)
Savona; Antonio (Sora, IT)
Veri; Mario (Rocca San Giovanni, IT)
Yet another achievement for Pisa, the "nowhere place"
Monday, September 27, 2010
Peter Thiel: Facebook Won’t IPO Until 2012 At The Earliest
Thiel says that Facebook wants to follow the example of Google, and doesn’t want to IPO until late in the process (which he claims is a byproduct of Sarbanes Oxley and other regulation)."
Sunday, September 26, 2010
Fishes in a lake
Saturday, September 25, 2010
Got a patent for Image Search
Abstract: "A system and method for determining if a set of images in a large collection of images are near duplicates allows for improved management and retrieval of images. Images are processed, image signatures are generated for each image in the set of images, and the generated image signatures are compared. Detecting similarity between images can be used to cluster and rank images."
Please note that the patent has been submitted before the classical paper PageRank for Product Image Search (2008) from Google, which presented similar ideas.
The algorithms described in the patent were used in Ask.com Image Search, which had the following judgement by PC-World 2007 "Returned very accurate image results, and it has a well-designed search results page. This is a worthy alternative to Google"
Inventors are:
Gulli'; Antonino (Pisa, IT)
Savona; Antonio (Sora, IT)
Yang; Tao (Santa Barbara, CA)
Liu; Xin (Piscataway, NJ)
Li; Beitao (Piscataway, NJ)
Choksi; Ankur (Somerset, NJ)
Tanganelli; Filippo (Castiglioncello, IT)
Carnevale; Luigi (Pisa, IT)
This idea has been ispired by a quite famous Andy Warhol painting
I am particularly proud of this patent, since it proves that innovation can be carried out even from Pisa, a "nowhere place in Italy" ;-). Bet won!
Friday, September 24, 2010
Ensemble Methods in Data Mining: Improving Accuracy Through Combining Prediction
Thursday, September 23, 2010
Facebook down -- Internet is crying
So it happens... When you are a little baby and you are about to become a kid. You need to make your own mistakes and sometime you need to fall down. Nothing wrong with it. Your mistakes will make you an adult.
So it happens.. Facebook went down for 2.5hours. My friend Nick wonders whether this increased the productivity in all the world ...
Apparently, the problem was generated by an automatic system used to maintain consistency in cache. Now Facebook is an adult, like Google, Bing, and Yahoo. All of them went down
Wednesday, September 22, 2010
Find the majority
Tuesday, September 21, 2010
Random generation
Monday, September 20, 2010
Maximum contiguous sum in an array
Your Personal Ads is waiting you
Last century was the age of massive and unpersonalized ads on TV, radio, and newspapers.
Ten years ago we saw the beginning of personalized ads with Google. The model was simple and therefore a huge revolution. You search what you want, I give you the results but we agree that I can use your query for serving targeted ads. Actually, the model was proposed originally by Goto.com and Lycos but they missed to understand the value .. and this is another story.
A couple of years ago we started to see another use of personalization. Again the model is simple. You are in a given place and access a service from there (either with your phone or with your desktop). I provide you the service, but will use your geo-location for serving local ads.
These are the days of multiple sensors. ImmersiveLabs is using a cam to detect your face and your sex. Your Iphone can send information about your walking style or your attitude. Your game console can send information about your training style or the what do you like to play. Your tv will soon send information about your entertainment needs. Facebook knows every web page you Like.
How many other ad sensors are there out in the world?
Gianni!!
Tuesday, September 14, 2010
Bing is the second one in US according to Nielsen
Monday, September 13, 2010
Why Facebook should work on a social graph based e-bay engine
On Ebay, a user can rank another user according to the quality of the transaction they concluded. Usually, each user take a look to the seller's ranking for assessing the potential risk of a bet. Even if each user is identified with a login and a password, the seller and the bidder do not know each others.
Facebook and the social graph will add an additional level of trust since both the seller and the bidder can identify a path of users that connect both of them and can provide references. Linkedin adopted a similar mechanism for introducing each others unknown persons. Facebook can use it for creating a new Ebay. In alternative, they can buy a competitor and integrate it in the social graph.
Sunday, September 12, 2010
count the frogs
Saturday, September 11, 2010
Chocolates and roses
Wednesday, September 8, 2010
Instant Search
- Estimate what is the percentage of your query log that can you cover with say X millions queries. Say that this is p%;
- Estimate what is the average lenght of a query;
- Evaluate whether would be better to leverage traditional inverted lists or tries;
- Estimate the impact of caching and your communication framework;
Cosmos Massive computations in Microsoft (comparison with Map Reduce, Hadoop and Skeleton Programming)
The adoption of SQL-like interfaces is one interesting extension to Map&Reduce. SQL-like statements allow to express parallel computations with no need to write code in a specific programming language (Java, C++ or whatever). These extensions has been originally inspired by Google's Sawzall and they have been made popular by Yahoo's Hadoop Pig and by Facebook's Hadoop Hive. All those extensions are very useful syntactic sugar, but they do no extend the Map&Reduce model.
Scope (Structured Computations Optimized for Parallel Execution) is a new declarative and extensible scripting language targeted massive data analysis. Quoting the paper "Scope: Easy and Efficient Parallel Processing of Massive Data Sets": However, this model (Map&Reduce) has its own set of limitations. Users are forced to map their applications to the map-reduce model in order to achieve parallelism. For some applications this mapping is very unnatural. Users have to provide implementations for the map and reduce functions, even for simple operations like projection and selection. Such custom code is error-prone and hardly reusable. Moreover, for complex applications that require multiple stages of map-reduce, there are often many valid evaluation strategies and execution orders. Having users implement (potentially multiple) map and reduce functions is equivalent to asking users specify physical execution plans directly in database systems. The user plans may be suboptimal and lead to performance degradation by orders of magnitude"
In other words, you can leverage loops, pipes and many other types of parallel patterns with NO need of emulating those steps as in pure Map&Reduce. The process is transparent to the user since she can just express a collection of SQL-like statements (a "Script") and the compiler will generate the more appropriate parallel execution patterns. For instance, (Example 3, in the article)
R1 = SELECT A+C AS ac, B.Trim() AS B1where A, B, C are colums in a SQL-like schema, and particular StringOccurs C# string function is used to filter the column C. This example shows how to write a user-defined function in scope.
FROM R WHERE StringOccurs(C, “xyz”) > 2
#CS public static int StringOccurs(string str, string ptrn)
{ int cnt=0; int pos=-1;
while (pos+1 < str.Length) {
pos = str.IndexOf(ptrn, pos+1);
if (pos < 0) break;
cnt++;
}
return cnt;
}
#ENDCS
Scope runs on the top of Cosmos storage system. "The Cosmos Storage System is an append-only file system that reliably stores petabytes of data. The system is optimized for large sequential I/O. All writes are append-only and concurrent writers are serialized by the system. Data is distributed and replicated for fault tolerance and compressed to save storage and increase I/O throughput."
The language Scope supports:
- Join: SQL-like;
- Select: SQL-like;
- Reduce: "it takes as input a rowset that has been grouped on the grouping columns specified in the ON clause, processes each group, and outputs zero, one or multiple rows per group";
- Process: "it takes a rowset as input, processes each row in turn, and outputs a sequence of rows";
- Combine: "it takes two input rowsets, combines them in some way, and outputs a sequence of rows";
Note that the users need to know neither the optimal mapping nor the optimal number of processes allocated for a particular SCOPE script execution. Everything is transparently computed by the SCOPE compiler and mapped on the top of a well defined set of "parallel design patterns". Dryad provides the basic primitives for SCOPE execution and Cosmos job allocation. Please refer this page if you are interested in more information about Dryad, or if you want to download the academic release of DryadLINQ.
This power of expression allows to express massive computations with very little SQL-like scripting (again from the above paper):
SELECT query, COUNT() AS count FROM "search.log"Here petabytes (and more!) of searchlogs are stored on the distributed Cosmos storage and processed in parallel to mine the one with at least 1000 "counts". Another example, this time with joins:
USING LogExtractor GROUP BY query
HAVING count > 1000
ORDER BY count DESC;
OUTPUT TO "qcount.result";
SUPPLIER = EXTRACT s_suppkey,s_name, s_address, s_nationkey, s_phone, s_acctbal, s_commen FROM "supplier.tbl" USING SupplierExtractor;
PARTSUPP = EXTRACT ps_partkey, ps_suppkey, ps_supplycost FROM "partsupp.tbl" USING PartSuppExtractor;
PART = EXTRACT p_partkey, p_mfgr FROM “part.tbl" USING PartExtractor;
// Join region, nation, and, supplier
// (Retain only the key of supplier)
RNS_JOIN = SELECT s_suppkey, n_name FROM region, nation, supplier WHERE r_regionkey == n_regionkey AND n_nationkey == s_nationkey;
// Now join in part and partsupp
RNSPS_JOIN = SELECT p_partkey, ps_supplycost, ps_suppkey, p_mfgr, n_name FROM part, partsupp, rns_join WHERE p_partkey == ps_partkey AND s_suppkey == ps_suppkey;
// Finish subquery so we get the min costs
SUBQ = SELECT p_partkey AS subq_partkey, MIN(ps_supplycost) AS min_cost FROM rnsps_join GROUP BY p_partkey;
// Finish computation of main query
// (Join with subquery and join with supplier
// again to get the required output columns)
RESULT = SELECT s_acctbal, s_name, p_partkey, p_mfgr, s_address, s_phone, s_comment FROM rnsps_join AS lo, subq AS sq, supplier AS s WHERE lo.p_partkey == sq.subq_partkey AND lo.ps_supplycost == min_cost AND lo.ps_suppkey == s.s_suppkey ORDER BY acctbal DESC, n_name, s_name, partkey;
// output result OUTPUT RESULT TO "tpchQ2.tbl";
Cosmos and Scope are an important part of the Bing & Hotmail systems, as described in "Server Engineering Insights for Large-Scale Online Services, an in-depth analysis of three very large-scale production Microsoft services: Hotmail, Cosmos, and Bing that together capture a wide range of characteristics of online services
Wired, Is the Web really dead? Reading numbers the way you like
According to the authors, the whole Web model is "dead" since this type of traffic is progressively reducing. App is the new rising start.
Many people expressed perplexity about the relation between the graph (traffic on internet) and the conclusion of the paper “Web is dead . Long live to
In more details, the fundamental misleading assumption is to consider the relative percentage growth instead of the absolute growth. Quoting Boing Boing: “In fact, between 1995 and 2006, the total amount of web traffic went from about 10 terabytes a month to 1,000,000 terabytes (or 1 exabyte). According to Cisco, the same source Wired used for its projections, total internet traffic rose then from about 1 exabyte to 7 exabytes between 2005 and 2010.”
The Web traffic had a huge increase but this increase has been relatively smaller when compared to video traffic. Probably this is also due to the data dimension of each video ;-). Same consideration for email, dns, etc.
Another misleading assumption is the definition of Video. Cisco created a such category which includes things like (Skype) video calls, Netflix, but ALSO youtube & hulu web traffic. It is questionable if this definition is correct. Perhaps, Youtube video traffic should be legitimately considered part of the Web traffic because this is a type of Web browser traffic.
Tuesday, September 7, 2010
Longest non decreasing subsequence
Monday, September 6, 2010
sum to 0
Sunday, September 5, 2010
Number of 1 in a sequence
Saturday, September 4, 2010
Partition an array
Friday, September 3, 2010
How Facebook works?
Thursday, September 2, 2010
Two beautilful Hadhoop books
Recently, I reviewed two beautiful books that I would suggest for your education
- Data-Intensive Text Processing with MapReduce which focuses on how to think and design algorithms in "MapReduce", with an emphasis on text processing algorithms common in natural language processing, information retrieval, and machine learning.
- Hadoop: The Definitive Guide with an emphasis on how to program a large hadoop cluster, and with real examples of industrial use in large organizations such as Last.Fm, Facebook and other.
Google and AOL renewed the contract
How many search providers are still out of there?
Different approaches to Universal Search.
- Having a set of classifiers, one for each domain that will guess whether that particular domain will have a set of relevant results for the given query. The pros is that you would avoid to send all the queries to all the verticals. The cons is that you will best guess the validity of the results, since you are not sending the real query to the vertical. This is Google pre-2004
- You have an infrastructure good enough to support Web-like traffic in all the different verticals. This is google post 2004. Note that this is a pull approach
- Another solution, not adopted by Google , is to push set of relevant queries from the vertical to the Query distributor. Consider that each vertical knows, at every given instant of time, the type of queries he can serve with good enough quality.
Wednesday, September 1, 2010
Hive and the SQL-Like fashion
Fulcrum was the first time I saw a SQL-like interface for retrieval back in 1996, now it's funny to see the Map/Reduce paradigm expressed in SQL-like as in
FROM (
FROM pv_users
MAP pv_users.userid, pv_users.date
USING 'map_script'
AS dt, uid
CLUSTER BY dt) map_output
INSERT OVERWRITE TABLE pv_users_reduced
REDUCE map_output.dt, map_output.uid
USING 'reduce_script'
AS date, count;
Tuesday, August 31, 2010
Sorting exceed the 1G keys/sec on GPUs
Monday, August 30, 2010
Apache Mahout: a formidable collection of Data mining algos on the top of Hadoop (Map Reduce)
Here you find some hints to run Mahout on the top of Amazon EC2. Here a collection of algorithms implemented . They include:
Classification
Logistic Regression (SGD implementation in progress: MAHOUT-228)
Support Vector Machines (SVM) (open: MAHOUT-14, MAHOUT-232 and MAHOUT-334)
Perceptron and Winnow (open: MAHOUT-85)
Neural Network (open, but MAHOUT-228 might help)
Random Forests (integrated - MAHOUT-122, MAHOUT-140, MAHOUT-145)
Restricted Boltzmann Machines (open, MAHOUT-375, GSOC2010)
Clustering
Canopy Clustering (MAHOUT-3 - integrated)K-Means Clustering (MAHOUT-5 - integrated)
Fuzzy K-Means (MAHOUT-74 - integrated)
Expectation Maximization (EM) (MAHOUT-28)
Mean Shift Clustering (MAHOUT-15 - integrated)
Hierarchical Clustering (MAHOUT-19)
Dirichlet Process Clustering (MAHOUT-30 - integrated)
Latent Dirichlet Allocation (MAHOUT-123 - integrated)
Spectral Clustering (open, MAHOUT-363, GSoC 2010)
Pattern Mining
Parallel FP Growth Algorithm (Also known as Frequent Itemset mining)
Regression
Locally Weighted Linear Regression (open)
Dimension reduction
Singular Value Decomposition and other Dimension Reduction Techniques (available since 0.3)
Principal Components Analysis (PCA) (open)
Independent Component Analysis (open)
Gaussian Discriminative Analysis (GDA) (open)
Evolutionary Algorithms
see also: MAHOUT-56 (integrated)
Sunday, August 29, 2010
Should Facebook buy Skype?
Skype has more than 560 million registered users, and it filed for a 136Million IPO . Facebook has about 500 million registered users and a pre-IPO value of 50 billion $.
Are the two business complementary? Probably:
Having the ability to call their friends from the favorite social network would be a great feature for final users. Increasing the Social graph and having a client installed in users' desktop would be a great opportunity for Facebook. Having an access to the Facebook computing power would be a chance for scaling the Skype platform and reducing their costs.
Saturday, August 28, 2010
Relational Join on Map Reduce
There is a simple trick for emulating relational join on the top of Map Reduce. Since all the items with the same key are sent to the same reducer, it is therefore easy to emulate a join on the reduce side. What are the other little tricks you need to adopt?
Obviously, you can alway use an higher level abstraction such as Hive on the top of Hadoop