Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Friday, August 10, 2012
Thursday, August 9, 2012
Find a triplet that sum to a given value
Given an array of integers
Wednesday, August 8, 2012
Tuesday, August 7, 2012
Monday, August 6, 2012
Check whether two strings are anagram of each other
Sunday, August 5, 2012
ind the maximum sum leaf to root path in a Binary Tree
Saturday, August 4, 2012
Intersection and Union
Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Discuss complexity and make your assumptions.
Friday, August 3, 2012
Add two numbers without using arithmetic operators
Hint: use bit operators
Thursday, August 2, 2012
Bing and Facebook
“Facebook is a partner with Google’s biggest
rival, Bing, to handle web searches.”
“Readers: Are you seeing the “search the Web”
link in your typeahead search results?”
“Facebook
had previously allowed users to filter their Facebook searches by web results
after clicking over to a main results page, but it hadn’t offered the option
from the typeahead, which only included Facebook objects. Making it more
efficient to search the web from Facebook’s search bar will give users an
incentive to use Facebook search rather than going to a separate search engine
like Google. “
Wednesday, August 1, 2012
An hidden gem, not so well known: Academic Search Microsoft. Want it integrated in bing?
http://academic.research.microsoft.com/Author/77558/antonio-gulli?query=antonio+gull
http://academic.research.microsoft.com/Author/77558/antonio-gulli?query=antonio+gull
Tuesday, July 31, 2012
Sharing revenues with skilled friends
In my previous postings I discussed about the opportunity of explicitly share your skills on facebook showing that the authenticity of those skills would be self-regulated by the social network. Also, I claimed that the current web search ads system is not necessarily the only monetization model available. In web search, when a query is submitted some relevant content is retrieved and ads are sold together with the results. The engine takes the money and the web content producers take no money. Web content producers take benefits from the traffic received by the search engine, but they directly take no money -- which is strange to me.
Now the question is what incentive could we give the users who are sharing their own skills?
First answer would be to send them traffic in analogy to what happen in web search. Anyway, I am not sure that this would be valuable for my friend Giuseppe who claimed that he is an expert in Photography. Why sending traffic to his Facebook page should have any additional value to him?
Now the question is what incentive could we give the users who are sharing their own skills?
First answer would be to send them traffic in analogy to what happen in web search. Anyway, I am not sure that this would be valuable for my friend Giuseppe who claimed that he is an expert in Photography. Why sending traffic to his Facebook page should have any additional value to him?
The second answer is to share revenue between my skilled friend Giuseppe and Facebook whenever Facebook shows Giuseppe among the friends skilled in Photography. The more likes Giuseppe gets the higher would be the chances to be retrieved for a search about Photography. Whenever ads shown for that topic are clicked Giuseppe will get a little amount of the revenues generated. He produced the content, he has the skill so he takes some direct money for it. In my view, this model would give a natural incentive to share skills and to get likes for those skills.
The third answer is still to about sharing revenues, but would be based on inserting ads into skilled pages. What is a skilled page? pretty simple. If Giuseppe declares a skill in Photography he can create a special page on his profile very similar to the traditional timeline but focused just on Photography. All the ads shown in that page are about the Photograpy topic and again there should be some form of revenue sharing as form of incentive to produce high quality, curated skilled pages. After all, Giuseppe is the expert so he has to tell something about his expertise.
Monday, July 30, 2012
Skilled friends can gain money after they share their skills for free
An anonymous reader told me: "people need an incentive/experience to provide this information for free. They will assume that their friends know - so why should they tell Facebook this information?"
In my previous posting, I showed that skills cannot be faked because they are judged by the rest of the friends. This is nothing but just applying the power of social ties which self-regulates authenticity.
Now, let's go to the next step. I believe that current web ads system is fundamentally flawed. A lot of people produce web content which is then indexed by search engines. When a query about a topic is submitted by a user some relevant content is retrieved and ads are sold together with the results. The engine takes the money and the content producers take no money.
Why that?
Yes, content producers will receive more traffic and this has certainly an economic value. Anyway, who said that this is the only model we can think of?
Do you have any alternative?
In my previous posting, I showed that skills cannot be faked because they are judged by the rest of the friends. This is nothing but just applying the power of social ties which self-regulates authenticity.
Now, let's go to the next step. I believe that current web ads system is fundamentally flawed. A lot of people produce web content which is then indexed by search engines. When a query about a topic is submitted by a user some relevant content is retrieved and ads are sold together with the results. The engine takes the money and the content producers take no money.
Why that?
Yes, content producers will receive more traffic and this has certainly an economic value. Anyway, who said that this is the only model we can think of?
Do you have any alternative?
Sunday, July 29, 2012
Skills cannot be faked
One more thought about my idea of skilled friends on Facebook. I don't believe the a friend can mystify her skills by declaring a talent which is not there. Her social network will understand this and she will look bad in front of her friends.
So, skills cannot be faked. Plus, when you declare a skill there is always the opportunity to like it and this will be an important signal to rank friends by skills.
So, skills cannot be faked. Plus, when you declare a skill there is always the opportunity to like it and this will be an important signal to rank friends by skills.
Saturday, July 28, 2012
An idea for Facebook: from friends to skilled friends (or how to make money)
Facebook has 900 millions of users, and everyone is connected to a number of friends. Sometime you don't know what are your friends' skills. In my network there are people expert in photography, people expert in art, people experts in skiing, people expert in surfing, and people expert in solar power, and people expert in philosophy, and people with an immense musical background, and many geeks, and people with tremendous interest for electrical cars, and people with a passion for astronomy and celestial stuffs, and ....
So many people, so much talent to discover.
So Facebook, let everyone declare their own skills and talents to their social network. Let my friends be skilled friends. Let me also tag the skills of my friends as I tag my friends' faces in pictures.
Then, let me discover this talent when I search: if I search for photography give the name of my friend Giuseppe who has a skill in this subject, and If I search surfing give me the name of Luca who is the expert here. If no friend is an expert in that topic, please find a skilled expert among the friends of my friend.
Transform generic search in search for skilled friends.
And when I search a skill, here you have the magic opportunity to sell ads about that topic.
So If i search for surfing give me the name of Luca, but also ads related to the topic. Give me the name of that online market where I can buy great surf tables or show me where to find swimsuits. Likewise, if I search for camera give me the name of Giuseppe but also ads for the latest Nikon D7000. And...
Transform generic search in a search for skilled friends, and make money out of a great user experience.
Friday, July 27, 2012
Implement an hash table with chains in case of collision
Thursday, July 26, 2012
Bing search meets Facebook: exciting typeahead progress
Very happy about the integration of typeahead/autosuggestion technologies between Bing and Facebook. Now you can Bing directly from Facebook search box. Congratulation to the teams that made this happening by establishing a collaboration with several locations in the world (California, Washington, and London). My team in London provided core backend technologies for Bing Autosuggestion.
Enjoy!
Enjoy!
Wednesday, July 25, 2012
A phone has two sides. An idea for phone manifactures
Yesterday, I was listening this conversation: "I have always to carry at least two phones. My iphone is great for browsing and the apps, and my blackberry is great for browsing emails". How many of you have a similar experience: either you have a phone with a large touch display which is great for browsing, or you have a phone with smaller display but with a decent keyboard. So you go out of there and buy your favourite Android, Windows Phone, Iphone AND you possibly buy a traditional Blackberry or the like.
Now I wonder why two devices? Why don't have just one with two sides? On one side you have the large touch display, and on the other side you have the smaller display but a good traditional keyboard.
I should probably patent this idea and sell it to companies out of there, but there is a war so I prefer to publish here and give it for free.. as in freedom
Now I wonder why two devices? Why don't have just one with two sides? On one side you have the large touch display, and on the other side you have the smaller display but a good traditional keyboard.
I should probably patent this idea and sell it to companies out of there, but there is a war so I prefer to publish here and give it for free.. as in freedom
Tuesday, July 24, 2012
Implement a tree inorder visit with no recursion
Monday, July 23, 2012
What colour would you pain an airplane
motivate your answer
Sunday, July 22, 2012
LRU
How to implement LRU caching scheme? What data structures should be used
Saturday, July 21, 2012
Implement set and traditional set operation
Please discuss trade-offs in your choice.
Friday, July 20, 2012
Given a stream of integers always maintain the median
This is a bit difficult, try with heaps
Thursday, July 19, 2012
Bitonic arrays
iven an array A[0 ... n-1] containing n positive integers, a subarray A[i ... j] is bitonic if there is a k with i <= k <= j such that A[i] <= A[i + 1] ... <= A[k] >= A[k + 1] >= .. A[j - 1] > = A[j]. Write a function that takes an array as argument and returns the length of the maximum length bitonic subarray.
Wednesday, July 18, 2012
Array and positions
Given an array of n distinct integers sorted in ascending order, write a function that returns true is there is an index i such that arr[i] is equal to i
Tuesday, July 17, 2012
Strange struct.
struct str{ int i: 1; int j: 2; int k: 3; int l: 4;};
what is this? is it a good and portable code?Monday, July 16, 2012
Two arrays
Given two sorted arrays of any length, find out the median of them if they are sorted into single array
Sunday, July 15, 2012
Find the maximum element in an array which is first increasing and then decreasing
Go with binary search (well, pretty much)
Saturday, July 14, 2012
Maze
Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array).
ex: 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1If there is a block it’s represented by 0.
If there is a path it’s represented by 1.
Friday, July 13, 2012
Beautification
Write a program for beautificaion of a program file in an IDE
Thursday, July 12, 2012
Linked list
Write a program to print the n-nodes from tail of the linked list.
Wednesday, July 11, 2012
IPv4
Write a program to Validate an IPv4 Address
Tuesday, July 10, 2012
Distributed sort
Given N machines. Each machine contains some numbers in sorted form. The amount of numbers for each machine is not fixed. Output the numbers from all the machine in sorted non-decreasing form.
Monday, July 9, 2012
Unique words
Design a system to calculate the number of unique words in a file..
1) What if the file is huge ?
2) Assuming that you have more than one computers available, how can you distribute the problem ?
Sunday, July 8, 2012
Array of 0 and 1
You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.
linear
Saturday, July 7, 2012
Friday, July 6, 2012
Thursday, July 5, 2012
Given an array of size n, find all the possible sub set of the array of size k
typical recursive problem
Wednesday, July 4, 2012
Sum 3 numbers
given an array and a target value. Find a,b,c such that a+b+c=target
Tuesday, July 3, 2012
fiven n points find m points closer to origin
in a r-space
Monday, July 2, 2012
Solve the coin change problem
def count( n, m ):
if n == 0:
return 1
if n < 0:
return 0
if m <= 0 and n >= 1: #m < 0 for zero indexed programming languages
return 0
return count( n, m - 1 ) + count( n - S[m], m )
Sunday, July 1, 2012
Regexp match
Write a function checkRegex() which takes two strings as input, one string represents a regex expression and other is an input string to match with the regex expression. Return true if it matches, else false. Regex may contain characters ‘a-z’, ‘.’ and ‘*’ where ‘.’ matches any character and ‘*’ means 0 or more occurrences of the previous character preceding it.
Saturday, June 30, 2012
Min and Max
Find the min and max in an array. Now do it in less than 2n comparisons
Friday, June 29, 2012
Event store
Question: Design a component that implements the following functionality..
1) Record an Event (For the sake of simplicity, treat the Event as an integer code)
2) Return the number of Events recorded in the last one minute.
3) Return the number of Events recorded in the last one hour.
i.e implement the following interface
Thursday, June 28, 2012
Points closer to a point
You are given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it. These three points ordered by distance.
Wednesday, June 27, 2012
Last 60secs
Create a data structure which is supposed to log number of user requests per second. At any point of time your boss can ask you the number of hits for the last 60 seconds.
Tuesday, June 26, 2012
Monday, June 25, 2012
Reverse words
Given a file with billions of records data. The file is too large to in main memory, and you need to reverse each word in that file and then save the reversed words to another file.
Sunday, June 24, 2012
Creative d80 -- Bluetooth wireless music box
I recently bought a Creative d80 -- Bluetooth wireless music box and my impression is WOW!! It is very cheap just less than $40 and the quality of music is impressive. I can stream over Bluetooth from my iphone, ipad, android, winphone, and windows 7. I don't have a Mac but it seems as easy as the remaining ones. If you have win7 make sure that your Bluetooth device has a stack supporting a2dp or enhanced data rate.
Geek is about founding creative and inexpensive cool technologies.
Geek is about founding creative and inexpensive cool technologies.
Saturday, June 23, 2012
This Ph.D. thesis changed the world as we know. 100 years. A true hero, with solid principles
https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf
https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf
Friday, June 22, 2012
Thursday, June 21, 2012
Tuesday, June 19, 2012
Monday, June 18, 2012
maximal subsets
Given a set S, find all the maximal subsets whose sum <= k. For example, if S = {1, 2, 3, 4, 5} and k = 7
Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}
Sunday, June 17, 2012
Lucky numbers are numbers whose prime factors are just 2, 3, 5.
Find the first k lucky numbers.
Saturday, June 16, 2012
Value of A and B
Given two sorted positive integer rrays A(n) and B(n). We define a set S = {(a,b) such that a in A and b in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. The tricky part is that we need an O(n)
algorithm.
Friday, June 15, 2012
true and false
Given a function bool Zoo(int x) and its called for y times , how you will generate the true with probability x/y times .
Thursday, June 14, 2012
Wednesday, June 13, 2012
Eggdrops
Solve the classical Google's interview problem.
Dynamic programming
Dynamic programming
k: Number of floors
n: Number of Eggs
eggDrop(n, k): Minimum number of trails needed to find the critical
floor in worst case.
1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.
eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): x in {1, 2, ..., k}}
Tuesday, June 12, 2012
you have a fleet of trucks and each truck has an autonomy of 1000KMs
How many kms in total you can cover if all the trucks start from the same place?
You have 25 horses and you can make races of 5 of them in parallell
How many races to get the top 3 horses?
Monday, June 11, 2012
A feature request for Facebook
Sometime I just want to pin a thread and follow it without expressing an explicit like. Would it be possible to just follow a thread?
Sunday, June 10, 2012
Monetizing free login
Several different providers are offering universal login schema, including Microsoft, Linkedin and Facebook. Apparently, none is monetizing this phase while there are plenty of opportunities to be leveraged.
Let's analyse a simple scenario where Alice, a Spotify user, decides to login using her Facebook account. Facebook knows Alice's geo-location, Alice's profile, Alice's past postings and likes. So Facebook has a lot of information to be mined for serving ads while Spotify does not have the same information. In other words, Facebook can sell ads to Spotify's users. So this could be the "Adsense" program for Facebook.
So my question is why Facebook is not opening this ads platform?
Let's analyse a simple scenario where Alice, a Spotify user, decides to login using her Facebook account. Facebook knows Alice's geo-location, Alice's profile, Alice's past postings and likes. So Facebook has a lot of information to be mined for serving ads while Spotify does not have the same information. In other words, Facebook can sell ads to Spotify's users. So this could be the "Adsense" program for Facebook.
So my question is why Facebook is not opening this ads platform?
Saturday, June 9, 2012
Friday, June 8, 2012
Thursday, June 7, 2012
Phonebook
Data structure TO use to design a phonebook. What is time complexity for retrieving, adding, and deleting entries
Wednesday, June 6, 2012
Tuesday, June 5, 2012
Monday, June 4, 2012
Write a function that takes 2 arguments: a binary tree and an integer n, it should return the n-th element in the inorder traversal of the binary tree
int findNthElementByInorder(Node *node, int &n)
{
if (node == null)
return -1;
findNthElementByInorder(node->left, n);
if (n == 0)
return node-> value;
else
n--;
findNthElementByInorder(node->right, n);
}
N-th
Write a function that takes 2 arguments: a binary tree and an integer n, it should return the n-th element in the inorder traversal of the binary tree.
int findNthElementByInorder(Node *node, int &n)
{
if (node == null)
return -1;
findNthElementByInorder(node->left, n);
if (n == 0)
return node-> value;
else
n--;
findNthElementByInorder(node->right, n);
}
Sunday, June 3, 2012
Reverse a linked list
Node* reverseLL(Node* n) {
Node* curr = n;
Node* prev = null;
while(curr !=null) {
Node* temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
Saturday, June 2, 2012
Duch national problem
void threeWayPartition(int data[], int size, int low, int high) {
int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] < low) {
swap(data[i], data[++p]);
++i;
} else if (data[i] >= high) {
swap(data[i], data[--q]);
} else {
++i;
}
}
Friday, June 1, 2012
Given array find 3 elements that sum up to 0
For each i = 1..length do
left = 0, right = length
While left < i and right > i do
if values[left] + values[i] + values[right] == 0
# Got solution here
if values[left] + values[i] + values[right] > 0
# means that right border should be moved
right--
else
# moving left border
left++
Thursday, May 31, 2012
Sort an array of objects
There are just three sizes large, small, medium. what is the optimal complexity? Can you make this in-place?
Wednesday, May 30, 2012
Given 2 very large numbers, each of which is so large it can only be represented as an array of integers, write a function to multiply them
const unsigned MULTIPLY_BASE = 10;
void multiplyLittleEndian(const vector < unsigned > &a, const vector < unsigned > &b, vector < unsigned > &r)
{
r.assign(a.size()+b.size(), 0);
unsigned ri=0;
for(unsigned ai=0; ai < a.size(); ++ai)
{
unsigned cri = ri++, carry = 0, am = a[ai], cr;
for(unsigned bi=0; bi < b.size(); ++bi, ++cri)
{
cr = carry + am*b[bi] + r[cri];
r[cri] = cr % MULTIPLY_BASE;
carry = cr / MULTIPLY_BASE;
}
while(carry)
{
cr = carry + r[cri];
r[cri++] = cr % MULTIPLY_BASE;
carry = cr / MULTIPLY_BASE;
}
}
while((!r.empty()) && r.back() == 0) r.pop_back(); // trim result
}
Tuesday, May 29, 2012
Sunday, May 27, 2012
add two numbers represented by strings
First need to reverse both strings, then add char by character and reverse final String again.
Saturday, May 26, 2012
Friday, May 25, 2012
Interweave a linked list
Interweave a linked list. Do it in Linear time and constant space. Input: A->B->C->D->E Output: A->E->B->D->C
Thursday, May 24, 2012
Wednesday, May 23, 2012
Implement a function to compute cubic root what is the time complexity?
pay attention to negative values, but it's a binary search
Tuesday, May 22, 2012
Roman strings
Get numeric number out of a roman string, linear time Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000 Input/Output: II = 2, III = 3, IV = 4 VI, VII, VIII IX = 9 XL = 40, XLIX = 49
mapping = {
'I' : 1,
'V' : 5,
'X' : 10,
'L' : 50,
'C' : 100,
'D' : 500,
'M' : 1000,
}
def roman(string):
prev = 0
totalsum = 0
for c in string:
if mapping[c] <= prev:
totalsum = totalsum + mapping[c]
else:
totalsum = totalsum - prev
totalsum = totalsum + mapping[c] - prev
prev = mapping[c]
print(totalsum)
roman("XCIX")
Monday, May 21, 2012
Thursday, April 19, 2012
About the openness
Google is complaining about the direction where Internet is going. Apparently, they say that there is less openness these days and it seems that the bad guy is Facebook, which is collecting user generated content which is not shared in an open way. I am puzzled.
If this is a genuine rant why are they building Google+ which is just a copycat of Facebook? Also, why they collect search data since 1998 about everyone's behaviour but they don't share this data with the rest of the world?
Long time ago, I dreamt about a different world with open standards for exchanging facebook-like news feeds but hosted by different providers (remember RSS and ATOM? something similar but social) so that data is public. Then, the aggregation is centralized and you access aggregated information in a similar way to what is happening nowadays with search engines. In that ideal world, login would be no longer centralized but it would be based on openID. The social graph would be shared across different servers and remote nodes would be just special form of href, so that someone can index public data.
(this is my personal idea and it's not representing any opinion expressed by my company)
If this is a genuine rant why are they building Google+ which is just a copycat of Facebook? Also, why they collect search data since 1998 about everyone's behaviour but they don't share this data with the rest of the world?
Long time ago, I dreamt about a different world with open standards for exchanging facebook-like news feeds but hosted by different providers (remember RSS and ATOM? something similar but social) so that data is public. Then, the aggregation is centralized and you access aggregated information in a similar way to what is happening nowadays with search engines. In that ideal world, login would be no longer centralized but it would be based on openID. The social graph would be shared across different servers and remote nodes would be just special form of href, so that someone can index public data.
(this is my personal idea and it's not representing any opinion expressed by my company)
Tuesday, April 17, 2012
Birthday
you are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?
Sunday, April 15, 2012
Saturday, April 14, 2012
An interesting project for parallel machine learning:
Interesting collection of data parallel machine learning algorithms
"MADlib is an open-source library for scalable in-database analytics. It provides data-parallel implementations of mathematical, statistical and machine-learning methods for structured and unstructured data.
"MADlib is an open-source library for scalable in-database analytics. It provides data-parallel implementations of mathematical, statistical and machine-learning methods for structured and unstructured data.
The MADlib mission: to foster widespread development of scalable analytic skills, by harnessing efforts from commercial practice, academic research, and open-source development."
Friday, April 13, 2012
How many zeros at the end of 100!
This is tricky but funny
Thursday, April 12, 2012
Wednesday, April 11, 2012
Tuesday, April 10, 2012
Compute 2^128 -- no computer and possibly no paper
can you just compute it in your mind?
Monday, April 9, 2012
Can you estimate the cost of Facebook data center?
Sunday, April 8, 2012
Saturday, April 7, 2012
Friday, April 6, 2012
How many numbers with a 7 in the first 10000 integers?
Thursday, April 5, 2012
DBScan
Hi Antonio,
First of all apologies if this query is out of scope- I appreciate you may have moved on to other things, or may be just too busy at the moment.
I was looking for a simple implementation of DBSCAN to use as a starting point for some work and I found your implemention here (http://codingplayground.blogspot.com/2009/11/dbscan-clustering-algorithm.html). I found it worked quite well for small enough data sets, but for large ones it was allocating excessive amounts of memory, and I eventually looked at the code to see where the problem could be. It seems to me there may be an issue with the cluster expansion part of your algorithm- this issue may not affect the results (I think it may still produce the correct clusters), but it uses much more memory than it needs and this problem is more severe for larger input datasets.
The problem is with these lines of code
specifically the line "ne.push_back(n1)". At this point in the algorithm you have found a cluster and are looking for density connected neighbours. You are adding all the new neighbours to the list to be considered, when you only need to add the ones that have not been considered yet. So rather than extending the original list with the full contents of the new list, you need to extend it with the difference of the two lists. This small change stabilises the memory usage and makes it run much faster.
kind regards
aonghus
First of all apologies if this query is out of scope- I appreciate you may have moved on to other things, or may be just too busy at the moment.
I was looking for a simple implementation of DBSCAN to use as a starting point for some work and I found your implemention here (http://codingplayground.blogspot.com/2009/11/dbscan-clustering-algorithm.html). I found it worked quite well for small enough data sets, but for large ones it was allocating excessive amounts of memory, and I eventually looked at the code to see where the problem could be. It seems to me there may be an issue with the cluster expansion part of your algorithm- this issue may not affect the results (I think it may still produce the correct clusters), but it uses much more memory than it needs and this problem is more severe for larger input datasets.
The problem is with these lines of code
Neighbors ne1 = findNeighbors(nPid, _eps);
// enough support
if (ne1.size() >= _minPts)
{
debug_cerr << "\t Expanding to pid=" << nPid << std::endl;
// join
BOOST_FOREACH(Neighbors::value_type n1, ne1)
{
// join neighbord
ne.push_back(n1);
//debug_cerr << "\tPushback pid=" << n1 << std::endl;
}
//debug_cerr << std::endl;
//debug_cerr << " ne: " << ne << endl;
debug_cerr << " ne size " << ne.size() << " " << ne1.size() << endl;
}
// enough support
if (ne1.size() >= _minPts)
{
debug_cerr << "\t Expanding to pid=" << nPid << std::endl;
// join
BOOST_FOREACH(Neighbors::value_type n1, ne1)
{
// join neighbord
ne.push_back(n1);
//debug_cerr << "\tPushback pid=" << n1 << std::endl;
}
//debug_cerr << std::endl;
//debug_cerr << " ne: " << ne << endl;
debug_cerr << " ne size " << ne.size() << " " << ne1.size() << endl;
}
specifically the line "ne.push_back(n1)". At this point in the algorithm you have found a cluster and are looking for density connected neighbours. You are adding all the new neighbours to the list to be considered, when you only need to add the ones that have not been considered yet. So rather than extending the original list with the full contents of the new list, you need to extend it with the difference of the two lists. This small change stabilises the memory usage and makes it run much faster.
kind regards
aonghus
Wednesday, April 4, 2012
Check if Alice has my phone number, and don't tell Eve
Alice is a friend of mine, Bob is my assistant but I don't want him to know my super-private phone number. Also, I want to check whether Alice has my super-private phone number but I don't want to communicate the number to Bob. What can I do to preserve my number?
Tuesday, April 3, 2012
An airplane is going from city A to city B
what would be the impact of the wind for a round-trip travel A to B?
Monday, April 2, 2012
Helium balloon in a car
What direction will the balloon go when you accelerate?
Sunday, April 1, 2012
One biased coin
You have a biased coin and the result can be H or T but biased towards T. How can you make sure whatever is the toss the result will be fair?
Subscribe to:
Posts (Atom)






