Gordian Labs Company Blog

Discrete Cosine Transforms and Route Matching

Andy Carra — Mon, 10 Aug 2009 18:28:50 +0000

On of the big improvements we’d like to make to Runometer is adding the ability to automatically detect and match routes. When people use simple pedometers (i.e. the nike/ipod dongle), routes need to be assigned manually… but when people use devices that record and upload route data as well as run data, we’d like to be able to determine when the routes are probably the same. As nice as it is to have our routes statistics climb in tandem with runs, most runners have a fixed set of routes they use during the course of their training.

Thinking about this issue, we don’t necessarily want to match ALL similar routes – we need a variable degree of precision based on the route length, and I think we need to give users a chance to determine whether or not they want their routes to match. The following is a series of approaches we’re evaluating, and the reasons behind doing so.

The bounding box (a.k.a. the naive approach):
Simply; if you select a tolerance for a bounding box, and only try and match a list of runs within that box, you can probably do pretty well. Our data model relies on using the bounding box for routes already (it’s generated on creation), so we’re not paying any overhead for this. In addition, MySQL’s spatial extensions are really good at working via bounding boxes* – MBRInterects and MBRContains. This is almost computationally free, and we can match these boxes very quickly on route upload, without wasting much time or compute power… but it has some major shortcomings. Our counter-case against using bounding rectangles will be laps around a track: the bounding box for one lap or 40 is exactly the same, although these are clearly very different runs!

* in fact, even MySQL’s more sophisticated OpenGIS implementation calls such as “contains” are only implemented with bounding boxes at the time of this writing (MySQL 5.1): see this note (http://dev.mysql.com/doc/refman/5.1/en/functions-that-test-spatial-relationships-between-geometries.html)
Bounding box and total Distance:
Ok, let’s try not to overcomplicate this problem. We can get rid of the issue with bounding boxes by simply adding distance. We don’t even need to rely on MySQL’s spatial functions for this… we get a route length and a run distance automatically on each upload, and store them in the database! This solves the countercase for bounding boxes alone, but is still fragile in some other ways, that also plague bounding boxes: it doesn’t say anything about the actual route! Specifically, configuration is an important issue: just because it fits in the same box, and matches the distance doesn’t mean the runs are even remotely similar. Consider living next to a park, but having multiple routes through the park, depending on mood, scenery, and time of day. It looks like we’ve disqualified this solution, too. Is it still “good enough” to give our users a chance to pick the right route from a list of thumbnails and names? Since some of our users now have hundreds of routes, I’m guessing “no.” At the time of this writing, my latest run matches 19 other runs using this solution, and some of them are very clearly wrong, and 10% of length disqualifies the “best” copy of the run I have on record, since my GPS frequently cuts out during a certain corner of the run.
The Big Guns: The Discrete Cosine Transform and Fast Fourier Transform
Since I learned about the Discrete Cosine Transform (DCT) and the Discrete and Fast Fourier Transform (DFT, FFT), I’ve been amazed at what versatile tools they are. If you listen to digitally compressed music, or watch video on-line, or view almost any digital image, you’re almost certainly a direct or indirect beneficiary of this technology. These two technologies are largely interchangeable in application, and they’re both from the digital signal processing world. For our purposes, we’re going to use DCT because of the convenience and efficiency of a specific library, but I urge you to read further about each; your mileage may vary!
- A bit of Background
  Signals and The Frequency domain
  What all the techniques mentioned here do is simple at a fundamental level: we take a signal (a change in frequency over time) and convert it into the frequency domain: that is, we assign a set of coefficients to the frequencies within the signal over a fixed window in time (a finite number of data points). In the case of the DCT, this means that we assign coefficients to each of a set of pre-defined cosine functions which oscillate at different frequencies, based on the behavior of the points in the “time” domain. Sound confusing? Don’t sweat the math – just understand that what we’re getting is a simplified model of how something changes over time organized by the most-defining behaviors first. The more compute power we spend extracting coefficients, the more accurate the model will be.
- How this Applies to Routes
  First of all, change in position over time is a signal. Our GPS traces and hand-drawn routes are rough quantizations of continuous routes that we want to match to one-another, and the two-dimensional images we generate of the traces are also well-suited to individual DCT application of the DCT, without requiring multiple time windows. The change in image pixel values, or the change longitude and latitude will match from run to run on the route, up to a number of significant coefficients – a threshold we define as significant. We can compare the differences between the coefficients of routes to a fixed precision, and use statistical techniques like Sum of Squared Differences (SSD) to determine “how different they are.”
Implementation
Since we don’t want to waste more time running this expensive comparison than necessary, we’ll only perform this check on routes which have distances within a certain tolerance of the current route by the first two techniques (15%, which might be overoptimistic, considering what a mess most of my GPS traces are), and which are contained within a box 10% larger on each side of the current route’s bounding box. This saves us the heavier processing time of DCT against runs which are clear misses. For our first implementation, we’ll use the route thumbnail images we use to give users a “glyph” of the run for processing, since they provide a discrete version of the run, and automatically normalize the route to a fixed image size. Once we’ve pared the list down using the first two techniques, we iterate over them and compare their DCT coefficients. If the SSD is beneath our chosen threshold, we propose the match to the user!

more reading:
http://en.wikipedia.org/wiki/Discrete_cosine_transform
(wikipedia: an overview)

http://www.exampleproblems.com/wiki/index.php/Discrete_cosine_transform
(basic reading)

http://140.134.132.124/dspace/handle/2377/1037
(using DCTs for handwritten chinese character recognition!)

Using MySQL Fulltext Search Engine with Data Driven Web Applications – Part II

John Wolthius — Tue, 11 Dec 2007 20:12:30 +0000

In part I, we discussed the basics of implementing a simple search functionality using the MySQL fulltext search index. In this post, we will build on those concepts, exploring paging, sorting, mixed data search, filtering and InnoDB.

Paging and Sorting

Often our search results are far too large to fit on a single results page. Wrapping the results in a paging interface is the obvious solution to this. Define a page size, divide up your results by this page size to get pages, and then use the limit and offset syntax in your SQL statement to query the results for any given page.

select id, description from product_descriptions

where MATCH(description) AGAINST ('"+$processed_search+"' IN BOOLEAN MODE)

limit "+$page_size+" offset ("+($page*$page_size)+");

In this code fragment, we add two variables, $page and $page_size. You determine the number of pages by dividing your total search resultset size by the pagesize, rounded up. This will give you the basic building blocks of a search result paging system.

Problems
There are a few problems with the simple example above. The main problem is that we are redoing the fulltext search every time we change pages. Depending on your application, the data we are searching can change, altering your result count and paging math and causing us to lose results in the cracks. It is also rather costly to both do the count of total search results as well as repeat the fulltext search each time we change pages. What we really want to do is perform the search once, save the results in a temporary table, and then do our paging and sorting on an unchanging snapshot of the results at the time you executed your search.

Search Snapshot Tables

We will need two new tables to store our search snapshots: Snapshots and snapshot_results.



create table search_snapshots

(

id int primary_key,

search_text varchar(1024) not null,

search_size int not null default 0,

search_date datetime not null default now()

);

create table search_snapshot_results (

search_snapshot_id int not null,

product_id int not null);

With these tables in place, we can do a better paging implementation. Instead of running the search query and displaying the results on our webpage for every page load, we instead do the following:

On search execution, insert a new record into search_snapshot table. insert the search text (thats all you have) and store the ID of the record created.
run your search query, but instead of just doing a normal select, do a select into statement, populating the search_snapshot_results table with the search id from step 1 and the product_id. note the rowcount of this statement
update the search_snapshot table with the result count from step 2.
forward the user to your search pages, but instead of running your fulltext search, instead load your results from the snapshot table, using the search_snapshot_id as your primary key, and joining search_snapshot_results to products to retrieve your content.

You now will have a faster and more reliable search result set to page over. Depending on your application, you can keep these snapshots around so that links into your search results will continue to work, or you may periodically delete the snapshots and results after a timeperiod has passed.

Sorting these results is now a simple matter as well, by simply adding order by statements to your query of search_snapshot_results.

General Purpose Search Table

You probably noticed that the search_snapshot_results table only had a key reference to the Product table, as opposed to having all the date right there. With a small modification, we could use the search_snapshot_table to store the search results of any content (or mix of content) that you may have in your database.



create table search_snapshot_results (

search_snapshot_id int not null,


result_type varchar(16),

result_frn_id int not null);

This new table can store results from any search you execute, you just need to specify a label in the result_type field to describe what table you should join to through result_frn_id. With this in place, you can reuse your filtering and paging code for any search type you’d like. The only thing you need to do is modify the join when rendering your results to match the result_type.

InnoDB

One of the big annoyances of the Fulltext search system is that it is currently MyISAM only, no InnoDB support. To get around this, I uses the following trick. Its not the most elegant or efficient solution, but it works. You may mix InnoDB and MyISAM table engines within a database, so I create the following table as a MyISAM table.

create table text_index (
id int unsigned primary key,
type varchar(16) not null,
frn_id int unsigned not null,
content LONGTEXT not null,
FULLTEXT(content)
);

This table’s purpose is to store the searchable text of an InnoDB record, index it, and keep track of the id of the record it is representing. When you do a fulltext search of this table, you specify your search term, and the TYPE of data you are searching and it will return a full list of ids in your InnoDB table for the type you specified. It is quite easy to populate your search_snapshot right out of a query of this table.

Now here is where having a properly abstracted data access layer in your project is useful. For the previous system to work, you need to find every place you can change the data you are able to search, and make sure you refresh the record in text_index as well. This means that every insert, update, and delete statement to Product table would need to be accompanied by an insert, update, or delete in the text_index as well to keep your search as accurate as possible. An easier solution, though less accurate, is to have a timed job that routinely deletes all records from text_index for a particular type, and then performs something like the following to refresh the index.

delete from text_index where TYPE='PRODUCT';

insert into text_index (type, frn_id, content)
select 'PRODUCT',product_id, product_description
from product_descriptions;

This will repopulate the search index for that table/type. It is a useful way of seeding your index
at the beginning as well.

CSS Diff Beta

John Wolthius — Wed, 05 Dec 2007 18:35:40 +0000

Our CSS Diff tool beta is now public!

In one of our recent contracts, we encountered a problem. The design team was using a content management system to maintain the non-transactional portions of their website, while the engineering team was building a tomcat/spring web application to handle shopping cart and search functionality. The content management system (OpenCMS) was its own versioning system and was largely incompatible with the CVS instance that the engineers were using for the web application. The result of this was that there were two sets of stylesheets for both sides of the application. As marketing and content personnel made changes in OpenCMS, the CSS stored there began to diverge from the copy the engineers were using and altering.

As we approached production, it became necessary to merge the CSS into a single file, but by that point both branches were upwards of 4000 lines each and had diverged wildly. Throwing both files into a traditional line based file differ was useless as one of the files had been passed through a sanitizer at some point earlier in its lifespan and its format was far too different. What was needed was a diff utility that understood CSS.

For this purpose, I wrote CSS Diff. Using the wc3 css parser libraries, the tool loads and parses each of the diverging css diff files into an internal representation, and comparing these representations, thus showing the substantive differences while ignoring the ordering, formating, and syntax ambiguity. It worked wonderfully, showing us which selectors are unique in each file, which selectors conflicted, as well as the attributes of the selectors that were in conflict.

Using the MySQL Fulltext Search Engine with Data Driven Web Applications – Part I

John Wolthius — Thu, 10 May 2007 20:44:31 +0000

Part I – The FULLTEXT index and BOOLEAN search language

Searching is one of the most fundamental and common features of the web. We are all used to having powerful search engines such as Google at our fingertips, both for searching the glut of information available on the Internet at large, as well as for indexing our own web sites to provide a search mechanism to our own users.

As long as your site is reasonably static and publicly browsable, engines like Google do a good job of indexing your data. But what do you do when your application becomes too complex or dynamic for it to be properly spidered? In that case, you need your own search engine, one that allows you control over what is being indexed as things change on your site, as well as control over what results are being returned. There are many such engines out there: commercial packages such as Verity, open source packages such as Lucene, as well as integrated engines such as the fulltext index and search features included in MySQL. In this article, I will describe how to use MySQL’s features for adding robust fulltext search to dynamic web applications that otherwise would be difficult to index.

In the past, the only way to do text searching in a database was to use the LIKE comparison in the WHERE clause. This was very limited and usually exceptionally inefficient. The good news is that MySQL has an index type called FULLTEXT that you can create on character data type fields (varchar, text, longtext, etc.). Instead of storing data to help SQL queries efficiently seek and sort the data within the table, it analysis the human language text (words) in the field indexed, so that data can be searched using their fulltext search matching language.

Some simple examples:

First we create a simple table that stores a product id and a product description. We create a fulltext index on the description field, indicating that we want to be able to use the fulltext search language to query data inserted in that field. It should be noted that MySQL’s fulltext indexes only work with the MYISAM database engine.

     create table product_descriptions (
          id int primary key,
          description text,
          FULLTEXT (description)
     ) engine = myisam;

Next we insert some test data into the table. As each row is inserted, the description field is indexed for fulltext searching.

     insert into product_descriptions
          values
               (1,'Peanut butter cookies'),
               (2, 'Chocolate chip cookies'),
               (3, 'Chocolate croissants'),
               (4, 'Peanut Butter Cups'),
               (5, 'Spinach Macaroons'),
               (6, 'Swedish butter cookies');

Now that we have a product description table with indexed data, lets do some example searches!

Searching for “cookies” gives you the 3 rows with the word cookie in them.

     select id, description
     from product_descriptions
     where MATCH(description)
          AGAINST ('cookies' IN BOOLEAN MODE);

id	description
1	Peanut butter cookies
2	Chocolate chip cookies
6	Swedish butter cookies

Searching for “cookies butter” gives you and OR search, returning all rows with a reference to cookies OR butter.

     select id, description
     from product_descriptions
     where MATCH(description)
          AGAINST ('cookies butter' IN BOOLEAN MODE);

id	description
1	Peanut butter cookies
2	Chocolate chip cookies
4	Peanut butter cup
6	Swedish butter cookies

By adding a “+” character before a word in a search, we indicate that the results MUST include that word. By putting a + before cookies and butter, we turn this into an AND search, in that all results must include both “cookies” and “butter”

     select id, description
     from product_descriptions
     where MATCH(description)
          AGAINST ('+cookies +butter' IN BOOLEAN MODE);

id	description
1	Peanut butter cookies
6	Swedish butter cookies

By adding a trailing “*” we can do partial matches on words or even single letters. The following query will return every row that has a word starting with “c”

     select id, description
     from product_descriptions
     where MATCH(description)
          AGAINST ('c*' IN BOOLEAN MODE);

id	description
1	Peanut butter cookies
2	Chocolate chip cookies
3	Chocolate croissants
4	Peanut butter Cups
6	Swedish butter cookies

That’s a quick overview of the basics of the MySQL Boolean query language. A more detailed description of the search language, as well as more advance concepts such as query expansion, can be found here at the MySQL website.

A Simple Search Method

So now that we have our product table, fulltext index, and a little familiarity with the Boolean search language, lets create a method for taking a search query from a html form and returning a result set you can display to your users! Lets assume you have a simple search form on your web application; nothing but a text input area and a submit button.

First lets define some pseudo code for a simple search method:

function search(String $search_string) {
     String db_query = "select id, description
          from product_descriptions
          where MATCH(description)
          AGAINST ('"+$search_string+"' IN BOOLEAN MODE)";
     Array results = execute_database_query(db_query);
     return results;
}

What this method does is pretty simple, it just inserts the raw search text from the web form directly into the AGAINST(’ ‘) block of the db query and executes it, returning the result rows, which could be displayed on a search results page. It doesn’t have any logic for handling AND or OR or partials, nor does it do any filtering to make sure the user hasn’t entered characters or keywords that will be interpreted by the Boolean search engine (+,-,*, etc). Also, NEVER EVER PASS DATA DIRECTLY FROM A FORM TO A DATABASE QUERY!!! It leaves you open to something known as a SQL injection attack which allows malicious users to run queries against your db. Always validate and escape form data to ensure this doesn’t happen.

Lets make the method a little smarter and safer. Most search engines do AND searches, in that if you enter two words in the search, you expect those words to both be in your results. They also do leading matched for the words entered. To do this, we will need to do some prepossessing of the search string, before passing it to the search query.

function search(String $search_string) {
     //strip Boolean search characters out of search string
     $search_string = string_replace($search_string,"+","");
     $search_string = string_replace($search_string,"-","");
     $search_string = string_replace($search_string,"*","");
     //split the search string up into an array of words
     Array $tokenized_search = split($search_string, " ");
     //init an empty final search string
     String $processed_search = "";
     //for each word in the search, wrap it
     //with an + and * character and then append
     //it to the processed_search variable
     foreach($tokenized_search as $token) {
          $processed_search+="+"+$token+"* ";
     }
     //build the sql for the query and query the DB
     String $db_query = "select id, description
          from product_descriptions
          where MATCH(description)
          AGAINST ('"+$processed_search+"' IN BOOLEAN MODE)";
     Array results = execute_database_query($db_query);
     return results;
}

For the search “Peanut Cookie” we would reprocess the search text to be “+Peanut* +Cookie*” before passing it off to the search engine. This means we would get all rows that contain the leading string “Peanut” as well as “Cookie”. Rows with the text “peanuts” or “peanutbutter” or “cookies” would also match, because of the trailing wildcard we added to each word.

Stopwords and Minimum Word Length

MySQL’s search engine also has concepts called stopwords and minimum word length. Stopwords are common words that are intentionally left un-indexed and are unsearchable, such as “a, and, for, the” and so on. The intention of these is to prevent lots of unnecessary data from getting indexed and muddying up result sets, but there are some side effects that need to be taken into account as well. For example, the word “down” is in the default stopwords list. if you do a search for “+down +stairs” it will always fail, even if your searching column has a row with the text “down stairs” indexed. This is because mysql removes “down” from the words it indexes, but it is not smart enough to remove “down” from the query it is passed, meaning that any query with a stopword with a + in front of it will always fail. I have gotten around this by creating a lookup function of the my stopwords list, and checking each token against it as I build my processed_search string. This prevents impossible queries from being executed for otherwise reasonable searches. It is also sometimes useful to reduce the size of your stopwords list, depending on your application. I find the full list is useful for applications that are indexing articles or large blocks of written text, while a much smaller list is useful for things like searchable user profiles.

Minumum word length is a mysql configuration setting that, like stopwords, determins whether a word can be indexed or not. The default setting is four letters, which means any word (say ‘foo’) under four characters will not be indexed. This can occasionally cause problems in much the same ways as stopwords do. If you do a required search for Foo (+foo*) it will fail because foo could never appear in the index. This is usually fine for most applications, but in cases where you index lots of acronyms, or if you are indexing user profiles where people actually have 2 or 3 letter names (”Mel” “Al” “Tim”, etc) you will need to reduce your min word length. Instructions for doing so can be found here.

Next Time

In my next post, i’ll go into detail about building more robust features around these basic search ideas. Paging, sorting, filtering, searching multiple types of data with abstracted search tables, InnoDB, and more!

New Look & Feel for Gordian Labs

Gordian Labs — Thu, 26 Apr 2007 19:05:31 +0000

As you might have noticed, Gordian Labs has a new look and feel for our internet presence. We’ve been focused on consulting work and product development for a while, but we’re going to be making more of our work openly available on the web. Hopefully you’ll enjoy some of our articles and products. Thanks to Yogeeta for developing the core Gordian Labs branding. Brahm has also created a new site design for Runometer that looks quite nice. Thanks, Brahm!

Runometer Logs Over 10,000 Miles

Gordian Labs — Tue, 17 Apr 2007 19:05:31 +0000

Runometer has crossed the 10,000 mile mark today… and what a trip it has been! Thanks to runner Teebo for taking us over this (quite literal) milestone, and thanks to all our users and supporters for continuing to use the site, giving us very valuable feedback and most of all, continuing to run!

Runometer adds Sidebar Badges

Gordian Labs — Sat, 31 Mar 2007 19:03:34 +0000

Runometer now vends narrow sidebar badges in addition to the normal (wider) horizontal images. Runometer weblog badges make it easy to publish your latest runs and statistics in your blog or website. Show off your latest run and route just like the badge at right. Or you can include aggregate statistics across many runs or a listing of several recent runs if you want to include more detail. Show off your progress to friends and visitors.

GPX Uploading Supported by Runometer

Gordian Labs — Fri, 23 Mar 2007 19:02:35 +0000

We’ve added support for uploading your run data from Garmin and MotionBased devices to Runometer. If you have a Garmin ForeRunner you can now have your maps created for you automatically!

Runometer in the News

Gordian Labs — Fri, 26 Jan 2007 18:51:48 +0000

A number of websites have featured Runometer in the last few days. Starting with a nice little feature in Hack a Day, we also got picked up by Engadget, Podofile, The Unofficial Apple Weblog, and Lifehacker. Thanks for all the mentions!