Notes on the history of the map tile
Web map tiles—the storing of geospatial data at different zoom levels in x/y/z indexed squares of raster (and later, vector) data for efficient storage and transmission of digital maps—are, despite their seeming simplicity, I think one of the most significant developments in geospatial software history. Tiling transformed the user experience of digital maps from one of tedious clicks-and-reloads to one of fluid, dynamic exploration. It made digital maps feel spatial, an interface that one literally moved through and across rather than a static image. This interactivity changed what everyday people expected of digital maps and likely were the gateway for a lot of people even getting interested in maps and geographic knowledge. (I know this was my experience!)
Despite their importance, I’ve found it weirdly hard to identify the genesis of digital map tiles. In general, credit tends to be given to Google Maps (or to Where2 Technologies, the 4-person company they acquired that became Google Maps) because they 1) were the first to implement raster tiles in a high-profile way and 2) they filed a patent for the method. But I haven’t found any interviews with or writing by any of the other original Where2 founders that actually gets into how they’d landed on the tile method.
This is probably not because the Where2 founders are humble dudes but because the concept of tiling map data was already out in the world, tried out by lots of people in different contexts.
Pre-web GIS tiling: there from the very beginning
The idea of breaking up a map into squares or rectangles isn’t a huge theoretical leap when looking at a print map with graticule lines that effectively do the same thing, and the idea of individual sheets of maps adding up to a larger world map was central to the ill-fated International Map of the World project chronicled by William Rankin in After The Map. So it’s maybe not surprising that methods for breaking up map data into “tiles” appeared in what’s maybe not the first “actual” Geographic Information System, but certainly the first project to call itself that.
In an essay about the Canada Geographic Information System (CGIS), developed by Roger Tomlinson in collaboration with IBM for the Canadian government, Tomlinson mentioned its use of a tile-based data structure (emphasis mine):
A key role was played by Guy Morton, who designed the data structure now known as the Morton Matrix, which was the underlying strength of the system. It involved creating “frames” to hold data in the largest units that could be conveniently processed by the computers available at the time. This concept was the origin of “tiling” employed in most modern GIS.
The Morton Matrix was known in France as the Lebesgue curve, after a French mathematician who first explored the concept in 1904, and is better known today as the z-order curve. Morton wrote up the method in a paper about the CGIS that currently can be found behind an expired SSL certificate on an old IBM server (I’m posting the PDF here for the sake of convenience). The logic of this data structure was partly driven by the material conditions of data storage, as Tomlinson explained:
The arrangement of the unit frames was crucial to operating efficiency of the system. Random access discs were not available in the early stages of system design, and searching a magnetic tape for data was a time-consuming sequential process. To overcome this constraint on the system’s efficiency, it was desirable that frames close together in the sequence should refer to locations close together on Earth’s surface and, similarly, that records from close locations on Earth should have the least possible separation in a sequential file.
If you’re reading this and thinking “huh, this kind of reminds me of quad trees”, congratulations: they’re very related! Although the 1974 paper by Raphael Finkel and J.L. Bentley doesn’t cite the z-order curve or any of its other variant names, it is definitely imagining geospatial applications: the “clear example” used in their paper for a two-dimensional data structure appropriate for quad trees is “cities on a map.” A 1984 paper out of the computer science department of the University of Maryland, College Park is the oldest citation I’ve found of a proposed use of quad trees in a GIS as a way of storing geospatial data. The paper notes that the research was supported by a contract with the US Army Engineer Topographic Laboratories, which seems like a worthwhile thread for future exploration.
I’d be surprised if the Where2 guys were reading any of these specific papers as they developed the product that became Google Maps, but the quad tree as a thing in computer science was pretty well established by then so they probably didn’t need to go that far back in the literature to land on this idea.
Patent rabbit hole
One way to figure out where the Where2 guys came up with this idea is to look at the citations in the 2005 patent filed by Google Maps for a “digital mapping system.” There are lots of patents cited, and it would probably behoove me to look more closely at all of them but two that immediately stand out are “Tiling of object-based geographic information system (GIS)”, a patent filed in 1998 by a company called PRC Public Sector, reassigned in 2009 to Northrop Grumman Public Safety Inc (👀 is appropriate here) and “Method and apparatus for distributing and displaying maps electronically”, filed in 2000 by a video games company called WildTangent.
The thing about patents is they aren’t always filed to protect already-existing technology: sometimes they’re just filed so someone can claim they thought up some method first (for example, the infamous “yelling ‘McDonald’s’ at the TV” patent). I wasn’t able to find evidence that either of these companies actually had or sold mapping or GIS products that might have used these tiling methods. This doesn’t mean those products didn’t exist or weren’t prototyped and abandoned, but anything I say about what these companies used this technology for is only speculation.
PRC Public Sector
The art from the PRC Public Sector patent is pretty visibly implementing a map tile structure:
But what was PRC Public Sector, and why was it absorbed into Northrop Grumman? Once you sift past search results about the People’s Republic of China, the most common PRC Public Sector hit are reports on an apparently kind of shitty police dispatch system—here’s one a from the city of San Jose, but there’s articles about Fairfax, Virginia police frustrated with the product as well.
The San Jose report calls the company “Litton PRC Public Sector”, which led me to Litton Industries, a defense contractor (among a million other things) acquired by Northrop Grumman in 2001. Litton Industries bought PRC from Black and Decker in 1995; Black and Decker acquired the company in 1989 when it bought Emhart, described in an article about the acquisition as “a diversified manufacturer of goods ranging from padlocks to shoemaking equipment.” (I have probably unwarranted fond feelings for this kind of deranged “what is it you even do” mega-corporation of yore than I do for today’s behemoths, maybe because the old companies paid more taxes and probably didn’t have some extractive surveillance agenda underlying their entries into totally unrelated markets.)
Emhart’s acquisition of PRC in 1986 for $210 million “stunned” industry analysts in 1986 according to a Washington Post article I found in ProQuest. PRC (an anodyne acronym for an anodyne name—Public Research Corporation) was founded in 1954 by former Rand researchers as a McLean, Virginia-based “professional services company” and had contracts across the federal government. At the time of the acquisition PRC had been losing money and been the subject of a critical report by the US Commerce Department over cost overruns on a project to automate the US Patent and Trademark Office. (Yes, it is cute that this query started and ended with patents.)
So at the time that PRC Public Sector employee Frederick Bryan Davies submits this tiles for GIS patent application (incidentally, Davies is attached to two other GIS patents from the same time period), the company was a subsidiary of Litton, and was probably on its way to being acquired when the patent was granted in 2001. I guess a re-org in Northrop Grumman years later led to the 2009 reassignment.
Given their work on police communications and dispatch, my best guess is that PRC Public Sector was angling to get into (or actually did get into) the crime mapping/GIS for cops market—a market that was more or less invented in the 1994-1998 window when Bill Bratton first implemented data-driven, crime-mapping focused policing methods in the NYPD and then evangelized those methods both in the media and as a consultant to police departments after Rudy Giuliani fired him in 1996.
WildTangent
WildTangent is still a going concern publishing games, though they were acquired by a German company called Gamigo in 2019. Their Wikipedia page is pretty thin but does mention their apparently “not very evil” web driver that was maybe spyware and that they were sued alongside Hulu (??) by a company that honestly sounds like a patent trolling situation but I guess wasn’t.
A Wall Street Journal article from 2000 found on ProQuest gives a little more detail: the company was founded by two former Microsoft guys who developed a product to “enable users to view high-speed three-dimensional animations over the Internet”—this is, I am assuming, the not very evil web driver.
The art attached to this patent doesn’t suggest a game-related use case, so maybe its author (WildTangent co-founder Jeremy Kenyon, about whom it is really hard to find any further information) might have just had the idea and patented it in a “maybe I’ll do this” sort of way? Or maybe they had some other non-game product idea they just didn’t get around to? It makes sense that a company probably rooted in doing graphics engineering for the web might look toward other graphics-intensive media they could problem-solve for, but I can’t find anything that indicates they actually implemented it. Their patent cites the PRC Public Sector patent, which it mainly differs from because it includes a server-client architecture for transmitting the tiles.
But also: a guy at Bell Labs first proposed web map tiles in 1997??
I’m honestly a little embarrassed that I hadn’t tried this before, but a dumbass Google Scholar search for mentions of map tiles and geographic data between 1995 to 2003 led me to a paper by a Bell Labs guy named Michael Potmesil that was presented at the sixth (!) annual World Wide Web Conference in 1997. The website of this conference appears to just be a subfolder of the personal website of a Swiss guy who worked as the webmaster for ETH Zurich (??), the upshot being that the paper is freely available online. It was also later published in a journal with the thrilling name Computer Networks and ISDN Systems. The title of the paper is a little more enthusiastic: “Maps Alive: viewing geospatial information on the WWW.”
Potmesil details two map-based applications that he describes as “geographical browsers”, one 2D and one 3D, both using quad trees in a tile-based architecture. Because this is 1997 and Javascript standardization is still being hashed out, the applications proposed are Java applets—which, charmingly, Potmesil proposes as modular applications with specific geographic programs he calls “mapplets” (get it, map and applet). It’s a pretty impressive paper for its time, essentially laying out a framework for methods that wouldn’t become common in the browser for nearly another decade. Look at this representation of tiles!
Potmesil was a graphics engineer, he also worked on something at Bell Labs called “the Pixel Machine.” His citation for using quad trees in a geographic application is Hanan Samet’s The Design And Analysis of Spatial Data Structures. I haven’t been able to track down contact information for him; I suspect the Bell Labs email address on the paper is defunct and that at this point he’s probably retired.
The 2005 version of Google Maps’ patent doesn’t cite Potmesil but an I guess updated patent application submitted in 2010 does, which to me suggests they maybe didn’t know about the paper when they submitted the patent. The PRC Public Sector application doesn’t cite it either, but that makes sense since it’s proposing something more like a desktop GIS than something for the web (side note, it’s very cute seeing it written out as “WWW” in Potmesil’s paper but I do think it’s funny that the acronym has more syllables than the actual phrase “World Wide Web”). Kenyon doesn’t cite it either.
It doesn’t seem super-likely to me that Potmesil’s work was deliberately or knowingly omitted. Given widespread prior research on quad trees and geographic data storage it would make sense that a bunch of different researchers independently converged on the idea of tiled data storage, and I don’t get the impression that the Sixth World Wide Web conference and Computer Networks and ISDN Systems were high-profile places for publishing research. Still, I am disappointed that I can’t find any contact information for Potmesil—I did DM a colleague of his credited in the paper on Instagram, we’ll see if that leads to anything? I would love to know what he was thinking when Google Maps launched, seeing a modern implementation of stuff he’d been thinking about nearly a decade before.
In conclusion: no one guy “invents” the map tile, that’s never how it works
Crediting the brothers Rasmussen and Google Maps with the map tile is sort of like crediting Steve Jobs and Apple for the smart phone: understandable but formally imprecise. Both are examples of a company taking technologies and user experiences that had been speculated on or experimented with and transforming them into the seemingly obvious, inevitable Way Things Are Done. I think it’s important to acknowledge the prior work on the tile method even if we can’t always draw a direct line from it to Google, partly because it’s cool to see people having these forward-thinking ideas way before they were mainstreamed into regular people’s lives and because the myth of genius invention by one big company or one cool guy is sort of soul-corroding.