666 and How Twitter Samples Tweets in Streaming API

After having played around with Twitter data for a while, I had a question: how Twitter samples the supposedly random tweets to send out through its sample streaming API?

I vaguely remember that it used to say "1% random sample" somewhere on the official documentation but I can no longer find that statement. So I decided to investigate the question by experiments. The result turns out to be far more fascinating than I expected (such as the appearance of 666).

This task would be trivial if I had firehose access but I do not. I initially thought of crawling tweets with ID's near the ones received in the stream sample and then do the counting. But I quickly found out how terribly inefficient that was: the tweet ids seem often to be very sparse. Then, thanks to Twitter's commitment to open source, I found their tweet ID generator on Github, wittily named snowflake (after a snowflake's large number of possible configurations, I suppose). In order to create a distributed solution to global unique ID generation, the essential idea of snowflake is to use timestamp and unique worker ID together to ensure uniqueness in an independent manner.

The first thing I noticed in snowflake is that whereas the 'created_at' property of the returned JSON tweet objects provides timing information at per-second resolution, one can recover per-millisecond timing information from snowflake! With this more precise timing information, some intriguing pattern emerges from the tweets in sample stream: within each second, all received tweets fall within a 10-millisecond-wide window. So we get 10/1000 = 1% of the millisecond timestamps which translates to roughly 1% of all tweets (assuming good randomness in tweet creation time) confirming the claim in my memory. But the surprise does not stop there, that sampling window is the same for every second! It is fixed exactly between the 657th and the 666th millisecond. So there is the 666 in the title. I wonder what is the story behind choosing 666 and this particular scheme of "random" sampling.

To make the post more complete, I should add that: 1. snowflake is used not only for tweet ID's but also direct message ID's. 2. before snowflake was activated sometime on 11/4/2010, Twitter used incremental ID's (the earliest existing tweet being 20).

To start playing with snow, you can use my little python module to create and melt a snowflake ID. (Indeed, you might soon find that not every tweet is delivered even in that 10 milliseconds window.)

If you find this interesting, leave a comment. We can also talk on twitter: @falcondai

The New (Time-of-Flight) Kinect Sensor and Speculations

In the official Xbox One release yesterday (2013/5/21), it is mentioned that the new Kinect sensor employs a time-of-flight camera to acquire depth image instead of using the Light Coding technology from the original Kinect (which is patented by PrimeSense). It amazed me because I heard about how expensive a time-of-flight camera is: SwissRanger 4000 (a popular choice in academic research) with 176x144 resolution at 50 FPS costs more than $4,000. So I started digging and found how ignorant I am to the recent development of the field.

To understand how time-of-flight (or TOF) cameras acquire a depth image, its Wikipedia page is a good place to start. The basic idea is that you need to measure the round-trip time (RTT) of the photons that are emitted by the sensor and reflected back. Given the speed of light being 3x10^8 m/s, the sensor would need the precision to measure 6 picoseconds difference in time to measure 1 millimeter difference in depth (1mm is the best precision the original Kinect could achieve). This high precision requirement, i.e. high frequency RF, makes the chip and circuitry design more challenging and costly. The surprise for me is that 3DV Systems (and Canesta) seemed to have found a way to lower the cost drastically and planned to release a RGB-Depth sensor, called ZCam, for under $100. (But before 3DV could sell it, the company was bought by Microsoft.)

Let's venture deeper into the hardware. Thanks for WIRED Magazine's exclusive report, we can see the performance and internals of the new Kinect sensor.

We can see from the picture of the circuit board that the three crucial components, RGB camera, infrared (IR) sensor, and IR illuminator, not unlike the original Kinect except that the IR sensor and illuminator are no longer exposed.

The external of the new Kinect sensor unveiled with Xbox One

Photo of the internal of a new Kinect from WIRED with labels added by me

Photo of an original Kinect sensor with components labeled. 

Thus the IR sensor and RGB camera are still separated (also confirmed by the different field of view when switching between the two streams in the WIRED video: http://youtu.be/Hi5kMNfgDS4?t=5m27s). If the sensor can capture both RGB and IR simultaneously from the same sensor (or just switching quickly between the two at 60Hz/60Hz or 30Hz/30Hz), texture mapping alignment in KinectFusion type of application would get better.

In case you wonder, the reason why I argue that the IR illuminator is the big rectangular block to the left of the IR sensor (instead of the other way around) is because the active IR image shows shadow due to IR illumination on the left but the screen we see is a mirror image: http://youtu.be/Hi5kMNfgDS4?t=5m8s. This shows that the IR illuminator is on the left to the IR sensor (which by the way should have a lens like the exposed RGB camera).

Comparing to the original Kinect, the most noticeable improvement of the new Kinect is the almost shadow-less depth image (see video http://youtu.be/Hi5kMNfgDS4?t=37s) due to the closer placement of IR sensor and illuminator. In fact, TOF technology allows for more flexibility with the illumination placement and design (thus better depth image). For comparison, google "kinect shadow" and take a look at the images.

Looking forward, the natural question to ask is when will depth sensing technology go mobile? Canesta seems to have some prototype for product can fit into the form factor of a phone: https://www.youtube.com/watch?v=5_PVx1NbUZQ and the video is two years old.

The trail that led to this new design of Kinect sensor is clear in retrospect. Microsoft acquired 3DV Systems and Canesta a few years ago which have both worked on TOF technologies extensively. The acquisitions obviously clear up some patent concerns for Microsoft (Bye, PrimeSense...). The down side is that we, as developers and consumers, might not see a more open-source friendly alternative with similar technology anytime soon. And we would have to rely on Microsoft to release good SDK and live with Windows when using the new Kinect in commercial applications.

Visualizing Geo-location Data with Google Map

Visualizing geo-location data is often more involved than other types of data because you probably want to put them into the context of places instead of just latitude-longitude values. There are many solution to this problem and mine might not be the best or the easiest. Please share your thoughts in comments if you have a better solution. So my solution is to place your data on Google map with their static image API: it can provide street views too!

Using Google Map Static Image API
To illustrate how easy this is, I will use some examples as well as links to the relevant entries in the reference. The basic idea is that all data (and other parameters) are passed in a request to Google in the URL string and then the rendered static image will be returned as a response.

Marking locations
This self-explanatory URL will give you a map with four lat-long pairs (41.791421,-87.598077), (41.791391,-87.599692), (41.790013,-87.599676), (41.790021,-87.599193) marked on a map:
http://maps.googleapis.com/maps/api/staticmap?size=800x800&markers=41.791421,-87.598077|41.791391,-87.599692|41.790013,-87.599676|41.790021,-87.599193&sensor=false

which will return the image below:

The basic syntax for the parameters is: 

markers=[markerStyles|]markerLocation1| markerLocation2|...

For more details, please consult https://developers.google.com/maps/documentation/staticmaps/#Markers

Marking a path

To link up the lat-long pairs marked in the previous section, simply substitute "marker" with "path": 

http://maps.googleapis.com/maps/api/staticmap?size=800x800&path=41.791421,-87.598077|41.791391,-87.599692|41.790013,-87.599676|41.790021,-87.599193&sensor=false 

which will return the image below:

For more details, please consult https://developers.google.com/maps/documentation/staticmaps/#Paths

Note

1. You can apply different styles (e.g. color) to paths (or markers) to discern multiple paths in one image.
2. Since there is often a limit on the length of request URL, you might need to squeeze your lat-long pairs in by encoding them: https://developers.google.com/maps/documentation/staticmaps/#EncodedPolylines. 
3. You can also have both markers and path at once by concatenating the parameters like such:  http://maps.googleapis.com/maps/api/staticmap?size=800x800&markers=41.791421,-87.598077|41.791391,-87.599692|41.790013,-87.599676|41.790021,-87.599193&path=41.791421,-87.598077|41.791391,-87.599692|41.790013,-87.599676|41.790021,-87.599193&sensor=false
4. You can use addresses instead of latitude-longitude pairs: http://maps.googleapis.com/maps/api/staticmap?size=800x800&markers=Chicago|DC|San%20Francsico&sensor=false