It's interesting that if you remove ~ullman from the site you get your first result returned at the very top of the search results again!
site:http://infolab.stanford.edu/ filetype:pdf view serializability
Browsing around Professor Ullman's page, I noticed that there were no (live) direct links to the original vs-old.pdf file that was at the top of your original search. I'm guessing that if you are restricting results to Professor Ullman's section of the infolab site, there will be no results returned, whereas there are likely to be other pages in the infolab that contain links to that particular document - which results in that pdf reappearing when submitting a less restrictive search.
Author's note (July 2016): The answer below was written in 2011, and is still working in Google Search. I have published new extensions that use a different method to remove the search result indirection, which works on even more Google sites and on mobile.
TL;DR: Don't track me Google is a user script Don't track me Google is an extension I made that allows you to copy normal URLs, while hiding the referrer to the sites you're visiting.
Installation
Explanation
I have written a method which replaces the link-modifying rwt function with a bogus function that can't be touched by Google.
By preventing Google from overwriting the rwt function, the link cannot be modified any more. This method depends on the Object.defineProperty method (Firefox 4+ and Chrome 5+). The fallback requires Firefox 2+ and Chrome 1+.
Firefox 2+
If you only want to remove the link-modifying behaviour, and not care about showing your search queries through the referrer, this GreaseMonkey script can be used:
(very non-strict @include rules using wildcards and the Magic TLD)
// ==UserScript==
// @name Don't track me Google
// @namespace Rob W
// @include http://*.google.tld/*
// @include https://*.google.tld/*
// @version 1.2
// @grant none
// ==/UserScript==
"use strict";
if (Object.defineProperty) {
Object.defineProperty(unsafeWindow,"rwt", {value: function(){return !0;}, writable: false });
} else {
unsafeWindow.__defineGetter__('rwt',function(){return function(){return !0}});
}
Google Chrome does not support Magic TLDs, so the closest you can get is *://*.google.com/* (repeat the rule, replace .com with other supported Google TLDs).
In Chrome, scripts have to be injected in the form of a <script> tag, because Content scripts are executed in an "isolated world".
Chrome & Firefox 2+ - Link to source code
On January 21st, 2012, I published an extended version, which includes a referrer-hiding method, so that others cannot see your search query. This greatly improves your privacy.
(Update from 2016: this referrer hiding is not needed any more in modern browser because of the referrer policy, which only shows the domain in the Referer header)
Best Answer
Google has a document to remove information.