0

I am writing an application to be used as a local disc documents store similar functionality to Firebase or MongoDB. The gist of how it works is a column hash table. For example:

Say I have a user document

{
  "first": "stack",
  "last": "overflow", 
  "age": 2147
}

I basically iterate each field as a column and save a hashed value as a filename for a file, that contains the unique row key(if multiple objects have the same value for a column there will be multiple row keys written to the file). Then save record in a directory with the key as the filename. So for a simple name = "stack" I have an O(1) lookup, hash the value, see if a file exists with the hashed value as a name, if exists, read all row keys from file. iterate each key and load data from file. I guess if the number of rows is large this will be a slower query.

What I am trying to do I want to ad a partial text search capability. My initial idea is to write all permutations of the value into the index and then do the same O(1) - file exists - check that I mentioned above. So if the query is name name contains st I will just look a filename for that value and read all rows keys.

Is this a good way to offer a partial text search? What are some common industry techniques?

Project

  • 1
    Are you sure permutations mean what you think it means? Permutations would indicate all letters in a word be combined in any order. – Esben Skov Pedersen Aug 4 at 6:43
  • No, you're right, I mean all sections of the stackoverflow -> s, st, sta, etc.. Good catch – Sam Orozco Aug 4 at 6:54
  • 2
    You should probably update the question then – Esben Skov Pedersen Aug 4 at 7:03
  • 1
    Still your design (using individual files for the hash buckets) will lead to abysmal performance. You're probably be much better off with a simple database such as SQLite that knows how to do indexes right instead of re-inventing the wheel. Note that SQLite has optional full text search modules, so it might already do 90% of what you need. – Hans-Martin Mosner Aug 4 at 7:49
  • -1 and voting to close as unclear, until the question is written in a way it describes what the OP means. – Doc Brown Aug 4 at 18:10
4

Is all permutations of a string a good way to index full text search?

Uhh, no. That is a very, very bad idea.

What happens when someone puts a moderately long string into your database? Say... like your question. Making a database of stack exchange questions seems like a normal sort of thing to do. At time of writing, just the content of the question is 1264 characters. The number of permutations of 1264 characters is... umm. Very large. My local calculator puts it around 4x10^3373. Even smaller strings will have enough permutations to fill up the entire bucket space of your hash, rendering it irrelevant.

I am not super familiar with common industry search techniques, but as I understand it they are largely machine learning algorithms these days. People do a search, you feed them some options, they pick the "right" one and your algorithm uses that feedback to correlate the search with the result to then find patterns in searches and results.

  • Sorry, I don't mean permutations, I mean into separate parts of the word. stackoverflow -> s, st, sta, stac, etc.. – Sam Orozco Aug 4 at 6:55
  • 2
    @SamOrozco then please modify and clarify your question. – Robert Andrzejuk Aug 4 at 10:19
2

The most common indexes are balanced trees, where finding a partial match at the beginning is easy. A filesystem is not a good backing structure for any index because of the high overhead (I understand that you are doing this as a learning experience so performance doesn't matter as much) but certainly it's unsuitable for a tree as you need to access several nodes until you find the match and writes may require altering several nodes for rebalancing.

Full text indexes often are implemented as trees as well, for example PostgreSQL GIN indexes use a B-Tree. When partial matches beyond the word beginning and approximate matches are required some kind of n-gram index is a good choice, where consecutive groups of n characters are extracted from each word, as they are more robust against misspellings. A trigram index (n=3), like the one implemented in PostgreSQL, would split 'stack overflow' like 'sta'|'tac'|'ack'| |'ove'|'ver'|'erf'|'rfo'|'flo'|'low'.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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