Waledac: malware cloud computing

It has been estimated that Waledac infected hundreds of thousands of computer. Is that a malware cloud?

Find the i-th element in a dynamic set

You are given a dynamic set of integers D. The set can increase/decrease its size. You are requested to provide the operator i-th(D, i) which returns the element with rank i in D.

Yahoo search deal

http://videos.webpronews.com/2010/03/05/yahoo-details-implementation-search-deal/

Containing objects

An object is defined in terms of triplets of integers . An object Oi can be contained in an object Oj if ai < aj, bi < bj, ci < cj. Given a set of objects S, find the maximum subset of objects that can be contained each other.

Solve the generalized problem where an object is represented in terms of n-ples.

Searching a set of strings

Suppose you are given a (large) set S of variable length strings. The set is very large, say 1 billion of strings. The goal is to identify exact string duplicates. How would you solve the problem?

Hashing with linked chains

Hashing can use a linked list whenever there is a conflict for a key. Here a couple of questions:

1) how would you organize the list? sorted / unsorted?
2) would you need to allocate/disallocate in case of delete and insertion with collisions?

Quicksort worst-case

Traditionally quicksort is considered quadratic in the worst case. there is a randomized version which makes it O(n log n). Do you know how to make it O(n log n) worst case without using randomization?

Why Google Pushed Buzz Out The Door Before It Was Ready

No more Don't be evil?

Ramdrive and Memory FS

Modern file systems automatically cache files in memory. Anyway, sometime is useful to work with a memory file system where you pre-load all the data.

On Unix this is typically realized mounting a memory file system:

 mount_mfs -s 20m swap /work

On Windows (XP/Vista/7), I found very useful to use this software Ramdisk from dataram, which creates a normal disk but in ram.

Bing goes mobile

Bing goes on WM7

Random Permutations

Let the array A[0, n-1], where A[i] contains the number i \in [0, n) with probability 1/n. Will the array A contain a uniformly random permutation of the numbers 0, .... n-1? Remember that there are n! permutations of the numbers [0, n-1)

Get k tags out of n tags

You have a dataset of N document with N tags associated for each document. How many documents should you process before seeing k unique tags, for a given k with k << N with high probability?

Largest span of increasing pair in an array of integers

Given an array of integers A[N], find the maximum value of (j-k) such that A[k] <= A[j] & j>k

Inversions

Let A[1 .. n] be an array of n distinct numbers. If i <> A[j], then the pair (i, j) is called an inversion of A. Suppose that each element of A is chosen randomly, independently, and uniformly from the range 1 through n. Compute the expected number of inversions.

Malloc and Free

A certain program makes use of malloc and free several times. Anyway, you forgot to free one block of memory allocated with one malloc. What strategy do you use to check the place where the unpaired malloc is located?

Find what is missing

You are given an unsorted list of n-1 distinct integers from the range 1 to n. Write a linear-time algorithm to find the missing integer. Please pay attention to potential overflow

Find all the patterns in a string

Find all the patterns which are present in the character array C. A pattern is a sub-array containing 2 or more chars and is having a frequency of more than one.

Microsoft and Yahoo.

It's done.

Google Now Includes MySpace Status Updates in Real-Time Search Results

MySpace and Google just announced that starting today, status updates from MySpace users will appear in Google's real-time search.

Google Buzz Kills Auto-Follow on Privacy Concerns

"Then there's advertising, which relies on data collection. Google wouldn't probably be as succe$sful if they didn't know that web users aren't very web savvy. Plus, when web users get a hint of data collection, they tend to swing to the other side of the pendulum and overstate the issue, ignoring things like anonymized data.

Perhaps Google got a little too comfortable with Internet ignorance. They certainly struck a nerve with the autofollowing and autosharing of Buzz. Still, it's doubtful this will do any serious damage to Google. The psychological relief of getting what you want from a company (in this case, greater perceived privacy) is easier than changing your email and search habits."

source: searchenginewatch

One fly and two colliding trains.

Two trains are running one against the other at 50 km/h each. They are 100Km far away. Soon they will collide. One fly is flying from one train to another, first it moves in one direction and as soon as it touches one train it flyies back in the other direction. The fly has a 30Km/h speed. How much space will the fly cover?

Carl Icahn selling off Yahoo shares

"Carl Icahn has substantially cut his stake in Yahoo, according to regulatory filings made public Friday.

The billionaire investor had just under 12 million shares of Yahoo at the end of 2009, according to the new filing with the Securities and Exchange Commission. That compares with more 60 million shares he held last summer"

Dark times at yahoo? Looking for next steve jobs

"I said: “many in this audience want Yahoo to be competitive and succeed but remain skeptical that you can.” Larry Cornett responded that he was at Apple during the “dark time” before the return of Steve Jobs, when critics were calling for the company to shut down. He likened the media perceptions of Yahoo Search now to that period in Apple’s history and promised that Yahoo Search would “be back.” He added that many of Yahoo’s innovations were being freely copied by its competitors but in more superficial ways."

Google to buy Aardvark

Aardvark, a company that lets you use IM, Twitter and e-mail to ask full-text questions and then get answers from people in or close to your social network, confirmed it signed a deal with Google.

Is google returning to Q&A?

IAC writes down value of search unit by nearly $1 billion

Will the next step be a merge? I bet so.

"New York-based IAC (NASDAQ: IACI) wrote down $991.9 million from the goodwill on IAC Search & Media, the part of its business that contains Ask.com and also the much smaller Dictionary.com. Goodwill is a company’s guess about the future earning power of an asset or company it has bought. It’s the difference between the price paid for the asset and its book value on the balance sheet. Ask.com started life in Berkeley in 1996 as Ask Jeeves -- it was an early dot-com darling. Later, the business moved to a tower in downtown Oakland and was bought by IAC in 2005 in a deal that valued it at $1.85 billion."

New comscore out

Microsoft sites grew January core search volume by 49.6% Y/Y, Google search volume growth of 16.7% Y/Y, Ask grew January core search volume by 15.5% Y/Y, Yahoo! January core search volume decreased by 8.9% Y/Y
source: business insider

Towards Recency Ranking in Web Search

Academia and search R&D labs are publishing more and more papers about recenty ranking. I am pretty excited about that since I spent the last 3 years on this topic both in Ask.com and in Bing.com.

Towards Recency Ranking in Web Search is an high quality paper from Yahoo! about relevancy ranking. The main contribution of the paper is twofold: it presents a query classifier for recency and a ranking model for recent results.

The query classifier builds two models representing the Content and the Query data at time t, respectively. The two models are then compared on different instants of time and a query is considered recent if it increases his probability of being generated in two different istants. This approach is interesting. Nevertheless there are queries that would fresh results, even if they are constantly observed (such as "Obama", "Britney Spears", "stock quotation", etc).

The ranking model aims at learning a ranking function based on four categories of recency-related features: timestamp features, linktime features, webbuzz features and page classification
features. The learning algorithm is GBrank. To solve the recency data insufficiency problem, the authors explored several modeling approaches by utilizing regular ranking data. In compositional model the normal ranking output is used as a training feature, while in over-weighting model the normal ranking output is used with recency features and an emphirical optimal weight is derived. In adaptation model, training data from normal ranking is used for learning a regression tree model, which is then fine-tuned with recency ranking data.

The evaluation set is made up of 70,131 query-url pairs collected during a period of four months (Feb.∼May, 2009) judged by humans and is based on NDGC metrics. One final result is worth mentioning. In the paper, linktime features are the most important recency features among all recency features. Quoting the authors: "Thus, recency is competing with popularity, which is usually indicated by link-based features and click-based features. This leads to the interesting topic on how to appropriately deal with the relationship between recency and popularity"

Compute all the items which appears more than p% of time

Write the C++ code for an optimal algorithm -- both in time and space.

Compute all the items which appears more than 50% of time

Given a stream of symbols, with a finite alphabet, compute all the items which appears more than 50% of time

Slides for LinkedIn People Search

Thanks to Greg for pointing out them. Interesting work@LinkedIn based on Lucene's customizations.

Beautiful video on Twitter Creation

Twitter Code Swarm from Ben Sandofsky on Vimeo.

Bing to power Facebook Search

Second, we are extending our cooperation outside the US, bringing the Bing-Facebook search integration to the more than 400 million people using Facebook around the world.

Anatomy of a Large-Scale Social Search Engine

Aardvark Q&A engine going to WWW10

• Users can ask questions in natural language, not keywords
• Content is generated “on-demand”, tapping the huge amount of information in peoples’ heads
• The system is fueled by the goodwill of its users

• 87.7% of questions sent to Aardvark got answered (very high answer rate!)
• 75.0% of users who asked Aardvark a question also answered a question for someone else (very high participation rate!)
• 70.4% of answer feedback had a rating of ‘good’ as opposed to ‘ok’ or ‘bad’ (high quality!)

Aol wil use Google, once again

So Bing is will probably power Yahoo, and Google will power AOL.
Who is out of this list?

A collection of code competition sites

1. http://geeksforgeeks.org/
2. http://stackoverflow.com
3. http://www.topcoder.com/tc
4. http://www.spoj.pl
5. http://www.projecteuler.net
6. http://codechef.com
7. http://uva.onlinejudge.org/

Anything missing from the list?

4th Russian Summer School in Information Retrieval

Great initiative from Russia

Machine Learning a pratical book

Introduction to Machine Learning it's a quite practical book that I do like to suggest for reading

merge two binary search tree in optimal space and time

ditto

Add two numbers representened in lists (with carry)

You are given two numbers with a strange list representation such as the below. Add them with carry. Find the optimal solution in space and time.

Num 1 = 123456
Num 2= 1234
Link-1->Link-2->Link-3->Link-4->Link5->Link6
Link-1->Link-2->Link-3->Link-4

Longest path

Find the longest path in a DAG

Ubuntu Firefox shuns Google for Yahoo! search

"The next release of Ubuntu will scrap Google as the default search engine on its Firefox browser in favor of Yahoo!, thanks to a new revenue-sharing deal between Yahoo! and commercial Ubuntu backer Canonical."

source: the register

Google is going social

When you search, you get what your friends are posting. In this case, the social graph is defined by all the Google services (Youtube, Blogger, etc) + Twitter. It’s not clear if Facebook is included, it seems to me that is not. What is your opinion?

Eleborate large dataset

I believe that if you were around in the 90-ties you may have heard about NoW or Skeleton programming. Isn't map & reduce just a sub-set of skeleton programming?

Where I'd like to invest: 3D UI

We live in a 3D world (no actualy more, but that is a different story), but so far our interactive experience were 2D. Now things are chaning and we start to see real 3D movies (such as Avatar).

What would be next?

I want to have a real 3D UI for my operative system and I don't just mean simulate it in a 2D screen, I mean project it and than interact with the users, like it is already happening to some extent for video games in Project Natal Then I want a 3D Search experience, which goes behind the 2D flat search. And I want a 3D social experience.

Any company out of there where I can put my money?

Kernel PCA

PCA is a dimension reduction technique for linearly separeted data. In order to deal with data that cannot be linearly separated, one can adopt the kernel trick. This generates the so called Kernel-PCA.

Here you have the code in C++ and Eigen.

Google founders to loose control

Google founders will sell around 5-6% of the company stocks on the market, for a current value of about 5.5 billion dollars. Woah! This way they will go under 50% of the company. Will they start something new ? I hope so.

Searches Soar in 2009; Google Tops List

The U.S. represented the largest individual search market in the world with 22.7 billion searches, comScore found, or or approximately 17 percent of searches conducted globally. China ranked second with 13.3 billion searches, followed by Japan with 9.2 billion and the U.K. with 6.2 billion.

About 87.8 million searches originated on the Google Sites network, a 58 percent increase. Just 9.44 million were made via Yahoo, which saw its own total jump by 14 percent. Chinese search engine Baidu.com finished third. But it was Microsoft, spurred by Bing, which showed the second-strongest growth out of the sites comScore measured, jumping 70 percent to 4.09 million searches. Russian search engine Yandex achieved the most considerable gains, growing 91 percent to 1.9 billion searches.

source PC Mag

Longest non decreasing sequence.

Given a sequence of N numbers. Find the length of the longest non-decreasing sequence.

HotWise: search market share

theft of search intellectual property: operation Aurora

I was in China while this was happening.

Google reported an

highly sophisticated and targeted attack on our corporate infrastructure originating from China that resulted in the theft of intellectual property from Google

Wired is giving some technical details. Apparentl,y is a problem with Adobe Reader and Microsoft IE (even if other programs can be affected)

Although the initial attack occurred when company employees visited a malicious website, Alperovitch said researchers are still trying to determine if this occurred through a URL sent to employees by e-mail or instant messaging or through some other method, such as Facebook or other social networking sites.Once the user visited the malicious site, their Internet Explorer browser was exploited to download an array of malware to their computer automatically and transparently. The programs unloaded seamlessly and silently onto the system, like Russian nesting dolls, flowing one after the other.

“The initial piece of code was shell code encrypted three times and that activated the exploit,” Alperovitch said. “Then it executed downloads from an external machine that dropped the first piece of binary on the host. That download was also encrypted. The encrypted binary packed itself into a couple of executables that were also encrypted.”

One of the malicious programs opened a remote backdoor to the computer, establishing an encrypted covert channel that masqueraded as an SSL connection to avoid detection. This allowed the attackers ongoing access to the computer and to use it as a “beachhead” into other parts of the network, Alperovitch said, to search for login credentials, intellectual property and whatever else they were seeking.

McAfee obtained copies of malware used in the attack, and quietly added protection to its products a number of days ago, Alperovitch said, after its researchers were first brought in by hacked companies to help investigate the breaches.

Although security firm iDefense told Threat Level on Tuesday that the Trojan used in some of the attacks was the Trojan.Hydraq, Alperovitch says the malware he examined was not previously known by any anti-virus vendors.

iDefense also said that a vulnerability in Adobe’s Reader and Acrobat applications was used to gain access to some of the 34 breached companies. The hackers sent e-mail to targets that carried malicious PDF attachments.

Alperovitch said that none of the companies he examined were breached with a malicious PDF, but he said there were likely many methods used to attack the various companies, not just the IE vulnerability.

Once the hackers were in systems, they siphoned off data to command-and-control servers in Illinois, Texas and Taiwan. Alperovitch wouldn’t identify the systems in the United States that were involved in the attack, though reports indicate that Rackspace, a hosting firm in Texas, was used by the hackers. Rackspace disclosed on its blog this week that it inadvertently played “a very small part” in the hack.

The company wrote that “a server at Rackspace was compromised, disabled, and we actively assisted in the investigation of the cyber attack, fully cooperating with all affected parties.”

Alperovitch wouldn’t say what the attackers might have found once they were on company networks, other than to indicate that the high-value targets that were hit “were places of important intellectual property.”

iDefense, however, told Threat Level that the attackers were targeting source-code repositories of many of the companies and succeeded in reaching their target in many cases.

Alperovitch says the attacks appeared to have begun Dec. 15, but may have started earlier. They appear to have ceased on Jan. 4, when command-and-control servers that were being used to communicate with the malware and siphon data shut down.

Microsoft issued a security warning

Microsoft is investigating reports of limited, targeted attacks against customers of Internet Explorer 6, using a vulnerability in Internet Explorer. This advisory contains information about which versions of Internet Explorer are vulnerable as well as workarounds and mitigations for this issue.

Our investigation so far has shown that Internet Explorer 5.01 Service Pack 4 on Microsoft Windows 2000 Service Pack 4 is not affected, and that Internet Explorer 6 Service Pack 1 on Microsoft Windows 2000 Service Pack 4, and Internet Explorer 6, Internet Explorer 7 and Internet Explorer 8 on supported editions of Windows XP, Windows Server 2003, Windows Vista, Windows Server 2008, Windows 7, and Windows Server 2008 R2 are vulnerable.

The vulnerability exists as an invalid pointer reference within Internet Explorer. It is possible under certain conditions for the invalid pointer to be accessed after an object is deleted. In a specially-crafted attack, in attempting to access a freed object, Internet Explorer can be caused to allow remote code execution.

Microsoft also issued a risk assesment that I encorauge you to visit

As you can see, the client configuration currently at risk is Windows XP running IE6. We recommend users of IE6 on Windows XP upgrade to a new version of Internet Explorer and/or enable DEP. Users of other platforms are at reduced risk. We also recommend users of Windows XP upgrade to newer versions of Windows.

The vulnerability is present in Internet Explorer 6, Internet Explorer 7, and Internet Explorer 8. All versions may crash after opening the attack code. However, there are a number of ways to limit the attack to an IE crash and prevent attacker code execution.

• Disable code executing from random locations of freed memory. Data Execution Prevention (DEP) prevents the execution of code from pages of memory that are not explicitly marked as executable. DEP is a supported feature on Windows XP Service Pack 2 and higher, Windows Server 2003 Service Pack 2 and higher, and all versions of Windows Vista, Windows Server 2008, and Windows 7. Some platforms enable DEP by default (see below). You can read more about DEP in this blog here and here. You can enable DEP on Windows XP and Windows Vista by clicking the Microsoft Fix It button below. (DEP is enabled by default for Internet Explorer 8 running on XP Service Pack 3, Windows Vista Service Pack 1 and higher, and Windows 7, so you do not need to use the "Microsoft Fix It" for those configurations.)

Mcafee released some advices for security here

Make sure that you have the latest version of McAfee security software on your computer with the latest signature files to protect yourself against the malware exploits within Operation Aurora. If you don't have security software, you can download a McAfee free trial.

Also, Microsoft recommends users change their browser security setting to HIGH and McAfee recommends that you restrict browsing to known sites until Microsoft provides a patch for the Internet Explorer exploit. To change your security settings to HIGH, open the browser, click on Tools>Options>Security and slide your setting up.

Adobe released a critical patch here

Adobe Reader 9.3 was released today, right on schedule, to address this issue. In the meantime, the company is realizing the changing nature of the platform business, and how Reader/Acrobat and Flash are now just as susceptible to potential attacks as any other platform, including Windows. Interestingly, the cross-platform nature of the Acrobat platform means that Mac users were just as susceptible to this exploit as Windows users.

Baidu CTO leaving

I was in Beijing these days. In my hotel I saw the 10 birthday anniversay for Baidu, the search market leader in China. Today, I saw the news about their CTO change. Something is happening in China.

Bing got +2.7% market share, since May 2009

"What is even more interesting is if you look at year-over-year query growth rates for each search engine. Bing’s growth is actually accelerating. Its growth rate in query volume was 49.4 percent in December, compared to 20.6 percent growth for Google (which was also above the average), and a 1.9 percent decline for Yahoo. Here are the year-over-year query growth rates for Bing for the past few months:"

source: techcrunch

PCA: Dimensional Reduction in Eigen

PCA (Principal Component Analisys) is a classical machine learning method to reduce the dimensionality of a problem. PCA involves the calculation of the eigenvalue decomposition of a data covariance matrix or singular value decomposition of a data matrix, usually after mean centering the data for each attribute. Playing with Eigen library, I started to implement PCA in C++.

OneRiot and Realtime ADS

OneRiot’s Realtime Ad Network RiotWise Now Open To The Masses

Google goes safe mode

HTTPs as default in GMAIL. I wonder why ...

Google enters the real estate business + maps

I was wondering when this was happening. Alessio told me about this a couple of years ago. He was right and I knew it.

Som clustering algorithm

Som (Self Organizing Map) is an interesting algorithm for mapping vectors into a lattice of nodes. Typically this is a 2D array of nodes or a toroid. This is an implementation with 2D array and boost::matrix

Store phone numbers

I used it my interviews. Now not any longer: Store 100 million phone numbers, with minimal memory space. Search must be efficient.

Getting eigenvalues solver in Windows

After testing Boost::numeric::bindings (with Atlas) on Windows, I definetively abandoning this solution. Anyone has any positive experience with them?

I am moving to Eingen library, which is a native template library ready to use. Just download it. Then in Visual Studio edit the proprierties of your project and in C++ add the appropriate include path. Then compile it, without any problem.

Eingensolver is defined in this class. Here a toy code example of use.

#include 
#include 


// import most common Eigen types USING_PART_OF_NAMESPACE_EIGEN
int main(int, char *[])
{
  using namespace Eigen;
 
  Matrix3f m3;
  m3 << 1, 2, 3, 4, 5, 6, 7, 8, 9;
  Matrix4f m4 = Matrix4f::Identity();
  Vector4i v4(1, 2, 3, 4);

  EigenSolver m_solve(m3);
  Vector3f m_solved_val = m_solve.eigenvalues().real();

  std::cout << "m3\n" << m3 << "\nm4:\n"
    << m4 << "\nv4:\n" << v4 
 << "\neigen:\n" << m_solved_val << "\n" << std::endl;

  std::string a;
  std::cin >> a;
}

Yahoo CEO Gives Herself a B-Minus

Carol Bartz said her first year was harder than she expected it would be "It was a little tougher internally than I think I had anticipated," Bloomberg quoted Bartz, 61, as saying. "I did move fast, but this is a big job."

2009 Word of the Year is “tweet”; Word of the Decade is “google”

Both of them have something to do with search. They have been decided by the American Dialect Society

Getting Blas and Lapack and Blas libraries in Windows without compiling them

Getting Lapack and Blas libraries in windows is quite annoying since there is not any prebuilt package that I am aware of. You need to compile a distribution of ATLAS, but this is quite demanding since there are a lot of dependencies for windows and current version appears like
broken.

One alternative solution, that I am exploring is based on extraction of symbols from R. You install it and then from Visual Studio command prompt perform a:

dumpbin /EXPORTS Rlapack.dll > Rlapack.def
dumpbin /EXPORTS Rblas.dll > Rblas.def

Next step is to use the calling standard described here. I will discuss about it in a follow-up posting.

Define a functor

In C you have the classical pointer to function which allows you to store a pointer to a parametric function f. Then you can pass the pointer to another function g, which will use f. A typical example is the cmp function you use to sort a generic array of type T elements. The problem with pointer to function is that you don't have a strong type system to check the signature of the function and this can generate potential horrid bugs.

In C++ and STL you typically define a functor object which had the type system check but is limited to unary, binary or ternary functions.

In Boost you resolve this problem by using the Boost Function library, which allows you to define a type checked function object with unlimited number of parameters.

Nearest Neighbour on KD-Tree in C++ and Boost

Wikipedia describes the pseudo-code for computing the nearest neighbour (nn) on an already built KDtree. Here you have a boost implementation of Nearest Neighbour with Kd-tree in boost.

Very curious about voice search on Nexus one

Google released a Phone, aiming at competing with Iphone, windows mobile, symbian, etc. I am quite interested in their voice search features. Have you used it?

In the end the love you receive is more than the love you give

You know that old song from Beatles. This is not the case for my life. The love I receive from Francesca, my wife, Lorenzo and Leonardo, my two kids is more than the love I give to them. Thanks for being here, my love.

Do you need to return more than a value

Typically you do

return_value function(parameters)
{

}

with boost::tuple you can return tuples of values. here is an example of code.

Your favourite 2009 posts

It seems that you prefer posts with code. Here the top 5 posts for 2009:

1. Adaboost : improve your weak performance

2. Simulated Annealing

3. Generic Skip list (skiplist)

4. DBSCAN clustering algorithm

5. K-means in C++

In the end the love you give is equal to the love you receive

New Year and off-topic. I had 3 teachers in my life.

• Antonio C, who taught how to use the power of imagination and think about a product before anyone else.
• Apostolos G, who taught how to realize world class industrial products
• Paolo F, who taught how important is theory and the beauty of algorithms.

I never had a chance to say thank you to them directly. I believe that the best way to thank them is to create new opportunities for other people, as they created opportunities for me.

PS: A 'teacher' is someone who is senior to me and I no longer work for him

Sort a huge file

You are given a huge file with say 100 terabytes of integers. They don't fit in internal memory, what strategy would you use?

Selecting the median in an array

Ok, this is a typical "easy" interview question: you are given an array of integers, select the median value. What is the optimal solution?

A good tool for POS tagging, Named Entity recognition, and chunking,

YamCha is a good tool for POS tagging, Named Entity recognition, and chunking, based on SVM.

Introduction to Computational Advertising : Andrei Broder's course online

"Computational advertising is a new scientific discipline, at the intersection of information retrieval, machine learning, optimization, and microeconomics. Its central challenge is to find the best ad to present to a user engaged in a given context, such as querying a search engine ("sponsored search"), reading a web page ("content match"), watching a movie, and IM-ing. As such, Computational Advertising provides the foundations for building ad matching platforms that provide the technical infrastructure for the $20 billion industry of online advertising.

In this course we aim to provide an overview of the technology used in building online advertising platforms for various internet advertising formats."

Handsout of Andrei's course on Computatitional Advertising are now on line

KD-Tree: A C++ and Boost implementation

According to wikipedia a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organiizing points in a k-dimensional space. In this implementation, points are represented as a boost ublas matrix (numPoints x dimPoints) and the kd-tree can be seen as a row permutation of the matrix. The tree is built recursively. At depth k, the (k % dimPoints) coordinates are analyzed for all the points and the median of them is selected with a quickselect algorithm. The quickselection induces a natural row-index permutation for points in two sets, which are recursively partitioned on the next levels of the tree.

Here you have the code.

Xmas present: Machine Learning: An Algorithmic Perspective

A very useful book for Machine Learning, with a lot of examples in python. Machine Learning: An Algorithmic Perspective is a must have in your library.

MultiArray: a useful container.

MultiArray is a useful boost container. Think about a hierarchical container which contains other containers. You can also have recursive definitions, where each level of the container can have other MultiArrays. Therefore a multi_array[float,2] is a matrix of float (dim=2), a multi_array[float,3] is a cuboid of float (dim =3). Instead, multi_array[multi_array[float,2], 3] is an object that you cannot represent with a 'simple' matrix: we are representing a cuboid where each cell is a matrix of floats.

MultiArrays can be accessed with the traditional iterator pattern, or accessed with the conventional bracket notation.

Maybe the most useful feature of MultiArray is the possibility to create views, where a subset of the underlying elements in a MultiArray as though it were a separate MultiArray.

Building an HTTP proxy for filtering content

I am very agnostic for what is concerned programming languages.

C++ is a must for any production ready code, such as online search code (and if you use STL and boost you have a rich lib set). C# is useful for offline code, due to the inner rich set of lib set. Some people loves Java for this stuffs (e.g. Lucene, Hadoop, and other very good enviroment). Then, you you are in the scripting coding for fast and dirty prototyping you may want to use python (which is good for strong typed system) or perl (which is good for the vast set of modules, see CPAN).

So, I need to write an HTTP proxy for filtering some content. What is my choice? In this case, perl with HTTP::Proxy module, which allows me to filter both headers and content.

A commodity vector space class

Sometime you need to realize a vectors space with dense vector. Here is a commodity class code.

PS: getting the sparse version is easy if you use Boost Ublas.

Is this... the real 3D Mandelbrot then?

Fashinating article. Are fractals a form for search? In my opinion, Yes they are.

"The original Mandelbrot is an amazing object that has captured the public's imagination for 30 years with its cascading patterns and hypnotically colorful detail. It's known as a 'fractal' - a type of shape that yields (sometimes elaborate) detail forever, no matter how far you 'zoom' into it (think of the trunk of a tree sprouting branches, which in turn split off into smaller branches, which themselves yield twigs etc.).

It's found by following a relatively simple math formula. But in the end, it's still only 2D and flat - there's no depth, shadows, perspective, or light sourcing. What we have featured in this article is a potential 3D version of the same fractal"

Facebook is growing big .. and I mean REALLY BIG!

Most Recent Facebook Common Stock Sale Values Company At $11 Billion, techcrunch reported. I already reported the Distribution of Facebook Users (~300M world wide). Anyway, what is really impressive is that FB is generating a lot of incoming traffic for many other web sites (you know when you embed some content). Very similar to what search engines are doing...

Conditional Random Fields

Conditional Random Fields are a framework to build probabilistic models for segmenting
and labeling sequence data and are a valid alternative to HMMs. CRF++ is a valid package for computing CRF

Social, Mobile and the Local search

Ok, Google is going to buy yelp. Anyway, who cares about directories anymore? I am particularly impressed by the combination of Local, Social and Mobile. Oh yes, I meant foursquare. Check it out. I say real time search with a reason.

SAT and hill-climbing

SAT is a classifical NP problem, now what is the best known algorithm for building an approximate solution? WalkSAT

Pick a random unsatisfied clauses
Consider 3 moves; flipping each variable
If (any improve the evaluation)
{
accept the best
}
else
{
probability 0.5 : take the least bad
probability 0.5: pick a random move
}

Impressive no? and what this algorithm reminds to you?

Ellg: an open source social platform

I do encorauge to try elgg platform. Ok, it is in PhP which I don't like, but is cool and rich which I like. Consider that Facebook was written in PhP, after all.

Trackle

Have a look I like the idea of tracking and sharing: Trackle.com

FB killed the AOL star

FB killed the AOL Star.

Wow they are rocketing

Neural Networks and backpropagation

I am studying once again NN and back-propagation. Any paper out of there that compares standard grandient descend update rule (delta rule), with the one where you add a momentum?

Any other suggestions for different update rules?

CTR and search engines

Chitka Research has released a report showing Bing users, the new search engine from Microsoft, clicking on ads 75% more often than Google users.

Good sign? Ask and AOL has more CTR than bing

Google: a usefult set of slides to build a distributed system

Designs, Lessons and Advice from Building Large Distributed Systems. Classical discussion about Map&Reduce and BigTable, plus an interesting overview about next incoming Snapper

Power Law and an Enrico Fermi's motivation

Power Laws are very frequent in data mining. For instance, you can find a power law in many properties of the web graph. I found a quite interesting explanation of power laws for modelling particles and cosmic radiation (Enrico Fermi 1949)

In this model, particles are produced at constant rate and the particles' distribution at time t is an exponential of the form \lamda * e ^ - (\lamda * t) (in other words there is a negative exponential contribution). In addition, particles gain energy when time is passing such as C e ^ (\alpha * t) (in other words this is giving a positive exponential contribution).

Under these two forces the particles will have a power law density. Can you explain why?

Google is running fast on News (Please do not forget History)

I do have a lot of respect about the last Google's initiatives in News. "Living Stories" is a very cool prototype: "Today, on Google Labs, we're unveiling some of the work we've done in partnership with two world-class news organizations: The News York Times and The Washington Post. The result of that experiment is the Living Stories prototype, which features new ways to interact with news and the quality of reporting you've come to expect from the reporters and editors at The Post and The Times."

The key idea is that: "Each story has an evolving summary of current developments as a well as an interactive timeline of critical events. Stories can be explored by themes, significant participants or multimedia."

Google, I do like the idea of a collaboration with NYT and WP. Anyway, the idea of following the evolution of the story is not a new idea. It has been published in a patent Systems and methods for clustering information and used live by Ask.com as the 'History' feature:

"A clustering algorithm is used to cluster the information according to the selected window of time .omega.. New clusters can be periodically linked to chains, or new topic clusters can be identified, periodically. The new clusters are compared to other clusters to discover similarities in topic. When similarities are found among clusters in different time windows, the clusters are linked together to form a chain or are added to a preexisting chain. This comparison with clusters in previous time windows can stop if no similar information is found for a period of time proportional to the extension of the current cluster or to an extension of the chain. The chain of clusters is organized in a hierarchy according to the temporal information of each cluster: the most recent cluster is typically displayed at the top of the chain and the oldest cluster is typically displayed at the bottom of the chain."

On Feb 2008, this article gave a positive judgment about the 'History' feature: "My vote – thumbs up. Ask.com has done well integrating social media with news in a clean, easy-to-use interface. Features like story history could save me time"

What are the zettabytes?

An interesting study about the information consumed in U.S.

"In 2008, Americans consumed information for about 1.3 trillion hours, an average of almost 12 hours per day. Consumption totaled 3.6 zettabytes and 10,845 trillion words, corresponding to 100,500 words and 34 gigabytes for an average person on an average day. A zettabyte is 10 to the 21st power bytes, a million million gigabytes. These estimates are from an analysis of more than 20 different sources of information, from very old (newspapers and books) to very new (portable computer games, satellite radio, and Internet video).

Video sources (moving pictures) dominate bytes of information, with 1.3 zettabytes from television and approximately 2 zettabytes of computer games. If hours or words are used
as the measurement, information sources are more widely distributed, with substantial amounts from radio, Internet browsing, and others. All of our results are estimates.

Previous studies of information have reported much lower quantities. Two previous How Much
Information? studies, by Peter Lyman and Hal Varian in 2000 and 2003, analyzed the quantity of original content created, rather than what was consumed. A more recent study measured consumption, but estimated that only .3 zettabytes were consumed worldwide in 2007.
Hours of information consumption grew at 2.6 percent per year from 1980 to 2008, due to a combination of population growth and increasing hours per capita, from 7.4 to 11.8. More surprising is that information consumption in bytes increased at only 5.4 percent per year. Yet the capacity to process data has been driven by Moore’s Law, rising at least 30 percent per year.

One reason for the slow growth in bytes is that color TV changed little over that period. High-definition TV is increasing the number of bytes in TV programs, but slowly.
The traditional media of radio and TV still dominate our consumption per day, with a total of 60 percent of the hours. In total, more than three-quarters of U.S. households’ information time is spent with noncomputer sources. Despite this, computers have had major effects on some aspects of information consumption. In the past, information consumption was overwhelmingly passive, with telephone being the only interactive medium.

Thanks to computers, a full third of words and more than half of bytes are now received interactively.

Reading, which was in decline due to the growth of television, tripled from 1980 to 2008, because it is theoverwhelmingly preferred way to receive words on the Internet."

Google is moving into Real-Time search

I am quite impressed of what google is doing in the real-time field, where they claim the monitor about 1 billion of fast moving urls.

Yahoo! and Microsoft cement 10-year search deal

Yahoo! and Microsoft have finalised the terms of their search agreement, five months after announcing the deal.

From The Telegraph
"Microsoft’s Bing and Yahoo! search are pooling their efforts in order to try and take on the dominance of Google in the search market. According to Net Applications’ most recent global figures, Google accounted for 85 per cent of all searches, while Bing took 3.3 per cent share and Yahoo! search accounted for 6.22 per cent of the total market. "

Inverting a matrix?

Can you leverage the techiques of yesterday's question to invert a matrix?

Dividing a number with no division

This could be an interview question, but do not expect me to ask this question anymore ;-)

"Given a>0 can you compute a^-1 without any division?"

Google Customizes More of Its Search Results

This is an important step for Google and I do appreciate the initiative. Personalized search has been one of the hot topic in the academia, with a lot of people trying to obtain a personalized version of page rank. Well, personalization is more about Dynamic ranking and not about Static ranking. Other search engines are also adopting personalized forms of ranking, but here google is raising the bar..

"For many of its users, Google offers Web search results that are customized based on their previous search history and clicks. For example, if someone consistently favors a particular sports site, Google will put that site high in the results when they look up sports topics in its search engine.

But there has always been one catch: people had to be signed in to a Google account to see such customization.

On Friday Google said it was extending these personalized search results to people who are not logged into the service."

Quoting Wikipedia, which cites me and Alessio

This is a study that Alessio and me carried out back in 2004. Alessio is now Director of Search, Oneriot the Realt Time search engine beyond Yahoo!. Wikipedia is now citing us.

A more recent study, which used Web searches in 75 different languages to sample the Web, determined that there were over 11.5 billion Web pages in the publicly indexable Web as of the end of January 2005.^[61]

Search capitalization

This is a one year comparison about market capitalization on 1 Dec 2009. I used Apple as benchmark since that tech stock had a great performance this year.

Web Search signals

Search Engine Watch just published an article about 'new' search signals. Well, I don't believe these are new signals since they are quite well discussed in already published seach patents (seo by the sea is a great source for search patents). In addition, query session data analysis is missing in the list and that is another very important class of signals.