Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I will inserting into a database the signatures of 500,000,000 pictures. The signatures will be generated using libpuzzle. Each signature is 338 bytes. (so 160 GB) plus a table for searching (read more below). I would prefer to keep the main database on one VPS server with a standard HDD (No SSD because of cost issues).

The most important aspect is search time, Insertion time does not matter.

In the past I have attempted this all within MySQL (with way less records) and had one database for everything, the main searching happened with a scheme like:

--
-- Table structure for table `signatures`
--

CREATE TABLE IF NOT EXISTS `signatures` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `compressed_signature` varchar(338) NOT NULL,
  `picture_id` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `picture_id` (`picture_id`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=1107725 ;

-- --------------------------------------------------------

--
-- Table structure for table `stored_pictures`
--

CREATE TABLE IF NOT EXISTS `stored_pictures` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `url` varchar(255) NOT NULL,
  `pid` bigint(20) unsigned NOT NULL,
  `num` int(11) NOT NULL,
  `updated_at` datetime DEFAULT NULL,
  `created_at` datetime DEFAULT NULL,
  `picture_id` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `idx_url` (`url`),
  KEY `idx_picture_id` (`picture_id`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=2773867 ;

-- --------------------------------------------------------

--
-- Table structure for table `words`
--

CREATE TABLE IF NOT EXISTS `words` (
  `pos_and_word` char(5) NOT NULL,
  `signature_id` int(11) NOT NULL,
  KEY `idx_pos_and_word` (`pos_and_word`),
  KEY `signature_id` (`signature_id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;
--

Where by nature of the libpizzle, you would search the words table for many signature_id and then get all the compressed_signature from the signatures table, do some math and spit back a score for each signature how similar it was for the search. Then for each similiarity that was above a threshold I would get the data I needed from stored_pictures by looking up the picture_id

It took about 5 minutes for 1 search to search 40,000,000 pictures - so I think there is room for improvement. Especially because I want this to be fast up to 500 million records.

Should I seperate all the non-essential data (only about 1% the size, which is everything that is related to the specific picture) in a seperate database? On a seperate server?

Because it's just doing a massive search for pos_and_word and spitting back all the signature_id's that could be a match, I assume that not having any type of relation with the data can help me pick a specific technology that will maximize my speed. Which technology is best for this?

share|improve this question
    
You have a picture and want to find a similar picture in the database. You calculate the signature of the picture, calculate a list of pos_and_word strings from the signature. By searching the "words" table you find all signatures of your stored images whoses list of pos_and_word strings has at least one pos_and_word in common with the pos_and_words list of the given picture. All signatures found compare with the signature of the given picture. If it is sufficient "similiar" then retrieve the picture and compare it to the given one. Is this right? –  miracle173 Mar 21 at 2:52
    
More or less but the picture itself is never stored, only the breakdown of it's pos_and_word and the "compressed signature". Say you uploaded a photo - it's pos_and_word matches 240 possible signatures. You get 240 signature_id's and then one by one you uncompress them using the lib, and use the lib to measure a similirity %. Lets say of the 240, only 8 were above 90%. You discard the 232 and do a lookup using the 8 picture_id to find the URL where the picture is found (not on my server but on the www) and display them. –  BHare Mar 21 at 8:29
    
(1) Can you tell me how much signatures you get on average in the first step (pos_and_word search)? Is 240 a realistic number. (2) How many of these signatures remain after the second step on average? (3) Do you know how many of the signatures that remain after you use the lib to measure the similariry are "false positives"? These are pictures that are classified as similiar by the algorithm but are not really similar pictures (copies). –  miracle173 Mar 27 at 8:17
    
(4) can you also tell me how much of the 5 minutes you spen on retrieving data from the database and on canlculating the similaritiy of two signatures? –  miracle173 Mar 27 at 8:35
    
(5) How many searches per day at present? Will this number increase? –  miracle173 Mar 27 at 11:37

2 Answers 2

You should consider using a real indexed search engine such as elasticsearch with runs on Java, uses a REST interface with json and so is exceedingly easy to program to, is free and open source, with a good community behind it.

www.elasticsearch.org

You could have it running on the same server as your application as long as you have a decent enough machine and it's built specifically for searching hundreds of millions of documents in near real time.

Pretty easy to install and setup and extremely easy to customize. It also has the added benefit of being built to run in the cloud (though not a requirement) and can cluster out very easily when your application begins to grow in popularity.

share|improve this answer
    
Does this mean elsasticsearch can be used to find images? At a first glance it los like a fulltext search. –  miracle173 Mar 26 at 8:38
    
@miracle173 If I understood your explanation above you're storing signatures of images , and searching on those. Using this you'd be able to store full image indexes in elasticsearch and then using a partial signature of the source image look for similar patterns. There are a number of different pattern matching options you can use to tighten or loosen the search, but it would give you ordered results of 'close' matches which you could then compare 1:1 as you currently do. It would allow you to operate essentially as you have but ES will do it in a fraction of the time, and can scale. –  oucil Mar 26 at 12:51
    
(1) As far as I can see from the documents supplied at the libpuzzle page the signatures are points of an an N-dimensional space (N about 600 or higher) where the coordinates are from {-2,-1,0,1,2}. Finding a similiar picture is transformed to finding points near (with respect to the Euclidean distance) the given point (signatures). So this is a nearst neihbor search. –  miracle173 Mar 27 at 7:17
    
(2) One method to find possible canditate signatures is to precalculate this list of pos_to_world values for each signature and retrieve the signatures that have common pos_to_world values with the given signature. This seems to be some kind of Locality-sensitive hashing. –  miracle173 Mar 27 at 7:18
    
(3) Retrieving a value by a key is a task where a database like mysql is designed for. So I cannot see what you gain if one changes to elasticsearch if one does not change the method. But I cannot see a better performing method using some pattern matching algorithms (instead of the present pos_to_world retrieving method) that retrieves the candidates faster or reduces the number of candidates significantly. So I cannot see how a change to elastic search could be used to speed up the data retrieval. –  miracle173 Mar 27 at 7:19

In your place, I would build my own search function. Database is good, but general search engine is not so perfect like custom, dedicated search function could be. And your data is not general one. Please take a look at Binary search trees for example. The idea is that if your signatures are sorted, then search for specific signature is much faster than general search over all signatures in the DB. This is not a complete solution - but a direction :)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.