Efficient FIFO/Queue data structure in Python

For the types of algorithms I implement these days, I need a fast FIFO-like data structure. Actually, I need a double-ended queue. Python has a list type, but it is somewhat a misnomer because its performance characterics are those of a vector. Recently, I found mxQueue which is a separate (non-free) download. Unfortunately, mxQueue has a non-Pythonic interface and, to make matters worse, I found out that Python comes by default with a really nice Queue of its own, called deque: you can find it in the new collection module.

Thus, as a good scientist, I decided to test these 3 implementations. As it turns out, Queue.deque is a perfectly good FIFO data structure:

Python class time (s)
list (Python’s default) 2.26
Queue.deque 0.42
mx.Queue.mxQueue 0.42

Through other tests, I was able to verify that both Queue.deque and mx.Queue.mxQueue have constant time deletion from both the head and the tail, unlike Python’s list.

Embedding fonts for IEEE

IEEE requires that your PDF files embed all fonts. If you are including figures, it might prove difficult to embed them. Here is a recipe that works. Start with a file called “ICRA05.pdf”.

  1. convert to ps: pdftops ICRA05.pdf
  2. convert back to pdf using prepress settings: ps2pdf14 -dPDFSETTINGS=/prepress ICRA05.ps
  3. check new ICRA05.pdf for horrendous formatting errors due to double conversion.

(Source: Owen Kaser.)

Subscribe to this blog
in a reader
or by Email.

A Tectonic Shift in Global Higher Education

(…) India, which accounts for a quarter of the developing world’s population and has the third largest higher education system in the world. Today, 23 percent of all higher education enrollments in India are in distance education “specifically in 13 national and state open universities and 106 institutions, mostly public, that teach both on campus and by correspondence. The government’s target is that by 2010, 40 percent of all higher education participation will take place using distance education.

(A Tectonic Shift in Global Higher Education, Sir John Daniel et al., August 2006.)

Google launches online, shareable, spreadsheet tool!

Google has done it again! Spreadsheets.google.com offers free (as in “no money”) shareable, online spreadsheets. The UI feels a lot like Excel and you can save and load Excel documents. Unfortunately, it does not appear to support the Open Document Format. Unlike Excel, you can easily share your Google spreadsheet.

spreadsheets.google.com image

Get an RSS feed of your favorite researcher

Want to monitor the publications of a researcher? As long as he submits his papers to arXiv.org and/or Cogprints, you can use citebase to get a RSS feed: enter the author’s name, do a search, then click on the RSS link. ArXiv also has RSS feeds if you are only interested in this particular repository.

Source: Peter Turney.

Further reading: See my earlier post on this topic.

Technique without theory or theory from technique? An examination of practical, philosophical, and foundational issues in data mining

Korukonda wrote a paper in the Journal of Human-Centred Systems (AI & Society) putting into question the (philosophical) foundation of Data Mining as a science. He puts it quite bluntly:

the current status of Data Mining as an intellectual discipline is tenuous.

This is of particular interest to me since I consider myself a Data Mining researcher. Unlike Korukonda, however, I consider that Data Mining can be equally user-driven (as in OLAP) or data-driven. I do not think that there is a well established definition of Data Mining, except that we all agree it has to do with analyzing lots of data. The lack of a theoretical foundation for Data Mining is a well known problem which was explicitely identified during IEEE Data Mining 2005 as one of the top 10 challenges facing the community.

Korunda makes some good points. First of all, he reminds us that “Knowledge from Data” can be misleading. He gives the example of “idiot correlation” where the wrong hypothesis is tested. He takes an example from the New York Times where a reporter wrote that they noticed a 4.5% increase in sales at Red Lobster in March despite the war in Irak. Why would this be interesting? It is well known that when working over large data sets, you will invariably find surprising relations between different variables, but these relations are not necessarily meaningful. The fact that they are well supported by the historical data is not sufficient to make them useful. Statistically, because the number of possible relations is exponentially large, some of them are always supported by the historical data. A review of the Data Mining literature would prove him right: many researchers design systems to blindly find relationships. This is one reason why I prefer user-driven Data Mining as in OLAP where meaningless relations are automically discarded by the user.

Nevertheless, he correctly points out that even though the process is flawed, it could still be that it is a useful paradigm. When facing large data sets, you can either give up or try something. Data Mining is the best paradigm we have for these types of problems.

Being a nice guy, Korukonda gives us the way out:

This focus needs to shift to the “why” questions, if DM is to establish itself as a scientific investigative tool or as a long-term solution to business problems. In other words, the outcome of DM should extend beyond discovery of patterns to finding causal explanations for the observed patterns and relationships.

Meanwhile, he cites Taschek who tells us that Data Mining is dead:

One reason data mining as a term failed was because data mining products did not work. Sure, the technology theoretically allowed companies to dig through historical data but it never lived up to its promise. (Taschek, eWeek, 2001)

I think that the Taschek quote must refer to data-driven Data Mining, because user-driven Data Mining is doing quite well with a worldwide market of 6 billions$ in software products alone.

Maybe the real question is whether it is sensible to take the human out of the loop. I always think that as long as strong AI escapes us, we have to keep the human in there because that’s our only chance for intelligence. Yes, paying an analyst to look at your data is expensive, but you can lower the costs by giving him the best tools money can buy.

The Scare Effect

Stephen cites Gwynne Dyer on these new scary terrorists who use liquid explosives:

Maybe it’s cynical, but there are strong grounds for suspecting that this is all a charade. If they infiltrated these terrorist cells many months ago and now have arrested most of the members, then why would they institute drastic new security measures on flights at this point? And did they really only realize in the last few days that explosives come in liquid form as well?

I’ve known since I was a kid and I was watching western movies that there are super-powerful liquid explosives. Putting those in bottles and getting in a plane is not exactly rocket science.

Either we have been assuming that terrorists (Muslim or otherwise) are stupid people, or else, our governments think we are fools. They had to know, for years and years, that terrorists could use liquid explosives. Aren’t our governments supposed to anticipate threats?

If you infiltrate a terrorist cell and find out they are clever and have good tricks to blow up airplanes, why would you make this public? Surely, you want to tell other governments, but why the big media outburst with all the juicy details on how you can fit enough explosive in a toothpaste tube to blow up a plane? Wouldn’t it be a better strategy to just arrest these guys, go to court and put them in jail? Aren’t you just helping to promote terrorists by turning the public light on young fools? Whether the airplanes have been blown up or not, these guys have won by showing that you can have a huge worldwide impact just by plotting such a scheme. The proponents of the war on terror have also won by heating up the security issue once more.

Clearly, this is all part of a public relation scheme.

I hear some guys in the USA got arrested for having too many cellular phones (and being muslims didn’t help). Yes, you can blow up planes using cellular phones as detonators. Yes, muslims own cellular phones. Where are we getting at?

It looks like we are building a case against Islam. That’s what it looks like. Yes, I want terrorists arrested efficiently. Yes, I want sane security measures taken. But, no, I do not want a war on Islam. Sometimes, there are wars you cannot win.

(I’m an atheist.)

IRMA 2007 – Data Warehousing and Mining track (October 1, 2006 / May 19-23, 2007)

The IRMA 2007 International Conference has a Data Warehousing and Mining track organized by Andrew Kusiak and Qiang Zhu. The conference will be held in Vancouver.

A key to success for enterprises in today’s competitive markets is their ability to manage the staggering volumes and complexity of data from various sources in an efficient and economic manner. Data warehousing and mining have become prevailing technologies for data analysis, knowledge extraction and decision support in modern enterprises and organizations. The emergence of vast applications and other related software/hardware technologies continues to raise challenges (e.g., demand for real-time, active, mobile, parallel, distributed, secure, and spatio-temporal characteristics) for data warehousing and mining. The objective of this track is to provide a forum for researchers and practitioners to disseminate and exchange ideas on both the technical and managerial issues associated with data warehousing and mining.

Papers on pretty much every related topics are invited.

Database-less: the new trend

Following Tim Bray, Kunal Anand argues in favor of database-less systems. Or rather, of relational-database-less systems. Because really, what is a store of XML files if not some form of database?

Several years ago, I wrote a GPL posting board. I claim I wrote the first GPL Java-based posting board. Interestingly, it was later studied in a M.Sc. thesis for the type of multithreading I used. I grew bored with the project mostly because I don’t have time for web dev. work. One choice I made at the time was to use flat text files for the database.

The project became hard to manage at some point mostly because XML tools back then were primitive so I didn’t use them. So, serialization and data structures were hand coded. These days, with XML tools being what they are, I really can see people building production systems, very scalable ones, without any relational database. Something like a posting board is mostly static anyhow, so you could rather easily regenerate all needed XML files when new posts come in.

I bet that, actually, for moderately small projects, an XML solution is probably generally more scalable and flexible. It might be slightly harder to get started, but serving text files is so much simpler for the machine than requesting data from an SQL engine!

SQL is so passé.

Big schools are no longer giving researchers an edge?

I found a couple of papers making a claim that is likely to be controversial: a researcher could be anywhere in the world and still get as much research done. This would be new effect from around 1990 (birth of the web?).

I’ll just cite the juicy parts and let you decide.

The disappearance of positive university fixed effects suggests that, as far as research productivity is concerned, elite universities are indeed losing their competitive edge. Because of the reduced importance of personal interactions, one traditional advantage of elite universities – to act as a focal point attracting the smartest faculty – is at risk.

Reference: E. Han Kim, Adair Morse, Luigi Zingales, Are Elite Universities Losing Their Competitive Edge?, NBER Working Paper No. W12245, May 2006.

(…), we find that the spillover effects associated with location [near a research superstar] have declined markedly over time. (…) These results are puzzling. One would expect the diffusion of the internet to diminish the role of geographic distance as a factor influencing the extent of spillovers, but not to the extent of making physical proximity irrelevant, or a hindrance.

Reference: Pierre Azoulay and Joshua Graff Zivin, Peer Effects in the Workplace: Evidence from Professional Transitions for the Superstars of Medicine, working paper (2005)

(Original source: Stephen Downes)

Research on Computers and Games

A student asked me today whether he could do research on videogames. The answer was a strong yes. Of course, all topics are valid ones. (Yes, you could even do research on porn, though it might be embarassing at times.)

I decided to have a look at what journals and conferences there are in Computer Science:

  • Computers and Games is a workshop/conference held every two years. Some of the content seems to intersect machine learning and theoretical computer science. Next one will be held in 2008, I guess. Seems like the game of Go is still the big open problem out there. How boring is that? We claim that intelligent machine are around the corner, and we still can’t have a computer play a good game of Go?
  • Network and System Support for Games seems to be an active workshop which stresses multiplayer and networked games.
  • The International Journal of Intelligent Games & Simulation looks to be a dead journal (please correct me if I’m wrong!).

Overall, judging from the dedicated conferences and workshops, it does not sound like video games is a very good topic in Computer Science. Not something to really specialize in. Of course, I’m sure e-Learning, Machine Learning, Graphics, HCI, and TCS researchers do a lot of great research on video games, but few of them would describe themselves as “video game researchers”.

The key point is that the practionners are way ahead of academia on this one.

One paper I really liked while doing this research: Smart Moves: Intelligent Pathfinding.

Open Source Moodle picking up speed!

Just as BlackBoard sues because it has a patent granting it all rights over Learning Management Systems, the Open Source (GPL actually!) Moodle is pickup up speed. The Open University, arguably the largest online university in the world, has adopted it and so has our very own UQAM. Myself, I use another Open Source solution, SPIP, these days.

I’m old enough to recall, several years ago, when Linux was not a serious platform. When the GPL was a communist invention.

The joke is very much over. If you are selling software, and there is an Open Source alternative, be very worried. It might not look like much initially, but free software has a way to grow when you are not looking.

So, you think you are a big shot?

According to an anonymous friend of mine, the University of California at Riverside reported having received 1700 applications for one faculty position. I hope they have some kind of smart text mining application, because sorting out 1700 applications ought to be a hard task.

I submit to you that finding the best candidate, in such a setting, is an ill-posed problem. You cannot possibly tell me that under some sensible ordering of the candidates, one comes up on top.

Here’s a proposed randomized algorithm: find the best 10% candidates according to some sensible measure, then choose one candidate at random. I bet my algorithm is hard to beat and would be able to predict accurately how a selection committee works.

The Power of the Marginal

I sometimes disagree quite a bit with Paul Graham, but The Power of the Marginal is a brilliant essay. Mostly, I think that Paul is a great observer, but he sometimes goes a bit too far into drawing conclusions. For example, he concluded that Europe could never match the USA economically because they had to support different languages. That’s about as silly as saying that Microsoft programmers can’t compete against the Java programmers because they have to support several languages (VB, C#, C++, and so on). But, as far as describing what one needs to be successful, he is right on the money more often than not. I would describe him as a modern-day Balzac. In fact, I’m looking for a co-author to write a paper I’ll call “From Balzac to Paul Graham”.

Allow me to quote some important parts of his essay…

You are not a member of the right private clubs? Don’t despair:

(…) great new things often come from the margins, and yet the people who discover them are looked down on by everyone, including themselves.

If you are a nobody, you still have several edges over people in-the-know:

There are real disadvantages to being an insider, and in some kinds of work they can outweigh the advantages (…) : the selection of the wrong kind of people, the excessive scope, the inability to take risks, the need to seem serious, the weight of expectations, the power of vested interests, the undiscerning audience, and perhaps most dangerous, the tendency of such work to become a duty rather than a pleasure.

Being able to take risks is an asset:

Outsiders should realize the advantage they have here. Being able to take risks is hugely valuable. Everyone values safety too much, both the obscure and the eminent. No one wants to look like a fool. But it’s very useful to be able to. If most of your ideas aren’t stupid, you’re probably being too conservative.

Brainstorming and risking it all on a possibly stupid idea, is not so stupid:

Almost everyone makes the mistake of treating ideas as if they were indications of character rather than talent– as if having a stupid idea made you stupid.

You don’t have a small army working for you? You can use this lack of ressources to your benefit:

So if you want to beat those eminent enough to delegate, one way to do it is to take advantage of direct contact with the medium. In the arts it’s obvious how: blow your own glass, edit your own films, stage your own plays. And in the process pay close attention to accidents and to new ideas you have on the fly.

Don’t try to compete directly with the expert, become an expert in a “new” field:

The second way to compete with focus is to see what focus overlooks. In particular, new things. So if you’re not good at anything yet, consider working on something so new that no one else is either. It won’t have any prestige yet, if no one is good at it, but you’ll have it all to yourself.

This quote is golden:

The professor who made his reputation by discovering some new idea is not likely to be the one to discover its replacement.

This paragraph is just great:

So if you’re an outsider you should actively seek out contrarian projects. Instead of working on things the eminent have made prestigious, work on things that could steal that prestige.

Here’s Paul’s conclusion:

If I had to condense the power of the marginal into one sentence it would be: just try hacking something together.

Babylon 5 is back

It seems like Babylon 5 is coming back. New episodes will be released on DVD. I know I’ll be preordering them as soon as possible. Joseph Michael Straczynski (JMS) was the first, as far as I know, to produce real science fiction for adults on television. Here’s what he had to say recently:

Every 6 months, I get together with WB to discuss what to do something with B5. The DVD sales have raised over 500 million in revenue. Now, I produced B5s 110 episodes at about 90 million dollars. Somehow, B5 is still 50 million in the red. Every time I mention that to WB they say We made a good deal, huh? Anyway, they asked if I wanted to do a feature film but I declined mainly because I can’t yet picture structuring a B5 movie as long as [Andreas Katsulas] and [Richard Biggs] insist on staying dead. Maybe in a year or two I’ll be able to but right now I can’t do something big and those two roles will NOT be recast.

So I thought about it, and I suggested a bunch of short films. Little mini-movies or an anthology show set in the Babylon 5 universe. I pick a character and develop an hour-long story around that character. Stories that I wanted to tell during the B5 series but never had the chance to develop. They said, Okay. I said I wanted complete creative control. Do not change my words that I write, and I want that in writing. They said, Okay. And I want to direct. They said, Okay.

This project was green lit less than two weeks ago. Its going to happen. Production starts in September in Vancouver, Canada. Post-production will occur from October to February with a release of the first three anthologies in the second quarter of 2007.

It looks like the title will be Babylon 5: The Lost Tales.

Source: slashdot.