Integer representation of dates

For a system at work, I needed to represent dates and times as integers. An integer representation is required because we need to import the data into a search index so we can efficiently perform point and range queries. The search system only supports range queries for integer types and one of our main use cases is querying based on a date range. Further, the system does not have a specific time data type, it just supports signed integers of 1, 2, 4, and 8 bytes. So the problem is how should we represent a date or time as an integer?

First, lets make the requirements more explicit. The input data comes is a JSON feed with ISO 8601 formatted strings for date and timestamp fields. Whatever representation we choose should be able to represent the full range of dates from the input including %Y, %Y-%m, %Y-%m-%d, and %Y-%m-%dT%H:%M:%S (formats specified using the notation for strftime). In addition, it is preferable if the representation is easy to use for a person, i.e., I would like to be able to encode a known date without needing a program.

Problems with Unix Time

The obvious first question is can we just use Unix time? It is well known and widely supported, but there are a few problems trying to use it for our application.

The first problem is that it has a limited range. If we use a 32-bit integer we run into the year 2038 problem. Right now we don't really care about dates that far in the future, but we do care about historical dates so the year 1901 problem is an immediate concern. This problem is easily solved by using a 64-bit integer giving a range of 1970 plus or minus around 290 billion years. We can afford to be that short-sighted.

The second problem is for some fields we do not know the precise timestamp. We only know a particular year, month, or day. Somehow we need to represent these dates as being distinct from a precise date. For example if all we know is that something occurred in 1970 we don't want to encode it as 1970-01-01, because now we can't distinguish it from something that we knew happened on January 1, 1970. Unix time uses all of the bits already so there is no room to represent these vague dates.

A third problem is that it is quite cumbersome for a person to figure out the unix timestamps for a given range. Say I want to find all entries within the year 1980, I would need to compute the unix timestamp values for the beginning (1980-01-01T00:00:00 is 315532800) and end of the year (1980-12-31T23:59:59 is 347155199). This is trivial to code, but for a person doing it manually it is a pain.

The second problem is the killer, Unix time is not an option. The other issues are annoying, but we could live with them, especially considering the benefits of using a representation that is common and widely supported like unix time. So, what is the alternative?

Concatenated Fields Representation

This is a representation I've seen numerous times, but I wasn't able to find an official name or spec for it. The idea is pretty simple, we have a date represented as %Y-%m-%dT%H:%M:%S, we just remove the punctuation symbols and use the values as digits so we get the numeric value %Y%m%d%H%M%S. The first thing that becomes apparent is that we need an integer type that can support at least 14 decimal digits (4 year + 2 month of year + 2 day of month + 2 hour of day + 2 minute of hour + 2 second of minute = 14 digits). If we only care about the date we need at least 8 digits and for just the time we need 6 digits. A 16-bit signed integer as a range of -32768 to 32767 so we need at least a 32-bit integer. The table below shows the max value for 32 and 64 bit signed integers using this representation for a time, date, and datetime.

	32-bit max	64-bit max
Time	23:59:59	23:59:59
Date	214748-12-31	922337203685477-12-31
DateTime	too small	922337203-12-31T23:59:59

For a time or date a 32-bit signed integer is more than enough. Time in particular is limited so the max value will be 23:59:59 and using 64-bits provides no value. For date and datetime types the additional room can be used to expand the range of years supported. However, even with 32-bit integers the date type can works through the year 214748 which is more than enough for our use cases, but if needed 64-bits will get you past the year 922 trillion. For datetime a 32-bit integer is too small for 14 decimal digits. A 64-bit value will provide support past the year 922 million, and more importantly it covers the full range of the 32-bit date.

How does this fit our requirements? It covers the full range of time values that we expect to get in the input. Vague dates that are missing the day and/or month can be encoded as %Y0000. The zeros are not valid for the month or the day of month so we can clearly distinguish from more specific dates. This format is also pretty easy for a human to use. So it fixes the problems with unix time, but have we added any new problems?

Yes. Probably the most annoying problem is that not all values are valid. For example the date 19701332 is nonsense. There is no 13th month or 32nd day of a month. This representation makes it really easy to have values that are complete garbage. In fact, most of the distinct values for the integer representation will not be valid dates. The table below shows the percentage of the distinct values that are valid:

	32-bit max	64-bit max
Time	0.002% (86,400 of 4,294,967,296)	0.000000000000468% (86,400 of 18,446,744,073,709,551,616)
Date	2.08% (89,335,584 of 4,294,967,296)	2.08% (383,692,276,733,158,848 of 18,446,744,073,709,551,616)
DateTime	too small	12.00% (2,213,609,288,860,213,248 of 18,446,744,073,709,551,616)

The second problem is closely related to the first. This representation wastes a lot of space and doesn't make good use of all the bits. For my purposes this is not a big problem, but if you are looking for a compact representation then this is a bad choice.

Finally, we cannot make use of the negative values. In the ISO 8601 representation the year can be negative to specify BCE dates. This approach cannot be used with this representation because the sign would apply to the entire value, not just the year, and that breaks the ordering. For example -0004-01-04 is earlier than -0004-12-30, but when represented as an integer -40104 is greater than -41230.

Summary

The concatenated fields representation is a user friendly way to represent common era dates as an integer. It is particularly useful if you need to support dates where only partial information is present, e.g., just the year.

Winter Solstice Lunar Eclipse

It was too cloudy where I was at to get a decent view of the recent lunar eclipse. Luckily William Castleman put up a nice time lapse video of the event:

Winter Solstice Lunar Eclipse from William Castleman on Vimeo.

Cloudstock Review

I just got home from attending Cloudstock and thought I would write up a brief review. Since the event was free and sponsored by a large number of companies, I was a little concerned that it would be a bunch of companies hocking their crap. There was a fair amount of selling and overall the conference was light on technical information, but a few of the presentations were interesting nonetheless. A full list of sessions is available on the cloudstock page though I don't see anyway to get access to the slides that were used. I think they were recording the sessions so maybe they'll be made available at some point.

Building a Scalable Geospatial Database on top of Apache Cassandra - Mike Malone (SimpleGeo)

This talk will explore the real world technical challenges we overcame at SimpleGeo while building a spatial database on top of Apache Cassandra. Cassandra offers simple decentralized operations, no single point of failure, and near-linear horizontal scalability. But Cassandra fell far short of providing the sort of sophisticated spatial queries we need. Our challenge was to bridge that gap.

This was the most interesting talk I attended. The main part of the talk was on how to use a distributed hash table, in particular Cassandra, as a spatial database. The key problem is how to support the needed types of queries including:

• Exact match: find a particular key
• Range: find all keys in some interval
• Proximity: find the nearest neighbors to a key
• Misc others: reasonable expectation of being able to adapt to new use cases

A typical distributed hash table works well for exact match on a given key, however, it is not particularly well suited to the other use cases. Cassandra uses a partitioning scheme similar to Amazon's Dynamo with the keys positioned along a ring. Furthermore, the partition function can be customized so that the keys will be ordered. For SimpleGeo they used a partition function that provided a Z-order curve. This approach allowed for simple range queries and preserves the locality for some points. They experienced two big problems though:

• Poor locality for some points. This is a general problem of the space-filling curves that some points in the n-D space will be close, but when following the curve will be much further apart. In practice, this means that some searches will be much more expensive than they should be.
• Non-random distribution of data. The default partition function will randomly spread out the data which avoids hotspots where many keys fall in the same bucket. By customizing the partition function to provide order it also led to a problem that the skew inherent in the dataset became a problem. In the presentation he showed a photo showing the distribution of lights and the clusters around cities. A similar photo is shown below of Egypt with obvious clustering around the Nile river.

To solve this problem they moved away from space-filling curves to something that looked like a kd-tree stored in the distributed hash. If I understood correctly each node in the tree is stored as an entry in Cassandra using the standard partitioning scheme. Exact match and range queries can be performed by standard tree searching and traversal with some caching to avoid problems with hot spots, in particular, the root node of the tree. Data skew can be accommodated by splitting a node when it gets to full. The nodes are stored using standard Cassandra so it avoids the customization that caused tricky problems with the ordering. Proximity queries are handled by first searching for the exact match and then checking the node to restrict the bound further. If the nearest neighbor is found within the same node and the radius is such that neighboring spaces could not have a closer neighbor, then we are done. If it is possible that a neighboring space has points that could match the query, then we go to the parent node and then to siblings until satisfied.

Overall, nice presentation and good progression though their various attempts and explaining the issues they encountered.

Teach a Dog to REST - Brian Mulloy (apigee)

It's been 10 years since Fielding first defined REST. So, where are all the elegant REST APIs? While many claim REST has arrived, many APIs in the wild exhibit arbitrary, productivity-killing deviations from true REST. We'll start with a typical poorly-designed API and iterate it into a well-behaved RESTful API.

Nothing spectacular, but he did have some reasonable advice for constructing APIs and some of the common problems they have seen. This presentation also had more of the sales element with the speaker frequently mentioning the apigee console for learning and playing around with APIs for popular services such as Twitter and LinkedIn. I personally found the speaker to be annoying, e.g. he had a schtick about not knowing how to pronounce idempotent methods that I'm pretty sure was an attempt at self-deprecation to help make the talk more appealing to a non-technical audience. The brief summary is:

• Be RESTful. The speaker seems to prefer RESTful interfaces over traditional RPC interfaces such as SOAP or JSON-RPC. The primary reasoning is that it leads to greater simplicity and fewer endpoints for the developer. His preferred interface is two URLs per resource: one for a collection, such as /dogs; and one for a specific element, such as /dogs/cujo. I liked his focus on APIs that are easy for developers to understand and to push for conventions that make it easier to reason about how APIs should work. If done right you can guess what the API will be without ever having to look at the documentation.
• Verbs are bad. Nouns are good. At first you might think he is a subject of Evil King Java, but it is not quite the same. The RESTful model is about managing resources and the argument is that the verbs are already provided as part of the HTTP Protocol. So really it is verbs as part of the URL are bad. URLs should refer to a noun.
• Plurals are better. Here he is referring to the name for collections and clearly stated that this point was just his opinion. I don't really have a strong preference, but I do agree with him that if a widely used convention was present, it would be much easier to guess what the URL should be for a given API. Plurals also do seem to make it clearer that the response would be a collection instead of a single item.
• Move complexity after the question mark. The basic idea here was that the messy parts of the API should be made query parameters to the URL. The justification is that there will be some mess and that other locations, such as HTTP headers, are more obscure and difficult to quickly hack together in a browser. Another good point I think he had is that you should try to make the API trivial to start using. The easier it is to play around with an API the more likely it is to get used.
• Borrow from leading APIs. This goes back to his theme about convention. By following other popular APIs it is more likely your API will be familiar to new developers looking at your system. He also mentioned that in his opinion LinkedIn was currently doing the best at designing clean easy to use APIs for their offerings.

One shortcoming that was brought out and emphasized during the questions at the end was he made no mention of error handling. Overall, ok but a 45 minute session was too long for this talk.

Your API Sucks - Marsh Gardiner (apigee)

We've learned the hard way that websites need great user experiences to survive. So why aren't we being this aggressive with API design? What are the deeper reasons behind why REST killed SOAP? And why aren't all API providers thinking about the truly important issues, making APIs that will be used by people? Come for the hall of shame and stay for the wake-up call.

Boring series of "don't do this" examples. At least the previous speaker bothered to explain why he was pushing for APIs to be a certain way. The speaker reminded me of John Hodgman, but without the humor. Waste of time.

Lunch

They had some pre-made sandwiches for the lunch. I don't make it into San Francisco that often so I decided to eat out instead.

Scaling Your Web App - Sebastian Stadil (Scalr)

Got app? Learn to scale it, with tricks for creating and managing scalable infrastructure on EC2 or elsewhere.

I came in late to this talk. The part I saw was him showing off their UI. Complete waste of time, I might as well have flipped through the tour on their website.

Inside MongoDB - Alvin Richards (mongoDB)

In this talk we'll describe and discuss MongoDB's data format (BSON), the insert path, the query optimizer, auto-sharding, replication, and more. The talk will be of interest to developers interested in MongoDB and looking to learn more about what's going on "under the hood", as well as anyone interested in distributed systems and the design decisions that go into creating a system like MongoDB.

Not a bad introductory overview. You could probably get the same information by spending an hour reading through the mongoDB documentation, but you wouldn't have easy access to someone for questions.

AWS Feedback Session - Jeffrey Barr (Amazon Web Services)

If you are an AWS user and want to ask questions or provide feedback, here's your chance. Senior AWS Evangelist Jeff Barr will be conducting an interactive feedback session on EC2, S3, RDS, and the other services. All of the feedback will be routed directly to the product teams.

This session was only really useful as a more direct way to communicate issues to Amazon. The speaker was quite knowledgable about the Amazon stack and its good to see they are eager to get customer feedback. One aspect that came up several times was the poor support for Windows. The two issues I remember were the long delay until new versions of Windows are available as to use and, one I found quite amusing, that if you create a VM snapshot of a Windows VM then apparently the admin password is changed in the original VM.

Hackathon

I skipped the hackathon.

Summary

Not bad for a free event. I heard from others that some of the sessions were worse about just being sales pitches than the ones I attended. Very little technical depth in most of the presentations.

Automatic Generation of Color Palettes

A problem I've had several times is how to automatically generate colors for use in graphs. The user will be able to select some set of items that should be included and I need to select colors for each item. The requirements are:

• The color for an item should be easy to distinguish from other items. Of course, it would also be nice if the colors looked decent, but from a functional perspective, the requirement is to be able to distinguish the items in the graph.
  
• I need to be able to generate an arbitrary number of colors and avoid a fixed color palette with a predefined number. For practical purposes the number will be limited by the ability to distinguish different colors, but it would be nice for the mechanism to scale gracefully as the number of items increases.
  
• The color of the background, for my purposes white, cannot be used.

When I examined a few tools, I found that most worked by having a fixed set of colors. My first attempt was to perform a naive increment of RGB pixel values. A trivial increment works well for shades of gray. This produces a palette like:

Hex	2	4	8	16
000000
0E0E0E
1C1C1C
2A2A2A
383838
464646
545454
626262
707070
7E7E7E
8C8C8C
9A9A9A
A8A8A8
B6B6B6
C4C4C4
D2D2D2

The problem is that grayscale can be difficult to distinguish with more than a few colors. That is why tools like gnuplot use line patterns and shapes. However, most of my use cases are for graphs shown on a color monitor so there is no need to limit to grayscale. What happens if we try a naive increment with color? My first attempt was to treat the color as a three byte integer and simply divide the desired number of colors to get the increment value. Looking at the palette below you can see the results are poor:

Hex	2	4	8	16
000000
0FFFF0
1FFFE0
2FFFD0
3FFFC0
4FFFB0
5FFFA0
6FFF90
7FFF80
8FFF70
9FFF60
AFFF50
BFFF40
CFFF30
DFFF20
EFFF10

After looking around for a bit I found that the HSV representation is fairly well suited for this problem. HSV stands for hue, saturation, and value. The color space is represented as a cylinder:

For more background the paper Color Spaces for Computer Graphics gives a good overview and discusses how the various color spaces were designed with respect to human perception of color. To generate a palette the saturation and value settings can be fixed. The 360^o for the hue can be divided by the desired number of colors and then we just increment the angle for each color. This technique gives a nice palette, but for more than around 8 colors it will be difficult for a person to distinguish some shades.

Hex	2	4	8	16
FF0000
FF5F00
FFBF00
DFFF00
7FFF00
1FFF00
00FF3F
00FF9F
00FFFF
009FFF
003FFF
1F00FF
7F00FF
DF00FF
FF00BF
FF005F

The Scala code I used for generating the palettes is shown below.

object Colors {

    import java.awt.Color

    def grayscale(num: Int): Seq[Color] = {
        // Truncate the full range of values to make sure we can distinguish
        // from the color white, i.e., (256, 256, 256).
        val range = 256 - 32

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta == 0) {
            throw new IllegalArgumentException(
                "grayscale can support at most " + range + " colors")
        }

        // Generate the sequence of colors
        (0 until num).map(n => {
            val value = n * delta
            new Color(value, value, value)
        })
    }

    def naiveIncrement(num: Int): Seq[Color] = {
        // Truncate the full range of values to make sure we can distinguish
        // from the color white, i.e., (256, 256, 256).
        val range = 0xFFFFFF - 0xFF

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta == 0) {
            throw new IllegalArgumentException(
                "naive increment can support at most " + range + " colors")
        }

        // Generate the sequence of colors
        (0 until num).map(n => {
            val value = n * delta
            new Color((value >> 16) & 0xFF, (value >> 8) & 0xFF, value & 0xFF)
        })
    }

    def hsv(num: Int): Seq[Color] = {
        // Range is 360 degrees for the hue
        val range = 360.0

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta < 1.0) {
            throw new IllegalArgumentException(
                "hsv can support at most " + range + " colors")
        }
        // Generate the sequence of colors
        (0 until num).map(n => {
            val hue = n * delta
            val h = hue / 60.0
            val x = ((1 - Math.abs(h % 2 - 1)) * 255).toInt
            val c = h match {
                case h if 0.0 <= h && h < 1.0 => (255, x, 0)
                case h if 1.0 <= h && h < 2.0 => (x, 255, 0)
                case h if 2.0 <= h && h < 3.0 => (0, 255, x)
                case h if 3.0 <= h && h < 4.0 => (0, x, 255)
                case h if 4.0 <= h && h < 5.0 => (x, 0, 255)
                case h if 5.0 <= h && h < 6.0 => (255, 0, x)
                case _ => (0, 0, 0)
            }
            new Color(c._1, c._2, c._3)
        })
    }

    def main(args: Array[String]): Unit = {
        if (args.length < 2) {
            println("Usage: scala Colors <palette> <num>")
            exit(1)
        }

        // Supported palettes
        val palettes = Map(
            "grayscale" -> grayscale _,
            "naive"     -> naiveIncrement _,
            "hsv"       -> hsv _
        )

        // Generate colors and print
        palettes(args(0))(args(1).toInt).foreach(c => {
            println(c.getRGB.toHexString.toUpperCase.substring(2))
        })
    }
}

Montana Thunderstorm

Cool photo of a supercell in Montana:

How Cats Lap

It's a bit humbling how little we know about common activities. A recent article in Science talks about how cats drink. This is a topic I have never given much thought, but it seems like something that would have been studied and understood a long time ago. It turns out it has been an open question for some time. A 1940's short film called Quicker'n a Wink captured a cat drinking using one of the earliest high speed cameras. Luckily the video is now on YouTube:



Before reading the paper or seeing the video included above, I tried to think about how lapping would work. I guessed that a cat would curve the tongue and make a cup to carry the water into the mouth. It turns out this is how dogs drink as shown in the video below:



Cats use a different technique. Like dogs they curve the tongue back, but cats barely touch the surface of the water with their tongue and then quickly withdraw the tongue letting the inertia create a stream of water into the mouth. For more information see:

• Supplementary videos for the paper
• Ed Yong's take
• Jerry Coyne's take

Jefferson Memorial: panel three contextomy

A friend on facebook recently posted the following quote attributed to Thomas Jefferson:

God who gave us life gave us liberty. Can the liberties of a nation be secure when we have removed a conviction that these liberties are the gift of God? Indeed I tremble for my country when I reflect that God is just, that his justice cannot sleep forever.

Given Jefferson's record on religion, I was curious what the context was for this quote. I quickly found that this was a truncated version of the quote from panel three of the Jefferson memorial. The full quote is:

God who gave us life gave us liberty. Can the liberties of a nation be secure when we have removed a conviction that these liberties are the gift of God? Indeed I tremble for my country when I reflect that God is just, that his justice cannot sleep forever. Commerce between master and slave is despotism. Nothing is more certainly written in the book of fate than that these people are to be free. Establish a law for educating the common people. This it is the business of the state and on a general plan.

However, what I found really surprising was how this quote was created. It was created by taking snippets from 5 different documents authored by Jefferson including: A Summary View of the Rights of British America, Notes on the State of Virginia Query XVIII, Jefferson's Autobiography, a letter to George Wythe, and a letter to George Washington (toward the bottom of image 21, though the snippet is often shown as a quote I couldn't find a text version of the full letter so I linked to the scanned version from the Library of Congress). The other panels do not seem to be quite as bad, but are also quote mined from various sources.

Why? Quote mining to come up with some new statement doesn't serve as a memorial to Jefferson or his ideas. I could comb through his writings and combine a collection of snippets to express just about any view. It's possible he would have agreed with the sentiment, but the actual statement only reflects the views of whomever cobbled it together. Truly disappointing.