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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 '14 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. – ParoX Mar 21 '14 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 '14 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 '14 at 8:35
    
(5) How many searches per day at present? Will this number increase? – miracle173 Mar 27 '14 at 11:37

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
    
Here someone describes how he uses sphinx fulltext search to find the signatures. This method seems to be similar to the method proposed by you. – miracle173 Mar 30 '14 at 20:50

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.